Teoria dos Grafos 2022-1

Pós-Graduação em Computação – IC/UFF
Professor Fábio Protti 

 

Horário:

Segundas e quartas, 9:00 – 11:00

 Formato:

·       Exposição de conteúdo

·       Resolução de exercícios

·       Atendimento de dúvidas

 

Bibliografia

1. D. B. West.  Introduction to Graph Theory. Prentice-Hall, New Jersey, 1996.

2. R. Diestel. Graph Theory. Springer, New York, 1997.

3. J. A. Bondy e U. S. R. Murty. Graph Theory with Applications. Elsevier, New York, 1979.

4. F. Harary. Graph Theory. Addison-Wesley, Reading, Massachusetts, 1969.

5. C. Berge. Graphs and Hypergraphs. Dunod, Paris, 1970.

6. B. Bollobás. Graph Theory: an Introductory Course. Springer, New York, 1979.

7. B. Bollobás. Modern Graph Theory. Graduate Texts in Mathematics 184, Springer-Verlag, NY, 1988.

8. M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.

9. G. Chartrand. Introductory Graph Theory. Dover, New York, 1997. 

10. N. L. Biggs, E. K. Lloyd e R. J. Wilson. Graph Theory: 1736-1936. Clarendon Press, Oxford, 1986.

11. T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley Interscience, 1995.

12. O. Ore. Graphs and their Uses.  New Mathematical Library 10, Mathematical Association of America, Washington D.C., 1990.

13. R. J. Wilson. Introduction to Graph Theory. Longman, Harlow, Essex, 1985. 

14. R. J. Wilson e J. J. Watkins. Graphs - An Introductory Approach. John Wiley & Sons, 1990.

15. R. M. Barbosa. Combinatória e Grafos. Nobel, 1975.

16. P. O. Boaventura Netto. Teoria e Modelo de Grafos. Edgard Blucher, SP, 1996. 

17. P. O. Boaventura Netto. Grafos: Teoria, Modelos, Algoritmos. Edgard Blucher, SP, 1996.

18. P. Feofiloff e C. L. Lucchesi. Algoritmos para Igualdades Minimax em Grafos. Sexta Escola de Computação, Campinas, 1988.

19. A. L. Furtado. Teoria de Grafos-Algoritmos. LTC, Rio de Janeiro, 1973.

20. C. L. Lucchesi. Introdução à Teoria dos Grafos. 12o. Colóquio de Matemática. Poços de Caldas, 1979. 

21. C. L. Lucchesi, I. Simon, J. Simon e T. Kowaltowski. Aspectos Teóricos da Computação. IMPA, Projeto Euclides, Rio de Janeiro, 1979. 

22. J. L. Szwarcfiter. Grafos e Algoritmos Computacionais. Campus, Rio de Janeiro, 1986.

 

 

Tópicos do Curso

 

Conceitos Básicos
Grafo simples, vértices, arestas, ordem, tamanho, multigrafo, laços, representação geométrica de grafos, vértices adjacentes, vizinhanças aberta e fechada, vértice isolado, vértice universal, extremos de uma aresta, complemento de um grafo, subgrafo, subgrafo próprio, subgrafo gerador, subgrafo induzido por um conjunto de vértices, subgrafo induzido por um conjunto de arestas, propriedade hereditária, grafos disjuntos (em vértices ou arestas), união de dois grafos, interseção de dois grafos, grau de um vértice, graus mínimo e máximo de um grafo, grafo regular, grafo k-regular, Teorema do Aperto de Mãos, sequência de graus, grafos isomorfos,  grafo trivial, grafo completo, clique, grafo nulo, conjunto independente ou estável, grafo bipartido, grafo bipartido completo, passeio, trilha, caminho, passeio fechado, ciclo, corda, ciclo induzido, grafos conexos e desconexos,  conjuntos maximais e máximos, conjuntos minimais e mínimos, componentes conexos, distância entre dois vértices, excentricidade de um vértice, diâmetro de um grafo, centro de um grafo, matriz de adjacências, caracterização de grafos bipartidos (G é bipartido sss G não contém ciclos de comprimento ímpar).

 

Árvores
Def.: Um grafo é acíclico se não possui ciclos.
Def.: Uma árvore é um grafo acíclico e conexo.
Def.: Uma floresta é um grafo acíclico (cada componente conexo de uma floresta é uma árvore).
Teorema 1: Um grafo T é uma árvore sss existe um único caminho entre cada par de vértices de T.
Def.: Uma folha de uma árvore é um vértice de grau um.
Teorema 2: Toda árvore não trivial tem pelo menos duas folhas.

Teorema 3: Se T é uma árvore então m=n-1. 
Lema: Seja T uma árvore com pelo menos três vértices. Seja F o conjunto das folhas de T. Seja T'=T-F. Então, T e T' têm o mesmo centro.
Teorema 4: (Jordan 1869) O centro de uma árvore ou é formado por apenas um vértice ou por dois vértices vizinhos.
Def. Uma ponte ou aresta de corte de um grafo G é uma aresta e tal que w(G-e)> w(G).
Teorema 5: Uma aresta e é uma ponte de G sss não existe ciclo contendo e em G.
Teorema 6: Um grafo conexo T é uma árvore sss cada aresta de T é uma ponte.
Def. Uma árvore geradora de um grafo G é um subgrafo gerador conexo e acíclico de G.
Fato: Todo grafo conexo possui uma árvore geradora. A idéia para verificar isto é ir retirando as arestas uma a uma de modo a manter o grafo conexo. Quando isto não for mais possível, as arestas remanescentes formam uma árvore geradora.
Teorema 7: Se G é conexo, então m >= n-1.

 

Conectividade
Def. Um conjunto de vértices V' contido em V(G) é um separador ou corte de vértices de G se w(G-V') > w(G).
Fato: Um grafo completo não admite cortes de vértices.
Def. Um conjunto desconectante de arestas é um conjunto E' contido em E(G) tal que w(G-E') > w(G).
Notação: Se S, T são subconjuntos de vértices de um grafo, então [S,T] é o conjunto de arestas de G que têm um extremo em S e outro em T.
Def: Seja S um subconjunto próprio e não vazio de vértices de um grafo G. Então, [S, V-S] é um corte de arestas.
Fato: Todo corte de arestas é um conjunto desconectante.
Teorema: Todo conjunto desconectante minimal é um corte de arestas.
Def: Um corte de arestas minimal é chamado de ligação, liga, bond ou co-ciclo. Observe que uma ponte é uma ligação.
Def: Seja H um subgrafo de G. O complemento de H em relação a G é o grafo G-E(H).
Def: Se T é uma árvore geradora de G então o complemento de T em relação a G é chamada co-árvore de T.
Teorema: A co-árvore C de uma árvore geradora T de um grafo G não contém cortes de arestas de G. Além disso, se e é uma aresta de T, então C+e contém um único co-ciclo.
Def: Um vértice v é uma articulação ou vértice de corte se w(G-v) > w(G).
Lema: Se v é articulação então existem dois vértices x, y distintos de v tais que todo caminho entre x e y contém v.
Teorema: Em uma árvore T não trivial, v é uma articulação sss v não é folha.
Corolário: Todo grafo conexo G não trivial possui pelo menos 2 vértices que não são articulações.
Def: A conectividade de arestas k'(G) de um grafo conexo não trivial G é a cardinalidade de um corte de arestas mínimo. Definimos k'(G)=0 se G é trivial ou desconexo.
Def: A conectividade de vértices k(G)  de um grafo conexo G é a cardinalidade de um corte de vértices mínimo, desde que G não seja completo. Definimos k(G)=n-1 se G é um grafo completo com n vértices, e k(G)=0 se G é trivial ou desconexo.
Nomenclatura: Dizemos que G é p-conexo em vértices [ arestas ] se  p <= k(G) [ p <= k'(G) ]. É claro que todo grafo conexo não trivial é 1-conexo (em vértices ou arestas).
Teorema (Whitney 1932): Se G é conexo, então k(G) <= k'(G) <= delta(G).
Proposição: Seja S contido em V(G). Então, a cardinalidade do corte [S, V-S] é igual à soma dos graus dos vértices em S menos duas vezes o número de arestas do grafo G[S].
Corolário: Se para algum subconjunto de vértices S de V(G) próprio e não vazio vale | [S, V-S] |  < delta(G), então | S | > delta(G).
Proposição: Se G é conexo e S é um subconjunto próprio e não vazio de V(G), então F= [S, V-S] é ligação sss G-F tem dois componentes conexos.
Fato: Um grafo conexo G com pelo menos três vértices é biconexo sss G não possui articulações.
Def: Um bloco de um grafo G é um subgrafo maximal conexo sem articulações.
Fato: Dois blocos diferentes em um grafo têm no máximo um vértice em comum.
Fato: Cada aresta de um grafo G está em um único bloco. Portanto, os blocos formam uma partição de E(G).
Def: Dois caminhos de u a v são internamente disjuntos se eles têm apenas os extremos em comum.
Teorema (Whitney 1932): Seja G um grafo com pelo menos três vértices. Então, G é biconexo sss para quaisquer dois vértices de G existem dois caminhos internamente disjuntos entre eles.
Corolário: Um grafo G com pelo menos três vértices é biconexo sss existe um ciclo que passa por cada par de vértices arbitrários de G.
Teorema (Menger): Um grafo com pelo menos k+1 vértices é k-conexo (em vértices) sss para quaisquer dois vértices de G existem k caminhos internamente disjuntos entre eles. [Este resultado é uma generalização do Teorema de Whitney.]
Teorema (Menger - versão arestas): G é k-conexo em arestas sss para quaisquer dois vértices de G existem k caminhos disjuntos em arestas entre eles.

 

Grafos Eulerianos e Hamiltonianos
Def: Um passeio Euleriano ou trilha fechada ou passeio de Euler de G é um passeio fechado que contém cada aresta de G exatamente uma vez. Um grafo é Euleriano se ele possui um passeio de Euler.
Teorema (Euler, 1736): Um grafo G conexo é Euleriano sss todo vértice de G possui grau par. [ Este resultado vale também para multigrafos. ] Uma demonstração consiste em executar o Algoritmo de Tucker: particionar G em ciclos simples e compor os ciclos até formar um passeio Euleriano. Este algoritmo é O(m).
Problema do Carteiro Chinês: Dado um grafo com pesos não negativos nas arestas, deseja-se um passeio fechado de comprimento mínimo que passe por todas as arestas.
Def: Um passeio Euleriano aberto é um passeio não fechado em G tal que toda aresta de G aparece exatamente uma vez no passeio.
Corolário: Um grafo conexo não Euleriano possui passeio Euleriano aberto sss existem exatamente 2 vértices de G com grau ímpar.
Def: Um ciclo [caminho] Hamiltoniano em um grafo G é um ciclo [caminho] que contém todos os vértices de G, uma vez cada. G é Hamiltoniano quando possui um ciclo Hamiltoniano.
Fato: Todo grafo Hamiltoniano é biconexo.
Teorema [condição necessária para um grafo ser Hamiltoniano]: Se G é um grafo Hamiltoniano, então todo subconjunto S de V(G) próprio e não vazio satisfaz w(G-S) <= | S |.  [ Para verificar que esta condição não é suficiente, tome o grafo de Petersen ].
Princípio da Casa de Pombo: "Se existirem n pombos em m < n casas, então existe pelo menos uma casa com no mínimo 2 pombos". Este princípio é usado na demonstração do próximo teorema.
Teorema (Dirac, 1952) [ condição suficiente para um grafo ser Hamiltoniano ]: Todo grafo com n >= 3 e delta(G) >=n/2 tem um ciclo Hamiltoniano.
Teorema (Ore, 1960): Se G é um grafo com n >= 3 e tal que para todo par de vértices distintos não adjacentes  u e v vale d(u)+d(v) >= n, então G é Hamiltoniano. [ Este resultado é mais forte do que o anterior, no sentido de que pode-se provar Dirac usando Ore ].
Lema 1: Seja G um grafo e a,b dois vértices não adjacentes de G satisfazendo d(a)+d(b) >= n. Então, G é Hamiltoniano sss G+(a,b) é Hamiltoniano.
Def: O fecho de um grafo G é o grafo C(G) obtido de G por sucessivas adições de arestas ligando pares de vértices não adjacentes cuja soma de graus seja >= n.
Lema 2: C(G) é bem definido (único).
Teorema (Bondy e Chvátal, 1976): G é Hamiltoniano sss C(G) é Hamiltoniano. [ A prova da necessidade é trivial; a prova da suficiência consiste em sucessivas aplicações do Lema 1 ].
Corolário: Se  C(G) é completo então G é Hamiltoniano.
Problema do Caixeiro Viajante: Dado um grafo completo G com pesos nas arestas, deseja-se obter um ciclo Hamiltoniano de G com peso mínimo.

 

Emparelhamentos
Def: Dado um grafo G, um subconjunto M de arestas de G tal que seus elementos não são adjacentes 2 a 2 é dito um emparelhamento de G.
Def: Um emparelhamento M satura um vértice v se alguma aresta de M é incidente a v. Neste caso, v é dito M-saturado. Caso contrário, v é M-insaturado.
Def: M é um emparelhamento maximal se não existe nenhum outro que o contém propriamente.
Def:  M é um emparelhamento máximo se não existe nenhum outro de cardinalidade maior.
Def: M é um emparelhamento perfeito se satura todo vértice do grafo.  Obs: Todo emparelhamento perfeito é máximo, mas a recíproca não vale.
Def: Seja M um emparelhamento em G. Um caminho M-alternante em G é um caminho tal que suas arestas alternadamente pertencem a M ou não. Este caminho será dito M-aumentante se os seus extremos inicial e final não são M-saturados.
Obs: o comprimento de um caminho M-aumentante é sempre ímpar.
Teorema (Berge, 1957): Um emparelhamento M em G é máximo se e somente se G não contém nenhum caminho M-aumentante.
Problema do Casamento: Dado um conjunto Y de rapazes e um conjunto X de moças com |Y| >= |X|, qual é a condição necessária e suficiente para que cada moça se case com um rapaz de que ela goste? A resposta para esta questão está no próximo teorema.
Def: Dado S um subconjunto de vértices de V(G), denotamos por N(S) ao conjunto de todos os vértices adjacentes a vértices de S.
Teorema (Hall, 1935): Seja G um grafo bipartido com partição de vértices V=X U Y. Então, G contém um emparelhamento que satura todo vértice de X se e somente se |N(S)| >= |S|, para todo subconjunto S de X.
Corolário: Se G é um grafo bipartido k-regular, k > 0, então G tem um emparelhamento perfeito.
Def: Uma cobertura de um grafo G é um subconjunto de vértices K de V(G) tal que toda aresta de G tem pelo menos um de seus extremos em K. A cobertura será mínima se não houver nenhuma outra de cardinalidade menor.
Fato: Para qualquer emparelhamento M e para qualquer cobertura K de um grafo G vale |M| <= |K|. O próximo teorema identifica uma classe de grafos para os quais a igualdade é atingida no caso limite.
Lema: Sejam M um emparelhamento e K uma cobertura de um grafo G tais que |M|=|K|. Então, M é máximo e K é mínima.
Teorema (König, 1931): Em um grafo bipartido, o número de arestas em um emparelhamento máximo é igual ao número de vértices em uma cobertura mínima.
Problema: Dado um grafo bipartido G com partição de vértices V=X U Y onde |X|=|Y|, encontrar um emparelhamento perfeito em G ou um certificado de que este tipo de emparelhamento não existe. O método húngaro fornece uma solução para o problema, e está bem descrito no livro de Bondy & Murty (número 3 da bibliografia).

 

Coloração de Arestas
Def: Uma k-coloração de arestas de um grafo G é uma atribuição de k cores 1,2,...,k às suas arestas. Esta coloração será própria se arestas adjacentes tiverem cores diferentes; neste caso,  cada conjunto de arestas de mesma cor é um emparelhamento.
Def: Um grafo é k-colorível em arestas se admitir uma k-coloração própria de arestas. Obviamente, todo grafo é m-colorível em arestas (m=|E(G)|). Além disso, se G é k-colorível, então G é r-colorível para todo r >= k.
Def: O índice cromático x'(G) de um grafo G é o menor k para o qual G é k-colorível. Obviamente, x'(G) >= Delta(G).
Def: Diz-se que uma cor i está representada no vértice v quando alguma aresta incidente a v possui a cor i.
Lema: Seja G um grafo conexo que não é um ciclo ímpar. Então existe uma 2-coloração de G tal que, em todo vértice de grau maior que um, as duas cores estão representadas.
Def: c(v) é o número de cores representadas no vértice v numa k-coloração de arestas C de um grafo G. Observe que C é própria sss c(v)=d(v).
Def: Uma k-coloração C' é uma melhoria de uma k-coloração C se a soma dos valores c'(v) é estritamente maior que a soma dos valores c(v). Uma k-coloração é ótima quando não admite melhoria.
Lema: Seja G um grafo com uma k-coloração ótima tal que existe um vértice u onde uma certa cor 0 não está representada em u e uma certa cor 1 está representada pelo menos duas vezes em u. Então, a componente conexa H de G[E₀ U E₁] que contém u é um ciclo ímpar.
Teorema: O índice cromático de um grafo bipartido é Delta.
Teorema (Vizing 1964, Gupta 1966, Fournier 1973) O índice cromático de um grafo qualquer é menor ou igual a Delta + 1.

 

Coloração de Vértices
Def: Uma k-coloração de vértices é uma atribuição de k cores aos vértices de um grafo. Esta coloração é própria quando vértices adjacentes reccebem cores distintas.
Obs: Um k-coloração própria particiona o conjunto de vértices do grafo em k conjuntos independentes.
Def: G é dito k-colorível se G admite uma k-coloração própria de vértices. O número cromático de G, denotado por x(G), é o menor inteiro k para o qual G é k-colorível.
Def: Um grafo G é crítico se x(H) < x(G) para todo subgrafo próprio H de G. Um grafo G é k-crítico quando for crítico e k-cromático.
Obs:  Todo grafo crítico é conexo, e todo grafo k-cromático tem um subgrafo k-crítico.
Teorema: Se G é k-crítico então delta(G) >= k-1.
Corolário: Todo grafo k-cromático possui pelo menos k vértices de grau >= k-1.
Cotas inferiores para o número cromático
1. x(G) >= w(G), onde w(G) é o número de vértices da maior clique de G.
2. x(G) >= n / alfa(G), onde alfa(G) é o numero de vértices do maior conjunto estável em G.
Cotas superiores para o número cromático
1. x(G) <= n (trivial)
2. x(G) <= Delta(G)+1
3. (Teorema de Brooks, 1941): Se G é conexo e não é uma clique nem um ciclo ímpar então x(G) <= Delta(G).
 

Planaridade

Def: Um grafo G é planar se existe uma representação (desenho, imersão) de G no plano de modo que as arestas se encontrem somente nos vértices, isto é, de modo que as arestas não se cruzem. Uma tal representação de G é dita plana ou planar. Uma representação planar divide o plano em regiões chamadas faces. Existe sempre uma única face chamada externa ou infinita, que não está limitada (tem área infinita). Qualquer representação planar de G possui sempre o mesmo número de faces; portanto, o número de faces de um grafo planar é uma invariante do mesmo. 

Fato: Se G é planar, todo subgrafo de G é planar.

Def: A fronteira de uma face f de um grafo planar conexo é um passeio fechado de arestas que limita e determina a face. Neste passeio, cada ponte é atravessada duas vezes. Notação: b(f) denota a fronteira da face f. 

Def: O grau de uma face f é o comprimento do passeio fechado que determina sua fronteira. Notação: d(f) é o grau da face f. 

Fato: A soma dos graus das faces de um grafo planar é igual ao dobro do seu número de arestas. 

Fórmula de Euler: Num grafo conexo planar com f faces, n vértices e m arestas, vale: f = m - n + 2. 

Corolário: Se G é um grafo planar simples com n >= 3, então m <= 3n - 6. 

Corolário: Se G é um grafo planar simples livre de triângulos com n >= 3, então m <= 2n - 4.

Corolário: Os grafos K_5 e K_{3,3} não são planares. 

Corolário: Se G é um grafo planar simples, então existe um vértice de G com grau <= 5. 

Def: A espessura (thickness) t(G) de um grafo G é o menor número de grafos planares cuja união é G. Claramente, G é planar se e só se t(G) =1. Um limite inferior para t(G) é o teto de m / (3n - 6). 

Def: Uma subdivisão de G é um grafo obtido de G pelo acréscimo de vértices de grau 2 ao longo das arestas de G. 

Lema: Se G é planar, toda subdivisão de G também é planar. 

Teorema de Kuratowski: Um grafo G é planar se e somente se G não contém subdivisão de K_5 ou K_{3,3}. 

Def: Uma contração de G é um grafo obtido de G pela identificação de dois vértices (adjacentes); a vizinhança do novo vértice contraído é igual à união das vizinhanças dos vértices originais. 

Teorema: Um grafo G é planar se e somente se G nenhum subgrafo de G possui K_5 ou K_{3,3} como contração. 

Def: Dado um grafo planar G, definimos seu dual G* da seguinte forma: a cada face f de G corresponde um vértice f* de G*, e a cada aresta e de G corresponde uma aresta e* de G*; além disso, dois vértices f* e g* de G* são ligados por uma aresta e* se e somente se as faces f e g em G são separadas pela aresta e. 

Fato: Se G é planar, então G* é planar. 

Fato: Se G é conexo, (G*)*  é isomorfo a G. 

Teorema das 4 cores (versão mapas): Em qualquer mapa, as regiões podem ser coloridas com (até) 4 cores, de modo que regiões adjacentes recebam cores distintas. 

Dualizando, temos: 

Teorema das 4 cores (versão grafos): Todo grafo planar é 4-colorível. 

    

Grafos Direcionados
Definições básicas: digrafos, arcos, arestas divergentes e convergentes, subdigrafo, grafo subjacente, orientação de um grafo, graus de entrada e saída, fontes e sumidouros, predecessores e sucessores, passeios/caminhos/ciclos direcionados, alcançabilidade, digrafo fortemente conexo, componentes fortemente conexos, digrafo unilateralmente conexo, digrafo fracamente conexo, digrafo desconexo, digrafo acíclico, redução transitiva de um digrafo, fecho transitivo de um digrafo.
Teorema (Gallai, 1968)  Dada uma orientação D de um grafo G, D possui um caminho direcionado com pelo menos x(G) vértices. Além disso, G possui uma orientação onde a igualdade se verifica.
Def: Um torneio é uma orientação de um grafo completo.
Corolário: Todo torneio possui um caminho Hamiltoniano.
Def: Um rei é um vértice que alcança qualquer outro vértice do grafo com no máximo dois arcos.
Teorema: Todo torneio tem um rei.