Teoría de grafos na investigación de operacións

Traballo Fin de Grao Teoría de grafos na investigación de operacións Yolanda Cobas Cornide 2020/2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Teoría de grafos na investigación de operacións Yolanda Cobas Cornide Xullo 2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Traballo proposto Área de Coñecemento: Estadística e investigación operativa Título: Teoría de grafos na investigación de operacións Breve descrición do contido Neste traballo estudarase a teoría de grafos que se utiliza en investigación de operacións analizando diversas técnicas e modelos diferentes aos xa estudados noutras materias da titulación. Recomendacións Outras observacións iii Índice general Resumo viii Introdución xi 1. Grafos: introducción 1 1.1. Grafos....................................... 1 1.2. Subgrafos ..................................... 6 1.3. Representación matricial de grafos . . . . . . . . . . . . . . . . . . . . . . . 7 1.4. Grao........................................ 9 2. Tipos de grafos 11 2.1. Definicións e resultados esenciais . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2. Radio, diámetro e excentricidade . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3. Parámetros asociados aos vértices e ás aristas . . . . . . . . . . . . . . . . . 18 2.4. Árbores ...................................... 19 3. Ciclos eulerianos y circuítos hamiltonianos 23 3.1. Cicloseulerianos ................................. 23 3.2. Circuitos hamiltonianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4. Grafos dirixidos 31 4.1. Definición e conceptos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2. Matrices de incidencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5. Grafos planos 37 5.1. Introducción.................................... 37 5.2. FórmuladeEuler................................. 38 5.3. Mapas....................................... 40 v vi ÍNDICE GENERAL 6. Coloreando grafos 43 6.1. Introducción.................................... 43 6.2. Polinomiocromático ............................... 46 6.3. TeoremadeBrooks................................ 49 7. Un exemplo con R 51 Bibliografía 57 2CAPÍTULO 1. GRAFOS: INTRODUCCIÓN v1 v2 v3 Figura 1.1: Grafo con conxunto de vértices V={v1,v2,v3} e conxunto de aristas E={{v1,v2},{v1,v3},{v2,v3}} Un tipo de grafo interesante no ámbito de investigación de operacións é o grafo aleatorio. Este consiste nun grafo cun conxunto finito de vértices no que as aristas que aparecen unen pares destos vértices de forma aleatoria. Podemos atopalos en grafos que representen, por exemplo, as vínculos nunha red social. É dicir, os vértices serían as persoas que son membros desa red social, e unha arista une dous vértices se esas duas persoas están relacionadas dalgunha forma. A importancia destes grafos aleatorios ven dada pola posibilidade de que estos vínculos varíen ao longo do tempo. Neste traballo centraremonos nos grafos que non son aleatorios. En función de como sexan as aristas dun grafo, é dicir, dos elementos de E, podemos distinguir tres tipos de grafos: Grafos dirixidos: son aqueles nos que E⊂V×V, é dicir, cada arista é un par ordeado de vértices, a arista (vi, vj)comeza no vértice vie remata no vértice vj. vi vj Aos grafos dirixidos dedicaremoslle un capítulo posteriormente no que se introducirán algunhas definicións e se extenderán outras que trataremos antes para grafos non dirixidos. Grafos non dirixidos: son aqueles nos que as aristas non son pares ordeados, é dicir, a arista (vi,vj) e a arista (vj,vi) son a mesma, e a representaremos por {vi, vj}. 1.1. GRAFOS 3 vi vj Grafos mixtos: son aqueles nos que algunhas aristas son pares ordeados de vértices e otras non. vi vj A partir de agora imos a referirnos simplemente a grafos dirixidos e non dirixidos. A continuación introdúcense algúns grafos non dirixidos con características de certo interese. Moitas de estas definicións poden extenderse tamén para grafos dirixidos, pero trataremos esos casos no capítulo posterior dedicado aos mesmos: En primeiro lugar, temos un grafo que contén todas as aristas posibles. Grafo completo (Kn): é un grafo con nvértices no que cada par de estos vértices é adxacente, é dicir, todas as aristas posibles están presentes. 1 2 3 45 6 O número máximo de aristas que pode haber nun grafo con nvértices é, no caso dun grafo non dirixido, n(n−1) 2, que son todas as posibles combinacións de elementos de {1, . . . , n}tomados de dous en dous. Deseguido, un grafo no que o conxunto de vértices está separado en dous subconxuntos e non existen aristas entre eles. 4CAPÍTULO 1. GRAFOS: INTRODUCCIÓN Grafo bipartito: é un grafo G= (V, E)onde o conxunto de vértices pódese separar en dous subconxuntos disxuntos, V=V1∪V2e ademais non pode ocorrer que exista unha arista e={vi, vj}con vi, vj∈V1nin unha arista e={wi, wj}con wi, wj∈V2, é dicir, non poden existir aristas que teñan ambos vértices en V1ou ambos en V2. v1 v2 v3 v4 w1 w2 w3 w4 Figura 1.2: Un grafo bipartito onde o conxunto de vértices Vsepárase en subconxuntos V1 en cor azul e V2en cor verde. Na seguinte definición mestúranse os dous anteriores, é dicir, o conxunto de vértices divídese en dous e están presentes todas as aristas posibles entre eles. Grafo bipartito completo: é un grafo bipartito no que todos os vértices de V1son adxacentes a todos os vértices de V2. v1 v2 v3 v4 w1 w2 w3 Figura 1.3: Un grafo bipartito completo onde o conxunto de vértices Vsepárase en subconxuntos V1en cor azul e V2en cor verde e están presentes todas as aristas posibles entre os vértices de V1eV2. A continuación presentamos un grafo que pode representarse nun plano sen que existan cruces entre as aristas. É utilizado habitualmente na teoría de grafos e dedicaráselle un capítulo máis adiante. 1.1. GRAFOS 5 Grafo plano é aquel que pode debuxarse nun plano sen que as súas aristas se corten. 1 2 3 45 6 4 3 5 2 1 6 Figura 1.4: Os dous diagramas representan o mesmo grafo. No tipo de grafo que se introduce a continuación vemos que entre dous vértices pode existir máis dunha arista. Multigrafo: é aquel no que cada par de vértices vi,vjpode estar conectado por máis dunha arista. vi vj A partir do grafo anterior, mediante a sustitución das aristas múltiples, constrúese o seguinte tipo de grafo. Grafo subxacente dun multigrafo: é o grafo que resulta ao reemplazar todas as aristas múltiples entre os nodos vievjpor unha única arista. vi vj 6CAPÍTULO 1. GRAFOS: INTRODUCCIÓN Por último, un tipo de grafo que se constrúe a partir doutro dado, cos mesmos vértices pero modificando as aristas que están presentes nel. Grafo complementario G: grafo que ten o mesmo conxunto de vértices que Gpero onde estes son adxacentes se e só se non o son en G. Figura 1.5: A esquerda un grafo G, e a dereita o seu grafo complementario, G 1.2. Subgrafos Nesta sección introdúcese un tipo de grafos que se constrúe a partir doutro, onde os vértices e as aristas son subconxuntos do grafo dado. Dado un grafo G= (V, E), un subgrafo G0de Gé un grafo cuxo conxunto de vértices V0é un subconxunto dos de G,V0⊂Ve cuxo conxunto de aristas E0é un subconxunto das de G,E0⊂E. Trivialmente Gé un subgrafo de él mesmo. Un subgrafo G0de Gdise propio se G0é distinto de G Exemplo 1.1. v1v2 v5 v7 v6 v3v4 v2 v1 v3 v7 v5 v4 Figura 1.6: Un grafo Ge un subgrafo G0de G Dentro dos subgrafos, cabe destacar dous tipos, onde os conxuntos de vértices e aristas teñen que verificar unhas condicións dadas. Dado G= (V, E)un grafo, se V0é un subconxunto de vértices de G, un subgrafo inducido por V0é o grafo formado por V0e polas aristas de Gque unan dous vértices de V0, e denótase G[V0]ou hV0i. Así mesmo, un subgrafo de expansión é un subgrafo G0= (V0, E0)de Gverificando V0=Ve as aristas 1.3. REPRESENTACIÓN MATRICIAL DE GRAFOS 7 de E0son aristas de Gque unen vértices de G0. Moitas propiedades dos grafos son herdadas dos subgrafos, é dicir, un grafo ten dita propiedade se todos os seus subgrafos inducidos a teñen. Algúns exemplos de estas propiedades son: ser planos, ser completos, ser bipartitos, . . . Exemplo 1.2. Sexa Go grafo do exemplo 1.1, vemos a continuación un exemplo de subgrafo inducido por V0={v1, v2, v3, v4, v5, v7}e un exemplo de subgrafo de expansión, nesa orde: v1v2 v5 v7 v6 v3v4 v2 v1 v3 v7 v5 v4 v1v2 v5 v7 v6 v3v4 1.3. Representación matricial de grafos Para a resolución de moitos problemas da investigación de operacións, vai ser de gran utilidade a representación matricial de grafos, que aporta información sobre estes de forma clara e resumida. Dado G= (V, E)un grafo, que pode ser dirixido ou non dirixido, con conxunto de vértices V={v1, v2,. . .,vn} e con conxunto de aristas E={e1, e2,. . .,em}, podemos representar este grafo pola matriz de adxacencia Ade orde n×ne con entradas aij: aij =(1se (i, j)é unha arista en G 0noutro caso. Esta matriz pode recibir tamén o nome de matriz "vértice-vértice". Se o grafo Gé dirixido, tamén pódese representar de forma matricial coa matriz de incidencia Bque é unha matriz de orde n×mdefinida como: bik =       1se ié o vértice final da arista ek −1se ié o vértice inicial da arista ek 0noutro caso. Esta matriz pode recibir tamén o nome de matriz "vértice-arista". Exemplo 1.3. Neste exemplo imos representar dous grafos, un dirixido e outro non dirixido, e a resumir o contido do primeiro destes nas matrices de adxacencia e incidencia e 8CAPÍTULO 1. GRAFOS: INTRODUCCIÓN do segundo na matriz de adxacencia. Sexa en primeiro lugar o grafo dirixido G: 1 2 3 45 6 Un grafo dirixido G Representamos a información desta matriz coa matriz de adxacencia coa matriz de incidencia AG=            010010 000100 010100 010000 000101 100100            BG=            −100001−1 0 0 0 11000000−1 1 0−1−10000100 001100001−1 000−1−101000 00001−1 0 −1 0 0            Sexa agora o grafo non dirixido G0: 1 2 3 45 6 Un grafo non dirixido G0 Por ser non dirixido só podemos representar a súa información coa matriz de adxacencia: 1.4. GRAO 9 AG0=            010011 101100 010110 011010 100101 100100            1.4. Grao Unha forma útil e sinxela de dar certa información sobre un grafo pode ser, facer referencia ao número de aristas que inciden en cada vértice, vendo así se é o mesmo para todos os vérties ou non, para iso introdúcese o concepto de grao. Nun grafo G, sexa dirixido ou non, definimos o grao dun vértice v,d(v), como o número de aristas que inciden nel. Utilizamos a notación δ(G)para referirnos ao menor dos grao de todos os vértices de Ge∆(G)para referirnos ao maior dos graos de todos os vértices de G. Exemplo 1.4. Nestes dous grafos, un dirixido e outro non, o grao dos vértices v1ew1é 2, de v2ew2é 1 e de v3ew3é 3. Neste caso, δ= 1 e∆=3. v1 v2 v3w1 w2 w3 Figura 1.7: Un grafo dirixido con V={v1, v2, v3}e un grafo non dirixido con V= {w1, w2, w3}. Cando todos os vértices dun grafo teñen o mesmo grao, dise que o grafo é regular. Teorema 1.5. En calquera grafo ou multigrafo G= (V, E), a suma dos graos dos vértices é igual ao doble do número de aristas. Pd(v) = 2|E| Demostración. Imos usar a matriz de incidencia e a suma das súas entradas. A suma das entradas da fila ié o grao do vértice vi,d(vi), polo tanto Pd(v)é igual ao número de entradas da matriz de incidencia. A suma das entradas da columna ké 2, xa que cada 10 CAPÍTULO 1. GRAFOS: INTRODUCCIÓN arista é incidente en dous vértices, en consecuencia, o número de entradas da matriz de incidencia é dúas veces o número de aristas, 2|E|. [2] Exemplo 1.6. A continuación exemplificamos o teorema anterior: Claramente os graos dos vértices do grafo non dirixido G= (V, E)son: d(v1)=3,d(v2)=2,d(v3)=3,d(v4)=2, polo tanto P4 i=1 d(vi) = 10. Ademais o número de aristas, |E|, é 5. Polo tanto, verifícase o resultado: P4 i=1 d(vi) = 10 = 2 ∗5 v1v2 v3v4 Grafo G= (V, E) Corolario 1.7. Nun grafo, o número de vértices de grao impar é par. Demostración. Usando o Teorema 1.5, Pd(v) = 2|E|. Como a parte dereita é par, ao ser unha igualdade, a parte esquerda tamén debe selo e entón a suma dos graos de todos os vértices debe ser par, polo tanto se hai vértices de grao impar, ten que haber unha cantidade par deles. [1] Exemplo 1.8. Utilizando o exemplo anterior, vemos que só hai dous vértices con grao impar son v1ev3de modo que hai un número par deles. v1v2 v3v4 Capítulo 2 Tipos de grafos Neste capítulo preséntanse os conceptos de cadeas, camiños, ciclos e circuítos, que na aplicación da teoría de grafos a problemas da vida cotidiana, son de gran importancia. Ademais introducimos algúns paramétros relacionados con estas definicións que permiten resumir a información que estes aportan a un grafo. Por último, preséntase o concepto de pesos, que é de vital necesidade cando se estudian problemas de análise de redes dos que veremos algún exemplo no vindeiro capítulo. 2.1. Definicións e resultados esenciais Nesta primeira sección introducimos as definicións de cadeas, camiños, ciclos e circuítos así como algúns resultados sobre os mesmos aplícados a grafos non dirixidos, o caso de grafos dirixidos tratarase noutro capítulo. Dado G= (V, E)un grafo non dirixido, tomamos unha secuencia de aristas distintas de G, (e1, e2, . . . , er), se existen vértices (v0, v1, . . . , vr)de modo que, para k∈ {1,2, . . . , r}, ek= (vk−1, vk), entón dicimos que a secuencia é unha cadea. Se temos unha cadea que verifica v0=vr, entón recibe o nome de ciclo ou cadea pechada. Unha cadea na que todos os vértices son distintos é un camiño. E ademais, unha cadea na que todos os vértices son distintos a excepción do primeiro e do último, v0=vr, é un circuito ou camiño pechado. En calquera das definicións anteriores, chámase lonxitude ao número de aristas que contén, l.1 Exemplo 2.1. Dado un grafo G= (V, E), exemplificamos as definicións anteriores: 1Cando estemos a falar do problema do camiño máis corto esta non será a definición de lonxitude que se usará. 11 18 CAPÍTULO 2. TIPOS DE GRAFOS curto contido en Ge, do mesmo xeito, a circunferencia dun grafo G,c(G), é a lonxitude do ciclo máis largo contido en G. Claramente, se estamos a falar de grafos acíclicos estos dous últimos conceptos non están definidos. Exemplo 2.14. No grafo do exemplo anterior, cúmplese que g(G) = c(G)=3. Ademais, C(G) = {v∈Vtal que ε(v) = R= 2}={v3, v4} Teorema 2.15. Dado Gun grafo que conteña ciclos. Tense: g(G)≤2D(G)+1. Demostración. Supoñamos g(G)≥2D(G)+2. Consideremos o circuíto Cde lonxitude g(G)3n G: C= (v1, v2, . . . , vg(G), v1). Supoñamos que P= (v1, w2, w3, . . . , wt, vD(G)+2)é o camiño máis curto dende v1aVD(G)+2. Pola definición de diámetro, Pdebe conter menos de D(G) + 1 aristas. Se Pnon contén ningún dos vértices vD(G)+3, vD(G)+4, . . . , vg(G), o circuíto: v1, w2, w3, . . . , wt, vD(G)+2, vD(G)+3, vD(G)+4, . . . , vg(D), v1 ten lonxitude menor que g(G). Doutro xeito, supoñamos que vké o vértice de menor índice de Cque pertence a P. De novo, v1, w2, w3, . . . , vk, vk+1, vk+2, . . . , vg(D), v1 é un circuíto con lonxitude menor que g(G). En calquera caso, chegamos a unha contradicción coa definición de g(G). [2] 2.3. Parámetros asociados aos vértices e ás aristas En moitas aplicacións dos grafos vai ser necesario definir unha función positiva chamada peso,w(vi, vj), asociada a cada arista (vi, vj)ou a cada vértice vi. Por exemplo, nos problemas de fluxo en redes, estos parámetros poden representar o “custo”ou “beneficio” asociado ao paso do fluxo por ese vértice ou arista. Defínese o peso dunha cadea, ciclo, camiño ou circuíto como a suma dos pesos das aristas que os forman. Definición 2.16. Dados dous vértices conectados vievjcon i6=jdun grafo G, chámase distancia ponderada de viavj,W(vi, vj), ao mínimo dos pesos de todas as cadeas que os unen. Este concepto está intimamente relacionado cun problema típico de investigación de operacións, o Problema do Camiño máis Curto, que presentamos máis adiante. Exemplo 2.17. Sexa Gun grafo con representación gráfica a que vemos a continuación. G ten como conxunto de vértices V={v1, v2, v3, v4, v5, v6}e cada arista ten un peso asociado. 2.4. ÁRBORES 19 v1v2v3 v4v5v6 5 3 2 4 4 3 5 2 6 Neste exemplo, podemos ver que os pesos entre cada unha das aristas son: w(v1, v2)=5, w(v1, v4)=4,w(v1, v5)=2,w(v2, v3)=2,w(v2, v5)=3,w(v2, v6)=6,w(v3, v6)=5, w(v4, v5)=3ew(v5, v6) = 4. Exemplificamos agora a distancia ponderada entre os vértices v1ev6, as posibles cadeas entre eles e os seus correspondentes pesos son: (v1, v2, v3, v6) con peso 12,(v1, v2, v6)con peso 11,(v1, v2, v5, v6)con peso 12,(v1, v5, v6)con peso 6,(v1, v5, v2, v6)con peso 11,(v1, v5, , v2v3, v6)con peso 12,(v1, v4, v5, v6)con peso 11, (v1, v4, v5, v2, v3v6)con peso 17,(v1, v4, v5, v2, v6)con peso 16. Polo tanto, a distancia ponderada, W(v1, v6), é 6. OProblema do Camiño máis Curto é un dos problemas máis coñecidos e estudados da teoría de grafos e consiste, como o propio nome indica, en atopar o camiño máis curto que una dous vértices dun grafo. Neste problema, cando nos referimos a camiño máis curto entendemos que a suma dos pesos das aristas que participan no camiño debe ser a mínima posible. 2.4. Árbores Dentro dos grafos non dirixidos, hai un tipo deles, as árbores, que son de gran utilidade no ámbito da investigación de operacións. Dado un grafo non dirixido G, dicimos que este grafo é unha árbore se é conexo e non contén ciclos. De acordo co teorema 2.6 unha árbore ten necesariamente n−1aristas. Nunha árbore, chamamos follas aos vértices que teñen grao 1e denominamos bosque a un grafo no cal as súas compoñentes conexas son árbores. Exemplo 2.18. Representamos gráficamente un bosque con duas árbores. A árbore 1ten como follas os vértices v1, v3, v5, v7e a árbore 2ten como follas os vértices v8, v11, v12. 20 CAPÍTULO 2. TIPOS DE GRAFOS v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 Definición 2.19. Unha árbore de expansión dun grafo Gé unha árbore que é subgrafo de expansión de ese grafo G. Ademais, un bosque maximal é un grafo no que cada compoñente conexa é unha árbore de expansión. Un problema clásico da investigación de operacións é o Problema da árbore de expansión mínima. Consiste en atopar unha árbore de expansión de modo que a suma dos pesos asociados as aristas que participan nel, sexa mínima. Definición 2.20. Unha estrela é unha árbore cun vértice adxacente a todos os demais. Nos grafos representados a continuación, debúxanse en vermello os vértices que son estrelas. Proposición 2.21. Dado un grafo G= (V, E)non dirixido, as siguientes propiedades son equivalentes: a) Gé unha árbore. b) Gé conexo e ten n−1aristas. c) Gé acíclico e ten n−1aristas. d) Gnon ten ciclos e, se engadimos unha arista calquera, formarase un ciclo (e só un). e) Gé conexo e, se eliminamos unha arista calquera, deixa de ser conexo. 2.4. ÁRBORES 21 f) Cada par de nodos de Gestán unidos por un único camiño. Demostración. (a)⇒(b)Por definición de árbore, Gé conexo e non ten ciclos e polo teorema 2.6 ten entón n−1aristas. (a)⇒(c)Igual que antes, por definición de árbore, Gé conexo e non ten ciclos e polo teorema 2.6 ten entón n−1aristas. (a)⇒(d)Sexan vi, vjdous vértices de G, se engadimos a arista e={vi, vj}que os une poden pasar duas cousas: que os vértices foran adxacentes e entón ao engadir a arista formase un ciclo de lonxitude 2 ou que os vértices non foran adxacentes, e entón hai un único camiño que os une, así ao engadir esta nova arista o camiño pechase formando un ciclo. (a)⇒(e)Sea e={vi, vj}a arista de Gque eliminamos. Supoñamos que o grafo G\{e} é conexo, entón podemos atopar nel unha cadea que una vievje, ao engadir a arista ede novo ao grafo, formariase un ciclo en Ge chegamos así a unha contradicción con que Gé unha árbore. (a)⇒(f)Como Gé unha árbore, é necesariamente conexo e polo tanto hai ao menos un camiño que une cada par de vértices. Supoñamos que hai máis dun camiño e cheguemos a unha contradicción. Se existen dous camiños distintos que unen dous vértices, e os concadeamos o resultado é un ciclo pero por ser Gunha árbore non pode ter ciclos, polo tanto chegamos a unha contradicción con que en Ghai vértices unidos por máis dun camiño. (f)⇒(a)Supoñamos que cada par de vértices están conectados por un único camiño e vexamos que Gé unha árbore. Veríficase que Gé conexo porque cada par de vértices están unidos por unha cadea e, ademais, é acíclico xa que se existise un ciclo existirían dous vértices unidos por máis dun camiño. [8] Corolario 2.22 (Teorema ou Fórmula de Cayley).O número de bosques con nvértices e s,1≤s≤n, compoñentes conexas ven dado por: F(n, s) = snn−s−1.(2.2) En particular, o número de árbores en nvértices é: F(n, 1) = nn−2.(2.3) Demostración. A demostración da ecuación 2.2 baséase na seguinte fórmula de recurrencia: F(n, s) = n−s X d=0 n−s dF(n−1, s +d−1) (2.4) con n≥1e1≤s≤n, onde F(1,1) = 1 eF(n, 0) = 0 para n≥1. Para probar a ecuación 2.4 consideramos un bosque con nvértices, {v1, v2, . . . , vn}, e s 22 CAPÍTULO 2. TIPOS DE GRAFOS compoñentes conexas e onde os vértices {v1, v2, . . . , vs}pertencen a compoñentes conexas distintas. Neste bosque o vértice v1debe ser de grao d= 0, . . . , n−s, é dicir, v1debe ser adxacente a dvértices en {vs+1, . . . , vn}. Chamemos a esos dvértices “secundarios". Podemos escoller dvértices secundarios entre os n−svértices de n−s dmaneiras. Eliminamos agora o vértice v1e as daristas incidentes nel. O grafo resultante é un bosque con conxunto de vértices {v2, . . . , vn},s+d−1compoñentes conexas e dvértices secundarios que pertencen todos a compoñentes conexas distintas. O número de esos bosques é F(n−1, s +d−1). Se engadimos n−s dF(n−1, s +d−1) para todos os posibles valores de d, obtemos F(n, s)e queda probada a ecuación 2.4. Por inducción a partir da ecuación 2.4 probamos a ecuación 2.2. Se n= 1 entón 2.2 verifícase trivialmente. Supoñamos agora que F(n, s) = i(n−1)n−i−2 para 1≤i≤n−1en > 1. Entón, por 2.4, F(n, s) = n−s X d=0 n−s d(s+d−1)(n−1)n−s−d−1=snn−s−1(2.5) para 1≤s≤nen > 1. Na ecuación 2.5 podemos escribir dn−s d= (n−s)n−s−1 d−1para d≥1e aplicando o teorema binomial queda probado 2.2. Capítulo 3 Ciclos eulerianos y circuítos hamiltonianos Neste capítulo falaremos de dous tipos de cadeas determinados, os ciclos eulerianos e os circuítos hamiltonianos. Ambos foron creados pola necesidade de resolver problemas da vida cotiá, como atravesar un número determinado de pontes ou viaxar entre unhas determinadas cidades, e constitúen hoxe en día unha ferramenta fundamental para resolver problemas da investigación de operacións. 3.1. Ciclos eulerianos A ciudade de Königsberg, chamada actualmente Kaliningrado, na antigua Prusia, estaba atravesada polo río Pregolya, que dividía dita cidade en catro partes. Para comunicar todas as partes da cidade construíronse sete pontes e moitos preguntáronse se era posible, partindo dunha das partes da cidade, percorrer todas as pontes unha única vez e chegar de novo ao punto de partida. Figura 3.1: Esbozo do mapa de la ciudad de Königsberg 23 24 CAPÍTULO 3. CICLOS EULERIANOS Y CIRCUÍTOS HAMILTONIANOS Os primeiros escritos sobre teoría de grafos foron publicados por Euler en 1736 e trataban precisamente desta cuestión, do Problema das Pontes de Königsberg. Cunha primeira ollada xa parece imposible atravesar todas as pontes da forma mencionada antes. Por exemplo, supoñamos que comezamos na parte Bda cidade que ten tres pontes, se usamos unha delas para entrar e a outra para sair de B, quédanos unha ponte sen usar: se a usamos para entrar nesta parte, xa non podemos sair a non ser que crucemos algunha ponte duas veces, polo tanto, deberíamos acabar na parte Be se usamos esta terceira ponte para sair de B, esta debería ser necesariamente a parte na que comezamos. Este razoamento pódese aplicar ao resto de partes, A, C eD, xa que todas teñen un número impar de pontes, pero é imposible que todas as partes sexan a inicial ou a final. Resumimos agora graficamente a información do mapa das pontes de Könisberg, onde os vértices A, B, C eDcorrespóndense con cada unha das partes da cidade e as aristas representan as pontes que as unen. En consecuencia, pódese traducir a pregunta: somos capaces de, partindo dunha das partes da cidade, percorrer todas as pontes unha única vez e volver á parte inicial? en: podemos encontrar unha secuencia de aristas que pase por todas as aristas do multigrafo unha única vez e empece e remate no mesmo vértice? Un multigrafo que verifica esta condición recibe o nome de multigrafo euleriano. C A B D Dado un grafo Gnon dirixido, unha cadea euleriana neste grafo é unha cadea que contén todas as aristas de Gexactamente unha vez. Se esta cadea é pechada, é dicir, o primeiro e o último vértice coinciden, entón chámase ciclo euleriano. Un grafo euleriano é aquel que contén un ciclo euleriano. 1 Exemplo 3.1. Sexa G= (V, E)o grafo dado a continuación, vexamos que é un grafo euleriano, xa que podemos atopar nel un ciclo euleriano, por exemplo, con vértice inicial e final v1. O ciclo euleriano sería: {v1, v4, v7, v5, v3, v6, v9, v8, v6, v5, v8, v4, v2, v1} 1A definición de grafo euleriano pode extenderse ao caso dun multigrafo. 3.1. CICLOS EULERIANOS 25 v1v2v3 v4v5v6 v7v8v9 Lema 3.2. Sexa Gun grafo no que cada vértice é de grao par, entón este pode ser separado en ciclos onde ningún ciclo ten una arista en común con ningún outro. Demostración. Dado un grafo G= (V, E)supoñamos que todos os vértices teñen grao par. Podemos formar un ciclo empezando nun vértice e percorrendo todos os vértices do grafo (como todos os vértices teñen grao par, se usamos unha arista para “entrar”nun vértice, sempre temos outra para “sair”). Como Gé un grafo finito nalgún momento regresamos ao vértice inicial. Podemos denotar ese ciclo como C1. Se eliminamos agora o ciclo C1do grafo (é dicir, eliminamos de Gtodas as aristas que participan no ciclo) obtemos un subgrafo G0.G0pode ser ou non conexo. Cada vértice de G0segue tendo grao par, xa que por cada vez que participou no ciclo eliminamos duas aristas de G. Así un ciclo C2pode obterse do mesmo xeito que o anterior e o proceso repítese ata que non quedan máis aristas. Teorema 3.3 (Teorema de Euler).Un grafo conexo G= (V, E)é euleriano se e só se todos os seus vértices teñen grao par. Demostración. Dado un grafo conexo G= (V, E), para cada m≥0, establecemos como S(m)a afirmación: Gten maristas e todas eles teñen grao par, entón Gé euleriano. Para probar este resultado procedemos por inducción en S(m). Se m= 0,S(m)non ten aristas. Dado que Gé conexo, a única forma de que un grafo conexo non teña aristas, é que só teña un vértice, que denotaremos por v1. Como d(v1)=0, que é par, Gé euleriano. Dado k≥1, supoñamos que se verifican S(1), S(2), . . . , S(k−1), queremos entón probar S(k). Sexa Gun grafo conexo con karistas e con todos os vértices de grafo par . Como G é conexo non ten vértices aislados, polo tanto, δ(G)≥1e como o grao dos vértices ten que ser de grao par, δ(G)≥2e polo visto no Lema 2.9, Gcontén un ciclo, e o denominamos C. Construimos agora un subgrafo G0de Geliminando o ciclo C.G0pode ser ou non conexo. Podemos dicir que G0é a unión das compoñentes conexas G0 1, G0 2, . . . , G0 t. O grao de cada Hicon i= 1 . . . t ten que ser par xa que os graos só poden ser ou 0ou 2. 26 CAPÍTULO 3. CICLOS EULERIANOS Y CIRCUÍTOS HAMILTONIANOS Aplicando a hipótese de inducción a cada Hitemos que S(m1), . . . , S(mt), sendo mio número de aristas de Hi, e cada Hivai ter un ciclo euleriano, que imos chamar Ci. Estamos en situación de crear un ciclo euleriano en Gunindo o ciclo Ce os ciclos Ci. Comezamos en calquer vértice de Cie atravesamos este ciclo ata chegar a algún Hi. Agora atravesamos Cie continuamos por Cata chegar ao seguinte Hi. Entón, séguese que Gé euleriano e queda completado así o prodeso de inducción de xeito que se verifica S(m)para m > 0. Un exemplo típico relacionado cos ciclos eulerianos é o Problema do Carteiro Chino (CPP). Este problema foi plantexado polo matemático chino Kwan Mei-Ko en 1960 nun artigo publicado nun diario chino e representa o traballo dun carteiro que ten que repartir a correspondencia pasando ao menos unha vez por cada rúa e volver ao oficina de correos intentando percorrer a menor distancia posible. Se representamos unha cidade cun grafo Gno que cada arista é unha das rúas da cidade e ten un peso asociado que representa a distancia de dita rúa, este problema consiste en atopar a cadea pechada máis curta de forma que pase ao menos unha vez por cada arista do grafo, é dicir, consiste en atopar o ciclo euleriano con menor peso. Este problema pode formularse sobre grafos dirixidos, non dirixidos e tamén sobre grafos mixtos. 3.2. Circuitos hamiltonianos En 1857 o matemático irlandés sir William Rowan Hamilton propuso un problema que consistía en viaxar a 20 cidades do mundo, situadas como os vértices dun dodecaedro regular, seguindo as aristas deste. Este problema recibe o nome de Xogo do Icosaedro. Sexa Go grafo que representa un dodecaedro regular con conxunto de vértices Vrepresentando as cidades, |V|= 20. Este xogo consiste en, empezando nun vértice, atopar unha secuencia de aristas que pase por todos os vértices do grafo ao menos unha vez e regrese logo ao vértice inicial. Un grafo no que se pode atopar unha secuencia desa clase chámase grafo hamiltoniano. Dado un grafo G, un camiño hamiltoniano é un camiño que contén todos os vértices de Gao menos unha vez. Se este camiño hamiltoniano verifica que o primeiro e o último vértice coinciden, entón recibe o nome de circuíto hamiltoniano. Un grafo que contén un circuíto hamiltoniano é un grafo hamiltoniano. 3.2. CIRCUITOS HAMILTONIANOS 27 Figura 3.2: Un grafo Gque representa un dodecaedro regular e ten sinalado en cor vermella un circuíto hamiltoniano . Definición 3.4. Dado un grafo Gcon nvértices, constrúese a clausura de G,[G], do seguinte xeito: se Gcontén dous vértices non adxacentes vievjverificando d(vi)+d(vj)≥n engadimos ao grafo a arista {vi, vj}e repetimos este proceso ata que calesquera dous vértices non adxacentes verifiquen d(vi) + d(vj)< n. O grafo resultante é a clausura de G. Exemplo 3.5. Vexamos como construir a clausura do grafo Gcon representación gráfica: v1v3 v2v4 v5 En primeiro lugar os graos dos vértices de Gson: d(v1)=2,d(v2)=2,d(v3)=3, d(v4) = 3,d(v5) = 2. Construimos agora a clausura: empezamos vendo canto suman os graos de v1e dos vértices que non son adxacentes a él: d(v1) + d(v4) = 5 ≥n= 5 e d(v1)+d(v5)=4n. Polo tanto, debemos engadir unha arista que una v1ev4. Facemos o mesmo para v2:d(v2)+d(v3) = 5 = ned(v2)+d(v5) = 4 n. Polo tanto debemos engadir unha arista que una v2ev3. Así, xa temos a suma dos graos dos vértices non adxacentes en G. No seguinte debuxo representamos as duas aristas que acabamos de engadir en cor azul. 34 CAPÍTULO 4. GRAFOS DIRIXIDOS un grafo dirixido cuxo conxunto de vértices V0é un subconxunto dos de Ge o conxunto de aristas E0son aristas de Gque unen vértices de G0. Un subgrafo de expansión G0= (V0, E0)dun grafo dirixido Gé un subgrafo que verifica V0=Ve as aritas son aristas de Gque unen vértices de G0. Definición 4.1. Sexa (e1, e2, . . . , er)una secuencia de aristas distintas en G. Se existen vértices (v0, v1, . . . , vr)tales que: al= (vl−1, vl)para l= 1,2, . . . , r dicimos que a secuencia é unha cadena. Se ademais todos os vértices son distintos, entón é un camiño. Se v0=vrentón é unha cadena pechada ou ciclo. Un camiño pechado é un circuito. Ademais, dada a secuencia de vértices correspondente (v0, v1, . . . , vn)pode pasar que (vi−1, vi)ou (vi, vi−1)con i= 0, . . . , n sexa unha arista en G, no primeiro caso denomínase arista cara diante e no segundo caso arista cara atrás. Definición 4.2. Se Gun grafo dirixido, decimos que un vértice vjéaccesible dende un vértice vise existe unha secuencia de aristas (e1, e2, . . . , en)verificando ek= (vk−1, vk)con vértice inicial vie vértice final vj. Cada vértice é accesible dende sí mesmo. Un vértice chamase raíz se é accesible dende calquera outro vértice. Dicimos que un grafo é conexo se para cada par de vértices distintos existe unha cadea que os une. Un grafo dirixido denomínase árbol se é conexo e non conten ciclos. Unha árbore de expansión dun grafo dirixido Gé unha árbore que é subgrafo de expansión de G. Ademais, se Gten unha raíz r, decimos que Gé unha árbore dirixida, ou ramificación con raíz r. Do mesmo xeito, un bosque dirixido é un grafo dirixido no que as súas compoñentes conexas son árbores dirixidas. 4.2. Matrices de incidencia Unha particularidade dos grafos dirixidos en contraposición cos non dirixidos é, como vimos previamente, que a súa información pode resumirse en matrices de incidencia. Por ese motivo, nesta sección presentamos algúns resultados relacionados coas matrices de incidencia que axudan a caracterizar os grafo que representan. Lema 4.3. Dado Gun grafo dirixido con nvértices. A matriz de incidencia, B, de Gten rango como máximo n−1. 4.2. MATRICES DE INCIDENCIA 35 Demostración. Ao sumar todas as filas de Bchegamos a unha fila onde todas as entradas son 0. [1] Teorema 4.4. Un grafo dirixido Gcon matriz de incidencia Bé un bosque se e só se as columnas de Bson linealmente independentes. Demostración. Vexamos que Gcontén un ciclo se e só se as columnas de Bson linealmente dependentes. “⇒”Supoñamos que Cé un ciclo en Gcon vértices {v0, v1, . . . , vk}e aristas {e1, . . . , ek}, e as columnas de Bque corresponden a esas aristas son c1, c2, . . . , ck. Se tomamos xi= 1 se eié unha arista “cara diante”exi=−1se eié unha arista “cara atrás”no ciclo C (para i= 1, . . . , k), entón a combinación x1c1+x2c2+. . . +xkcké igual a 0. “⇐”Supoñamos que as columnas de Bson linealmente dependentes. Entón dadas as columnas c1, . . . , ckde Be os enteros x1, . . . , xk6= 0 tense que x1c1+x2c2+. . . +xkck= 0. Tomamos E0como o conxunto de aristas que corresponden as columnas c1, . . . , ckeV0 o conxunto de vértices incidentes nas arista de E0e escribimos o grafo G0= (V0, E0). Tense entón que no grafo subxacente non dirixido correspondente todos os vértices teñen ao menos grao 2, e, polo lema 2.5 vemos que ningunha das compoñentes conexas do grafo subxacente non dirixido é un árbol, en consecuencia, todas as compoñentes conexas do grafo subxacente non dirixido conteñen ciclos e este grafo non dirixido non pode ser un bosque. [1] Teorema 4.5. Dado un grafo dirixido Gcon nvértices e pcompoñentes conexas, entón a matriz de incidencia Bde Gten rango n−p. . Demostración. En consecuencia do Teorema 4.4, o rango de Bé o número de aristas dun bosque maximal, T, contido en G. Se p= 1 verifícase que Té unha árbore e ten exactamente n−1aristas, entón Bten rango n−1 = n−p. Supoñamos agora que p6= 1. Entón Gpode separarse nas súas compoñentes conexas e entón, Té unión disxunta de párbores. Supoñamos que esos árbores teñen un número n1, n2, . . . , npde vértices respectivamente. Entón a matriz de incidencia Bde Gten rango (n1−1) + (n2−1) + . . . + (np−1) = n−p. [1] Definición 4.6. Unha matriz dise unimodular se é unha matriz de enteros cuxo determinante é +1 ou -1. E unha matriz dise totalmente unimodular se é unha matriz de enteros para a cal cada submatriz cadrada ten determinante 0,+1 ou -1. Teorema 4.7. Dada Ba matriz de incidencia dun grafo dirixido G. Entón Bé totalmente unimodular. 36 CAPÍTULO 4. GRAFOS DIRIXIDOS Demostración. Tomamos calquera submatriz cadrada, B0, de Bcon kfilas e columnas. Usamos inducción en k. Se k= 1,B0vai ter determinante 0,+1 ou -1 trivialmente. Tomamos agora k6= 1. Se B0contén unha columna de ceros, entón detB0= 0. Asumimos agora que todas as columnas de B0conteñen dúas entradas distintas de cero e, nese caso, B0define un grafo dirixido G0con kvértices e aristas. Entón, polo teorema 4.4 as columnas de B0son linealmente dependentes e de novo detB0= 0. Por último, asumimos que hai unha columna de B0que ten exactamente unha entrada distinta de cero. Entón calculamos o determinante de B0expandíndoa con respecto a dita columna. Obtense entón un factor ±1multiplicado polo determinante dunha ((k−1) ×(k−1))-submatriz cadrada B00, e o resultado seguese por inducción. [1] Corolario 4.8. Dado un grafo dirixido Gcon nvértices e n−1aristas. Dada Ma matriz construida a partir da matriz de incidencia, B, de Geliminando unha fila arbitrariamente. Se Gé un árbol, entón detM = +1 ou detM =−1, noutro caso detM = 0. Demostración. A fila que se elimina de Bé necesariamente unha combinación lineal doutras filas de B. Polo teorema 4.5 Mten rango n−1se e só se Gé un árbol. E, en consecuencia do teorema 4.7, tense o resultado. [1] Definición 4.9. Un árbol de expansión dun grafo dirixido Gé un subgrafo Tde Gque verifica que |T|é árbol de expansión de |G|. Teorema 4.10. Dada unha matriz Mconstruída a partir da matriz de incidencia de G eliminando unha fila arbitraria, o número de árbores de expansión de Gven dado por det(MMT). Demostración. Sexa no número de vértices de G. Para calquera subconxunto Sformado polos índices de n−1columnas, denotamos por Msá matriz formada polas n−1columnas de Mque corresponden S. Entón temos que: det(MMT) = PSdet(MsMT s) = PS(detMS)2 sendo a primeira igualdade consecuencia do teorema de Cauchy-Binet 1. Polo corolario 4.8, detBS6= 0 se e só se as aristas de Gque corresponden a Sforman un árbol, ademais, nese caso (detMS)2= 1 e tense o resultado. [1] 1Pódese ver unha demostración do Teorema de Cauchy-Binet en [3] Capítulo 5 Grafos planos Como xa vimos antes, algúns grafos contan coa propiedade de poder representarse sobre un plano sen que as súas aristas se corten, neste capítulo estudaremos algúns resultados sobre estos que teñen certo interese. 5.1. Introducción Un grafo pode representarse gráficamente nun plano de distintas formas, por exemplo: v4 v3 v2 v1 v4 v3 v2 v1 A información que conteñen ambas gráficas é a mesma, xa que representan o mesmo grafo, pero existe unha diferencia notable entre ambos: no da parte esquerda hai duas aristas que se cortan, mentres que no da dereita non. Estes grafo que poden representarse nun plano sin que as súas aristas se corten reciben o nome de grafos planos. O número de cruce dunha representación gráfica dun grafo é o número de pares de aristas que se cortan. Nun grafo plano verifícase necesariamente que o número de cruce é 0. 37 38 CAPÍTULO 5. GRAFOS PLANOS 5.2. Fórmula de Euler Xa estudamos parte da contribución do matemático alemán Leonhard Euler á teoría de grafos co problema dos pontes de Königsberg, pero esta non acabou ahí. Euler intentou, con éxito, establecer unha relación entre os vértices, as aristas e as caras dun grafo. Cando falamos de caras referímonos ás rexións nas que se divide o plano nunha representación gráfica dun grafo conexo. É preciso tamén definir unha cara exterior que se corresponde co plano exterior da representación. Exemplo 5.1. Dado un grafo Gcon representación gráfica: O número de vértices de este grafo é: V= 5, o número de aristas é: E= 7 e o número de caras é: F= 4, as tres rexións nas que divide o plano máis a cara exterior. No ano 1750, Euler demostró o seguinte resultado, que dá a relación entre as aristas, os vértices e as caras dun grafo: Teorema 5.2. Dado un grafo G, supoñamos que a súa representación gráfica nun plano ten un número vde vértices, ede aristas e fde caras. Verifícase entón: v−e+f= 2 . Demostración. Procedemos por inducción no número de aristas. Se e= 0 o grafo necesariamente ten v= 1 ef= 1, polo tanto se verifica o teorema. Se e= 1 ou e= 2 temos un camiño de e+ 1 vértices e 1cara. Supoñemos entón que o resultado se verifica para grafos con un número de aristas Eou menor, e tomamos entón e=E+ 1. Se Gé unha árbore, entón v=e+ 1 ef= 1, polo tanto, v−e+f=e+ 1 −e+ 1 = 2 xa que doutro xeito Gcontería un ciclo. Escollemos unha das aristas que participa no ciclo, esta separa duas caras (unha delas pode ser a cara exterior), polo tanto se eliminamos esta arista obtemos un novo grafo que ten unha cara e unha arista menos que o inicial. Tería entón Earistas e en termos do grafo orixinal, v−(e−1) + (f−1) = 2 e séguese o resultado. [2] 5.2. FÓRMULA DE EULER 39 Corolario 5.3. Todas as representacións nun plano dun mesmo grafo plano conexo teñen o mesmo número de caras. Demostración. Supoñamos que o grafo ten earistas e vvértices e que ten duas representacións nun plano con número de caras fef0respectivamente. Entón, v−e+f=2=v−e+f0 de onde temos f=f0. [2] En consecuencia do corolario anterior, falamos das caras dun grafo e non das caras dunha representación nun plano. Cando falamos de grafos planos podemos establecer unha serie de restriccións sobre o número de vértices, aristas e caras. Vexamos algunha a continución: Teorema 5.4. Dado un grafo plano conexo Gcon earistas, vvértices e fcaras e no cal ningunha das compoñentes conexas ten menos de 3vértices, verifícase: 3f≤2e. Demostración. O resultado se verifica claramente se f= 1 ee= 2, polo tanto podemos supoñer que cada cara de Gten 3aristas. A matriz de adyacencia arista-cara,A, de Gé unha matriz de dimensións e×fcuxas entradas aij veñen dadas por: aij =(1se a i-ésima arista pertence á frontera da j-ésima cara 0noutro caso. Denotamos por σa suma de todas as entradas de A. Como cada arista pertence ao sumo a duas caras de G, a suma das entradas de cada fila de Aé ao sumo 2. Como hai un número ede filas verifícase σ≤2e. E como cada cara ten como moito 3aristas na súa fronteira cúmplese 3f≤σe en consecuencia seguese o resultado. [2] Teorema 5.5. Dado un grafo plano conexo con un número vde vértices e ede aristas onde v≥3, verifícase: e≤3v−6 Demostración. Supoñamos que o grafo ten un número fde caras. Polo Teorema 5.4, 3f≤ 2e, logo f≥2e 3. Polo Teorema 5.2 tense que v−e+f= 2, entón v−e+2e 3≤2. De onde se deduce que 3v−e≤6e queda probado o resultado. [2] Vexamos estes resultados aplicados agora a un exemplo. Sexa Gun grafo plano conexo con representación gráfica: 40 CAPÍTULO 5. GRAFOS PLANOS O número de vértices é v= 4, o de aristas é e= 6 e o de caras é f= 4, polo tanto verifícase a fórmula de Euler, v−e+f= 4 −6 + 4 = 2. Ademais, tamén satisfanse o Teorema 5.4, 3f= 12 ≤12 = 2e, e o Teorema 5.5, e= 6 ≤6 = 3v−6. Se escribimos ademais outra representación nun plano do mesmo grafo vemos que o número de caras non varía: Corolario 5.6. Todos os grafos planos teñen, polo menos, un vértice de grao menor que 6. Demostración. Sexa Gun grafo plano con nvértices, n≥3, e maristas. Procedemos por reducción ao absurdo. Supoñamos que todos os vértices de G,{v1, v2, . . . , vn}, teñen grao maior que 6,d(vi)≥6con I= 1,...,6. Sabemos que: d(v1) + d(v2) + . . . +d(vn)≥2m, en consecuencia, temos que: 2m=d(v1) + d(v2) + . . . +d(vn)≥6n. É dicir, m≥3n≥3n−6 e chegamos a unha contradicción co Teorema 5.5. Polo tanto , ao menos un vértice de G ten que ter grao inferior a 6. 5.3. Mapas Cando estamos a falar dun mapa referímonos comunmente a unha representación gráfica da Terra ou dunha parte dela, por exemplo, un mapa dun continente dividido en países ou un mapa dun país dividido en comunidades, provincias ou estados. Podemos recoller a información de calquer mapa nun grafo, por exemplo, un mapa de España dividido en 5.3. MAPAS 41 comunidades, asignámoslle un vértice a cada comunidade e unimos dous vértices por unha arista se as comunidades comparten unha frontera. Figura 5.1: Mapa de España dividido en comunidades. Figura 5.2: Grafo que representa o mapa de España Francis Guthrie, un estudiante de Hamilton, formuloulle ao mesmo a seguinte conxetura: os cartógrafos saben que calquer mapa (o que se entende como mapa en teoría de grafos) pode ser coloreado por catro cores ou menos, pero existe unha proba matemática de iso? Esta conxetura non pudo ser resolta por Guthrie nin polo seu irmán, que tamén era alumno de Hamilton. En 1859 o matemático Alfred Kempe publicou unha proba para este resultado, pero anos máis tarde, en 1890, Percy John Heawood descubrió unha falacia na proba de Kempe, xa que atopou un mapa onde a proba deste non funcionaba, e publicou unha versión menos restrictiva de este resultado, o Teorema das Cinco Cores, que dí que todo grafo plano pode ser coloreado con cinco cores. Pero, en 1976, Ken Appel e Wolfgang Haken da unha demostración para o resultado inicial, todo grafo plano pode ser coloreado con catro cores. Foron estos os inicios do que hoxe coñécese como coloreado de grafos, que estudaremos no capítulo seguinte. 42 CAPÍTULO 5. GRAFOS PLANOS Capítulo 6 Coloreando grafos Como vimos no capítulo anterior, o feito de colorear un mapa dunha rexión co menor número de cores posible deu lugar ao que hoxe se coñece como coloreado de grafos. Neste capítulo introducimos este concepto así como algúns dos resultados máis significativos e definicións relacionadas co mesmo. 6.1. Introducción A coloración de grafos é unha asignación de etiquetas, chamadas cores, a elementos dun grafo (vértices ou aristas). Os primeiros resultados sobre coloración de grafos foron sobre grafos planos en coloración de mapas, como vimos no capítulo anterior. Definición 6.1. Se C={c1, c2, . . .}é un conxunto de obxetos indefinidos chamados cores, unha C−coloración,ξ, dun grafo G= (V, E)é unha aplicación: ξ:V−→ C. Os conxuntos Vi={v∈V:ξ(v) = ci}son chamados clases de cores. Desta forma, unha coloración dun grafo pode ser definida como unha partición do conxunto de vértices, V, en clases de cores. Unha coloración adecuada dun grafo Gé aquela na que dous vértices adxacentes non poden pertencer á mesma clase de cor ou dous aristas que sexan incidentes nun mesmo vértice non poden pertencer á mesma clase de cor (en función de se estamos a colorear vértices ou aristas). Unha coloración adecuada se dice n-coloración se o conxunto Cten nelementos. Se un grafo Gten unha n-coloración chamase grafo n-coloreado. Onúmero cromático,χ(G), dun grafo Gé o número natural máis pequeno, n, para o cal existe unha n-coloración de G. Úsase a expresión “Gén-cromático”para expresar χ(G) = 43 50 CAPÍTULO 6. COLOREANDO GRAFOS adxacentes a v, existe un camiño Pij dende viavkformado por vértices coloreados con ciecjen ξ. Imos comprobar agora que Pij =Gij. Supoñamos que vié de grao maior ou igual a 2en Gij. Entón, viten dous vértices adxacentes de cor cj, e hai un cor ckque non colorea a ningún vértice adxacente a vi. Podemos recolorear vicon ckevcon cie temos unha n-coloración de G. Entón vi, é igualmente para vj, é de grao 1en Gij. Digamos que hai un vértice vi1que é adxacente a vien Gij; entón vi1=v2ou vi1ten grao maior ou igual a 2ou vi1é adxacente a un único vértice vi2en Gij . Se Gij non é un camiño, ten que haber un vértice wde grao maior ou igual a 3que sexa adxacente a ven Gij. Se ξ(w) = ci, entón wé adxacente a 3vértices coloreados en ci, entón, debe haber unha cor ckque non coloree a ningún vértice adxacente a w. Podemos entón recolorear vicon cj,vi1con ci,vi2con cj,. . .,wcon ckevcon calquera color agás ci, dando así unha nova n-coloración de G. O caso ξ(w) = cjé similar a este. Cada Gij é un camiño dende viavj. Supoñamos que upertence aos camiños Gij e Gik con j6=k. Entón, ξ(u) = cie, a menos que u=xi,uten dous vértices adxacentes coloreados ca cor cje dous con ck. De novo, hai algún cor que non colorea a ningún vértice adxacente a ue podemos recolorear o grafo. Polo tanto, as cadeas de Kempe só se intersecan nos vértices iniciais e finais. Supoñamos agora que hai dous vértices vievjadxacentes a vpero que non son adxacentes entre eles en G, entón, tampouco son adxacentes en G v, e o camiño Gij contén un vértice distinto de vj, digamos w, adxacente a vicon ξ(vi) = cj. Escollemos unha cor ck(distinto de ciecj) e intercambiamos as cores dos vértices de Gik, entón agora, vicolorease ca cor ck. Consideramos a cadea de Kempe para esta nova coloración de G\v. Claramente upertence á jk-cadea1, xa que é adxacente a vi, que é o vértice final da jk-cadea . De igual forma, wpertence a ij-cadea. E esto contradí o dito no primeiro parágrafo. Polo tanto, todos os vértices adxacentes a vson adxacentes entre eles. Como vé un vértice calquera de GeGé conexo, este debe ser un grafo completo. Pero esto contradí a hipótese do teorema. [2] 1Cando falamos dunha ij-cadea facemos referencia a unha cadea que une os vértices vievj Capítulo 7 Un exemplo con R Neste último capítulo imos ver unha forma de representar grafos coa ferramenta R. Iremos vendo como programar en R algúns dos grafos que hemos utilizado durante o traballo, sempre dunha forma o máis sinxela posible. En primeiro lugar, debuxamos un grafo non dirixido e un dirixido: ambos grafos con 3 vértices que están numerados. g1 <- graph( edges=c(1,2, 2,3, 3,1), n=3, directed=F ) plot(g1) ● ● ● 1 2 3 Para o grafo dirixido, usamos un código similar ao caso non dirixido coa diferenza de que cambiamos o parámetro "directed", é dicir, dirixido, de F(falso) a T(verdadeiro). g2 <- graph( edges=c(1,2, 2,3, 3,1), n=3, directed=T ) plot(g2) 51 52 CAPÍTULO 7. UN EXEMPLO CON R 1 2 3 Implementamos a continuación un exemplo de grafo completo con 5vértices, que ten un comando sinxelo e específico: g3 <- make_full_graph(5) plot(g3, vertex.size=10, vertex.label=NA) ● ● ● ●● Un grafo bipartito representaríase da seguinte forma, neste caso, na primeira liña de código establecemos as aristas e na segunda damoslles aos vértices o nome que desexamos, por exemplo os vértices que estan na columna da esquera son os Vie os da dereita os Wi con i= 1 . . . 4: bipartito<-graph.formula(0--1,1--2,2--3,4--5,5--6,6--7) V(bipartito)$label<-c("V1","W1","V2","W2","V3","W3","V4","W4") plot(bipartito) 53 V1 W1 V2 W2 V3 W3 V4 W4 Además, podemos asignarlle as aristas uns parámetros, como pode ser o peso, vexamos como facelo sobre o exemplo anterior: bipeso<-graph.formula(0--1,1--2,2--3,4--5,5--6,6--7) V(bipeso)$label<-c("V1","W1","V2","W2","V3","W3","V4","W4") E(bipeso)$label<-c("(5)","(3)","(4)","(2)","(2)","(1)") plot(bipeso) (5) (3) (4) (2) (2) (1) V1 W1 V2 W2 V3 W3 V4 W4 Como vimos antes, podemos definir un grafo a partir das matrices de adxacencia e incidencia, pero ao traballar en R, só podemos facelo a partir da matriz de adxacencia, vexamos como: f1 <- c(0,1,0,0,1,0) f2 <- c(0,0,0,1,0,0) f3 <- c(0,1,0,1,0,0) f4 <- c(0,1,0,0,0,0) f5 <- c(0,0,0,1,0,1) f6 <- c(1,0,1,0,0,0) 54 CAPÍTULO 7. UN EXEMPLO CON R adx <- rbind(f1,f2,f3,f4,f5,f6) gadx<-graph.adjacency(adx) plot(gadx) 12 3 4 5 6 Neste caso, primeiro construimos a matriz de adxacencia por filas co comando rbind e logo construimos o grafo co comando graph.adjacency. Por último, podemos colorear os grafos en R, xa sexan as aristas ou os vértices. Vexamos como podemos facelo: en primeiro lugar, supoñamos que temos un grafo calquera: color<-graph.formula(0--2,0--3,1--2,1--5,2--5,2--3,3--4,3--6,4--6, 5--7,5--8,7--8,8--9,6--9,6--10,9--10,8--11,9--11) plot(color) 0 2 3 1 5 4 6 7 8 9 10 11 Imos agora a colorear os vértices deste grafo: 55 V(color)$color<-c("red","green","blue","red","blue","green","red", "red","green","blue","green","red") > plot(color) 0 2 3 1 5 4 6 7 8 9 10 11 E, por último, imos colorear as aristas deste mesmo grafo: E(color)$color<-c("blue","red","green","red","black","blue","black", "blue","green","red","green","blue","red","blue","black","green", "green","red") E(color)$width <- c(3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3) plot(color) 0 2 3 1 5 4 6 7 8 9 10 11 56 CAPÍTULO 7. UN EXEMPLO CON R Bibliografía [1] Jungnickle, Dieter, Graphs, Networks and Algorithms, 4th ed., Springer, New York, 2013 [2] Wallis, W.D., A Beginner’s Guide to Graph Theory, 2nd ed., Birkhäuser Boston [3] Hajós,G., Uber eine Konstruktion nicht n-färbbarer Graphen, Wiss. Z., Martin-LutherUniv. Halle-Wittenb., Math.-Nat.wiss. Reihe 10, 116–117 (1961) [4] Foulds, L.R., Graph Teory-A Survey Of Its Use In Operations Research, University of Canterbury, Christchurch, N.Z, 35–65 (1982) [5] Murga Díaz, Rosa María, Coloración en grafos, Universidad de Cantabria, Curso 20122013 [6] https://culturacientifica.com/2017/05/10/teorema-los-cuatro-colores-2-error-kempela-clave-la-prueba/ [7] https://kateto.net/netscix2016.html [8] Gonzalez Díaz, Julio, Programación lineal y entera, Universidade de Santiago de Compostela, 2018-2019 57