Baixe Teória dos Grafos e outras Notas de estudo em PDF para Engenharia Informática, somente na Docsity! Uma Introdução Sucinta à Teoria dos Grafos http://www.ime.usp.br/~pf/teoriadosgrafos/ P. Feofiloff Y. Kohayakawa Y. Wakabayashi 9/8/2007 2 Prefácio Este texto é uma breve introdução à Teoria dos Grafos. Para embarcar nessa introdu- ção, o leitor1 só precisa ter alguma familiaridade com demonstrações matemáticas formais e com a notação básica da teoria dos conjuntos elementar. A teoria dos grafos estuda objetos combinatórios — os grafos — que são um bom modelo para muitos problemas em vários ramos da matemática, da informática, da engenharia e da indústria. Muitos dos problemas sobre grafos tornaram-se célebres porque são um interessante desafio intelectual e porque têm importantes aplicações práticas. Nesta breve introdução, vamos nos restringir a quatro temas intimamente re- lacionados: conjuntos estáveis, coloração de vértices, emparelhamentos e colora- ção de arestas. Muitos outros temas e problemas, podem ser encontrados nos li- vros de Bondy–Murty [BM76], Wilson [Wil79], Diestel [Die00], Bollobás [Bol98], Lovász [Lov93], Lovász–Plummer [LP86], Lucchesi [Luc79] e Biggs–Lloyd–Wilson [BLW76]. Mesmo numa breve introdução como esta, é inevitável esbarrar em questões de complexidade computacional, pois muitos dos problemas da teoria dos grafos têm motivação algorítmica. O leitor interessado em aprofundar seus conhecimen- tos nessa área pode consultar os livros de Garey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97]. Estas notas foram preparadas para um mini-curso na II Bienal da SBM (Socie- dade Brasileira de Matemática), realizada em Salvador em outubro de 2004. Uma versão corrigida do texto, bem como bibliografia adicional e apontadores para ma- terial na internet, podem ser encontrados em http://www.ime.usp.br/~pf/teoriadosgrafos/ Exercícios O texto contém vários exercícios. Alguns são bastante simples e servem apenas para que o leitor confira seu entendimento do assunto. Outros levantam assuntos que não serão abordados no texto propriamente dito. Os exercícios que julgamos difíceis têm prefixo D, os muito difíceis têm prefixo D DD, e os problemas em aberto têm prefixo A. O prefixo dos exercícios particular- DD A 1 No que segue, todas as ocorrências de “leitor” devem ser entendidas como “leitora e leitor”. Para nós, as leitoras são pelo menos tão importantes quanto os leitores. 5 6 mente fáceis é F. Todos os demais têm prefixo E.F O leitor não deve sentir-se obrigado a resolver todos os exercícios de uma seção antes de começar a estudar a próxima. Recursos na teia WWW Há muito material de teoria dos grafos na teia WWW. A lista abaixo é um tanto arbitrária: os sítios mencionados não são necessariamente os melhores nem os mais representativos. • Graph Theory, de Stephen Locke: http://www.math.fau.edu/locke/graphthe. htm • Open Problems – Graph Theory and Combinatorics, de Douglas West: http://www. math.uiuc.edu/~west/openp/ • Graph Theory, no MathWorld da Wolfram Research: http://mathworld. wolfram.com/topics/GraphTheory.html • Teoria dos Grafos, na Wikipédia: http://pt.wikipedia.org/wiki/Teoria_dos_ grafos • Graph Theory, na Wikipedia: http://en.wikipedia.org/wiki/Graph_theory • The MacTutor History of Mathematics Archive, sítio de história da matemá- tica na St. Andrews University (Escócia): http://turnbull.mcs.st-and.ac. uk/~history/Indexes/HistoryTopics.html. Veja, em particular, a coleção de biografias de matemáticos em http://www-gap.dcs.st-and.ac.uk/~history/ BiogIndex.html Os autores Os autores do texto — Paulo Feofiloff, Yoshiharu Kohayakawa e Yoshiko Waka- bayashi — são professores do Departamento de Ciência da Computação (http: //www.ime.usp.br/dcc/) do Instituto de Matemática e Estatística da Universidade de São Paulo. Agradecimentos Agradecemos o apoio do MCT/CNPq (Projeto PRONEX Proc. CNPq 664107/1997– 4), da FAPESP/CNPq (Projeto Temático/PRONEX Proc. FAPESP Proc. 2003/09925– 5) e do CNPq (Proc. 300334/93–1 e 304527/89–0). Também agradecemos aos orga- nizadores da II Bienal da SBM pela boa vontade com que atenderam os sucessivos pedidos de prorrogação do prazo de entrega do texto. 7 São Paulo, novembro de 2004 P. F., Y. K., Y. W. 10 CAP. 1 CONCEITOS BÁSICOS Exemplo 1.3 O grafo das palavras é definido assim: cada vértice é uma palavra da língua portuguesa e duas palavras são adjacentes se diferem em exatamente uma posição. Por exemplo, rato e ralo são adjacentes, enquanto ralo e rota não são. Faça uma figura da parte do grafo definida pelas palavras abaixo: caiado cavado cavalo girafa girava ralo ramo rata rato remo reta reto rota vaiado varado virada virado virava Exemplo 1.4 Um cubo de dimensão k , ou k -cubo, é o grafo definido da seguinte maneira: os vértices do grafo são todas as seqüências b1b2 · · · bk em que cada bi per- tence a {0, 1} ; dois vértices são adjacentes se diferem em exatamente uma posição. Faça figuras dos cubos de dimensões 1 , 2 e 3 . Exemplo 1.5 O grafo dos estados do Brasil é definido assim: cada vértice é um dos estados da República Federativa do Brasil; dois estados são adjacentes se têm uma fronteira comum. Quantos vértices tem o grafo? Quantas arestas? AM RR RO TO MT MS PE PA GO PR SP BA SE AL CE PI MA ES RJ PB RN SC RS AP MG AC Figura 1.3: Adjacência entre estados do Brasil (veja exemplo 1.5). Exemplo 1.6 Seja M uma matriz simétrica com linhas e colunas indexadas por um conjunto V . Suponha que Mvv = 0 para todo v em V . O grafo da matriz M é definido da seguinte maneira: o conjunto de vértices do grafo é V e dois vértices u e v são adjacentes se Muv 6= 0 . Exemplo 1.7 A grade p–por–q é o grafo definido assim: o conjunto de vértices é o produto cartesiano {1, 2, . . . , p}× {1, 2, . . . , q} e dois vértices (i, j) e (i′, j′) de V são adjacentes se i = i′ e |j − j′| = 1 ou se j = j′ e |i − i′| = 1 . (Veja a figura 1.4.) Quantas arestas tem a grade p–por–q? Exemplo 1.8 Seja V o conjunto de todos os subconjuntos de {1, 2, 3, 4, 5} que têm exatamente 2 elementos. Digamos que dois elementos v e w de V são adjacentes 1.2 Alguns exemplos de grafos 11 se v ∩ w = ∅ . Essa relação de adjacência sobre V define o grafo de Petersen4 (veja figura 1.4). r r rrrrr r r r r r r rrr r rr r rr XX Q Q QC C C C JJ A A A A Z Z Z Z Figura 1.4: Uma grade 3–por–4 (veja exemplo 1.7) e um grafo de Petersen (veja exemplo 1.8). Exemplo 1.9 Os hidrocarbonetos conhecidos como alcanos têm fórmula química CpH2p+2 , onde C e H representam moléculas de carbono e hidrogênio respectiva- mente. As moléculas de alcanos podem ser representadas por grafos como os da figura 1.5. r rrr r rr r rr r r rr r rrrrr rr r rr r r r rr rrrrr r Figura 1.5: Etano (C2H6 ), butano (C4H10 ) e isobutano (C4H10 ). Os vértices em que incide uma só aresta representam átomos de hidrogênio (H ); os demais representam átomos de carbono (C ). Veja o exemplo 1.9. Exemplo 1.10 Sejam U e W dois conjuntos mutuamente disjuntos e seja A o con- junto de todos os pares não-ordenados da forma uw com u ∈ U e w ∈ W . Dizemos que (U ∪W,A) é um grafo bipartido completo. Dizemos que esse grafo é um Kp,q , Kp,q sendo p := |U | e q := |W | . (Veja uma generalização desse conceito na seção 3.4.) Exemplo 1.11 Seja V um conjunto de pontos no plano. Digamos que dois desses pontos são adjacentes se a distância entre eles é menor que 2 . Essa relação de adja- cência define o grafo dos pontos no plano (sobre o conjunto V ). Faça uma figura do grafo definido pelos pontos abaixo. (0, 2) (1, 2) (2, 2) (0, 1) (1, 1) (2, 1) (0, 0) (1, 0) (2, 0) Exemplo 1.12 Suponha dados k intervalos de comprimento finito, digamos I1, . . . , Ik , na reta real. Digamos que dois intervalos Ii e Ij são adjacentes se 4 Julius Petersen (− ), matemático dinamarquês. 12 CAP. 1 CONCEITOS BÁSICOS Ii ∩ Ij 6= ∅ . Essa relação de adjacência define um grafo com conjunto de vértices {I1, . . . , Ik} . Esse é um grafo de intervalos. Faça uma figura do grafo definido pelos intervalos [0, 2] , [1, 4] , [3, 6] , [5, 6] e [1, 6] . Exemplo 1.13 Seja uma relação de ordem parcial sobre um conjunto finito V . Portanto, a relação é transitiva (se x y e y z então x z ), anti-simétrica (se x y e y x então x = y ) e reflexiva (x x para todo x). Digamos que dois elementos distintos x e y de V são adjacentes se forem comparáveis, ou seja, se x y ou y x . Essa relação de adjacência define o grafo de comparabilidade da relação . Exemplo 1.14 Um grafo é planar se pode ser desenhado no plano sem que as curvas que representam arestas se cruzem. Mostre que o grafo dos estados do Brasil (veja exemplo 1.5) é planar. Mostre que o grafo do 3-cubo (veja exemplo 1.4) é planar. Verifique que K5 não é planar. Exemplo 1.15 Duas arestas de um grafo G são adjacentes se têm uma ponta co- mum. Essa relação de adjacência define o grafo das arestas de G .5 Se G ′ denota o grafo das arestas de G então V (G ′) = A(G) e cada aresta de G ′ é um par ab em que a e b são arestas adjacentes de G . (Veja a figura 1.6). Faça uma figura do grafo das arestas de um K3 e de um K1,3 (veja exemplo 1.10). Faça uma figura do grafo das arestas de um K4 . Quantos vértices e quantas arestas tem o grafo das arestas de um Kn ? Seja G o grafo das arestas de um K5 . Desenhe G . Você já viu esse grafo neste texto? PPPPPPPP PPP r r rr rr rv u w y x z t H H vu yz vw wx ux xy s s s s s s Figura 1.6: Um grafo (esquerda) e seu grafo das arestas (direita). 1.3 Isomorfismo Um isomorfismo entre dois grafos G e H é uma bijeção f de V (G) em V (H) tal que dois vértices v e w são adjacentes em G se e somente se f(v) e f(w) são adjacentes em H . 5 Na literatura em inglês, esse grafo é conhecido como line graph e denotado por L(G) . A expres- são “grafo das arestas” não é padrão em português. 1.4 Vizinhanças, cortes e graus 15 E 1.20 Mostre que todo grafo tem um número par de vértices de grau ímpar. E 1.21 Mostre que todo grafo com dois ou mais vértices tem pelo menos dois vérti- ces de mesmo grau. E 1.22 Quantas arestas tem o grafo da dama 8–por–8 (veja exemplo 1.1)? Quantas arestas tem o grafo do cavalo 8–por–8? E 1.23 Quantas arestas tem o grafo das arestas de um grafo G? E 1.24 Quais são os graus dos vértices de uma molécula de alcano (veja exem- plo 1.9)? E 1.25 Mostre que ∆(G) = n(G) − δ(G) − 1 e δ(G) = n(G) − ∆(G) − 1 para todo grafo G . E 1.26 Mostre que se G é um grafo com δ(G) > 0 e m(G) < n(G) então G tem pelo menos dois vértices de grau 1 . E 1.27 A matriz de adjacências de um grafo G é a matriz M com linhas e colunas indexadas por V (G) tal que M [u, v] = 1 se uv ∈ A(G) e M [u, v] = 0 em caso contrário. (Compare com o exemplo 1.6.) Qual a matriz de adjacências do grafo definido na figura 1.1? Qual a matriz de adjacências de um K4 ? Qual a matriz de adjacências de uma grade 3–por–4? Qual a matriz de adjacências de um 3-cubo? Quanto vale a soma dos elementos da linha u da matriz? Quanto vale a soma dos elementos da coluna v? F 1.28 Seja A um conjunto finito. Defina as seguintes operações de soma e multi- plicação por escalar para as partes de A : para quaisquer subconjuntos E e F de A , pomos E + F := (E r F ) ∪ (E r F ), 1 · E = E e 0 · E = ∅ . Mostre que a tripla (2A,+, ·) é um espaço vetorial sobre o corpo dos inteiros mó- dulo 2 . E 1.29 Dado um grafo G , seja D(G) a coleção de todos os cortes de G , isto é, D(G) := {∇(X) : X ⊆ V (G)} . Mostre que D(G) é um subespaço vetorial do espaço (2A(G),+, ·) definido no exercício 1.28. Dizemos que D(G) é o espaço dos cortes (ou dos cociclos) de G . 16 CAP. 1 CONCEITOS BÁSICOS 1.5 Caminhos e circuitos Um caminho é qualquer grafo da forma ({v1, v2, . . . , vn} , {vivi+1 : 1 ≤ i < n}) . Em outras palavras, um caminho é um grafo C cujo conjunto de vértices admite uma permutação (v1, v2, . . . , vn) tal que {v1v2, v2v3, . . . , vn−1vn} = A(C) . Os vértices v1 e vn são os extremos do caminho. O caminho que acabamos de descrever pode ser denotado simplesmente por v1v2 · · · vn . Por exemplo, o grafov1 · · · vn ({u, v, w, z}, {wz, vz, uw}) é um caminho, que pode ser denotado por uwzv . r r r r r rrrr rr SSSS##cc##cc Figura 1.9: Um caminho e um circuito. Um circuito10 é um grafo da forma ({v1, v2, . . . , vn} , {vivi+1 : 1 ≤ i < n} ∪ {vnv1}) , com n ≥ 3 . Em outras palavras, um circuito é um grafo O com n(O) ≥ 3 cujo conjunto de vértices admite uma permutação (v1, v2, . . . , vn) tal que {v1v2, v2v3, . . . , vn−1vn} ∪ {vnv1} = A(O) . Esse circuito pode ser denotado simplesmente por v1v2 · · · vnv1 . v1 · · · vnv1 O comprimento de um caminho ou circuito é o número de arestas do grafo. É claro que um caminho de comprimento k tem k + 1 vértices e um circuito de comprimento k tem k vértices. Um triângulo, quadrado, pentágono e hexágono é o mesmo que um circuito de comprimento 3, 4, 5 e 6 respectivamente. Um caminho ou circuito é par se tem comprimento par, e ímpar se tem compri- mento ímpar. Exercícios E 1.30 Mostre que o complemento de um caminho de comprimento 3 é um caminho de comprimento 3 . Mostre que o complemento de um circuito de comprimento 5 é um circuito de comprimento 5 . E 1.31 Mostre que todo corte de um circuito tem cardinalidade par. Isto é, mostre que, para qualquer conjunto X de vértices de um circuito O , o corte ∇O(X) tem cardinalidade par. 10 Alguns livros dizem “ciclo” no lugar do nosso “circuito”. 1.6 Subgrafos 17 1.6 Subgrafos Um subgrafo de um grafo G é qualquer grafo H tal que V (H) ⊆ V (G) e A(H) ⊆ A(G) . Um subgrafo H de G é próprio se V (H) 6= V (G) ou A(H) 6= A(G) . O subgrafo de G induzido por um subconjunto X de V (G) é o grafo (X,B) em que B é o conjunto de todas as arestas de G que têm ambas as pontas em X . Esse subgrafo é denotado por G[X] G[X] . Para qualquer subconjunto X de V (G) , denotaremos por G − X o subgrafo G−X G[V (G) rX] . Se v é um vértice de G então G− v é uma abreviatura de G− {v} . G− v Se a é uma aresta de G então G−a é o grafo (V (G), A(G)r{a}) . A propósito, se G− a {x, y} é um elemento de V (G)(2) , denota-se por G+xy o grafo (V (G), A(G)∪{xy}) . G + xy Se um caminho v1 · · · vn é subgrafo de G , dizemos simplesmente que v1 · · · vn é um caminho em G ou que G contém o caminho v1 · · · vn . Por exemplo, se dissermos que uvwz é um caminho em G , devemos entender que ({u, v, w, z}, {uv, vw,wz}) é um subgrafo de G . Convenção análoga vale para circuitos que são subgrafos de G . Exercícios E 1.32 Seja G ′ o grafo das arestas de um grafo G . Mostre que G ′ não contém K1,3 (veja exemplo 1.10) como subgrafo induzido. (Em outras palavras, mostre que não existe subconjunto X de V (G ′) tal que G ′[X] é um K1,3 .) E 1.33 Uma floresta é um grafo sem circuitos. Mostre que um grafo G é uma floresta se e somente se cada uma de suas arestas é um corte, ou seja, para cada aresta a existe um subconjunto X de V (G) tal que ∇(X) = {a} . E 1.34 Digamos que um grafo é par se todos os seus vértices têm grau par. Dado um grafo G , seja O(G) a coleção dos conjuntos das arestas de todos os subgrafos pares de G . Mostre que O(G) é um subespaço vetorial do espaço (2A(G),+, ·) definido no exercício 1.28. Dizemos que O(G) é o espaço dos ciclos de G . E 1.35 Seja G um grafo e considere os espaços O(G) e D(G) definidos nos exercí- cios 1.34 e 1.29 respectivamente. Mostre que |O ∩ D| ≡ 0 mod 2 para todo mem- bro O de O(G) e todo membro D de D(G) . (Sugestão: Mostre que O pode ser es- crito como uma união disjunta de circuitos, ou seja, que existem circuitos O1, . . . , Ok dois a dois disjuntos nas arestas tais que O = A(O1) ∪ · · · ∪ A(Ok) .) 1.7 Grafos conexos e componentes Um grafo é conexo se, para qualquer par {v, w} de seus vértices, existe um caminho com extremos v e w . Por exemplo, o grafo do bispo (veja 1.2) não é conexo (a menos que o tabuleiro tenha uma só linha e uma só coluna). Capítulo 2 Conjuntos estáveis, cliques e coberturas Um conjunto de vértices de um grafo é estável1 se seus elementos são dois a dois não-adjacentes, ou seja, se nenhuma aresta tem ambas as pontas no conjunto. Em outras palavras, um conjunto X de vértices de um grafo G é estável se o grafo induzido G[X] é vazio. Eis um exemplo. Digamos que meu grafo G representa a planta de uma cidade: os vértices são as esquinas e as arestas são os trechos de ruas que ligam as esqui- nas. Quero instalar uma rede de postos de gasolina na cidade. A legislação exige que cada posto fique numa esquina e impede que dois postos fiquem em esquinas adjacentes. Quantos postos no máximo posso instalar na cidade? Um conjunto estável X é maximal se não faz parte de um conjunto estável maior, ou seja, se X não é subconjunto próprio de outro conjunto estável. É muito fácil encontrar um conjunto estável maximal: comece com um conjunto estável X e examine os demais vértices um a um; se o vértice examinado for adjacente a al- gum dos que estão em X , descarte-o; caso contrário, acrescente-o a X . É bem mais difícil — e mais interessante — encontrar um conjunto estável máximo. 2.1 Conjuntos estáveis máximos Um conjunto estável X é máximo se |X| ≥ |Y | para todo conjunto estável Y . A cardinalidade de um conjunto estável máximo de um grafo G é denotada por α(G) . Vamos nos referir a esse número como índice de estabilidade do grafo. É claro que todo conjunto estável máximo é maximal, mas a recíproca não é verdadeira. Por exemplo, todo K1,9 (veja exemplo 1.10) tem um conjunto estável maximal de cardinalidade 1 mas o seu índice de estabilidade é 9 . 1 Há quem diga “conjunto independente” no lugar do nosso “conjunto estável”. 20 2.2 Delimitações inferiores 21 Eis alguns exemplos. O índice de estabilidade de um Kn é 1 , enquanto o índice de estabilidade de um Kn é n . Se G é o grafo da dama 8–por–8 (veja exemplo 1.1) então α(G) ≥ 7 , pois é possível colocar 7 damas no tabuleiro de modo que elas não se ataquem mutuamente.2 Este capítulo estuda a relação entre o índice de estabilidade e outros parâmetros do grafo. A intuição sugere, por exemplo, que α é tanto maior quanto menores forem os graus dos vértices. É possível comprovar essa intuição? Exercícios F 2.1 Mostre que, em geral, um conjunto estável máximo num grafo não é único. E 2.2 Encontre um conjunto estável máximo num circuito de comprimento n . En- contre um conjunto estável máximo num caminho com n vértices. E 2.3 Encontre um conjunto estável máximo na grade p–por–q (veja exemplo 1.7). E 2.4 Seja Gt o grafo da dama t–por–t (veja exemplo 1.1). Mostre que α(G8) = 8 . Calcule α(G5) , α(G6) e α(G7) . D 2.5 Seja Gt o grafo da dama t–por–t (veja exemplo 1.1). Calcule α(Gt) para todo t ≥ 9 . E 2.6 Encontre um conjunto estável máximo nos grafos do cavalo, do bispo, da torre e do rei (veja exemplo 1.2). 2.2 Delimitações inferiores Para obter uma delimitação inferior de α , basta encontrar um conjunto estável ra- zoavelmente grande. A delimitação abaixo, por exemplo, usa um conjunto estável maximal arbitrário. Ela comprova a intuição de que conjuntos estáveis maximais são tanto maiores quanto menores forem os graus dos vértices. Delimitação 2.1 Para todo grafo G tem-se α(G) ≥ n(G) ∆(G) + 1 . PROVA: É suficiente mostrar que todo conjunto estável maximal tem pelo menos n ∆+1 vértices. Para qualquer conjunto estável X tem-se |∇(X)| = ∑ x∈X g(x) . 2 É possível colocar mais que 7 damas no tabuleiro? 22 CAP. 2 CONJUNTOS ESTÁVEIS, CLIQUES E COBERTURAS Suponha agora que X é maximal. Então cada vértice em V (G) r X é vizinho de algum vértice em X , donde |V (G) rX| ≤ |∇(X)| . Logo, |V (G) rX| ≤ ∑ x∈X g(x) ≤ |X| ·∆(G) . Segue daí que n(G) = |X| + |V (G) r X| ≤ |X| · (1 + ∆(G)) . Resta apenas observar que α(G) ≥ |X| . A delimitação 2.1 admite uma generalização muito interessante: Delimitação 2.2 Para todo grafo G tem-se α(G) ≥ ∑ v∈V (G) 1 g(v) + 1 . PROVA: Adote a abreviatura hG( ) := (gG( ) + 1) −1 . Queremos mostrar queh( ) α(G) ≥ ∑ v hG(v) . A prova é uma indução em n(G) . É fácil verificar que a desigualdade vale quando n(G) ≤ 2 . Suponha agora que n(G) > 2 e que o resultado é válido para grafos com menos que n(G) vértices. Seja x um vértice de grau mínimo e seja Y o conjunto dos vizinhos de x , isto é, Y := Γ(x) . Essa escolha de x garante que hG(x) + ∑ y∈Y hG(y) ≤ hG(x) + |Y | · hG(x) = hG(x) + gG(x)hG(x) = (1 + gG(x))hG(x) = 1 . Seja H o subgrafo induzido pelo complemento de {x} ∪ Y , isto é, H := G[Z] com Z := V (G) r (Y ∪ {x}) . Por hipótese de indução, α(H) ≥ ∑ z∈Z hH(z) . ComoZ gH(z) ≤ gG(z) e portanto hH(z) ≥ hG(z) para todo z em Z , temos α(H) ≥ ∑ z∈Z hG(z) . Para todo conjunto estável S em H , o conjunto S ∪ {x} é estável em G . Portanto, α(G) ≥ 1 + α(H) ≥ 1 + ∑ z∈Z hG(z) ≥ hG(x) + ∑ y∈Y hG(y) + ∑ z∈Z hG(z) = ∑ v∈V (G) hG(v) , como queríamos provar. As delimitações discutidas acima são justas: nos grafos completos, por exemplo, tem-se α = ⌈ n ∆+1 ⌉ .3 (Veja também o exercício 2.8). Mas α pode ficar arbitrariamente longe de n/(∆ + 1) e mesmo de ∑ 1/(g(v) + 1) : num Kp,p , por exemplo (veja exem- plo 1.10), temos α = p enquanto ∑ 1/(g(v) + 1) < 2 . 3 Para qualquer número real x , denotamos por dxe o único inteiro j tal que j − 1 < x ≤ j . 2.4 O índice de estabilidade da maioria dos grafos 25 subconjuntos de cardinalidade k , temos |Q(n, k)| ≤ nk 2N−K , e portanto |Q(n, k)| |G(n)| ≤ nk 2−k(k−1)/2 . Segue daí que 2 log2(|Q(n, k)|/|G(n)|) ≤ 2k log2 n− k(k − 1) = k (1 + 2 log2 n− k) ≤ d(2 + ε) log2 ne (1 + 2 log2 n− (2 + ε) log2 n) = d(2 + ε) log2 ne (1− ε log2 n) . (2.2) Como limn→∞(1− ε log2 n) = −∞ , temos lim n→∞ log2 |Q(n, k)| |G(n)| = −∞ , e isso prova (2.1). Por exemplo, se ε = 0,2 então, em virtude de (2.2), temos |Q(1024, 22)| ≤ 2220−231|G(1024)| e portanto uma fração de pelo menos 1 − 2−11 (mais que 99,9%) dos grafos em G(1024) têm α < 22 . Exercícios E 2.15 Prove que, por menor que seja o número positivo η , temos α(G) < n/(2 log2 n + 1 + η) para quase todo grafo G em G(n) . (Sugestão: acompanhe a demonstração do teorema 2.4, tomando ε = (1 + η)/ log2 n .) E 2.16 Fixe um grafo H (o grafo de Petersen, por exemplo). Prove que quase todo grafo G em G(n) contém um subgrafo induzido isomorfo a H . (Suponha que H tem h vértices. Escolha partes duas a duas disjuntas U1, . . . , Um de V (G) , com m = bn/hc e |Ui| = h . Qual é a probabilidade de nenhum Ui induzir uma cópia de H ?) E 2.17 Prove que quase todo grafo G em G(n) tem diâmetro ≤ 2 , isto é, prove que quase todo G em G(n) é tal que, para quaisquer vértices distintos u e v , existe em G um caminho de comprimento no máximo 2 com extremos u e v . (Na verdade, quase todo G em G(n) é tal que quaisquer dois vértices u e v de G são extremos de um caminho de comprimento exatamente 2 .) D 2.18 Prove que quase todo grafo em G(n) é conexo. 26 CAP. 2 CONJUNTOS ESTÁVEIS, CLIQUES E COBERTURAS 2.5 Cliques Uma clique8 ou conjunto completo num grafo é qualquer conjunto de vértices dois a dois adjacentes. Em outras palavras, X é uma clique se o grafo induzido G[X] é completo. Há uma relação óbvia entre cliques e conjuntos estáveis: Observação 2.5 Um conjunto X de vértices é uma clique em um grafo G se e somente se X é estável no grafo complementar G . A cardinalidade de uma clique máxima de um grafo G é denotada por ω(G) . De acordo com a observação acima, ω(G) = α(G) para todo grafo G . Exercícios E 2.19 Encontre uma clique máxima no grafo da dama (veja exemplo 1.1), ou seja, disponha o maior número possível de damas no tabuleiro de modo que elas se ata- quem mutuamente. Encontre cliques máximas nos grafos do cavalo, do bispo, da torre e do rei (veja exemplo 1.2). E 2.20 Encontre uma clique máxima no grafo dos estados do Brasil (veja exem- plo 1.5). F 2.21 Mostre que ω(G) ≤ ∆(G) + 1 para todo grafo G . E 2.22 Deduza delimitações inferiores e superiores para ω(G) a partir das delimita- ções 2.1 e 2.2. E 2.23 Seja G ′ o grafo das arestas de um grafo G (veja o exemplo 1.15). Mostre que, para cada vértice v de G , o conjunto ∇G(v) é uma clique em G ′ . Mostre que o conjunto das arestas de qualquer triângulo em G é uma clique em G ′ . Mostre que ∆(G) = ω(G ′) se ∆(G) 6= 2 . Mostre que 2 ≤ ω(G ′) ≤ 3 se ∆(G) = 2 . D 2.24 Mostre que ω(G) ≥ 3 para todo grafo G com mais que n(G)2/4 arestas. (Veja o exercício 2.12.) 8 A palavra clique é um neologismo emprestado do inglês. Uma clique é uma “panelinha”, um grupo exclusivo, um conjunto de pessoas que se conhecem entre si e têm algum interesse comum. Nesse contexto, a palavra não tem nenhuma relação com “estalido”. 2.6 Coberturas 27 D 2.25 A intuição sugere que, em todo grafo, ω é grande se α for pequeno e vice- versa. Ramsey9 mostrou que isso de fato é assim para grafos suficientemente gran- des. Seja r(s, t) o menor número natural tal que todo grafo G com n(G) ≥ r(s, t) tem α(G) ≥ s ou ω(G) ≥ t . Mostre que r(s, t) ≤ ( s+t−2 s−1 ) . (Sugestão: mostre que r(s, t) ≤ r(s−1, t)+r(s, t−1) para quaisquer s ≥ 2 e t ≥ 2 .)10 E 2.26 Seja ε um número real positivo fixo e, para todo inteiro n ≥ 2 , ponha k = d(2 + ε) log2 ne . Prove a seguinte delimitação para os números de Ramsey (veja exercício 2.25): existe n0 tal que r(k, k) > n para todo n ≥ n0 . (Sugestão: Siga os passos da prova do teorema 2.4.) E 2.27 Prove a seguinte delimitação para os números de Ramsey (veja exercí- cio 2.25): r(k, k) > 2k/2 para todo inteiro k ≥ 2 . (Essa delimitação é um pouco mais “limpa” que a do exercício 2.26; a idéia central da prova é a mesma.) 2.6 Coberturas Uma cobertura de um grafo é qualquer conjunto de vértices que contenha pelo me- nos uma das pontas de cada aresta. Em outras palavras, um conjunto X de vértices é uma cobertura se toda aresta do grafo tem pelo menos uma de suas pontas em X . Há uma relação simples entre coberturas e conjuntos estáveis: Observação 2.6 Em qualquer grafo G , um conjunto X de vértices é uma cobertura se e somente se V (G) rX é um conjunto estável. A cardinalidade de uma cobertura mínima de um grafo G é denotada por11 β(G) . Se um guarda postado em um vértice do grafo é capaz de vigiar todas as arestas que incidem no vértice, então β é o número mínimo de guardas necessário para vigiar todas as arestas do grafo. Segue imediatamente da observação acima que β(G) = n(G) − α(G) para todo grafo G . 9 Frank P. Ramsey (−  ), lógico, matemático, e economista inglês. 10 A determinação do valor exato do número de Ramsey r(s, t) é um problema difícil ainda longe de estar resolvido. 11 O símbolo tradicional para esse número é “β0 ”. Mas nesse texto parece mais apropriado e consistente escrever “β ”. 30 CAP. 3 COLORAÇÃO DE VÉRTICES Exercícios E 3.1 Exiba um grafo com duas colorações mínimas diferentes. E 3.2 Mostre que os conjuntos estáveis que compõem uma coloração mínima não são necessariamente máximos. Mais precisamente, exiba uma coloração mínima {X1, . . . , Xk} em que nenhum dos conjuntos estáveis Xi é máximo. E 3.3 Qual o número cromático do grafo dos estados do Brasil (veja exemplo 1.5)? E 3.4 Qual o número cromático do grafo de Petersen (veja exemplo 1.8)? E 3.5 Encontre uma coloração mínima dos vértices do grafo da dama t–por–t (veja o exercício 1.1). Trate inicialmente dos casos t = 2, . . . , 6 . E 3.6 Encontre colorações mínimas dos vértices dos grafos do cavalo, do bispo, da torre e do rei (veja exercício 1.2). D 3.7 Prove que χ(G) ≤ λmax(G) + 1 , onde λmax(G) é o maior autovalor da matriz de adjacências de G (veja exercício 1.27).2 D 3.8 Um museu de arte tem uma grande sala cujo contorno é um polígono fechado, não necessariamente convexo, com n lados. Queremos postar guardas em alguns dos vértices do polígono de modo que cada ponto da sala possa ser visto por pelo menos um dos guardas (o ângulo de visão de cada guarda só é limitado pelas pare- des da sala). Mostre que bn/3c guardas são suficientes. Mostre que bn/3c guardas são necessários para certos polígonos.3 DD 3.9 Mostre que χ(G) ≤ 4 para todo grafo planar G (veja o exemplo 1.14).4 3.2 Algumas delimitações superiores Para obter uma delimitação superior do número cromático de um grafo basta mos- trar a existência de uma coloração com poucas cores. Eis uma delimitação superior muito simples, que confirma a intuição de que um grafo com poucas arestas tem número cromático pequeno: Delimitação 3.1 Para todo grafo G tem-se χ(G) ≤ 1 2 + √ 2m(G) + 1 4 . 2 Veja o livro de Biggs [Big74]. 3 Veja o livro de Aigner–Ziegler [AZ98, p.165]. 4 Este é o célebre Teorema das Quatro Cores. 3.3 Algumas delimitações inferiores 31 PROVA: Seja {X1, . . . , Xk} uma coloração mínima. Então, para todo i e todo j distinto de i , existe uma aresta com uma ponta em Xi e outra em Xj . Assim, m(G) ≥ ( k 2 ) = (k2 − k)/2 . Logo, k ≤ (1 + √ 8m+ 1)/2 . Considere agora uma delimitação mais sofisticada. Ela confirma a intuição de que χ é tanto menor quanto menor o grau máximo do grafo. Delimitação 3.2 Para todo grafo G tem-se χ(G) ≤ ∆(G) + 1 . PROVA: Nossa prova é uma indução no número de vértices. Se n(G) = 1 , a proposição é obviamente verdadeira. Suponha agora que n(G) > 1 . Seja x um vértice qualquer e H o grafo G − x . Por hipótese de indução, χ(H) ≤ ∆(H) + 1 . Seja {X1, . . . , Xk} uma coloração mínima de H . Como ∆(H) ≤ ∆(G) , temos k ≤ ∆(G) + 1 . Se essa desigualdade é estrita, então {{x}, X1, . . . , Xk} é uma coloração de G com não mais que ∆(G) + 1 cores. Suponha agora que k = ∆(G) + 1 . Como gG(x) ≤ ∆(G) = k−1 , o vértice x é adjacente a não mais que k−1 cores diferentes. Portanto, existe i tal que Xi ∪ {x} é um conjunto estável. Se substituirmos Xi por Xi ∪ {x} em {X1, . . . , Xk} teremos uma coloração de G com ∆(G) + 1 cores. Embora existam grafos (os completos e os circuitos ímpares, por exemplo) em que χ = ∆ + 1 , a diferença entre χ e ∆ pode ser arbitrariamente grande (este é o caso, por exemplo, dos grafos K1,n definidos no exemplo 1.10). Exercícios D 3.10 Mostre que χ(G) ≤ ∆(G) para todo grafo não-regular G . Mostre algo mais geral: se G é conexo mas não é um grafo completo nem um circuito ímpar então χ(G) ≤ ∆(G) . (Esse fato é conhecido como Teorema de Brooks5.) 3.3 Algumas delimitações inferiores Para obter uma delimitação inferior do número cromático de um grafo é preciso mostrar que todas as coloração exigem muitas cores. Eis uma delimitação inferior simples: Delimitação 3.3 Para todo grafo G tem-se χ(G) ≥ n(G) α(G) . PROVA: Seja {X1, . . . , Xk} uma coloração dos vértices de G . É claro que k ≥ χ(G) e |Xi| ≤ α(G) para cada i . Portanto, n(G) = |X1|+ · · ·+ |Xk| ≤ k ·α(G) . Segue daí que k ≥ n(G)/α(G) . 5 Publicado em  por R. L. Brooks. 32 CAP. 3 COLORAÇÃO DE VÉRTICES Eis outra delimitação inferior, simples mas útil: Delimitação 3.4 Para todo grafo G tem-se χ(G) ≥ ω(G) . PROVA: A desigualdade decorre do seguinte fato óbvio: para qualquer colora- ção {X1, . . . , Xk} dos vértices e qualquer clique C tem-se k ≥ |C| . Essa desigualdade vale, em particular, se a coloração é mínima e a clique é máxima. Logo, χ ≥ ω . A delimitação inferior 3.4 tem a seguinte conseqüência interessante: se um grafo G tem uma coloração de vértices e uma clique de mesma cardinalidade então a colo- ração é mínima (e a clique é máxima). Assim, para tornar evidente a minimalidade de uma determinada coloração {X1, . . . , Xk} , é suficiente exibir uma clique com k vértices. Considere, por exemplo, o grafo da dama 4–por–4 (veja exemplo 1.1). É fácil encontrar uma coloração do grafo com 5 cores e uma clique com 5 vértices. Por- tanto, a coloração é mínima e a clique é máxima. Algo semelhante ocorre no grafo da torre t–por–t . Infelizmente, a desigualdade da delimitação 3.4 é estrita para muitos grafos. A diferença entre χ e ω (e até o quociente χ/ω ) podem ser arbitrariamente grandes, embora exemplos desse fenômeno não sejam simples (veja exercício 3.16). Exercícios E 3.11 O grafo de Catlin6 é definido da seguinte maneira: comece com um pentá- gono P ; troque cada vértice v de P por um triângulo Tv (os triângulos correspon- dentes a vértices diferentes são disjuntos); finalmente, troque cada aresta vw de P por 9 arestas ligando cada vértice de Tv com cada vértice de Tw . Encontre uma coloração mínima do grafo de Catlin. Use a delimitação 3.3 para mostrar que sua coloração é, de fato, mínima. E 3.12 Mostre que χ(G) = ω(G) se G é um grafo de intervalos (veja exemplo 1.12). (Sugestão: Faça indução no número de intervalos. Comece por retirar o intervalo cujo extremo direito está mais à esquerda.) E 3.13 Mostre que χ(G) = ω(G) se G é um grafo de comparabilidade (veja exem- plo 1.13). (Sugestão: Retire do grafo o conjunto dos vértices que são maximais na ordem parcial. Aplique indução.) 6 Construído em  por P. A. Catlin. 3.5 O número cromático da maioria dos grafos 35 F 3.21 Mostre que χ(G) = ω(G) para todo grafo bicolorível G . F 3.22 Seja G um grafo bicolorível conexo (veja seção 1.7). Mostre que G tem uma única bicoloração. Em outras palavras, se {U,W} e {U ′,W ′} são bicolorações de G então U = U ′ (e portanto W = W ′ ) ou U = W ′ (e portanto W = U ′ ). D 3.23 Mostre que m(G) ≤ n(G)2/4 para todo grafo bicolorível G . (Isso é um caso especial do exercício 2.24.) A 3.24 Encontre uma boa caracterização da classe {G : χ(G) ≤ 3} dos grafos trico- loríveis. r r r r r r r r r HH HHH HH HHH r r r rrr rrr r r r ZZ Z Z Z Z Z Z Z Z Figura 3.2: Exercício 3.20. Esses grafos são bicoloríveis? 3.5 O número cromático da maioria dos grafos O número cromático de quase todos os grafos (veja seção 1.8) é surpreendentemente alto se comparado com o número de vértices do grafo: Teorema 3.6 Por menor que seja o número positivo ε , temos χ(G) > 1 2 + ε n log2 n para quase todo grafo G em G(n) . PROVA: De acordo com a delimitação 3.3, o número cromático de todo grafo G satisfaz a desigualdade χ(G) ≥ n α(G) . De acordo com o teorema 2.4, para qualquer ε > 0 e para quase todo G em G(n) , temos α(G) < (2 + ε) log2 n . Isso prova o resultado. Por exemplo, se ε = 0,2 então |Q(1024, 22)| ≤ 2−11|G(1024)| e portanto uma fração de pelo menos 1 − 2−11 (mais que 99,9%) dos grafos em G(1024) têm χ ≥ 47 = ⌈ 1024 22 ⌉ . 36 CAP. 3 COLORAÇÃO DE VÉRTICES Pode-se mostrar (embora isso não seja fácil)10 que a delimitação inferior dada pelo teorema 3.6 é bastante justa: por menor que seja o número ε no intervalo aberto (0, 2) , tem-se χ(G) < 1 2− ε n log2 n para quase todo grafo G em G(n) . 3.6 Considerações computacionais Para encontrar uma coloração mínima dos vértices de um grafo, basta examinar to- das as partições do conjunto de vértices.11 Esse algoritmo consome tempo superior a 2n para analisar um grafo com n vértices, o que é decididamente insatisfatório na prática. (Veja o que dissemos na seção 2.7 a respeito da computação do conjunto estável máximo de um grafo.) Infelizmente, não se conhece um algoritmo substan- cialmente melhor; suspeita-se mesmo que um algoritmo substancialmente melhor não existe.12 Outra questão computacional relevante é o da certificação de uma coloração mí- nima dada: que objeto é suficiente exibir para provar a minimalidade da coloração? Infelizmente, não se conhece (exceto no caso da bicoloração) um certificado que seja substancialmente melhor que a comparação da coloração dada com cada uma das demais colorações do grafo. 10 Este é um teorema célebre publicado em  por B. Bollobás. 11 O número B(n) de partições de um conjunto com n elementos é conhecido como número de Bell. Os números de Bell satisfazem a recorrência B(n + 1) = ∑n k=0 B(k) ( n k ) e crescem bem mais que 2n . 12 Veja os livros de Garey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97]. Capítulo 4 Emparelhamentos Duas arestas de um grafo G são adjacentes se têm uma ponta comum.1 Um empa- relhamento num grafo é um conjunto de arestas duas a duas não-adjacentes. Em ou- tras palavras, um emparelhamento é um conjunto E de arestas tal que |E∩∇(v)| ≤ 1 para cada vértice v . Eis uma ilustração do conceito de emparelhamento. Suponha que um projeto de engenharia consiste em um grande número de tarefas e que cada tarefa deve ser executada por um time dois operários compatíveis. Gostaríamos de executar o maior número possível de tarefas simultaneamente. A mão de obra disponível pode ser representada por um grafo cujos vértices são os operários e cujas arestas são os pares de operários compatíveis. Um emparelhamento nesse grafo é uma coleção de times que podem atuar simultaneamente. Um emparelhamento é um tipo particular de conjunto estável: um conjunto E de arestas de um grafo G é um emparelhamento se e somente se E é estável no grafo das arestas de G (veja o exemplo 1.15). Este capítulo vai mostrar que sabemos bem mais sobre emparelhamentos que sobre conjuntos estáveis. 4.1 Emparelhamentos máximos Um emparelhamento E é maximal se não for parte de um emparelhamento maior, ou seja, se E não for subconjunto próprio de outro emparelhamento. Encontrar um emparelhamento maximal num grafo é fácil: comece com um emparelhamento ar- bitrário F e examine as arestas restantes uma a uma; toda vez que encontrar uma aresta que não é adjacente a nenhuma das que já estão em F , acrescente-a a F . É bem mais difícil — e mais interessante — procurar por um emparelhamento má- ximo. Um emparelhamento E é máximo se |E| ≥ |F | para todo emparelhamento F . Denotaremos por α ′(G) 1 Há quem diga que duas arestas sem ponta comum são independentes. 37 40 CAP. 4 EMPARELHAMENTOS O seguinte exemplo é o protótipo do nosso problema: dado um conjunto U de moças e um conjunto W de rapazes, queremos casar cada moça com um dos rapazes que ela conhece (sem violar a lei da monogamia). Em que condições isso é possível? Há uma condição necessária muito simples e natural para que nosso problema tenha solução: Proposição 4.2 Se um grafo (U,W )-bipartido tem um emparelhamento que satura U então |Γ(X)| ≥ |X| para todo subconjunto X de U . PROVA: Seja G o grafo em questão e E um emparelhamento que satura U . Seja H o grafo (V (G), E) . Para qualquer subconjunto X de U tem-se |ΓG(X)| ≥ |ΓH(X)| = |X| . Essa condição necessária tem a seguinte conseqüência imediata: para mostrar que um grafo (U,W )-bipartido não tem um emparelhamento que satura U , basta exibir um subconjunto X de U tal que |Γ(X)| < |X| . A prova da recíproca da proposição 4.2 foi publicada em  por Hall3: Teorema 4.3 (Hall) Para qualquer grafo (U,W )-bipartido, se |Γ(X)| ≥ |X| para todo subconjunto X de U então o grafo tem um emparelhamento que satura U . PROVA: Seja G o grafo em questão e suponha que |ΓG(X)| ≥ |X| para todo subconjunto X de U . A prova prossegue por indução na cardinalidade de U . Se |U | = 1 então é claro que o grafo tem um emparelhamento que satura U . Suponha agora que |U | > 1 e que o resultado vale para todo grafo (U ′,W ′)-bipartido em que |U ′| < |U | . Considere as alternativas a seguir. ALTERNATIVA 1: |ΓG(X)| > |X| para todo subconjunto próprio e não-vazio X de U . Escolha uma aresta uw , com u em U . Seja U ′ := U r {u} , W ′ := W r {w} e G′ := G[U ′ ∪W ′] . É claro que G′ é (U ′,W ′)-bipartido. Observe que |ΓG′(X)| = |ΓG(X) r {w}| ≥ |X| para todo subconjunto X de U ′ . Assim, por hipótese de indução, G′ admite um emparelhamento, digamos E ′ , que satura U ′ . Finalmente, E ′ ∪ {uw} é um empare- lhamento em G que satura U . ALTERNATIVA 2: |ΓG(Y )| = |Y | para algum subconjunto próprio e não-vazio Y de U . Seja H o subgrafo de G induzido por Y ∪ΓG(Y ) . É claro que H é (Y,ΓG(Y ))- bipartido e |ΓH(X)| = |ΓG(X)| ≥ |X| para todo subconjunto X de Y . A hipótese de indução garante, então, a existência em H de um emparelhamento F que satura Y . Agora considere o subgrafo G′ :=F 3 Philip Hall (−  ), matemático inglês. 4.3 Emparelhamentos em grafos bipartidos 41 G[U ′ ∪ W ′] , onde U ′ := U r Y e W ′ := W r ΓG(Y ) . É claro que G′ é (U ′,W ′)- bipartido. Suponha, por um instante, que |ΓG′(X ′)| < |X ′| para algum subconjunto X ′ de U ′ . Então |ΓG(X ′ ∪ Y )| = |ΓG(X ′) ∪ ΓG(Y )| ≤ |ΓG(X ′)|+ |ΓG(Y )| < |X ′|+ |Y | = |X ′ ∪ Y | . Essa desigualdade contradiz as hipóteses da presente alternativa. Concluímos assim que |ΓG′(X ′)| ≥ |X ′| para todo subconjunto X ′ de U ′ . Portanto podemos supor, por hipótese de indução, que G′ tem um emparelhamento E ′ que satura U ′ . Finalmente, é claro que F ∪ E ′ é um emparelhamento em G que satura U . A expressão “teorema de Hall” é muitas vezes usada para designar a união da teorema de Hallproposição 4.2 com o teorema 4.3. Essa união constitui uma boa caracterização dos grafos (U,W )-bipartidos dotados de um emparelhamento que satura U . Emparelhamentos máximos em grafos bipartidos A subseção anterior preparou o terreno para a caracterização dos emparelhamentos máximos em grafos bipartidos. Em  , König4 demonstrou a delimitação inferior de α ′ que complementa a delimitação superior 4.1: Teorema 4.4 (König) Em todo grafo bipartido G tem-se α ′(G) ≥ β(G) . PROVA: Seja {U,W} uma bipartição de G . Basta provar que existe um empare- lhamento tão grande quanto uma cobertura. Seja C um cobertura mínima e defina C os conjuntos UC := U ∩ C, WC := W ∩ C,UC := U r C e WC := W r C . Seja H o subgrafo de G induzido por UC ∪ WC . É evidente que H é (UC ,WC)- H bipartido. Como mostraremos a seguir, a minimalidade de C garante que H satisfaz a hipótese do teorema de Hall. Seja X um subconjunto qualquer de UC . O conjunto (C r X) ∪ ΓH(X) é uma cobertura de G , pois toda aresta que tem uma ponta em X também tem uma ponta em ΓH(X) . Como a cardinalidade dessa cobertura é |C| − |X|+ |ΓH(X)| , a minima- lidade de C exige que tenhamos |ΓH(X)| ≥ |X| . 4 Dénes König (− ), matemático húngaro e autor do primeiro livro sobre a teoria dos grafos (Theorie der endlichen und unendlichen Graphen, Akademischen Verlagsgesellschaft, Leipzig, 1936). 42 CAP. 4 EMPARELHAMENTOS O teorema 4.3 permite concluir agora que H tem um emparelhamento F que sa- tura UC . Um argumento simétrico mostra que o subgrafo H ′ de G induzido por WC ∪ UC tem um emparelhamento F ′ que satura WC . Para concluir, observe que F ∪ F ′ é um emparelhamento em G e que |F ∪ F ′| = |F |+ |F ′| = |UC |+ |WC | = |C| , como queríamos provar. A combinação da delimitação 4.1 com o teorema 4.4 é conhecida como “teorema de König” ou “teorema de König–Egerváry”5. O teorema pode ser enunciado assim:teorema de König– Egerváry em todo grafo bipartido G , α ′(G) = β(G) , ou seja, um emparelhamento máximo tem a mesma cardinalidade que uma cober- tura mínima. Essa igualdade min-max é uma manifestação do teorema da dualidade em programação linear (veja por exemplo, o livro de Chvátal [Chv83]). Exercícios F 4.11 Mostre que o grafo da figura 4.1 não tem um emparelhamento que sature os cinco vértices que estão na parte superior da figura. E 4.12 Suponha dada uma coleção {C1, . . . , Ck} de subconjuntos de um certo con- junto W . Imagine que cada elemento de W é uma pessoa e cada Ci é o conjunto dos membros de um clube. Queremos escolher um conjunto de representantes distintos dos clubes, ou seja, um conjunto w1, . . . , wk de pessoas tal que wi ∈ Ci para cada i e wi 6= wj sempre que i 6= j . Mostre que um tal conjunto de representantes distintos existe se e somente se | ⋃ i∈I Ci| ≥ |I| para todo subconjunto I de {1, . . . , k} . E 4.13 Seja G um grafo (U,W )-bipartido tal que |U | = |W | . Seja M a matriz inde- xada por U ×W e definida por M [u,w] = 1 se uw é uma aresta de G e M [u,w] = 0 caso contrário. (Portanto, M é uma submatriz da matriz de adjacências de G , defi- nida no exercício 1.27.) O permanente da matriz M é o número6 perm(M) := ∑ π ( ∏ u∈U M [u, π(u)] ) , onde a soma se estende a todas as bijeções π : U→W . Mostre que o permanente de M é igual ao número de emparelhamentos perfeitos em G .7 5 Eugene Egerváry, matemático húngaro. 6 O permanente tem definição semelhante ao do determinante: no determinante, cada produto∏ M [u, π(u)] é precedido do sinal da permutação π . Existem algoritmos rápidos para calcular o determinante de uma matriz quadrada. No entanto, não se conhece um algoritmo rápido para o cálculo do permanente. Suspeita-se mesmo que um tal algoritmo não existe. 7 Essa relação entre permanentes e emparelhamentos foi útil para a descoberta de vários dos teoremas estudados neste capítulo (veja o livro de Lovász–Plummer [LP86]). 4.4 Emparelhamentos em grafos arbitrários 45 hipóteses). Suponha agora que n(G) > 1 e que o resultado é verdadeiro para grafos com menos que n(G) vértices. Suponha que G satisfaz as hipóteses e seja S∗ um subconjunto maximal de V (G) tal que i(G− S∗) = |S∗| . (O conjunto S∗ está bem definido pois i(G − s) = 1 para todo vértice s .) Sejam G1, . . . , Gk os componentes ímpares de G−S∗ , com k = i(G−S∗) . Sejam H1, . . . , Hl os componentes pares de G−S∗ . A maneira como escolhemos S∗ garante o sucesso dos três passos que passamos a descrever. 1. Seja F o grafo com conjunto de vértices {G1, . . . , Gk}∪S∗ cujas arestas são to- dos os pares Gis para os quais existe em G uma aresta da forma vs , com v em V (Gi) e s em S∗ . O grafo F é ({G1, . . . , Gk}, S∗)-bipartido e prova-se que satisfaz as hi- póteses do teorema de Hall 4.3. Portanto, F tem um emparelhamento que satura {G1, . . . , Gk} . 2. Para cada i e cada vértice v em Gi , prova-se que Gi − v satisfaz as hipóteses do teorema que estamos procurando provar. Logo, Gi− v tem um emparelhamento perfeito por hipótese de indução. 3. Prova-se que cada Hi satisfaz as hipóteses do teorema que estamos procu- rando provar. Assim, cada Hi tem um emparelhamento perfeito por hipótese de indução. Se tomarmos a união dos emparelhamentos descritos em 1, 2 e 3 acima, teremos um emparelhamento perfeito em G . A expressão “teorema de Tutte” é freqüentemente usada para designar a união teorema de Tutteda proposição 4.5 com o teorema 4.6. O teorema constitui uma boa caracterização dos grafos dotados de emparelhamentos perfeitos. Emparelhamentos máximos A caracterização dos emparelhamentos máximos em grafos arbitrários está intima- mente relacionada com o teorema de Tutte. É conveniente introduzir o seguinte parâmetro γ :9 para todo grafo G , seja γ(G) o valor mínimo da expressão 1 2 n(G)− 1 2 ( i(G− S)− |S| ) para todos os subconjuntos S de V (G) . Não é difícil estabelecer a seguinte delimi- tação superior: Delimitação 4.7 Para todo grafo G , tem-se α ′(G) ≤ γ(G) . Para provar essa delimitação, basta mostrar que, para todo S , qualquer empare- lhamento deixa de saturar pelo menos i(G− S)− |S| vértices. Os detalhes da prova são um bom exercício. 9 A letra “γ ” parece adequada nesse texto, mas não é notação padrão. 46 CAP. 4 EMPARELHAMENTOS Berge10 mostrou em  a delimitação inferior que complementa 4.7: Teorema 4.8 (Berge) Para todo grafo G , tem-se α ′(G) ≥ γ(G) . Para provar o teorema, basta mostrar que existe um emparelhamento E∗ e um conjunto S∗ tais que E∗ deixa de saturar i(G−S∗)−|S∗| vértices no máximo. Infeliz- mente, não temos espaço nesse texto para exibir os detalhes da prova. Ela pode ser encontrada nos livros de Diestel [Die00] e Lovász–Plummer [LP86], por exemplo. A combinação da delimitação 4.7 com o teorema 4.8 é conhecida como “teorema de Tutte–Berge” e pode ser formulada assim: em qualquer grafo G ,teorema de Tutte– Berge α ′(G) = γ(G) . Exercícios F 4.20 Suponha que um grafo G satisfaz a condição i(G − S) ≤ |S| para todo con- junto S de vértices. Prove, sem usar o teorema 4.6, que n(G) é par. E 4.21 Seja G um grafo e S um subconjunto de V (G) . Mostre que i(G − S) ≤ i(H − S) para qualquer subgrafo H de G tal que V (H) = V (G) . E 4.22 Na prova do teorema de Tutte 4.6, mostre que cada grafo Hi satisfaz a con- dição i(Hi − S) ≤ |S| para cada conjunto S de vértices. E 4.23 Na prova do teorema de Tutte 4.6, mostre que, para cada i e cada vértice v em Gi , o grafo Gi − v satisfaz a condição i((Gi − v) − S) ≤ |S| para cada conjunto S de vértices. E 4.24 Na prova do teorema de Tutte 4.6, mostre que o grafo F satisfaz as hipóteses do teorema de Hall 4.3: |ΓF (X)| ≥ |X| para cada subconjunto X de {G1, . . . , Gk} . E 4.25 Deduza o teorema de Hall 4.3 do teorema de Tutte 4.6. E 4.26 Seja G um grafo 3-regular sem cortes de tamanho 1 (ou seja, sem conjuntos X de vértices tais que |∇(X)| = 1). Mostre que G tem um emparelhamento perfeito. Mostre que nem todo grafo 3-regular tem um emparelhamento perfeito. E 4.27 Prove a delimitação 4.7. E 4.28 Deduza o teorema de König 4.4 do teorema de Berge 4.8. 10 Claude Berge (− ), matemático francês. 4.5 Considerações computacionais 47 4.5 Considerações computacionais Existem algoritmos rápidos11 (e muito interessantes) para encontrar um emparelha- mento máximo num grafo. O algoritmo específico para grafos bipartidos produz um emparelhamento e uma cobertura de mesma cardinalidade.12 O algoritmo mais geral aceita qualquer grafo e produz um emparelhamento e um conjunto de vértices que satisfazem a relação estabelecida no teorema 4.8.13 11 Os algoritmos consomem tempo limitado por um polinômio no número de vértices do grafo. 12 Veja os livros de Lovász–Plummer [LP86, p.12], Bondy–Murty [BM76, p.80] e Diestel [Die00, p.30]. 13 O algoritmo foi descoberto em  por Jack Edmonds. Veja o livro de Lovász–Plummer [LP86, p.358]. 50 CAP. 5 COLORAÇÃO DE ARESTAS Teorema 5.2 (König) Para todo grafo bipartido G tem-se χ ′(G) ≤ ∆(G) . PROVA: Nossa prova é uma indução no número de arestas de G . Se m(G) = 0 , a proposição é obviamente verdadeira. Suponha agora que m(G) > 0 . Seja xy uma aresta de G . Por hipótese de indução, o grafo G − xy admite uma coloração {E1, . . . , Ek} com k ≤ ∆(G − xy) cores. É claro que k ≤ ∆(G) . Se k < ∆(G) então {E1, . . . , Ek, {xy}} é a coloração de G desejada. Suponha no que segue que k = ∆(G) . Como gG(x) ≤ k , alguma cor Ej está ausente em x , ou seja, Ej ∩ ∇G(x) = ∅ . Analogamente, alguma cor Ei está ausente em y . Se i = j então Ei ∪ {xy} é um emparelhamento e portanto se acrescentarmos xy a Ei teremos uma coloração de G com ∆(G) cores. Suponha agora que i 6= j . Seja C o componente do grafo (V (G), Ei ∪ Ej) queC contém x . Como Ei e Ej são emparelhamentos e Ej está ausente em x , C é um caminho e suas arestas estão alternadamente em Ei e Ej . Suponha por um instante que y está em C . Então y é um extremo de C , pois Ei está ausente em y . Logo, o comprimento de C é par e assim C + xy é um circuito ímpar. Mas G não tem circuitos ímpares, em virtude do teorema 3.5. Assim, podemos garantir que y não está em C . Considere agora os conjuntos Fi := Ei ⊕ A(C) e Fj := Ej ⊕ A(C) .3 É fácil verificar que Fi ∪ {xy} e Fj são emparelhamentos mutuamente disjuntos. Portanto, se tro- carmos Ei por Fi ∪ {xy} e Ej por Fj , teremos uma coloração das arestas de G com ∆(G) cores. A combinação da delimitação inferior 5.1 com a delimitação superior 5.2 dá uma boa caracterização das colorações mínimas de arestas em grafos bipartidos. Ela pode ser reformulada assim: χ ′(G) = ∆(G) para todo grafo bipartido G . Exercícios E 5.9 Exiba colorações mínimas das arestas dos grafos representados nas figuras 4.1 e 4.2. E 5.10 Uma escola pode ser representada por um grafo (U,W )-bipartido: cada vér- tice em U é um professor, cada vértice em W é uma turma de alunos e um professor é adjacente às turmas para as quais deve dar aulas. Uma semana letiva é dividida em períodos (segunda-feira das 8h às 10h, segunda-feira das 10h às 12h, etc.) e cada 3 X ⊕ Y := (X r Y ) ∪ (Y r X) ≡ (X ∪ Y ) r (X ∩ Y ) . Esta é a diferença simétrica entre os conjuntos X e Y . 5.4 Delimitação superior 51 período é representado por uma cor. Uma coloração das arestas do grafo é uma pro- gramação das aulas da semana. Quantos períodos são necessários e suficientes para cumprir o programa de aulas?4 5.4 Delimitação superior É um tanto surpreendente que ∆ + 1 cores são suficientes para colorir as arestas de qualquer grafo. Esse fato foi descoberto em  por Vizing5 (e redescoberto em  por Gupta6): Teorema 5.3 (Vizing) Em todo grafo G tem-se χ ′(G) ≤ ∆(G) + 1 .7 PROVA: Nossa prova é uma indução no número de arestas de G . Se m(G) = 0 , a proposição é trivialmente verdadeira. Suponha agora que m(G) > 0 . Seja xy uma aresta de G . Por hipótese de indução, o grafo G − xy admite uma coloração com não mais que ∆(G − xy) + 1 cores. Digamos que {E0, . . . , Ek} é uma tal coloração. É claro que k ≤ ∆(G − xy) ≤ ∆(G) . Se k < ∆(G) então {E0, . . . , Ek, {xy}} é a coloração de G desejada. No que segue, vamos supor que k = ∆(G) e mostrar que G admite uma coloração com k + 1 cores. Diremos que uma cor Ei está presente em v se Ei ∩ ∇(v) 6= ∅ e ausente em v em caso contrário. Como temos ∆(G) + 1 , alguma cor está ausente em cada vértice do grafo. Um leque é uma seqüência (xy0, . . . , xyj) de elementos de ∇(x) , distintos dois a dois, dotada da seguinte propriedade: para h = 1, . . . , j , a cor de xyh está ausente em yh−1 . Seja (xy0, . . . , xyj) um leque maximal. Como j < ∆(G) = k , podemos ajustar a j notação (permutando E0, . . . , Ek se necessário) de modo que xyh ∈ Eh e Eh está ausente em yh−1 para h = 1, . . . , j . Temos dois casos a considerar: CASO 1: alguma cor está ausente em yj e em x . Podemos supor, sem perda de generalidade, que a cor ausente em x e yj é E0 . Para h = 1, . . . , j , troque Eh por (Eh r {xyh}) ∪ {xyh−1} . Isso produz uma coloração de G−xyj . Agora, aplique a cor E0 à aresta xyj , ou seja, troque E0 por E0 ∪ {xyj} . Isso produz a coloração de G desejada. CASO 2: toda cor ausente em yj está presente em x . Seja Ei uma cor ausente Ei 4 Este é o “problema da grade de horários” (timetabling problem). 5 Vadim G. Vizing (−), matemático russo. 6 Ram Prakash Gupta. 7 Convém não confundir a desigualdade χ ′ ≤ ∆ + 1 com a desigualdade χ ≤ ∆ + 1 discutida no teorema 3.2: as razões para a validade de uma e de outra são muito diferentes. 52 CAP. 5 COLORAÇÃO DE ARESTAS 24 5 1 3 6 rrr r r rr s " " " " b b b b T T T T x y3 y1 y2 y5 y6 y0 y4 −(3) −(4) −(1) −(5) −(0) −(6) −(2) −(4) 34 5 1 2 0 6 rrr r r rr s " " " " b b b b T T T T x y3 y1 y2 y5 y6 y0 y4 Figura 5.1: Ilustração da prova do teorema de Vizing 5.3. As cores são E0, . . . , Ek . Um rótulo p junto a uma aresta indica que a aresta está em Ep (a aresta xy0 não tem cor). Um rótulo −(p) junto a um vértice indica que Ep está ausente no vértice. A figura ilustra o subcaso 2A da prova, com j = 6 e i = 4 . O leque à esquerda mostra a coloração no início do subcaso 2A; o leque à direita mostra a coloração no fim do subcaso. em yj . Em virtude da maximalidade do leque, i ∈ {1, . . . , j−1} . Podemos su- por, sem perder generalidade, que E0 está ausente em x . Seja H o grafo induzidoE0 por E0 ∪ Ei : H := (V (G), E0 ∪ Ei) . Os componentes desse grafo são caminhos e circuitos. Ademais, gH(x) ≤ 1 , gH(yi−1) ≤ 1 e gH(yj) ≤ 1 , uma vez que E0 está ausente em x e Ei está ausente em yi−1 e em yj . Assim, os componentes de H que contêm x , yi−1 e yj são cami- nhos. Um dos dois subcasos a seguir se verifica: SUBCASO 2A: x e yi−1 estão em dois componentes distintos de H . Seja C o componente de H que contém yi−1 . Troque as cores E0 e Ei nesse componente. Mais formalmente, seja F0 := E0 ⊕ A(C) e Fi := Ei ⊕ A(C) e seja Fh := Eh para todo h distinto de 0 e de i . Observe que {F0, . . . , Fk} é uma coloração de G − xy0 e F0 esta ausente em x e em yi−1 . Ade- mais, (xy0, . . . , xyi−1) é um leque com relação à nova coloração. Portanto, uma troca de cores análoga à descrita no caso 1 produz uma coloração de G . Mais especificamente, basta trocar Fh por (Fh r {xyh}) ∪ {xyh−1} para h = 1, . . . , i−1 e trocar F0 por F0 ∪ {xyi−1} para obter a coloração de G desejada. SUBCASO 2B: x e yi−1 estão num mesmo componente de H . Nesse caso, x e yj estão em componentes diferentes de H . Seja C o componente de H que contém yj . Seja F0 := E0 ⊕ A(C) , Fi := Ei ⊕ A(C) e Fh := Eh para todo h distinto de 0 e de i . Observe que {F0, . . . , Fk} é uma coloração de G − xy0 e que F0 esta ausente em x e em yj . Como yi−1 não está em C , a cor Fi está ausente em yi−1 , e portanto a seqüência (xy0, . . . , xyj) é um leque com relação à nova coloração. Assim, uma troca de cores análoga à descrita no caso 1 produz uma coloração de G . Mais especificamente, basta trocar Fh DICIONÁRIO 55 inglês português knight (in chess) cavalo (do xadrez) length comprimento line graph grafo das arestas lower bound delimitação inferior matching emparelhamento maximal maximal maximum máximo minimal minimal minimum mínimo neighbor vizinho neighborhood vizinhança null vazio, nulo odd ímpar path caminho pawn (in chess) peão (do xadrez) polygon circuito queen (in chess) dama (do xadrez) random graph grafo aleatório rank posto rook (in chess) torre (do xadrez) set conjunto spanning subgraph subgrafo gerador stability number índice de estabilidade stable estável tree árvore two-colorable bicolorível upper bound delimitação superior vertex vértice vertex cover cobertura Apêndice B Alfabeto grego A teoria dos grafos, como outras áreas da matemática, recorre freqüentemente ao alfabeto grego: α A alfa ν N nü β B beta ξ Ξ ksi γ Γ gama o O ômicron δ ∆ delta π Π pi ε E epsilon ρ P rô ζ Z zeta σ Σ sigma η H eta τ T tau θ Θ teta υ Υ upsilon ι I iota ϕ Φ fi κ K kapa χ X qui λ Λ lambda ψ Ψ psi µ M mü ω Ω ômega O símbolo ∇ não pertence ao alfabeto grego. Dizem que o nome do símbolo — nabla — designa uma harpa egípcia. Não confunda ∇ com ∆ . 56 Bibliografia [AZ98] M. Aigner and G. M. Ziegler. Proofs from THE BOOK. Springer, 1998. 24, 30 [Big74] N. Biggs. Algebraic Graph Theory, volume 67 of Cambridge Tracts in Mathe- matics. Cambridge University Press, 1974. 30 [BLW76] N. L. Biggs, E. K. Lloyd, and R. J. Wilson. Graph Theory 1736–1936. Cla- redon Press, Oxford, 1976. [História da Teoria dos Grafos, com reprodução de artigos clássicos]. 5 [BM76] J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Mac- millan/Elsevier, 1976. [http://www.ecp6.jussieu.fr/pageperso/bondy/ books/gtwa/gtwa.html]. 5, 33, 47 [Bol98] B. Bollobás. Modern Graph Theory, volume 184 of Graduate Texts in Mathe- matics. Springer-Verlag, 1998. 5 [Chv83] V. Chvátal. Linear Programming. W. H. Freeman, 1983. 42 [Die00] R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, second edition, 2000. [http://www.math.uni-hamburg. de/home/diestel/books/graph.theory/index.html]. 5, 46, 47 [GJ79] M. R. Garey and D. S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. 5, 13, 28, 36, 53 [Har92] D. Harel. Algorithmics: The Spirit of Computing. Addison-Wesley, second edition, 1992. 5, 13, 28, 36, 53 [Lov93] L. Lovász. Combinatorial Problems and Exercises. North-Holland, second edition, 1993. 5 [LP86] L. Lovász and M. D. Plummer. Matching Theory, volume 29 of Annals of Discrete Mathematics. North-Holland, 1986. 5, 42, 46, 47 [Luc79] C. L. Lucchesi. Introdução à Teoria dos Grafos. 12o¯ Colóquio Brasileiro de Matemática. IMPA (Instituto de Matemática Pura e Aplicada), 1979. 5 57 60 ÍNDICE REMISSIVO coloração de arestas, 48 de vértices, 29 mínima, 29, 48 colorível, 29 comparabilidade, 12 complemento, 9 completo, 9 componente, 18 conexo, 18 ímpar, 44 comprimento de caminho, 16 de circuito, 16 conexo, 17 conjunto completo, 26 estável, 20 maximal, 20 máximo, 20 independente, 20 cor, 29, 48 ausente, 51 presente, 51 corte, 14 cubo, 10 D, 5 DD, 5 ∆(G) , 14 δ(G) , 14 dama do xadrez, 9 diferença simétrica, 50 Dilworth, 33 Egerváry, 42 emparelhamento, 37 que satura, 38 maximal, 37 máximo, 37 perfeito, 38 espaço dos ciclos, 17 dos cociclos, 15 dos cortes, 15 estável, 20 maximal, 20 máximo, 20 extremos de caminho, 16 F, 6 floresta, 17 g(v) , 14 Γ(X) , 14 Γ(v) , 14 G(n) , 19 grade, 10 grafo, 8 aleatório, 19 bicolorível, 33 bipartido, 34 bipartido completo, 11 complementar, 9 completo, 9 da dama, 9 da torre, 9 das arestas, 12 das palavras, 10 de Catlin, 32 de comparabilidade, 12 de Grötzsch, 33 de intervalos, 12 de matriz simétrica, 10 de Mycielski, 33 de Petersen, 11 de Turán, 23 do bispo, 9 do cavalo, 9 do rei, 9 dos estados, 10 grade, 10 planar, 12 regular, 14 simples, 8 vazio, 9 grau, 14 máximo, 14 mínimo, 14 Grötzsch, 33 grupo, 13 Hall, 40 hexágono, 16 hidrocarbonetos, 11 ÍNDICE REMISSIVO 61 i(G) , 44 incide, 8 independente, 37 índice cromático (χ ′ ), 48 de estabilidade (α), 20 intervalos, 12 isomorfismo, 12 Kn , 9 Kn , 9 König, 41, 50 L(G) , 12 laços, 8 leque de arestas, 51 line graph, 12 m(G) , 9 matriz de adjacências, 15 positiva semidefinida, 24 maximal, 20, 37 máximo, 20, 37 min-max, 42 mínima, 29, 48 Mycielski, 33 n(G) , 9 nabla (∇), 14 número cromático (χ), 29 de Bell, 36 de cores, 29 de Ramsey, 27 ω , 26 ordem parcial, 12 palavras, 10 par não-ordenado, 8 partição, 29 pentágono, 16 Petersen, 11 planar, 12 ponta de aresta, 8 posto de matriz, 24 programação linear, 42 quadrado, 16 quase todo, 19 quatro cores, 30, 53 Ramsey, 27 regular, 14 rei do xadrez, 9 representantes distintos, 42 satura (emparelhamento), 38 semidefinida (matriz), 24 slither, 38 subgrafo, 17 induzido, 17 maximal, 18 próprio, 17 teorema da dualidade, 42 das 4 cores, 30, 53 de Berge, 46 de Bollobás, 36 de Brooks, 31 de Dilworth, 33 de Hall, 40 de König, 41, 50 de König–Egerváry, 42 de Turán, 23 de Tutte, 44 de Tutte–Berge, 46 de Vizing, 51 torre do xadrez, 9 triângulo, 16 Turán, 23 Tutte, 44 vazio, 9 vértice, 8 saturado, 38 vértices adjacentes, 8 Vizing, 51 vizinhança, 14 vizinho, 8 χ , 29 χ ′ , 48 xadrez, 9