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[E0 U E1]
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.