trabalho de afd
18062 palavras
73 páginas
Uma Introdução Sucinta à Teoria dos Grafos http://www.ime.usp.br/~pf/teoriadosgrafos/ P. FeofiloffY. Kohayakawa
Y. Wakabayashi
9/8/2007
2
Sumário
1
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
2
Conceitos básicos
Grafos aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
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
3
Conjuntos estáveis, cliques e coberturas
Considerações computacionais . . . . . . . . . . . . . . . . . . . .
28
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