Aspectos algebraicos en teoría de grafos

Facultad de Matemáticas Departamento de Geometría y Topología TRABAJO FIN DE GRADO Aspectos algebraicos en Teoría de Grafos Francisco Javier Franco Galvín Sevilla, Junio 2016 Facultad de Matemáticas Departamento de Geometría y Topología TRABAJO FIN DE GRADO Aspectos algebraicos en Teoría de Grafos La Profesora Tutora: Fdo: María Trinidad Villar Liñán Prof. Titular de Universidad Fdo: Francisco Javier Franco Galvín A mi abuela. Agradecimientos Quisiera agradecer a varias personas la dedicación que me han prestado y los conocimientos que me han transmitido a lo largo de estos cuatro años universitarios. Gracias a ellos, esta memoria ha dado su fruto. Entre ellas, y en primer lugar, a María Trinidad Villar Liñán, mi tutora en este Trabajo de Fin de Grado, por todo lo que me ha enseñado y ayudado ante todas las dicultades que se han presentado durante la elaboración de este proyecto. Seguidamente, al resto de profesores de la Universidad de Sevilla. Concretamente, expresar mi reconocimiento a aquellos del departamento de Geometría y Topología, por hacerme descubrir el interesante mundo de la Teoría de Grafos. Agradecer también este trabajo a mis padres, que desde el primer momento en el que decidí empezar mi etapa universitaria me han apoyado y ayudado lo suciente para que pudiera cumplir uno de mis sueños. Al resto de mi familia y, en especial, a mi abuela, que se hubiera sentido más orgullosa de su nieto de lo que ya lo estaba. Y nalmente a mis amigos, que han conseguido que estos cuatro años sean menos duros de lo que podrían haber sido. Muchas gracias a todos. 5 6 Abstract Algebraic Graph Theory applies algebraic methods to problems about graphs. Throughout this project we will study the relationship between matrices and polynomials which are associated with graphs and invariant properties of graphs under isomorphisms. From matrices associated with graphs we can study properties about the connectivity as the number of connected components a graph has and the number of paths with a specic length contained therein. In addition to these problems, we will focus on Kirchho theorem, a classic result that counts how many spanning trees a graph has. We will also study other invariants: the characteristic polynomial of a graph, the chromatic polynomial and the Tutte polynomial. From these objects we will know the basic structural properties of the graph that represents as the number of vertices, edges or triangles that it has; and some information about the problem of colouring the graph or the number of subgraphs which are contained in it. 7 14 1.1. CONCEPTOS BÁSICOS EN TEORÍA DE GRAFOS v1v2 v3 v4 Figura 1.1: Grafo, digrafo y grafo etiquetado. Si la arista e está dirigida desde u hasta v , diremos que v es adyacente a u ó que e es incidente a v . Llamaremos lazo a toda arista del tipo e=uu . Diremos que G es un multigrafo si tiene aristas múltiples , es decir, aristas repetidas. Si G tiene lazos decimos que G es un pseudografo . Un grafo es simple si no tiene ni aristas múltiples ni lazos. Cabe notar que la denición inicial de grafo corresponde en realidad con la noción de grafo simple. Figura 1.2: Grafo simple, pseudografo y multigrafo. El grado de un vértice v en un grafo G no dirigido, que lo denotaremos por δ(v) , es el número de aristas de G incidentes con v . En el caso de ser G un grafo dirigido, no podemos hablar de grado de un vértice v , sino de grado de entrada y grado de salida de un vértice, que los denotaremos por δ−(v) y δ+(v) respectivamente. En un digrafo, el grado de entrada de un vértice es el número de aristas incidentes a él y el grado de salida de un vértice es el número de sus vértices adyacentes. Un grafo se dice regular si todos sus vértices tienen el mismo grado. CAPÍTULO 1. PRELIMINARES 15 1.1.2. Isomorsmo de grafos Diremos que dos grafos G= (V, E) y G0= (V0, E0) son isomorfos si existe una aplicación biyectiva f entre V y V0 de forma que uv dene una arista en G si y sólo si f(u)f(v) dene una arista en G0 . vi→v0 i v1v2v3 v4v5v6 v0 1 v0 2 v0 3 v0 4 v0 5 v0 6 Figura 1.3: Isomorsmo entre dos grafos. 1.1.3. Subgrafos Sea S⊆V un subconjunto de vértices del grafo G . Denominamos subgrafo inducido o generado por S al subgrafo de G que tiene a S como conjunto de vértices y cuyas aristas son todas aquellas del grafo G con los dos extremos en S . Un subgrafo se dice maximal o spanning si contiene todos los vértices del grafo en el que está contenido. Figura 1.4: Grafo, subgrafo y subgrafo maximal o spanning . Sea G un grafo y v∈V uno de sus vértices. Se denomina subgrafo G−v al subgrafo de G inducido o generado por V− {v} , es decir, al subgrafo de G que se obtiene eliminando el vértice v y todas las aristas incidentes con él, aunque los otros extremos de esas aristas permanecen. Sea G un grafo y e∈E una de sus aristas. Se denomina subgrafo G−e al subgrafo de G inducido por E− {e} , es decir, al subgrafo de G que se obtiene eliminando la arista e , aunque sus extremos permanecen. 16 1.1. CONCEPTOS BÁSICOS EN TEORÍA DE GRAFOS v e GG−v G −e Figura 1.5: Grafo G= (V, E) , subgrafo de G inducido por V−{v} y subgrafo de G inducido por E− {e} . 1.1.4. Operaciones con aristas Sea G= (V, E) un grafo cualquiera, podemos denir las siguientes operaciones en el conjunto E : 1. Adición de aristas . Resulta de añadir una arista e al grafo G , que denotaremos por G+e . Si e∈G , entonces obtendremos una arista múltiple en G . 2. Eliminación o supresión de aristas . Consiste en eliminar una arista e∈G , pero sin suprimir los vértices extremos. Esta eliminación la describiremos por G−e . 3. Contracción de aristas . Usaremos G/e para denotar la contracción de la arista e en el grafo G . Cuando contraemos una arista e=uv en un grafo lo que hacemos es identicar los vértices u y v , de manera que pasan a ser un mismo vértice y la arista e se pierde. En el caso en que el grado de uno de los vértices extremos de e sea exactamente igual a uno, la arista no se pierde, sino que se convierte en un lazo dentro del conjunto de aristas de G/e . Tras la contracción, el resto de vértices de G/e siguen manteniendo las mismas adyacencias que en G . 4. Contracción simple de aristas . Denotaremos por G∠e a la contracción simple de la arista e en G . Consiste en contraer la arista pero teniendo en cuenta que la contracción de ésta no puede originar ni lazos ni aristas múltiples, así que eliminaremos este tipo de aristas cuando aparezcan. En la Figura 1.6 pueden verse algunos ejemplos de estas operaciones sobre un grafo. CAPÍTULO 1. PRELIMINARES 17 Figura 1.6: Operaciones con aristas en un grafo G . 1.1.5. Caminos y ciclos Un camino en G es una sucesión nita de vértices γ={v1v2. . . vs} tales que dos elementos consecutivos de la misma son siempre adyacentes. Cuando G se trata de un grafo con aristas múltiples es conveniente denir los caminos como sucesiones nitas de vértices y aristas. Así un camino podría ser γ={v1e12v2e23 . . . es−1,svs} , donde eij denota la arista que une los vértices vi y vj . Un recorrido en G es un camino en el cual todas las aristas que lo forman son distintas. Un arco en G es un recorrido en el que todos los vértices que lo forman son distintos. Véase la Figura 1.7. Un ciclo en G es un camino cerrado en G que es un arco, excepto en el hecho de que el primer y último vértice coinciden. Véase la Figura 1.8. 18 1.1. CONCEPTOS BÁSICOS EN TEORÍA DE GRAFOS v1 v2v3 v4 v5 v6 v7 Figura 1.7: Arco. v1 v2v3 v4 v5 v6 v7 Figura 1.8: Ciclo. 1.1.6. Conexión Un grafo se dice conexo si dos cualesquiera de sus vértices pueden unirse mediante un arco. Si un grafo no es conexo, se dice disconexo . Se denomina componente conexa de un grafo a todo subgrafo conexo del mismo que tenga el mayor número posible de vértices. Los vértices aislados, que no tienen aristas incidentes, se consideran también componentes conexas del grafo. v1v2 v3 v4 v5v6 G Figura 1.9: Grafo disconexo con tres componentes conexas. Se denomina longitud de un camino en el grafo al número de aristas que lo forman. Se denomina distancia entre dos vértices u, v ∈V a la menor longitud de todos los arcos que los unen, si los hay. La denotaremos por d(u, v) . Si no existe ningún arco que una los vértices u y v tomaremos por convenio que d(u, v) = ∞ . En el grafo de la Figura 1.7, vemos que el camino marcado tiene longitud tres ya que está formado por tres aristas. La distancia entre los vértices v4 y v6 es uno ya que hay una arista que los une. La distancia entre v1 y v4 es dos ya que como mínimo esos vértices pueden conectarse a través de dos aristas, por ejemplo la arista v1v2 y a continuación la v2v4 . Si G es un grafo conexo, llamaremos diámetro de G a la mayor longitud entre dos cualesquiera de sus vértices. CAPÍTULO 1. PRELIMINARES 19 Puede observarse en la misma Figura 1.7 que su diámetro es 2. Se denomina punto de corte de un grafo G a todo vértice v∈V tal que el grafo G−v tenga más componentes conexas que G . Se denomina puente de un grafo G a toda arista e∈E tal que G−e tenga más componentes conexas que G . La eliminación de un punto de corte o de un puente en un grafo conexo lo desconectaría. Un grafo se dice no separable si es conexo y no tiene puntos de corte. Se denomina bloque de G a todo subgrafo de G no separable maximal. 1.1.7. Operaciones binarias entre grafos Sean G1= (V1, E1) y G2= (V2, E2) dos grafos, entonces se denen las siguientes operaciones: 1. Grafo unión : G1∪G2= (V1∪V2, E1∪E2) . 2. Grafo intersección : G1∩G2= (V1∩V2, E1∩E2) . 3. Grafo suma : G1+G2= (V1∪V2, E1∪E2∪ {uv|u∈V1, v ∈V2}) . 1.1.8. Familias innitas de grafos Grafos Pn o lineales Son grafos de n vértices y un arco de longitud n−1 . Todos los vértices de estos grafos tienen por tanto grado dos, excepto dos de ellos, que tienen grado 1. P2P3P4 Figura 1.10: Grafos Pn o lineales. Grafos Cn o ciclos Son grafos regulares y conexos de n vértices de grado 2 cada uno de ellos. Grafos Kn o completos Son grafos regulares de n vértices de grado n−1 cada uno de ellos. 20 1.1. CONCEPTOS BÁSICOS EN TEORÍA DE GRAFOS C3C4C5 Figura 1.11: Grafos Cn o ciclos. K3K4K5 Figura 1.12: Grafos Kn o completos. Grafos bipartitos Son aquellos grafos cuyo conjunto de vértices V se puede descomponer en dos subconjuntos disjuntos no vacíos V1 y V2 de modo que para toda arista uv ∈E se verique que u∈V1 y v∈V2 . Grafos Kn,m o bipartitos completos Son aquellos grafos bipartitos en los que existen todas las aristas posibles. En ellos, n=|V1| y m=|V2| . v1v2v3v4 v5v6v7 Figura 1.13: Grafo bipartito. v1v2v3v4 v5v6v7 K3,4 Figura 1.14: Grafo bipartito completo. Grafos Wn o ruedas Son aquellos grafos del tipo Wn=K1+Cn−1 , con n≥4 , que se obtienen mediante la unión de un vértice aislado ( K1 ) con un ciclo de n−1 vértices. CAPÍTULO 1. PRELIMINARES 21 1.1.9. Árboles Un grafo G se dice acíclico si no contiene ciclos. Si un grafo es conexo y acíclico es llamado árbol . Un árbol G= (V, E) se caracteriza por ser conexo y vericar |E|=|V| − 1 . Se dice que un grafo es un bosque si es acíclico y disconexo. Se denomina árbol maximal o spanning de un grafo G a todo subgrafo maximal de G que sea además árbol. 1.1.10. Grafos duales Un grafo plano o planar es un grafo que puede ser representado en el plano sin que ninguna arista se cruce. Un grafo dual G∗ de un grafo plano G es un grafo que tiene un vértice por cada región de G , y una arista por cada arista en G uniendo a dos regiones vecinas. GG∗ Figura 1.15: Grafo planar y construcción de su grafo dual. Si G= (V, E) y G∗= (V∗, E∗) son dos grafos planares cuyos conjuntos de regiones son R y R∗ respectivamente, entonces se verica que |E∗|=|E| , |V∗|=|R| y |R∗|=|V| . 1.2. Conceptos algebraicos Recogeremos en esta sección los resultados de álgebra lineal que utilizaremos en los próximos capítulos aunque hay conceptos que supondremos conocidos y pueden consultarse en [6]. Estas deniciones y resultados que ahora expondremos, a diferencia de los relacionados con grafos, serán enumerados para poder hacer referencia a ellos cuando sea necesario. 22 1.2. CONCEPTOS ALGEBRAICOS 1.2.1. Matrices y determinantes Denición 1.2.1 ( Traza de una Matriz ) . Sea A= (aij) una matriz cuadrada de orden n . Denotamos por tr(A) a la traza de la matriz A , es decir, a la suma de los elementos de su diagonal principal. tr(A) = n X i=1 aii Proposición 1.2.2. Sea A una matriz cuadrada de orden n y sean λk 1, . . . , λk n los autovalores de su potencia n -ésima (donde pueden existir repeticiones). Entonces se verica tr(Ak) = n X i=1 λk i. Denición 1.2.3 ( Matrices Congruentes ) . Dos matrices cuadradas A y B son congruentes si puede pasarse de A a B mediante un número nito de operaciones elementales la y las mismas operaciones y en el mismo orden pero en columnas. Proposición 1.2.4. Dos matrices cuadradas A y B son congruentes si y sólo si existe una matriz cuadrada regular P vericando B=PtAP . Denición 1.2.5 ( Menor de un Elemento ) . Sea A= (aij) una matriz cuadrada de orden n . El menor del elemento aij de la matriz A es la matriz de orden n−1 que resulta de suprimir la la i y la columna j en A . Denición 1.2.6 ( Cofactor de un Elemento ) . El cofactor de un elemento de una matriz es el determinante del menor de ese elemento. Teorema 1.2.7 ( Teorema de Expansión de Laplace ) . Sea A= (aij) una matriz cuadrada de orden n . Entonces det(A) = n X i,j=1 (−1)i+jaijcij, donde cij es el cofactor del elemento aij en A . 1.2.2. Polinomios Denición 1.2.8 ( Polinomio Mínimo ) . Sea A una matriz de orden n . El polinomio mínimo de A , denotado por ψA , es el polinomio mónico de menor grado que satisface A , es decir, ψA(A)=0 . CAPÍTULO 1. PRELIMINARES 23 1.2.3. Espacios vectoriales Teorema 1.2.9 ( Teorema de la Dimensión ) . Sean U y V dos k -espacios vectoriales donde U tiene dimensión nita, y sea f:U−→ V una transformación lineal. Entonces dim(U) = dim(Ker(f)) + dim(Im(f)), siendo Ker(f) e Im(f) el núcleo y la imagen de la aplicación f respectivamente. En [6] se puede encontrar los conceptos de núcleo e imagen de una transformación lineal, así como los de dimensión y bases de espacios vectoriales. Observación 1.2.10. Si la aplicación lineal f puede ser descrita mediante una matriz A de dimensión n×m , entonces n=dim(Ker(A)) + dim(Im(A)) = dim(Ker(A)) + rg(A). 30 2.1. LA MATRIZ DE ADYACENCIA v1v2 v5 e1 e8 Figura 2.4: Camino γ1 entre v2 y v5 . v2 v5 v6 e7 e10 Figura 2.5: Camino γ2 entre v2 y v5 . Teorema 2.1.5. Sea G un grafo de n vértices con matriz de adyacencia A= (aij) . Entonces el elemento (i, j) de Ak , que denotaremos por a(k) ij , es el número de caminos de longitud k desde vi a vj . Demostración. Realizaremos la prueba por inducción. Para k= 1 , según el teorema, el elemento aij indica el número de caminos diferentes de longitud uno entre vi y vj . Esto se verica por la denición de matriz de adyacencia, ya que un camino de longitud uno desde vi a vj es justamente la arista que une ambos vértices. Ahora supondremos que el teorema es cierto para k−1 , con k > 1 . Es decir, a(k−1) ij es el número de caminos diferentes de longitud k−1 desde vi hasta vj . Queremos probar el teorema para k , es decir, a(k) ij es el número de caminos diferentes de longitud k entre vi y vj . Como Ak=Ak−1A , se tiene que a(k) ij =Pn t=1 a(k−1) it atj . Por otro lado, los caminos de longitud k entre vi y vj son caminos de longitud k−1 entre vi y vt , siendo vt un vértice adyacente a vj , seguidos de una arista vtvj . Como hemos supuesto en la hipótesis de inducción que bit es el número de caminos de longitud k−1 desde vi hasta vt , y sabemos por nuestro caso base que atj es el número de caminos de longitud uno entre vt y vj , entonces el número total de caminos entre vi y vj será Pn t=1 a(k−1) it atj , que es tal y como hemos denotado a las entradas de la matriz Ak . Cabe notar que el razonamiento seguido en la prueba anterior es válido tanto si G es dirigido como si no lo es. De este teorema podemos deducir de forma inmediata las siguientes propiedades. CAPÍTULO 2. MATRICES ASOCIADAS A GRAFOS 31 Corolario 2.1.6. Sea G un grafo simple. Siguiendo la notación del teorema anterior se tiene que: 1. a(2) ii =δ(vi) . 2. a(3) ii es el doble del número de triángulos que contienen al vértice vi . Considerando por ejemplo el grafo simple de la Figura 2.1, tenemos que las potencias segunda y tercera de su matriz de adyacencia son A2=         311112 130121 102011 110201 121031 211113         A3=         462265 624236 240322 223042 632426 562264         De aquí, jándonos en la diagonal de la matriz A2 , tenemos que los vértices v1, v2, v5 y v6 tienen grado 3, mientras que los vértices v3 y v4 tienen grado 2. Por otro lado, hallando la mitad de los elementos de la diagonal de la matriz A3 , deducimos que los vértices v1 y v6 están contenidos en dos triángulos, los vértices v2 y v5 están en un único triángulo cada uno de ellos, y ningún triángulo del grafo contiene a los vértices v3 ó v4 . 2.1.2. Conexión El resultado que acabamos de estudiar es de gran utilidad para determinar si un grafo es o no conexo. Esto es ya que dos vértices estarán en una misma componente conexa si existe algún camino entre ambos. Teorema 2.1.7 ( Caracterización de Grafos Conexos ) . Sea G un grafo de n vértices con matriz de adyacencia A y sea B= (bij) la matriz B=A+A2+... +An−1. Entonces G es conexo si y sólo si bij 6= 0 , con i6=j , es decir, si y sólo si los elementos extradiagonales de la matriz B son no nulos. Demostración. Al igual que antes, denotaremos por a(k) ij al elemento (i, j) de la matriz Ak , donde k= 1, ..., n −1 . Entonces bij =a(1) ij +a(2) ij +... +a(n−1) ij . 32 2.1. LA MATRIZ DE ADYACENCIA Por el Teorema 2.1.5, sabemos que los elementos a(k) ij indican el número de caminos distintos de longitud k entre vi y vj . Así deducimos que bij es el número de caminos diferentes entre vi y vj de longitud menor que n . Supongamos en primer lugar que G es conexo, es decir, que para todo par de vértices hay un camino que lo une. El grafo G tiene n vértices, por lo que dicho camino atravesará a lo más n vértices y su longitud será por tanto menor que n . Como este resultado se tiene para dos vértices cualesquiera, entonces bij 6= 0 , con i6=j . Recíprocamente, si suponemos que bij 6= 0 , con i6=j , entonces hay al menos un camino de longitud menor que n desde vi a vj . Esto quiere decir que para todo (i, j) , con i6=j , los vértices vi a vj están en la misma componente conexa. Por consiguiente, G es un grafo conexo. Ilustremos el teorema con dos ejemplos. Utilizándolo vamos a comprobar que el grafo G1 de la Figura 2.6 es conexo y que el grafo G2 de la Figura 2.7 no lo es. v1v2 v3 v4 G1 Figura 2.6: Grafo conexo. v1v2 v3 v4 G2 v5 Figura 2.7: Grafo disconexo. Sea A1=    0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0     la matriz de adyacencia del grafo G1 . Entonces A2 1=    2 1 1 1 1 3 0 1 1 0 1 1 1 1 1 2     y A3 1=    2 4 1 3 4 2 3 4 1 3 0 1 3 4 1 2     . Por lo tanto, B1=A1+A2 1+A3 1=    4 6 2 5 6 5 4 6 2 4 1 2 5 6 2 4     . CAPÍTULO 2. MATRICES ASOCIADAS A GRAFOS 33 Como todos los elementos extradiagonales de B1 son no nulos, podemos armar que G1 es un grafo conexo. Análogamente, siendo A2=      01010 10010 00001 11000 00100       la matriz de adyacencia de G2 , se tiene lo siguiente: A2 2=      21010 12010 00100 11020 00001       A3 2=      23030 32030 00001 33020 00100       A4 2=      65050 56050 00100 55060 00001       Así, B2=      10 10 0 10 0 10 10 0 10 0 0 0 2 0 2 10 10 0 10 0 0 0 2 0 2       Como B2 tiene ceros extradiagonales, G2 no es un grafo conexo. Las matrices de adyacencia de grafos disconexos, al igual que la de los grafos bipartitos como vimos en la Proposición 2.1.4, tienen una forma característica. Proposición 2.1.8. Si G es un grafo con dos componentes conexas, existe un etiquetado de los vértices de G de manera que su matriz de adyacencia A resulta de la forma A=A1θ θ A2, donde A1 y A2 son las matrices de adyacencia de cada una de las componentes conexas de G . En el caso de que G sea un grafo disconexo con más de dos componentes conexas, existe un etiquetado de vértices tal que la matriz de adyacencia es diagonal por bloques. Anteriormente dedujimos que el grafo G2 de la Figura 2.7 era disconexo. Por la proposición anterior, existe una reordenación de vértices que transforma su matriz de adyacencia en una matriz diagonal por bloques. 34 2.2. LA MATRIZ DE INCIDENCIA En este caso, intercambiando las etiquetas v3 y v4 , quedarían los vértices {v1, v2, v3} en una componente conexa y {v4, v5} en la otra. Y, paralelamente, la matriz de adyacencia resultante del nuevo etiquetado, A0 2 , es la matriz que surge tras intercambiar las las y columnas 3 y 4 en la matriz A2 . v1v2 v3 v4 G2 v5 A2=      01010 10010 00001 11000 00100       v1v2 v4 v3 G0 2 v5 A0 2=      01100 10100 11000 00001 00010       Figura 2.8: Reordenación de vértices en grafos disconexos. En A0 2 puede observarse que cada bloque de la diagonal es matriz de adyacencia de una de las componentes conexas de G0 2 . Observamos que este resultado es consistente para grafos no simples en general. 2.2. La matriz de incidencia Existen otras formas de representar grafos mediante matrices. Cada representación matricial tiene sus virtudes y desventajas. En particular, la matriz de incidencia es muy utilizada en la programación. Denición 2.2.1 ( Matriz de Incidencia ) . Sea G= (V, E) un grafo etiquetado con n vértices y m aristas, V={v1, ..., vn} y E={e1, ..., em} . La matriz de incidencia de G viene denida por Mn×m= (mij) , donde si G es un grafo no dirigido, mij =   0 si vi no es incidente con ej 1 si vi es incidente con ej 2 si la arista ej es un lazo en el vértice vi CAPÍTULO 2. MATRICES ASOCIADAS A GRAFOS 35 y si G es un grafo dirigido, mij =       0 si vi no es incidente con ej 1 si vi es el comienzo de la arista dirigida ej −1 si vi es el nal de la arista dirigida ej 2 si ej es un lazo en el vértice vi En las Figuras 2.9 y 2.10 se muestran dos ejemplos de grafos con sus respectivas matrices de incidencia. v1v2 v3 v4 v5 e1 e2 e3 e4 e5e6 G1 M1=      100010 110001 011000 001200 000011       Figura 2.9: Grafo no dirigido y su matriz de incidencia. v1v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 G2 e7 M2=      1 0 0 0 −1 0 0 −1 1 0 0 0 1 −1 0−1−1 0 0 0 0 0012000 0 0 0 0 1 −1 1       Figura 2.10: Grafo dirigido y su matriz de incidencia. De la denición de matriz de incidencia derivan las propiedades que aparecen en esta proposición. Proposición 2.2.2. Se verica 1. La matriz de incidencia, al igual que la de adyacencia, depende del etiquetado del grafo. Si M1 y M2 son dos matrices de incidencia para diferentes etiquetados de un mismo grafo G , entonces podemos pasar de la matriz M1 a la matriz M2 mediante intercambios de las y columnas. 2. Para grafos no dirigidos, la suma de los elementos de la i-ésima la de M da el grado del vértice vi de G , mientras que la suma de los elementos de cualquier columna siempre es dos. 36 2.2. LA MATRIZ DE INCIDENCIA 3. Para digrafos sin lazos, la suma de los elementos de la i-ésima la de M da la diferencia entre el grado de salida y el grado de entrada en vi , mientras que la suma de los elementos de cualquier columna siempre es cero. El siguiente resultado proporciona una relación entre las matrices de adyacencia e incidencia de un grafo. Proposición 2.2.3. Sea G un grafo simple con matriz de adyacencia A y matriz de incidencia M , y sea D una matriz diagonal cuyos elementos de la diagonal son los grados de los vértices correspondientes, entonces A+D=MMt. Demostración. Si i=j , el producto de la i -ésima la de M por la j -ésima columna de Mt es el grado del vértice vi en G . Si i6=j , la entrada (i, j) en MMt es 1 ó 0 según vi y vj sean adyacentes o no en G . Ahora vamos a considerar grafos simples. Dando una orientación a las aristas podemos construir la matriz de incidencia β asociada al grafo G con respecto a esta orientación. Este tipo de matrices son usadas en ciencias de la computación para representar grafos de ujo de datos o grafos de control de ujos, en los que aparecen todos los caminos que pueden ser descritos por un programa durante su ejecución. Denición 2.2.4 ( Matriz de Incidencia respecto a una orientación ) . Sea G un grafo simple no dirigido en el que tanto sus vértices como sus aristas están etiquetadas. Dando una orientación a las aristas de G podemos obtener la matriz de incidencia β= (βij) denida como sigue: βij =   +1 si vi es el vértice nal de ej −1 si vi es el vértice inicial de ej 0 en otro caso Aunque parezca un concepto sin relevancia lo usaremos en la proposición que sigue, la cual nos ayudará a demostrar el resultado principal de la Sección 2.3: el Teorema de Kirchho . Proposición 2.2.5. Sea G un grafo simple con n vértices y sea β la matriz de incidencia de G con respecto a una orientación dada. Denotando por rg(β) al rango de la matriz β y por ω al número de componentes conexas de G , entonces se verica rg(β) = n−ω . CAPÍTULO 2. MATRICES ASOCIADAS A GRAFOS 37 Demostración. Sean G1, . . . , Gω las componentes conexas de G y ni el número de vértices de cada componente Gi . Entonces, al igual que vimos para la matriz de adyacencia de grafos disconexos en la Proposición 2.1.8, β tiene una descomposición en bloques de modo que, para cada i con 1≤i≤ω , β(i) es la matriz de incidencia, con respecto a la orientación correspondiente jada en β , de la i -ésima componente conexa de G . Para cada i con 1≤i≤ω , como la suma de los elementos de cada columna de β(i) es nula, el rango de esta matriz es rg(β(i))≤ni−1 . Para concluir que rg(β) = n−ω , basta probar que rg(β(i)) = rg (β(i))t=n−1 para cada i con 1≤i≤ω . Por el Teorema 1.2.9, tenemos que dim(Im(fi)) + dim(Ker(fi)) = ni, donde fi es la aplicación denida por la matriz (β(i))t . Como la dimensión de la imagen de fi coincide con el rango de (β(i))t , que queremos ver que es exactamente ni−1 , probemos que el núcleo de (β(i))t tiene dimensión 1. Para esto veamos que { 1 t= (1,...,1)t} es base para este subespacio. Claramente 1 tβ(i)= 0 , o sea, 1 ∈Ker (β(i))t . Sólo falta demostrar que Ker (β(i))t está generado por 1 . Sea x∈Ker (β(i))t . Consideremos dos coordenadas xl y xk cualesquiera de x , relacionadas respectivamente a los vértices vl y vk de Gi . Como Gi es conexo, existe un subconjunto de vértices {vl=vj1, vj2, . . . , vjr =vk} , tales que existe una arista entre vjp y vj(p+1) para cada p= 1, . . . , r −1 . Además, para cada una de estas r−1 aristas, existe una columna cp en β(i) (no necesariamente la p -ésima) cuyas entradas de orden jp y j(p+ 1) en cp valen una 1 y otra −1 , siendo el resto iguales a cero. Como xtβ(i)= 0 , entonces xtci= 0 y, por tanto, xjp =xj(p+1) . Pero como esto se tiene para todo p= 1, . . . , r −1 , se llega a que para cada l y k , xl=xk . Luego x=α 1 , para algún escalar α y así, 1 genera Ker (β(i))t . 2.3. La matriz laplaciana. Teorema de Kirchho El objetivo principal de esta sección es encontrar la forma de contar cuántos árboles maximales diferentes están contenidos en un grafo. Este es uno de los problemas más antiguos y famosos en Teoría de Grafos y fue resuelto por Kirchho mientras estudiaba circuitos eléctricos en 1847. Este resultado es conocido como Teorema de Kirchho o Teorema de matriz-árbol, y tiene gran importancia en diversos contextos, como la representación de moléculas en Química o el diseño de redes (Sección 4.6 de [9]). 38 2.3. LA MATRIZ LAPLACIANA. TEOREMA DE KIRCHHOFF Para presentarlo necesitaremos denir el concepto de matriz laplaciana y dar unos resultados previos que usaremos en su prueba. Denición 2.3.1 ( Matriz Laplaciana ) . Sea G un grafo simple no dirigido y etiquetado con n vértices, V={v1, ..., vn} . Denimos la matriz laplaciana o de Kirchho como Ln×n= (lij) , con lij =   δ(vi) si i=j −1 si i6=j y vi es adyacente con vj 0 en otro caso Equivalentemente, L=D−A , donde D= (dij) es una matriz diagonal con dii =δ(vi) y A es la matriz de adyacencia de G . v1v2 v3 v4 G L=    2−1 0 −1 −1 3 −1−1 0−1 1 0 −1−1 0 2     Figura 2.11: Grafo y su matriz laplaciana. Proposición 2.3.2. Si β es la matriz de incidencia asociada al grafo G tras darle una orientación a sus aristas, entonces L=ββt . Demostración. En primer lugar vamos a construir la matriz β= (βij) eligiendo una orientación arbitraria, es decir, cambiando uno de los dos unos que aparecen en cada columna de la matriz de incidencia M de G por −1 . La entrada (i, j) de ββt es βi1βj1+βi2βj2+. . . +βimβjm , que toma el valor δ(vi) si i=j , −1 si vi y vj son adyacentes, y 0 en otro caso. Por lo tanto ββt=L . De esta proposición podemos deducir que la matriz laplaciana L es una matriz simétrica y semidenida positiva. Por tanto, todos sus autovalores son mayores o iguales que cero. Proposición 2.3.3. Sea G un grafo con n vértices y ω componentes conexas. Entonces el rango de L es rg(L) = n−ω . CAPÍTULO 2. MATRICES ASOCIADAS A GRAFOS 39 Demostración. Esta armación deriva directamente de la Proposición 2.2.5. De hecho, el rango de L es igual al rango de la matriz de incidencia β con respecto a cualquier orientación considerada en G , ya que hemos visto en la Proposición 2.3.2 que L=ββt . En todo lo que sigue, consideraremos que G es un grafo simple y conexo con n vértices y m aristas. Lema 2.3.4. La matriz adjunta de L , adj(L) , es múltiplo de J , siendo J la matriz cuadrada de orden n cuyas entradas son todas iguales a 1. Demostración. Como G es un grafo conexo, podemos armar por la Proposición 2.3.3 que rg(L) = n−1 . Además, el núcleo de L tiene dimensión 1 y es generado por 1 . Por otro lado, como L·adj(L) = det(L)·I= 0 ·I=θ (con θ la matriz nula de orden n ), entonces cada columna de adj(L) pertenece al núcleo de L , siendo así un múltiplo del vector 1 t . Pero como L es una matriz simétrica, entonces adj(L) también es simétrica y tiene, por lo tanto, todas las entradas iguales. Lema 2.3.5. Sea β la matriz de incidencia de G con respecto a una orientación dada. Entonces, toda submatriz cuadrada suya tiene determinante 0, 1 ó −1 . Demostración. Sea S una submatriz cuadrada de β . Si cada columna de S tiene dos entradas no nulas, entonces estas entradas son 1 y −1 y, por tanto, cada columna tiene suma igual a 0. Luego det(S) = 0 . Supongamos ahora que al menos una columna de S tiene exactamente entrada no nula. En este caso, denotando por S0 a la matriz resultante al eliminar la la y la columna en la que se encuentra dicha entrada, obtenemos det(S) = det(S0) . Repitiendo este proceso, llegaremos a una matriz con determinante nulo o con una entrada no nula de β que tendrá entonces determinante 1 ó −1 . Lema 2.3.6. Consideremos cualquier submatriz de β obtenida tomando n−1 de sus columnas. Esta matriz de dimensión n×(n−1) corresponde a un subgrafo H de G que es maximal. Entonces, eliminando cualquier la de esta submatriz, la matriz resultante β0 es cuadrada de orden n−1 y tiene |det(β0)|= 1 ó 0, según el subgrafo H sea o no un árbol. 46 3.1. POLINOMIO CARACTERÍSTICO Proposición 3.1.6. Sea G un grafo con n vértices y m aristas, y pG(λ) = λn+a1λn−1+a2λn−2+. . . +an su polinomio característico. Entonces los coecientes de pG(λ) satisfacen: 1. a1= 0 . 2. −a2=m . 3. −a3= 2t , siendo t el número de triángulos de G . Demostración. Si p(λ) = λn+a1λn−1+a2λn−2+. . . +an es el polinomio característico de A , entonces ai= (−1)iXMi(A), donde Mi(A) representa los menores principales de orden i de la matriz A . 1. Como la diagonal principal de A está formada por ceros, entonces todos sus menores principales de orden 1 valen 0. De aquí se deduce que a1= 0 . 2. Cualquier menor principal de A de orden 2 con entradas no nulas es necesariamente de la forma  0 1 1 0  . Este menor aparece en A por cada par de vértices adyacentes de G y tiene valor −1 . Por lo tanto, (−1)2a2= (−1)m . Luego −a2=m . 3. Existen ocho posibilidades de menores principales de A de orden 3:  011 101 110 , 011 100 100 , 010 101 010 , 010 100 000 ,  001 001 110 , 001 000 100 , 000 001 010 , 000 000 000 . De estos determinantes, el único no nulo es el primero, cuyo valor es 2. Este menor principal corresponde a tres vértices de G mutuamente adyacentes, o sea, un triángulo. Así, (−1)3a3= 2t . De donde sigue, −a3= 2t . CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 47 Hemos visto que el polinomio característico del grafo diamante es λ4− 5λ2−4λ . En este polinomio, a1= 0 , a2=−5 y a3=−4 , por lo que se cumple la Proposición 3.1.6 ya que G tiene cinco aristas y dos triángulos. Una vez conocidos los conceptos de polinomio característico y autovalores de un grafo, y recordando el Teorema 2.1.5, se deduce el siguiente resultado. Proposición 3.1.7. Sea G un grafo con n vértices y m aristas y sean λ1, . . . , λs sus autovalores. Si denotamos por Tk al número de caminos cerrados de longitud k≥1 que aparecen en G , entonces Tk=tr(Ak) . Por lo tanto, Tk=Pn i=1 λk i , donde λk i son los autovalores de la matriz Ak . En particular, 1. La suma de los cuadrados de los autovalores es dos veces el número de aristas, es decir, tr(A2)=2m . 2. Si G es un grafo regular de grado k , entonces Pn i=1 λ2 i=kn . 3. La suma de los cubos de los autovalores es seis veces el número de triángulos de G , es decir, tr(A3) = 6t . Demostración. Del Teorema 2.1.5 se tiene que el número de caminos cerrados de longitud k de G coincide con la traza de la matriz Ak . Esto es ya que los elementos de la diagonal principal de Ak indican el número de caminos de longitud k desde i hasta él mismo y, por lo tanto, los caminos serán cerrados. Por otra parte, de la Proposición 1.2.2 se tiene Tk=Pn i=1 λk i . 1. La suma de los cuadrados de los autovalores es el número de caminos cerrados de longitud dos de G . Por cada arista de G tenemos dos caminos cerrados de longitud dos, uno que se recorre partiendo de uno de los vértices extremos, y otro camino partiendo del otro. Por lo tanto tr(A2)=2m . 2. Si G es un grafo regular de grado k se verica kn = 2m y, entonces, usando la propiedad anterior se tiene el resultado. 3. Esto se tiene porque un triángulo puede ser recorrido cerradamente de seis maneras distintas ya que para cada vértice hay dos formas de llegar a sí mismo. 48 3.1. POLINOMIO CARACTERÍSTICO Proposición 3.1.8. Sea G un grafo conexo con diámetro d , entonces tiene al menos d+ 1 autovalores distintos. Demostración. Sean λ1, . . . , λs los autovalores distintos de G . Como A es simétrica con coecientes reales, su polinomio mínimo tiene grado s y, por tanto, (A−λ1I)(A−λ2I)· · · (A−λsI)=0. De aquí se deduce que As es combinación lineal de I, A, A2, . . . , As−1 . Supongamos que s≤d y consideremos u y v dos vértices de G tales que d(u, v) = s . Entonces, denotando por ai uv a la entrada de la matriz Ai que relaciona los vértices u y v , se tiene que ai uv = 0 para todo i con 0≤i≤t−1 y as uv >0 . Esto contradice el hecho de que As pueda expresarse como combinación lineal de I, A, A2, . . . , As−1 . Entonces s≥d+ 1 . El diámetro del grafo diamante de la Figura 3.1 es dos y vimos que tenía 4 autovalores distintos. Por lo tanto, para este caso concreto, se verica la proposición anterior ya que G tiene al menos 3 autovalores diferentes. Proposición 3.1.9. Sea G un grafo con n vértices, m aristas y autovalores λ1, . . . , λn , entonces λ1≤s2m1−1 n. Demostración. Probaremos mediante un problema de optimización que el máximo valor posible que puede tomar λ1 es el que aparece en el resultado. Para denir el problema de maximización necesitamos imponer unas restricciones que vendrán dadas por identidades ya vistas anteriormente. De la Proposición 3.1.7 tenemos que Pn i=1 λi= 0 y Pn i=1 λ2 i= 2m . Sean f , g y h funciones de Rn en R denidas por f(x1, . . . , xn) = x1 , g(x1, . . . , xn) = x1+. . . +xn y h(x1, . . . , xn) = x2 1+. . . +x2 n , podemos considerar el siguiente problema de maximización: m´ax f(x1, . . . , xn) s.a : g(x1, . . . , xn)=0 h(x1, . . . , xn)=2m CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 49 Denimos entonces la función lagrangiana L(x1, . . . , xn, k1, k2) = x1−k1(x1+. . . +xn)−k2(x2 1+. . . +x2 n−2m) y, resolviendo utilizando los multiplicadores de Lagrange, obtenemos: ∂L ∂x1 = 1 −k1−2k2x1= 0 (3.1) ∂L ∂xi =−k1−2k2xi= 0, para todo i , 2≤i≤n (3.2) Además conocemos que: x1+. . . +xn= 0 (3.3) x2 1+. . . +x2 n= 2m (3.4) Tenemos que k26= 0 , ya que, de lo contrario, de (3.1) y (3.2) tendríamos que k1 sería simultáneamente igual a 0 y 1. De (3.2) sigue que para cada i , con 2≤i≤n , xi=−k1 2k2 . Sustituyendo esto en (3.3) llegamos a que x1+ (n−1) −k1 2k2= 0 . Luego, x1= (n−1) k1 2k2 (3.5) Sustituyendo (3.5) en (3.4), obtenemos (n−1)2k1 2k22 +(n−1) −k1 2k22 = = (n−1) k1 2k22 (n−1 + 1) = n(n−1) k1 2k22 = 2m . Entonces k1 2k2 =r2m n(n−1) y, volviendo a (3.5), obtenemos x1= (n−1)s2m n(n−1) =s(n−1)22m n(n−1) =s2m1−1 n. 50 3.1. POLINOMIO CARACTERÍSTICO Veamos que este resultado se verica para el grafo diamante de la Figura 3.1. En ese grafo n= 4 , m= 5 y 2,56155 y, entonces, se cumple λ1= 2,56155 ≤s2·5·1−1 4≃2,73861. La proposición que sigue nos da una ligera idea sobre cómo son los autovalores de un grafo en el caso en que éste sea regular. Proposición 3.1.10. Sea G un grafo regular de grado k . Entonces: 1. k es un autovalor de G . 2. G es conexo si y sólo si la multiplicidad de k es 1. 3. Cualquier autovalor λ de G satisface |λ| ≤ k . Demostración. 1. Sea 1 el vector columna (1,1,...,1)t . Como G es regular de grado k , entonces la suma de los elementos de cada la de la matriz de adyacencia A de G es k , el grado de cada vértice. Entonces se tiene que A 1 =k 1 , o sea, k es un autovalor de G . 2. Sea (x1, x2, . . . , xn)t un autovector asociado al autovalor k de G y supongamos que xj es una entrada de x con valor absoluto máximo. Como Ax =kx , entonces (Ax)j=Pxi , donde el sumatorio es considerado sobre los k vértices vi que son adyacentes a vj . Luego Pxi=kxj . De ahí tenemos que, para cada l con vl adyacente a vj , |xj|+ (k−1)|xj|=Xxi≤X|xi|≤|xl|+ (k−1)|xj|. De ahí llegamos a que |xj|≤|xl| y, por tanto, xl=xj para todos estos k vértices. Como G es conexo, podemos repetir sucesivamente lo anterior hasta llegar que todas las entradas de x son iguales. Entonces x es múltiplo de 1 y el autoespacio asociado al autovalor k tiene dimensión 1. Recíprocamente, si suponemos ahora que el autovalor k tiene multiplicidad 1 y que G es un grafo disconexo con G1, . . . , Gs componentes conexas. Como cada una de ellas es un grafo regular de orden k entonces k es un autovalor de multiplicidad 1 para cada componente Gi . Además, por la Proposición 3.1.5, como pG(λ) = pG1(λ)· · · pGs(λ) se sigue que k es un autovalor de G de multiplicidad s , que contradice la hipótesis. Luego, G es conexo. CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 51 3. Sea y un vector no nulo de G asociado al autovalor λ y sea yj la entrada de y con máximo valor absoluto. Al igual que antes, Pyi=λyj y |λ||yj|=|Pyi| ≤ P|yi| ≤ k|yj| . Luego, |λ| ≤ k . Consideremos el grafo G regular de grado 3 que aparece en la Figura 3.2. Si calculamos su polinomio característico obtenemos pG(λ) = λ6−9λ4− 4λ3+ 12λ2 y su espectro es spec(G) = 310−2 1 1 2 2 . De ahí vemos que el grado del grafo regular G , que es 3, es autovalor con multiplicidad 1 y los valores absolutos del resto de autovalores son inferiores a éste. Por lo que se verica esta proposición. v1 v2v3 v4 v6v5 G A=         010101 101001 010110 101010 001101 110010         Figura 3.2: Grafo regular de grado 3 y su matriz de adyacencia. Si el lector lo desea puede obtener más información sobre el polinomio característico de un grafo y, en general, acerca de la teoría espectral de grafos en los Capítulos 2 y 3 de [3]. 3.2. Polinomio cromático En esta sección nos centraremos en contar de cuántas formas distintas puede colorearse los vértices de un grafo con un número determinado de colores de manera que vértices adyacentes tengan coloraciones distintas. Para ello construiremos un polinomio en una variable, el llamado polinomio cromático , cuya evaluación por números naturales indicará cuántas son esas formas distintas de colorear el grafo. Insistamos desde un principio en que trabajaremos con grafos simples o multigrafos. Con esto podemos presentar la denición de polinomio cromático, pero antes deniremos qué entendemos por coloreado de un grafo. 52 3.2. POLINOMIO CROMÁTICO Denición 3.2.1 ( Coloración de un Grafo ) . Sea G= (V, E) un grafo simple y S el conjunto de colores de la colección {1, . . . , k} . Una coloración de los vértices de G con los colores de S es una correspondencia tal que a cada uno de los vértices de G se le asigna un color de S de manera que dos vértices adyacentes no pueden recibir el mismo color. Formalmente, una k− coloración es una aplicación c:V−→ S tal que c(u)6=c(v) si existe una arista de G que une u y v . El valor de c(u) es el color que recibe el vértice u en la coloración c . Además, se dice que un grafo G es k -coloreable si existe una k -coloración en vértices de G . Aquí se presenta una 4 − coloración del grafo de la Figura 3.2. 1 23 2 34 Figura 3.3: Ejemplo de coloreado de un grafo. Sin embargo, es fácil ver que este grafo puede ser coloreado también con tres colores (coloreando con 1 el vértice coloreado con 4), que es el mínimo número de colores con el que lo podemos colorear. Esto es lo que se entiende por número cromático de un grafo. Denición 3.2.2 ( Número Cromático ) . Se dene el número cromático de un grafo G como el menor valor k∈N tal que G es k -coloreable y se denota por χ(G) . Si k=χ(G) se dice que el grafo G es k -cromático. Por lo dicho anteriormente, el grafo de Figura 3.3 es 3 − cromático. Nota 2. Usaremos en lo que sigue χG(k) para denotar el número de maneras de colorear G con a lo más k colores. Esta misma notación será usada también para el polinomio cromático. El polinomio cromático fue introducido por G. D. Birkho en 1912 para únicamente grafos planares con el objetivo de demostrar el Teorema de los cuatro colores. Más tarde, en 1932, H. Whitney generalizó este polinomio para grafos en general (Sección 9.3 de [4]). El Teorema de los cuatro colores establece que todo mapa geográco con regiones continuas puede ser coloreado con cuatro colores diferentes de forma CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 53 que no queden regiones adyacentes con el mismo color. Además del problema de los cuatro colores hay muchos otros que pueden resolverse mediante la coloración de un grafo de forma similar. Por ejemplo, la distribución de las conferencias de un congreso de manera que dos conferencias que puedan ser de interés para una persona no se impartan al mismo tiempo; el almacenamiento de productos químicos donde hay determinados productos que son incompatibles entre sí y, por lo tanto, deben almacenarse de manera independiente; o distribuir las especies de animales de un zoológico teniendo en mente que hay especies que no pueden cohabitar en un mismo territorio. En la siguiente proposición se mencionan algunas propiedades inmediatas de χG(k) . Proposición 3.2.3. Denotando por χG(k) al número de formas distintas en las que podemos colorear G con k colores, entonces: 1. Si k < k0 entonces χG(k)< χG(k0) . 2. Si k < χ(G) entonces χG(k)=0 . 3. Si k≥χ(G) entonces χG(k)≥1 . 4. El número cromático de un grafo G es el menor número entero k a partir del cual no se anula χG(k) . 5. Si G y G0 son grafos isomorfos, entonces χG(k) = χG0(k) ya que las coloraciones de G son transformadas por el propio isomorsmo en coloraciones de G0 . 6. Si G es un grafo disconexo con G1, . . . , Gr componentes conexas, entonces χG(k) = χG1(k)· · · χGr(k) . A continuación veremos dos resultados para el cálculo de χG(k) cuando G es un grafo con puntos de corte o aristas puente. Proposición 3.2.4. Si un grafo G=G1∪G2 tiene un punto de corte v que es el único vértice común entre G1 y G2 , entonces χG(k) = χG1(k)·χG2(k) k. Demostración. En primer lugar sería necesario notar que siendo G un grafo cualquiera y v uno de sus vértices elegido de forma arbitraria, el número de 54 3.2. POLINOMIO CROMÁTICO coloraciones de G con los colores {1, . . . , k} en las que el vértice v toma el color 1 sería χG(k)/k . Este mismo resultado se obtendría si en lugar de tomar v el color 1, adquiriera cualquiera de los otros colores. v G1G2 Figura 3.4: Situación de la Proposición 3.2.4. Volviendo a nuestro problema y recordando que V(G1)∩V(G2) = {v} , sin haber restricciones de colores para el vértice v , tenemos que existen χG1(k) formas de colorear el grafo G1 con k colores. En cualquiera de estas coloraciones ya habremos jado un color en el vértice v , por lo tanto ahora podremos colorear G2 de χG2(k)/k diferentes, tal y como notamos antes. Deducimos entonces que χG(k) = χG1(k)·χG2(k) k . Proposición 3.2.5. Sea G un grafo con una arista puente e=uv que conecta las componentes G1 y G2 del grafo G−e , entonces χG(k) = χG1(k)·χG2(k) k(k−1) . Demostración. Basta notar que si tenemos un grafo cualquiera G y una arista suya e=uv , entonces el número de coloraciones de G con k colores donde u recibe el color 1 y v recibe el color 2 es χG(k) k(k−1). Al igual que antes, en lugar de los colores 1 y 2 podríamos haber elegido cualquier otro par de colores. Considerando entonces una coloración cualquiera de G1 donde los vértices u y v tengan colores distintos i y j respectivamente, podemos hacer una partición de las χG2(k) coloraciones de G2 según la coloración de G1 descrita CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 55 v G1G2 u Figura 3.5: Situación de la Proposición 3.2.5. anteriormente, es decir, donde los vértices u y v tomen los colores i y j . Estas coloraciones estarían en proporción 1/k(k−1) , así que χG(k) = χG1(k)·χG2(k) k(k−1) . Ahora vamos a calcular las expresiones de χG(k) para grafos lineales y completos mediante un proceso constructivo. Proposición 3.2.6. χPn(k) = k(k−1)n−1 , con n > 1 . Demostración. Sea Pn el grafo lineal de vértices ordenados v1, . . . , vn . Para el primer vértice, v1 , tenemos a nuestra disposición k colores. Una vez jado el color del vértice v1 , tendremos disponible únicamente k−1 colores para v2 ya que no podemos usar el mismo color que hemos asignado al vértice v1 . · · · kk−1k−1k−1k−1 Figura 3.6: Situación de la Proposición 3.2.6. A partir de ahí, cada vértice tendrá un color prohibido que corresponde al usado en el vértice anterior, por lo tanto, utilizando la regla del producto, se tiene el resultado. Observación 3.2.7. Para que χPn(k) no se anule es necesario y suciente que k≥2 . Proposición 3.2.8. χKn(k) = k(k−1)(k−2) · · · (k−n+ 1) . 62 3.3. POLINOMIO DE TUTTE de árboles maximales de un grafo general G , lo que estos estudiantes denominaron por complejidad del grafo y denotaron por C(G) . En [12, 13], el propio Tutte describe el proceso seguido hasta encontrar el polinomio, algunas de las propiedades que éste posee e incluso su relación con los rectángulos perfectos. Entre los cuatro encontraron una fórmula recursiva que relacionaba la complejidad de un grafo G con las complejidades de dos nuevos grafos. Siguiendo la notación de [12], los grafos involucrados en la fórmula recursiva son: G0 e , que resultaba de suprimir la arista e de G ; y G00 e , que aparecía tras contraer la misma. La fórmula era C(G) = C(G0 e) + C(G00 e) (3.6) Tutte se preguntó si existía otra fórmula recursiva similar a (3.6) para algún invariante de grafos bajo isomorsmo. Paralelamente, según Tutte, R. M. Foster había observado que el polinomio cromático de un grafo satisfacía tal fórmula recursiva pero con un menos en lugar de un más, como vimos en la Denición 3.2.11. Las funciones que cumplen (3.6) son denominadas W − funciones en [12]. Por otra parte, algunas funciones de grafos, denominadas V − funciones, son multiplicativas por componentes, es decir, el valor de la función para un grafo dado es producto de los valores de las funciones de sus componentes. Tutte consiguió jugando con las V,W − funciones para grafos no dirigidos un polinomio en dos variables del cual se podían obtener el polinomio cromático y otros polinomios interesantes anulando alguna de las variables y reajustando los signos. Este polinomio Tutte lo llamó polinomio dicromato (del inglés, dichromate polynomial ) pero más tarde, y en honor suyo, este polinomio pasó a ser llamado polinomio de Tutte a pesar de que H. Whitney había encontrado una expresión muy similar con coecientes análogos, como veremos en (3.8) y (3.9). El polinomio de Tutte puede ser calculado por distintos algoritmos. Sin embargo, el que se puede emplear de forma general y el que usaremos en la Sección 3.3.1 para calcularlo es el que en principio empleó Tutte, conocido ahora como algoritmo de eliminación − contracción de aristas y similar al de la Denición 3.2.11. CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 63 3.3.1. Algoritmo de eliminación − contracción de aristas El objetivo de esta sección es obtener el polinomio de Tutte de manera recursiva. Esta recursión la haremos usando el algoritmo de eliminación − contracción de aristas en el que, tras dichas operaciones progresivas, se llega a grafos formados únicamente por una arista. Esta arista puede ser del tipo e=uv , es decir, el grafo P2 ; o una arista e=uu , que denominamos lazo. Finalmente procederemos a la reconstrucción del polinomio a partir de los casos base. De aquí en adelante, si un grafo G está formado únicamente por una arista lazo o P2 , denotaremos su polinomio de Tutte por Te(x, y) . Denición 3.3.1 ( Polinomio de Tutte ) . El polinomio de Tutte de un grafo G= (V, E) no dirigido se dene de manera recursiva como sigue: 1. TG(x, y)=1 si G no tiene aristas. 2. Te=uv(x, y) = x . 3. Te=uu(x, y) = y . 4. TG(x, y) = TG−e(x, y) + TG/e(x, y) , siempre que e∈E no sea ni un puente ni un lazo. 5. Si G=G1∪G2 tiene un punto de corte v que es el único vértice común entre G1 y G2 , entonces TG(x, y) = TG1(x, y)·TG2(x, y) . Por lo tanto, en el caso en que e∈E sea un puente o un lazo aplicaremos este resultado y obtendremos que: a ) Si e es un lazo en G entonces TG(x, y) = y·TG−e(x, y) . b ) Si e es un puente en G entonces TG(x, y) = x·TG/e(x, y) . Usando el apartado 5 es fácil deducir que TPn(x, y) = xn−1 . Además, denotando por Ln al grafo formado por n lazos unidos entre sí por un vértice, se tiene que TLn(x, y) = yn . Tras la denición algorítmica es fácil observar que salvo encontrarnos en uno de los casos base, todos los pasos son recursivos y en el peor de los casos cada llamada recursiva generaría dos nuevas llamadas. Esto es lo que hace realmente difícil el cálculo manual de este polinomio para grafos con un gran número de aristas que no son ni lazos ni puentes, por ejemplo del tipo Kn . 64 3.3. POLINOMIO DE TUTTE En las siguientes proposiciones hallaremos el polinomio de Tutte de diversos tipos de grafos. Estas expresiones nos facilitarán en ocasiones el cálculo de dicho polinomio. Proposición 3.3.2. Sea Mn el multigrafo formado por 2 vértices y n aristas. Entonces TMn(x, y) = x+Pn−1 i=1 yi . Demostración. Para M2 usando el algoritmo se obtiene TM2(x, y) = Te=uv(x, y) + Te=uu(x, y) = x+y. Por inducción en n se tiene lo siguiente: TMn(x, y) = TMn−1(x, y) + TLn−1(x, y) = TMn−1(x, y) + yn−1= =TMn−2(x, y) + yn−2+yn−1=TM2(x, y) + y2+. . . +yn−1= =x+y+y2+. . . +yn−1=x+Pn−1 i=1 yi . Proposición 3.3.3. TCn=y+Pn−1 i=1 xi . Demostración. Para C3 usando el algoritmo se obtiene TC3(x, y) = TP3(x, y) + TM2(x, y) = x2+x+y. Por inducción en n se tiene que TCn(x, y) = TPn(x, y) + TCn−1(x, y) = xn−1+TCn−1(x, y) = =xn−1+xn−2+TCn−2(x, y) = xn−1+. . . +x3+TC3(x, y) = =xn−1+. . . +x3+x2+x+y=y+Pn−1 i=1 xi . En la Figura 3.15 puede verse la descomposición del grafo pez en los ciclos C3 y C4 a través de su punto de corte. Por lo tanto, haciendo uso del apartado 5 de la Denición 3.3.1 y de la Proposición 3.3.3, concluimos que el polinomio de Tutte del grafo pez es TG(x, y)=(x3+x2+x+y)(x2+x+y). En la Figura 3.16 se muestran las llamadas que generaría el algoritmo para el cálculo del polinomio de Tutte del grafo C4 . A la izquierda de cada nodo aparece el grafo obtenido tras la eliminación de la arista destacada y CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 65 3 2 x x x y+ + + 2 x x y + + Figura 3.15: Descomposición del grafo pez en dos ciclos. a la derecha del mismo el grafo resultante tras su contracción. Dejamos de ramicar un nodo cuando el grafo que aparezca en éste sea una arista del tipo lazo o P2 , o podamos obtener fácilmente aristas de este tipo descomponiendo el grafo por sus puntos de corte. 3 x 2 x y x Figura 3.16: Llamadas del algoritmo de eliminación − contracción sobre el grafo C4 . Llegados a este punto es fácil notar que el polinomio de Tutte del grafo toro de la Figura 3.8 es TG(x, y) = x2(x2+x+y). (3.7) 66 3.3. POLINOMIO DE TUTTE Esto se debe a que el grafo toro tiene dos puntos de corte que descomponen el grafo en dos grafos P2 y en un grafo C3 . Esa misma descomposición se tendría para el grafo de la Figura 3.17, por lo que tal grafo tendría el mismo polinomio de Tutte. Figura 3.17: Grafo con el mismo polimonio de Tutte que el grafo toro. De aquí deriva una interesante propiedad del polinomio de Tutte. Observación 3.3.4. El polinomio de Tutte es invariante por isomorsmo, es decir, grafos isomorfos están denidos por el mismo polinomio de Tutte; sin embargo, el recíproco no es cierto en general. 3.3.2. Deniciones alternativas Además de la denición recursiva dada anteriormente, en este epígrafe daremos dos deniciones alternativas y equivalentes de este polinomio: una en función de sus subgrafos maximales y otra en términos de sus árboles maximales. Para profundizar en ellas pueden verse [2, 11, 12]. Denición 3.3.5. Sea G= (V, E) un grafo no dirigido y E0⊆E . Si denotamos por c(E0) al número de componentes conexas del subgrafo que viene dado por (V, E0) , entonces el polinomio de Tutte de G se dene como TG(x, y) = X E0⊆E (x−1)c(E0)−c(E)(y−1)c(E0)+|E0|−|V|. (3.8) En lo que sigue, c(E0) simbolizará el número de componentes conexas del subgrafo maximal dado por (V, E0) . Como ejemplo, vamos a calcular el polinomio de Tutte del grafo K3 . En este grafo c(E) = 1 y |V|= 3 . Los valores de c(E0) y de |E0| dependerán del subgrafo dado por (V, E0) en cada caso. En el Cuadro 3.1 se muestran los sumandos originados en el polinomio de Tutte por los subgrafos maximales del grafo K3 , conforme a la denición anterior. CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 67 Subgrafos Maximales |E0|c(E0) Sumando Originado 0 3 (x−1)2 1 2 x−1 2 1 1 3 1 y−1 Cuadro 3.1: Obtención de los sumandos del polinomio de Tutte originados por cada uno de los subgrafos maximales del grafo K3 . De esa manera, sumando todos los sumandos originados, se obtiene que TK3(x, y)=(x−1)2+ 3(x−1) + 3 + (y−1) = x2+x+ 1. Por otra parte, de la Denición 3.3.5 es claro ver que se verica el apartado 5 de la Denición 3.3.1, es decir, todo grafo G que es unión disjunta de dos grafos G1 y G2 ( G=G1∪G2 ) verica que TG(x, y) = TG1(x, y)·TG2(x, y). En el siguiente resultado caracterizaremos el polinomio de Tutte del grafo dual de cualquier grafo plano. Proposición 3.3.6. Para todo grafo plano G se verica TG(x, y) = TG∗(y, x). Demostración. Basta usar el hecho de que si X⊆E , entonces se tiene que r∗(E) = |E| − r(E) y r∗(X) = |X| − r(E) + r(E−X) , donde r∗ denota la 68 3.3. POLINOMIO DE TUTTE función rango de G∗ . Entonces, TG∗(x, y) = X X⊆E (x−1)r∗(E)−r∗(X)(y−1)|X|−r∗(X)= =X X⊆E (x−1)|E|−r(E)−|X|+r(E)−r(E−X)(y−1)r(E)−r(E−X)= =X X⊆E (x−1)|E−X|−r(E−X)(y−1)r(E)−r(E−X)= =X X⊆E (y−1)r(E)−r(E−X)(x−1)c(E−X) Haciendo ahora el cambio Y=E−X , tenemos TG∗(x, y) = X Y⊆E (y−1)r(E)−r(Y)(x−1)c(Y)=TG(y, x). Consideremos de nuevo G el grafo toro y comprobemos que este resultado se verica. En la Figura 3.18 aparece la construcción de uno de los grafos duales de G . G G∗ Figura 3.18: Grafo toro y uno de sus grafos duales. Utilizando entonces el algoritmo de eliminación − contracción de aristas podemos deducir que su polinomio de Tutte asociado es TG∗(x, y) = y2(y2+y+x). Recordando que TG(x, y) = x2(x2+x+y) es el polinomio de Tutte asociado al grafo toro, puede corroborarse el resultado. A continuación daremos en el Teorema 3.3.10 otra presentación equivalente al polinomio de Tutte. Ésta denición, de hecho, fue la dada originalmente por Tutte en 1954 (véase [11]). En ella se usa la noción de actividad , que describiremos seguidamente. CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 69 Denición 3.3.7 ( Arista Interna y Externa ) . Sea T un árbol maximal de G= (V, E) . Una arista de E se dice interna si está en T . En otro caso la llamaremos externa . En la Figura 3.19 aparecen representados un grafo G , un árbol maximal suyo T y de nuevo el grafo G donde sus aristas han sido destacadas con trazo continuo si son aristas internas y con trazo discontinuo si son externas. G T Figura 3.19: Grafo G , árbol maximal suyo T y representación de sus aristas internas y externas. Ahora se denirán los conceptos de aristas externamente activas e internamente activas en grafos conexos. Primeramente será necesario jar una ordenación en las aristas de G , digamos e1, . . . , em . Denición 3.3.8 ( Arista Internamente Activa ) . Sea T un árbol maximal de G= (V, E) y sea ei una arista interna. Sean T1 y T2 las dos componentes de T−ei . Diremos entonces que ei es una arista internamente activa en T si para cada arista ej con i6=j que tenga un extremo en T1 y otro en T2 se verica j < i . Denición 3.3.9 ( Arista Externamente Activa ) . Sea T un árbol maximal de G= (V, E) y sea ei una arista externa de extremos a y b . Sea P el único arco desde a hasta b en T . Diremos que ei es una arista externamente activa en T si toda arista ej de P satisface j < i . Una vez visto estos conceptos sobre actividad de aristas en grafos podemos denir el polinomio de Tutte de la siguiente manera. Teorema 3.3.10. Sea G= (V, E) un grafo conexo. Dando un orden al conjunto de aristas E , el polinomio de Tutte de G es igual al TG(x, y) = X T⊆G xi(T)ye(T), 70 3.3. POLINOMIO DE TUTTE Árboles Maximales i(T)e(T) Sumando Originado e1 e2e3 #{e2, e3}= 2 0 x2 e1 e2e3 #{e3}= 1 0 x e1 e2e3 0 #{e3}= 1 y Cuadro 3.2: Obtención de los sumandos del polinomio de Tutte originados por cada uno de los árboles maximales del grafo K3 . donde la suma es considerada sobre todos los árboles maximales T de G e i(T) y e(T) representan el número de aristas internamente activas y externamente activas respectivamente de cada árbol maximal T . En [11] se demuestra que el polinomio de Tutte obtenido con este teorema es independiente de la ordenación jada en el conjunto de aristas. Usando este teorema vamos a calcular de nuevo el polinomio de Tutte del grafo K3 . En el Cuadro 3.2 aparecen los sumandos que los árboles maximales de K3 generan en el polinomio de Tutte. De esta manera es claro ver que TK3(x, y) = (x−1)2+ 3(x−1) + 3 + (y−1) = x2+x+ 1. Verdaderamente el polinomio de Tutte es interesante por las propiedades que contiene acerca del grafo al que hace referencia. En especial destacaremos el teorema que se da a continuación, que sigue directamente del Teorema 3.3.10, y está estrechamente relacionado con el Teorema 2.3.7 o de Kirchho. Teorema 3.3.11. TG(1,1) da el número de bosques maximales de G , es decir, el número de subconjuntos de aristas sin ciclos con el mismo número de componentes conexas que G . En el caso en el que G sea conexo, TG(1,1) coincide con el número de árboles máximales contenidos en él. CAPÍTULO 3. POLINOMIOS ASOCIADOS A GRAFOS 71 Observemos que este teorema es equivalente al Teorema 2.3.7. Con ellos tenemos dos alternativas para saber cuántos árboles maximales tiene un grafo cualquiera, o bien a través de los cofactores de su matriz laplaciana, o bien mediante una evaluación en su polinomio de Tutte. Como vimos en (3.7), el polinomio de Tutte del grafo toro es TG(x, y) = x2(x2+x+y). De ahí tenemos que TG(1,1) = 3 . Esto signica que este grafo tiene tres árboles maximales, los mostrados en la Figura 3.20. Figura 3.20: Árboles maximales del grafo toro. Otras propiedades interesantes que derivan de este polinomio son las que aparecen en la siguiente proposición. Proposición 3.3.12. 1. TG(2,1) da el número de bosques de G . 2. TG(1,2) da el número de subgrafos maximales contenidos de G . 3. TG(2,0) da el número de orientaciones acíclicas de G . 4. TG(2,2) = 2|E| . Corroboraremos esta proposición para el caso en que G es el grafo toro. Para ese caso, el número de bosques es TG(2,1) = 28 . Éstos aparecen representados en la Figura 3.21. Por otra parte, considerando los árboles maximales del grafo toro de la Figura 3.20 junto al propio grafo G , tendremos los TG(1,2) = 4 subgrafos maximales de G . En cuanto a las orientaciones acíclicas, G tiene TG(2,0) = 24 . Un ciclo Cn tiene 2n−2 orientaciones acíclicas. Esto se debe a que a cada arista podemos darle dos orientaciones distintas y, por lo tanto, el ciclo 78 BIBLIOGRAFÍA [14] W. T. Tutte, Graph Theory. As I have known it , Oxford Science Publications, 2012.