Como se sabe, un grafo $G$ consiste de vértices y aristas, donde éstas se pueden ver como pares de vértices. El conjunto de vértices suele denotarse con $V$ y el de aristas con $E$ --y el grafo con $G(V,E)$. Como ya se dijo en el post Modelación de Relaciones, la utilidad principal de los grafos es la modelación de relaciones.
Para empezar, es conveniente considerar las relaciones simétricas (si $uRv$ entonces $vRu$), como la relación de amistad ("es amigo de ") o la de congruencia ("es congruente con"). Pero algunas relaciones no son simétricas, como la relación padre-hijo ("es hijo de") o la de divisibilidad ("divide a"). En esos casos, el grafo modelo es dirigido u orientado --las aristas tienen una dirección.
Valencia de un vértice
Una de las dificultades de aprendizaje que presenta la teoría de grafos es su extensa terminología. Para superar esa dificultad sugiero --al interesado en estudiar esta disciplina-- aprender los conceptos en bloques.
Por ejemplo, vértice y arista pero también adyacencia (de vértices) e incidencia entre vértices y aristas (de manera más precisa, aristas incidentes con un vértice). Estos cuatro conceptos iniciales de la teoría de grafos se pueden asociar a la metáfora del poliedro (ver mi post Modelación de Relaciones).
En este post voy a añadir un quinto concepto: grado o valencia de un vértice. Y demostraremos un teorema, elemental pero importante, con la finalidad de enfatizar la relación íntima que guarda la teoría de gráficas (grafos) con la combinatoria.
El grado (o valencia) de un vértice $v$ se define como el número de aristas que inciden en él, y se denota con $g(v)$ --si $g(v)=0$, se dice que $v$ es un vértice aislado.
(El término valencia es posiblemente más adecuado, si uno recuerda su curso de química --la valencia es el "poder combinante de un elemento". Porque las aristas incidentes en el vértice "combinan" a éste con los vértices que son el otro extremo de esas aristas.) Esta definición nos permite presentar un teorema, elemental pero importante.
Teorema (de la relación entre valencias y aristas)
En todo grafo $G(V,E)$, la suma de las valencias es igual al doble del número de aristas. En símbolos: $$\sum_{v \in V} g(v) = 2|E|$$
Demostración
Primero observemos que por cada vértice $v$ hay $g(v)$ aristas, y por cada arista hay dos vértices. Vamos a contar de dos formas (doble conteo) las parejas (vértice, arista incidente).
La primera forma consiste en recorrer los vértices y enumerar, para cada uno, sus aristas incidentes. Por ejemplo, al llegar al vértice $v_k$, enumeramos las aristas incidentes, digamos, $a_{k1}, a_{k2},\ldots,a_{g(v_k)}$. Al final del recorrido se tiene una lista de $\sum_{v\in V} g(v)$ parejas, es decir, el lado izquierdo de la fórmula.
La segunda forma es recorrer las aristas y enumerar, para cada una, sus vértices extremos. Por ejemplo, al llegar a la arista $a_j$ enumeramos sus vértices extremos, digamos $v_{a_j1}$ y $v_{a_j2}$. Al final del recorrido, se tiene una lista de $2|E|$ parejas.
Pero las dos listas tienen exactamente los mismos elementos. (El lector debería convencerse de ello, trabajando sobre uno o dos grafos pequeños y elaborando las dos listas.)
Demostración alternativa
Consideremos el grafo $G(V,E)$. Vamos a proceder eliminando aristas una a una (como deshojando una margarita) y ver el efecto en la suma de valencia: al quitar una primera arista, el grafo que queda tiene 2 unidades menos que la suma de las valencias del original (a la suma de valencias del grafo original le resto dos unidades), lo mismo pasa al quitar una segunda arista (la suma de valencias del grafo original se ha reducido en 4), etc.; continuando de esa manera, cada vez que quito una arista, la suma de valencias se reduce en 2 unidades, y al quitar la última arista, la suma de valencias se reduce a cero. Se logra entonces ver que $$\sum_{v\in V} g(v)-2|E|=0$$
Comentario: notando que la suma de las valencias es par y que esa suma es una suma de números pares o impares, es inmediata la prueba del siguiente
Corolario (y dos problemas)
En todo grafo $G(V,E)$, el número de vértices de grado impar es par.
Problema (lema del apretón o handshake lemma)
¿Cuántos diferentes saludos de mano son posibles en una reunión de $n$ personas?
Solución
El problema se deja modelar mediante un grafo: los vértices son las personas y las aristas los apretones de mano. El máximo número de apretones ocurre cuando cada persona saluda de mano a todas las restantes n-1. Traducido al grafo, esto significa que todos los vértices del grafo tienen valencia $n-1$.
El lector podría desear realizar de nuevo el doble conteo --como en la demostración del teorema anterior. Pero si confiamos en el teorema, podemos usarlo de inmediato: $(n-1)n=2|E|$, es decir, $|E|=(n-1)n/2$. (Con n=10 personas, el número de apretones posibles son 45 -chéquenlo.)
Problema (apretones impares en Beverly Hills)
Cada personaje de la serie Beverly Hills 90210 se enamoró un cierto número de veces de otros de la misma serie cambiando de pareja sentimental varias veces durante su estancia en la prepa, pero siempre con una persona diferente y del mismo grupo. Demostrar que los personajes que se enamoraron un número impar de veces es par.
Solución
Consideremos el número total de pares (p,x) de parejas sentimentales p y participantes x que se formaron en la serie mencionada. Este número debe ser par, puesto que cada pareja tuvo dos participantes. Por ejemplo, la relación de Brenda y Dylan se registraría como (p_1, Brenda), (p_1, Dylan).
Sin embargo, este número se puede obtener también enlistando el número de romances en que cada personaje individual estuvo involucrado, para cada uno de ellos (algunos personajes tuvieron un número impar de romances y otros un número par).
Pero, el número total de ítems en estas listas es el mismo que los de la primera lista (de hecho son los mismos ítems en ambas formas de contar los pares (p,x)). Por tanto, el número de personajes que tuvieron un número impar de romances es par --dado que su suma es par.
Comentarios
1) Dejando a un lado el hecho de que el teorema y su corolario, así como el lema del apretón, se convierten en ejemplos de escasa trascendencia una vez que se traducen a relaciones de amistad o romance, lo que habría que destacar aquí es que, aunque aparentemente nada se sabe del grafo (o de los romances en un cierto grupo de personas), sí se sabe algo --bajo el supuesto de que la paridad del número tuviese alguna trascendencia.
2) En la solución del problema de los romances se repitió el mismo argumento del teorema y su corolario --en el contexto romántico de la serie. Claramente es un argumento combinatorio, pero es mucho más difícil de seguir si no tenemos el modelo del grafo en que se habla de valencias. De ahí la utilidad del modelo como una ayuda al razonamiento.
3) Conviene destacar que los argumentos combinatorios empleados son experimentos imaginarios. En ese sentido, podría plantearse la pregunta: ¿qué tan válido es un argumento combinatorio como demostración?
4) Por otro lado, es conveniente que el aprendiz sepa de que está hablando cuando elabore un argumento combinatorio. Porque el argumento podría resultar falaz. Es decir, el aprendiz debería experimentar con ejemplos para llenar de realidad el experimento imaginario, y no tratar de imitar la forma del argumento dejando de lado el contenido.
Porque es muy fácil llegar a creer que el argumento es correcto, dado que viene en un libro. Pero los libros podrían estar mal (sobre todo cuando son traducciones y algo se ha perdido en ella).
Por ejemplo, con otra redacción, el problema de los romances es el primero del libro The USSR Olympiad Problem Book. En este caso, la modelación mediante un grafo permite la aplicación del corolario. Sin embargo, es interesante el argumento combinatorio de la solución en el libro mencionado.
Primero porque se ahorra el grafo y argumenta directamente sobre el contexto dado --lo cual es común en problemas de concurso de los que se espera que todo mundo los pueda resolver. Pero también es interesante porque es una solución errónea --algo se perdió en la traducción. He aquí el problema y su solución:
Los saluda
jmd