4.1: Definiciones

Última actualización
Guardar como PDF

Page ID: 115781

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Template:MathJaxLevin

¡Investiga!

¿Cuáles (si las hay) de las siguientes gráficas son las mismas?

$image-59.svg$ $image-60.svg$ $image-61.svg$ $image-62.svg$ $image-63.svg$

Las gráficas anteriores no están etiquetadas. Por lo general, pensamos en una gráfica como que tiene un conjunto específico de vértices. ¿Cuáles (si las hay) de las siguientes gráficas son las mismas?

$image-64.svg$ $image-65.svg$ $image-66.svg$ $image-67.svg$

En realidad, todas las gráficas que hemos visto anteriormente son solo dibujos de gráficas. Una gráfica es realmente un objeto matemático abstracto que consta de dos conjuntos$V$ y$E$ donde$E$ está un conjunto de subconjuntos de 2 elementos de$V\text{.}$ ¿Son las gráficas de abajo iguales o diferentes?

Gráfica 1:

$V = \{a, b, c, d, e\}\text{,}$
$E = \{\{a,b\}, \{a, c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{d,e\}\}\text{.}$

Gráfica 2:

$V = \{v_1, v_2, v_3, v_4, v_5\}\text{,}$
$E = \{\{v_1, v_3\}, \{v_1, v_5\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_3, v_5\}, \{v_4, v_5\}\}\text{.}$

Antes de comenzar a estudiar gráficas, tenemos que ponernos de acuerdo sobre qué es una gráfica. Si bien casi siempre pensamos en las gráficas como imágenes (puntos conectados por líneas) esto es bastante ambiguo. ¿Es necesario que las líneas sean rectas? ¿Importa qué tan largas sean las líneas o qué tan grandes sean los puntos? ¿Puede haber dos líneas que conecten el mismo par de puntos? ¿Una línea puede conectar tres puntos?

La forma en que evitamos ambigüedades en matemáticas es proporcionar definiciones concretas y rigurosas. Elaborar buenas definiciones no es fácil, pero es increíblemente importante. La definición es el punto de partida acordado a partir del cual proceden todas las verdades en matemáticas. ¿Hay una gráfica sin bordes? Tenemos que mirar la definición para ver si esto es posible.

Queremos que nuestra definición sea precisa e inequívoca, pero también debe estar de acuerdo con nuestra intuición para los objetos que estamos estudiando. Tiene que ser útil: podríamos definir una gráfica para que sea un mamífero de seis patas, pero eso no nos permitiría resolver ningún problema sobre puentes. En cambio, aquí está la (ahora) definición estándar de una gráfica.

Definición

Un gráfico es un par ordenado$G = (V, E)$ que consiste en un conjunto no vacío$V$ (llamado vértices) y un conjunto$E$ (llamado los bordes) de subconjuntos de dos elementos de$V\text{.}$

Extraño. En ninguna parte de la definición se habla de puntos o líneas. A partir de la definición, una gráfica podría ser

\ begin {ecuación*} (\ {a, b, c, d\},\ {\ {a, b\},\ {a, c\},\ {b, c\},\ {b, d\},\ {c, d\}\}). \ end {ecuación*}

Aquí tenemos una gráfica con cuatro vértices (las letras$a, b, c, d$) y cuatro aristas (los pares$\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\})$).

Mirar conjuntos y conjuntos de conjuntos de 2 elementos es difícil de procesar. Es por ello que a menudo dibujamos una representación de estos conjuntos. Ponemos un punto hacia abajo para cada vértice, y conectamos dos puntos con una línea precisamente cuando esos dos vértices son uno de los subconjuntos de 2 elementos en nuestro conjunto de aristas. Así, una forma de dibujar la gráfica descrita anteriormente es la siguiente:

$image-68.svg$

Sin embargo, también podríamos haber dibujado la gráfica de manera diferente. Por ejemplo, cualquiera de estos:

$image-69.svg$ $image-70.svg$

Debemos tener cuidado con lo que significa que dos gráficas sean “iguales”. En realidad, dada nuestra definición, esto es fácil: ¿Son iguales los conjuntos de vértices? ¿Los conjuntos de bordes son iguales? Sabemos lo que significa que los conjuntos sean iguales, y los gráficos no son más que un par de dos tipos especiales de conjuntos.

Ejemplo$\PageIndex{1}$

¿Son iguales las siguientes gráficas?

\ begin {ecuación*} G_1 = (\ {a, b, c\},\ {\ {a, b\},\ {b, c\}\});\ qquad G_2 = (\ {a, b, c\},\ {\ {a, c\},\ {c, b\}\})\ end {ecuación*}

igual?

Solución: No. Aquí los conjuntos de vértices de cada gráfica son iguales, lo cual es un buen comienzo. Además, ambas gráficas tienen dos aristas. En la primera gráfica, tenemos bordes$\{a,b\}$ and $\{b,c\}\text{,}$ while in the second graph we have edges $\{a,c\}$ and $\{c,b\}\text{.}$ Now we do have $\{b,c\} = \{c,b\}\text{,}$ so that is not the problem. The issue is that $\{a,b\} \ne \{a,c\}\text{.}$ Since the edge sets of the two graphs are not equal (as sets), the graphs are not equal (as graphs).

Aunque dos gráficas no sean iguales, podrían ser básicamente las mismas. Las gráficas del ejemplo anterior podrían dibujarse así:

$image-71.svg$

Las gráficas que son básicamente las mismas (pero quizás no iguales) se denominan isomórficas. Daremos una definición precisa de este término después de un ejemplo rápido:

Ejemplo$\PageIndex{2}$

Considera las gráficas:

$G_1 = \{V_1, E_1\}$dónde$V_1 = \{a, b, c\}$ y$E_1 = \{\{a,b\}, \{a,c\}, \{b,c\}\}\text{;}$
$G_2 = \{V_2, E_2\}$dónde$V_2 = \{u,v,w\}$ y$E_2 = \{\{u,v\}, \{u,w\}, \{v,w\}\}\text{.}$

¿Estas gráficas son las mismas?

Solución

Las dos gráficas NO son iguales. Basta con notar que$V_1 \ne V_2$ since $a \in V_1$ but $a \notin V_2\text{.}$ However, both of these graphs consist of three vertices with edges connecting every pair of vertices. We can draw them as follows:

Claramente queremos decir que estas gráficas son básicamente las mismas, así que si bien no son iguales, serán isomórficas. La razón es que podemos renombrar los vértices de una gráfica y obtener la segunda gráfica como resultado.

Intuitivamente, las gráficas son isomórficas si son básicamente las mismas, o mejor aún, si son las mismas excepto por los nombres de los vértices. Para que el concepto de renombrar vértices sea preciso, damos las siguientes definiciones:

Gráficas isomórficas

Un isomorfismo entre dos gráficas$G_1$ and $G_2$ is a bijection $f:V_1 \to V_2$ between the vertices of the graphs such that if $\{a,b\}$ is an edge in $G_1$ then $\{f(a), f(b)\}$ is an edge in $G_2\text{.}$

Two graphs are isomorphic if there is an isomorphism between them. In this case we write $G_1 \isom G_2\text{.}$

An isomorphism is simply a function which renames the vertices. It must be a bijection so every vertex gets a new name. These newly named vertices must be connected by edges precisely if they were connected by edges with their old names.

Example $\PageIndex{3}$

Decide whether the graphs $G_1 = \{V_1, E_1\}$ and $G_2 = \{V_2, E_2\}$ are equal or isomorphic.

$V_1 = \{a,b,c,d\}\text{,}$ $E_1 = \{\{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\}$
$V_2 = \{a,b,c,d\}\text{,}$ $E_2 = \{\{a,b\}, \{a,c\}, \{b,c\}, \{c,d\}\}$

Solution

The graphs are NOT equal, since $\{a,d\} \in E_1$ but $\{a,d\} \notin E_2\text{.}$ However, since both graphs contain the same number of vertices and same number of edges, they might be isomorphic (this is not enough in most cases, but it is a good start).

We can try to build an isomorphism. How about we say $f(a) = b\text{,}$ $f(b) = c\text{,}$ $f(c) = d$ and $f(d) = a\text{.}$ This is definitely a bijection, but to make sure that the function is an isomorphism, we must make sure it respects the edge relation. In $G_1\text{,}$ vertices $a$ and $b$ are connected by an edge. In $G_2\text{,}$ $f(a) = b$ and $f(b) = c$ are connected by an edge. So far, so good, but we must check the other three edges. The edge $\{a,c\}$ in $G_1$ corresponds to $\{f(a), f(c)\} = \{b,d\}\text{,}$ but here we have a problem. There is no edge between $b$ and $d$ in $G_2\text{.}$ Thus $f$ is NOT an isomorphism.

Not all hope is lost, however. Just because $f$ is not an isomorphism does not mean that there is no isomorphism at all. We can try again. At this point it might be helpful to draw the graphs to see how they should match up.

$image-74.svg$ $image-75.svg$

Alternativamente, observe que en$G_1\text{,}$ the vertex $a$ is adjacent to every other vertex. In $G_2\text{,}$ there is also a vertex with this property: $c\text{.}$ So build the bijection $g:V_1 \to V_2$ by defining $g(a) = c$ to start with. Next, where should we send $b\text{?}$ In $G_1\text{,}$ the vertex $b$ is only adjacent to vertex $a\text{.}$ There is exactly one vertex like this in $G_2\text{,}$ namely $d\text{.}$ So let $g(b) = d\text{.}$ As for the last two, in this example, we have a free choice: let $g(c) = b$ and $g(d) = a$ (switching these would be fine as well).

Deberíamos comprobar que esto realmente es un isomorfismo. Definitivamente es una bijección. Debemos asegurarnos de que se respeten los bordes. Los cuatro bordes en$G_1$ are

\ comenzar {ecuación*}\ {a, b\},\ {a, c\},\ {a, d\},\ {c, d\}\ end {ecuación*}

Bajo el isomorfismo propuesto estos se convierten

\ comenzar {ecuación*}\ {g (a), g (b)\},\ {g (a), g (c)\},\ {g (a), g (d)\},\ {g (c), g (d)\}\ final {ecuación*}\ comenzar {ecuación*}\ {c, d\},\ {c, b\},\ {c, a\},\ {b, a\}\ fin {ecuación*}

que son precisamente los bordes en$G_2\text{.}$ Thus $g$ is an isomorphism, so $G_1 \cong G_2$

En ocasiones hablaremos de una gráfica con un nombre especial (como$K_n$ o la gráfica de Peterson) o quizás dibujaremos una gráfica sin etiquetas. En este caso realmente nos estamos refiriendo a todas las gráficas isomórficas a cualquier copia de esa gráfica en particular. Una colección de gráficos isomórficos a menudo se llama clase de isomorfismo. ¹ Esto no es diferente a la geometría, donde podríamos tener más de una copia de un triángulo en particular. Ahí en vez de isomórfico decimos congruente.

Hay otras relaciones entre las gráficas que nos importan, además de la igualdad y el ser isomórfico. Por ejemplo, compare el siguiente par de gráficas:

$image-76.svg$ $image-77.svg$

Estos definitivamente no son isomórficos, pero fíjense que la gráfica de la derecha parece que podría ser parte de la gráfica de la izquierda, sobre todo si la dibujamos así:

$image-78.svg$

Nos gustaría decir que la gráfica más pequeña es una subgráfica de la más grande.

Deberíamos dar una definición cuidadosa de esto. De hecho, hay dos nociones razonables sobre lo que debe significar un subgrupo.

Subgrafías

Decimos que$G_1 = (V_1, E_1)$ es un subgrafo de$G_2 = (V_2, E_2)$ proporcionado$V_1 \subseteq V_2$ y$E_1 \subseteq E_2\text{.}$

Decimos que$G_1 = (V_1, E_1)$ es un subgrafo inducido de$G_2 = (V_2, E_2)$ proporcionado$V_1 \subseteq V_2$ y$E_1$ contiene todos los bordes de los$E_2$ cuales son subconjuntos de$V_1\text{.}$

Observe que cada subgrafía inducida es también una subgráfica ordinaria, pero no a la inversa. Piense en un subgrafo como resultado de eliminar algunos vértices y aristas de la gráfica más grande. Para que el subgrafo sea un subgrafo inducido, aún podemos eliminar vértices, pero ahora solo eliminamos aquellos bordes que incluían los vértices eliminados.

Ejemplo$\PageIndex{4}$

Considera las gráficas:

$image-82.svg$ $image-79.svg$ $image-80.svg$ $image-81.svg$

Aquí ambos$G_2$ y$G_3$ son subgráficos de$G_1\text{.}$ Pero solo$G_2$ es una subgrafía inducida. Cada borde en$G_1$ que conecta vértices en también$G_2$ es un borde en$G_2\text{.}$ En$G_3\text{,}$ el borde$\{a,b\}$ está adentro$E_1$ pero no$E_3\text{,}$ aunque los vértices$a$ y$b$ están en$V_3\text{.}$

El grafo NO$G_4$ es un subgrafo de$G_1\text{,}$ aunque parezca que todo lo que hicimos es eliminar vértice$e\text{.}$ La razón es que en$E_4$ tenemos el borde$\{c,f\}$ pero esto no es un elemento de$E_1\text{,}$ así que no tenemos el requerido$E_4 \subseteq E_1\text{.}$

Volver a algunas definiciones básicas de teoría gráfica. Observe que todas las gráficas que hemos dibujado arriba tienen la propiedad de que ningún par de vértices está conectado más de una vez, y ningún vértice está conectado consigo mismo. A las gráficas como estas a veces se les llama simples, aunque solo las llamaremos gráficas. Esto se debe a que nuestra definición para una gráfica dice que los bordes forman un conjunto de subconjuntos de 2 elementos de los vértices. Recuerda que no tiene sentido decir que un conjunto contiene un elemento más de una vez. Por lo que ningún par de vértices se puede conectar por un borde más de una vez. Además, dado que cada arista debe ser un conjunto que contenga dos vértices, no podemos tener un solo vértice conectado consigo mismo por una arista.

Dicho esto, hay ocasiones en las que queremos considerar bordes dobles (o más) y bucles de borde único. Por ejemplo, la “gráfica” que dibujamos para el problema de Puentes de Königsberg tenía bordes dobles porque realmente hay dos puentes que conectan una isla en particular con la costa cercana. A estos objetos los llamaremos multígrafos. Este es un buen nombre: un multiset es un conjunto en el que se nos permite incluir un solo elemento varias veces.

Las gráficas anteriores también están conectadas: se puede obtener de cualquier vértice a cualquier otro vértice siguiendo alguna trayectoria de bordes. Una gráfica que no está conectada puede considerarse como dos gráficas separadas dibujadas muy juntas. Por ejemplo, la siguiente gráfica NO está conectada porque no hay ruta de$a$ a$b\text{:}$

$ex-gt-non-connected.svg$

La mayoría de las veces, tiene sentido tratar las gráficas no conectadas como gráficas separadas (piense en la gráfica anterior como dos cuadrados), así que a menos que se indique lo contrario, asumiremos que todas nuestras gráficas están conectadas.

Los vértices en una gráfica no siempre tienen bordes entre ellos. Si agregamos todos los bordes posibles, entonces la gráfica resultante se llama completa. Es decir, una gráfica está completa si cada par de vértices está conectado por un borde. Dado que una gráfica está determinada completamente por qué vértices son adyacentes a qué otros vértices, solo hay una gráfica completa con un número dado de vértices. Damos a estos un nombre especial:$K_n$ es la gráfica completa sobre$n$ vértices.

Cada vértice adentro$K_n$ es adyacente a$n-1$ otros vértices. Llamamos al número de aristas que emanan de un vértice dado el grado de ese vértice. Entonces cada vértice en$K_n$ tiene grado$n-1\text{.}$ ¿Cuántos bordes$K_n$ tiene? Uno podría pensar que la respuesta debería ser$n(n-1)\text{,}$ ya que contamos$n-1$ los$n$ tiempos de bordes (una vez por cada vértice). Sin embargo, cada borde es incidente a 2 vértices, por lo que contamos cada borde exactamente dos veces. Así hay$n(n-1)/2$ aristas en$K_n\text{.}$ Alternativamente, podemos decir que hay${n \choose 2}$ aristas, ya que para dibujar una arista debemos elegir 2 de los$n$ vértices.

En general, si conocemos los grados de todos los vértices en una gráfica, podemos encontrar el número de aristas. La suma de los grados de todos los vértices siempre será el doble del número de aristas, ya que cada arista se suma al grado de dos vértices. ¡Observe esto significa que la suma de los grados de todos los vértices en cualquier gráfica debe ser pareja!

Ejemplo$\PageIndex{5}$

En un reciente seminario de matemáticas, 9 matemáticos se saludaron dándose la mano. ¿Es posible que cada matemático le diera la mano exactamente a 7 personas en el seminario?

Solución

Parece que esto debería ser posible. Cada matemático elige a una persona a la que no darle la mano. Pero esto no puede suceder. Nos estamos preguntando si una gráfica con 9 vértices puede tener cada vértice tener grado 7. Si tal gráfica existiera, la suma de los grados de los vértices sería$9\cdot 7 = 63\text{.}$ This would be twice the number of edges (handshakes) resulting in a graph with $31.5$ edges. That is impossible. Thus at least one (in fact an odd number) of the mathematicians must have shaken hands with an even number of people at the seminar.

Una definición final: decimos que una gráfica es bipartita si los vértices se pueden dividir en dos conjuntos,$A$ y$B\text{,}$ sin dos vértices en$A$ adyacentes y no dos vértices en$B$ adyacentes. Los vértices en$A$ pueden ser adyacentes a algunos o todos los vértices en$B\text{.}$ Si cada vértice en$A$ es adyacente a todos los vértices en$B\text{,}$ entonces la gráfica es una gráfica bipartita completa, y obtiene un nombre especial:$K_{m,n}\text{,}$ dónde$|A| = m$ y$|B| = n\text{.}$ La gráfica en el rompecabezas de casas y servicios públicos es$K_{3,3}\text{.}$

Gráficos Nombrados

Algunas gráficas se utilizan más que otras, y obtienen nombres especiales.

$K_n$: La gráfica completa sobre los$n$ vértices.
$K_{m,n}$: La gráfica bipartita completa con conjuntos de$m$ y$n$ vértices.
$C_n$: El ciclo sobre$n$ vértices, solo un bucle grande.
$P_n$: El camino en$n$ vértices, solo un camino largo.

Hay muchas definiciones a las que hacer un seguimiento en la teoría de grafos. Aquí hay un glosario de los términos que ya hemos utilizado y pronto encontraremos.

Definiciones de teoría de grafos

Gráfica: Una colección de vértices, algunos de los cuales están conectados por aristas. Más precisamente, un par de conjuntos$V$ y$E$ donde$V$ es un conjunto de vértices y$E$ es un conjunto de subconjuntos de 2 elementos de$V\text{.}$
Adyacente: Dos vértices son adyacentes si están conectados por una arista. Dos bordes son adyacentes si comparten un vértice.
Gráfica bipartita: Una gráfica para la que es posible dividir los vértices en dos conjuntos disjuntos de tal manera que no haya aristas entre dos vértices cualesquiera del mismo conjunto.
Gráfica bipartita completa: Una gráfica bipartita para la cual cada vértice del primer conjunto es adyacente a cada vértice del segundo conjunto.
Gráfica completa: Una gráfica en la que cada par de vértices es adyacente.
Conectado: Se conecta una gráfica si hay una ruta desde cualquier vértice a cualquier otro vértice.
Número cromático: El número mínimo de colores requeridos en una correcta coloración de vértice de la gráfica.
Ciclo: Un camino (ver abajo) que inicia y se detiene en el mismo vértice, pero que no contiene otros vértices repetidos.
Grado de un vértice: El número de aristas que inciden a un vértice.
Sendero de Euler: Un paseo que usa cada borde exactamente una vez.
Circuito de Euler: Un camino de Euler que inicia y se detiene en el mismo vértice.
Multígrafo: Un multígrafo es igual que un gráfico pero puede contener múltiples bordes entre dos vértices así como bucles de borde único (es decir, un borde de un vértice a sí mismo).
Plano: Un gráfico que se puede dibujar (en el plano) sin ningún cruce de bordes.
Subgrafía: Decimos que$H$ es un subgrafo de$G$ si cada vértice y borde de también$H$ es un vértice o borde de$G\text{.}$ Decimos$H$ es un subgrafo inducido de$G$ si cada vértice de$H$ es un vértice de$G$ y cada par de vértices en$H$ son adyacentes en $H$si y solo si son adyacentes en$G\text{.}$
Árbol: Una gráfica (conectada) sin ciclos. (Una gráfica no conectada sin ciclos se llama bosque). Los vértices en un árbol con grado 1 se llaman hojas.
Coloración de vértices: Asignación de colores a cada uno de los vértices de una gráfica. Un color de vértice es apropiado si los vértices adyacentes siempre se colorean de manera diferente.
Caminar: Una secuencia de vértices tal que los vértices consecutivos (en la secuencia) son adyacentes (en la gráfica). Un paseo en el que no se repite ningún vértice se llama simple