Gráficas, grados y lema de Euler#
Introducción#
En este introduciremos el concepto de gráfica. A grandes rasgos, una gráfica guarda la información de cuándo hay pares de elementos distintos de un conjunto que estén «relacionados entre sí». Esta relación debe ser simétrica para poder ser representada mediante una gráfica. Aún con esta restricción, hay una multitud de situaciones cotidianas que pueden ser modeladas mediante una gráfica:
Los elementos pueden ser personas y la relación que se conozcan entre sí.
Los elementos pueden ingredientes de cocina y la relación que sean compatibles en una misma receta.
Los elementos pueden ser ciudades y la relación que haya una carretera directa de ambos sentidos entre ellas.
A lo largo de esta parte del libro estudiaremos varias de las propiedades básicas de las gráficas y plantearemos los problemas teóricos más cotidianos que se estudian sobre ellas. Más adelante, en la última parte del libro, hablaremos de algoritmos que nos ayudarán a resolver varios de estos problemas computacionalmente.
Gráficas#
Definición. Una gráfica \(G\) consiste de un conjunto \(V\) de vértices y un conjunto \(E\) de aristas. Cada elemento de \(E\) es una pareja de elementos de \(V\).
A \(|V|\) se le llama el orden de \(G\) y a \(|E|\) se le llama el tamaño de \(G\). Así, una gráfica con \(n\) vértices es una gráfica de orden \(n\) y una gráfica con \(m\) aristas es una gráfica de tamaño \(m\).
Formalmente, una arista es una pareja del estilo \(\{u,v\}\) con \(u\) y \(v\) vértices. Como estamos pensando a \(\{u,v\}\) como conjunto, no lo distinguimos de \(\{v,u\}\). Cuando no haya riesgo de confusión, la llamaremos simplemente la arista \(uv\) (ó \(vu\)). Si \(G\) tiene a la arista \(uv\), entonces diremos que \(u\) y \(v\) son adyacentes o bien que son vecinos.
Las gráficas tienen una descripción conjuntista, pero cuando tenemos una gráfica chica es mejor representarla mediante un diagrama. Dibujamos un punto grande por cada vértice y trazamos un segmento (usualmente recto) que una a dos vértices cada que sean aristas en la gráfica.
Si bien se pueden definir y estudiar gráficas de orden o tamaño infinitos, nosotros asumiremos todo el tiempo que el orden es finito (y por lo tanto el tamaño también).
Ejemplo. La gráfica con conjunto de vértices \(V=\{a,b,c,d,e\}\) y conjunto de aristas \(\{ab,bc,cd,de,ea,ac,be\}\) es de orden \(5\) y tamaño \(7\). Un posible diagrama es el siguiente:
En el diagrama también se intersectan los segmentos \(cd\) y \(be\), pero esto es por casualidad y no implica que ahí haya un vértice. En el diagrama anterior los puntos que representan a los vértices \(a\), \(c\), \(d\) quedaron alineados. Esto podría causar ambigüedad al determinar si \(ad\) es una arista o no. En este ejemplo sabemos que no por la descripción conjuntista, pero en general debemos tener cuidado al usar diagramas. \(\square\)
No es necesario dar todas las aristas de una gráfica de manera explícita. Podemos dar una descripción implícita también.
Ejemplo. Consideremos a la gráfica \(G\) con conjunto de vértices \(V=\{1,2,3,4,5,6\}\) y en donde tenemos una arista \(ij\) si \(i-j\) es impar. Un posible diagrama para \(G\) es el siguiente:
Observa cómo el diagrama nos permite concluir de manera relativamente fácil que \(G\) tiene \(9\) aristas. \(\square\)
Vecindades y grados#
El tamaño y el orden una gráfica son valores globales, en el sentido de que debemos conocer todos los vértices y aristas de la gráfica para conocerlos. Hay otras propiedades que nos interesan acerca de las gráficas que son más locales, en el sentido de que sólo «ocurren» cerca de un vértice o un conjunto de vértices. Dos ejemplos son los siguientes.
Definición. Sea \(G\) una gráfica y \(S\) un subconjunto de vértices. Definimos la vecindad de \(S\) como aquellos elementos de \(G\) que sean adyacentes a por lo menos un elemento de \(S\). En general, usamos la notación \(N(S)\). Pero cuando \(S\) sólo tiene un vértice \(v\), entonces escribimos simplemente \(N(v)\).
Cuando un vértice no tiene vecinos decimos que es un vértice aislado.
Definición. Sea \(G\) una gráfica y \(v\) un vértice de \(G\). El grado de \(v\) es la cantidad de vecinos que tiene, es decir, es igual a \(|N(v)|\). En símbolos, lo llamaremos \(\deg(v)\).
Hagamos primero un ejemplo sencillo.
Ejemplo. Consideremos la siguiente gráfica:
El vértice \(j\) no tiene vecinos, así que su grado es \(0\) y es un vértice aislado.
La vecindad del vértice \(g\) es \(\{a,e,d,h\}\), así que tenemos \(\deg(g)=4\). El grado se puede leer fácilmente del diagrama, incluso sin ver detenidamente a qué vertices se llega. Simplemente nos enfocamos en un vértice y vemos cuántas aristas salen de él. Así, podemos ver que \(i\) y \(b\) son otros dos vértices de grado \(4\).
Los vértices no aislados con la menor cantidad posible de vecinos son \(e\) y \(f\), que tienen grado \(2\). Los que tienen la mayor cantidad posible de vecinos son \(a\) y \(h\), que tienen \(5\) vecinos cada uno.
¿Qué sucede si nos preguntamos por las vecindades de algunos conjuntos de vértices? Consideremos \(S=\{a,d,f\}\). La vecindad \(N(S)\) consiste de todos los vértices que son adyacentes a algún elemento de \(S\). Así,
Observa que \(a\) y \(f\) están, pues son vecinos el uno del otro, pero \(d\) no, pues no es adyacente ni a \(a\), ni a \(d\), ni a \(f\). \(\square\)
En muchos casos no es necesario saber toda la información de la gráfica para calcular estos parámetros.
Ejemplo. Consideremos la gráfica \(G\) cuyos vértices son el conjunto de enteros \(\{2,\ldots,100\}\) y en donde \(ab\) es una arista si y sólo si se cumplen las siguientes dos condiciones:
\(a\neq b\)
\(a\) divide a \(b\) o \(b\) divide a \(a\).
Si queremos calcular el grado de \(2\) no es necesario conocer todas las aristas de \(G\) de manera explícita. Basta darse cuenta de que \(2\) divide a \(50\) números de \(2\) a \(100\). Así, su vecindad es \(\{2,4,\ldots,98,100\}\) y entonces \(\deg(2)=50\). Del mismo modo, para calcular el grado de \(53\) basta con notar que como es primo su único divisor menor a él es \(1\). De este modo, no tiene vecinos en los vértices que tenemos. Así, su grado es \(0\) y es un vértice aislado.
Tomemos \(P\) el conjunto de números primos en \(\{2,\ldots,100\}\), es decir, \(P=\{2,3,5,7,\ldots,97\}\). Sabemos que cualquier número compuesto en \(\{2,\ldots,100\}\) es divisible por algún número en \(P\), y que los números de \(P\) sólo son divisibles entre sí mismos. Así, si \(n\in\{2,\ldots, 100\}\) es compuesto, tenemos que \(n\in N(P)\) y si es primo entonces \(n\notin N(P)\). En otras palabras, la vecindad de \(P\) son los números compuestos en \(\{2,\ldots,100\}\). \(\square\)
El lema de Euler#
¿Será posible saber el tamaño de una gráfica conociendo el grado de sus vértices? La respuesta es que sí. El siguiente resultado enuncia esto de manera precisa.
Lema. Sea \(G\) una gráfica con conjunto de vértices \(V\). Tenemos que
Demostración. Damos una demostración por doble conteo. Contemos cuántas parejas \((v,e)\) existen tal que \(v\) es un vértice de \(G\) y \(e\) es una arista de \(G\) en donde \(v\) participa.
Por un lado, si fijamos la primer entrada como un vértice \(v\), habrá tantas \(e\) posibles como vecinos de \(v\), es decir \(\deg(v)\). De este modo, una manera de contar las parejas que nos interesan da \(\sum_{v\in V} \deg(v)\). Por otro lado, si fijamos la segunda entrada como una arista \(e\), habrá exactamente dos \(v\) posibles: sus extremos. De este modo, otra manera de contar las parejas que nos interesan da \(2|E|\).
Como estamos contando lo mismo, ambas cuentas son iguales, como queríamos. \(\square\)
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Realiza diagramas para las siguientes gráficas. Da su tamaño y orden. Encuentra los grados de cada vértice y verifica que se cumple en ellas el lema de los saludos.
\(V=\{a,b,c,d,e,f,g\}\), \(E=\{ab,bc,cd,de,ef,fg,ga,ad,dg,gc,cf,fb,be,ea\}\).
\(V\) es los enteros del \(1\) al \(14\) y hay una arista entre dos vértices si sus números son distintos y uno divide al otro.
\(V\) es el conjunto de países de América del Sur y hay una arista entre dos vértices si los países correspondientes comparten frontera.
Resuelve los siguientes incisos:
Muestra que en cualquier gráfica siempre existen por lo menos dos vértices que tienen el mismo grado.
Muestra que en cualquier gráfica siempre hay una cantidad impar de vértices de grado impar. Como sugerencia, usa el lema de Euler.
Construye una gráfica de orden \(7\) en donde los grados de sus vértices sean \(1,2,2,2,3,3,3\). ¿Es única la gráfica que puedes construir? ¿En qué sentido o sentidos?
Resuelve los siguientes incisos:
¿Qué posibles tamaños puede tener una gráfica de orden \(n\)?
Muestra que una gráfica con \(5\) vértices y \(6\) aristas siempre tiene por lo menos un vértice con grado por lo menos \(3\).
Sean \(n\) y \(k\) enteros positivos con \(1\leq k \leq n-1\). ¿Cuántas aristas debe tener una gráfica con \(n\) vértices para garantizar que tiene por lo menos un vértice de grado por lo menos \(k\)?
¿Cómo se ve una gráfica en donde todos los vértices tienen grado menor o igual a dos? Se lo más preciso posible con tu descripción para cubrir todos los posibles casos.