Uma introdução sucinta à teoria dos grafos - p. feofiloff y. kohayakawa y. wakabayashi 11/5/2009

Uma Introdução Sucinta à Teoria dos Grafos http://www.ime.usp.br/~pf/teoriadosgrafos/ P. Feofiloff
Y. Kohayakawa
Y. Wakabayashi
11/5/2009
2
Sumário
1 Conceitos básicos 8
1.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Alguns exemplos de grafos . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Isomorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Vizinhanças, cortes e graus . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 Caminhos e circuitos . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6 Subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.7 Grafos conexos e componentes . . . . . . . . . . . . . . . . . . . . 17
1.8 Grafos aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Conjuntos estáveis, cliques e coberturas 20
2.1 Conjuntos estáveis máximos . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Delimitações inferiores . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Delimitações superiores . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 O índice de estabilidade da maioria dos grafos . . . . . . . . . . . 24
2.5 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6 Coberturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.7 Considerações computacionais . . . . . . . . . . . . . . . . . . . . 28
3 Coloração de vértices 29
3.1 Colorações mínimas . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Algumas delimitações superiores . . . . . . . . . . . . . . . . . . . 30
3.3 Algumas delimitações inferiores . . . . . . . . . . . . . . . . . . . 31
3.4 Bicoloração e grafos bipartidos . . . . . . . . . . . . . . . . . . . . 33
3.5 O número cromático da maioria dos grafos . . . . . . . . . . . . . 35
3.6 Considerações computacionais . . . . . . . . . . . . . . . . . . . . 36
3
4
4 Emparelhamentos 37
4.1 Emparelhamentos máximos . . . . . .