Teoria de Grafos

Teoria dos Grafos - Mestrado e Doutorado - UFRJ - 2007
COPPE/Sistemas e IM/NCE
Profs. Celina M. H. de Figueiredo e Fábio Protti

Horário
3as e 4as, das 10:00 às 12:00

Locais:

1. COPPE/Sistemas -- sala H-324 A

2. NCE -- sala NCE 02

Provas
Primeira Prova - 11/07 - PEGUE O GABARITO
Segunda Prova - 05/09

Listas

entregar Listas 1,2,3 até 31/07

entregar Listas 4,5 até 22/08

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.

Links Interessantes
Manual de Referência de Teoria dos Grafos da Florida Atlantic University

Glossário de Teoria dos Grafos da Wikipedia

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.
Teorema 2: Se T é uma árvore então m=n-1.
Def.: Uma folha de uma árvore é um vértice de grau um.
Corolário 3: Toda árvore não trivial tem pelo menos duas folhas.
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 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 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 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 disjuntos internamente 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 disjuntos internamente
entre eles.
Corolário: G é biconexo com pelo menos três vértices 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 disjuntos internamente
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 comprimento 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 não é M-saturado.
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 dos Casamentos Estáveis: 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 maior.
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 G 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): x(G) <= Delta(G), se G é conexo e não é
uma clique nem um ciclo ímpar.

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 é 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, 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 de seus vértices; 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 de comprimento pelo menos x(G)-1. 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.