Área do Usuário

Login

Teoria dos Grafos

Gratuita          572KB          Publicado: 22/12/2009

4830 downloads

Um grafo é um par (V,A) em que V é um conjunto arbitrário e A é um subconjunto de V (2) . Os elementos de V são chamados vértices e os de A são chamados arestas. Neste texto, vamos nos restringir a grafos em que o conjunto de vértices é finito

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
34
4 Emparelhamentos 37
4.1 Emparelhamentos máximos . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Delimitação superior . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Emparelhamentos em grafos bipartidos . . . . . . . . . . . . . . . 39
4.4 Emparelhamentos em grafos arbitrários . . . . . . . . . . . . . . . 43
4.5 Considerações computacionais . . . . . . . . . . . . . . . . . . . . 47
5 Coloração de arestas 48
5.1 Colorações mínimas . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Delimitação inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3 Grafos bipartidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.4 Delimitação superior . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.5 Considerações computacionais . . . . . . . . . . . . . . . . . . . . 53
A Dicionário de termos técnicos 54
B Alfabeto grego 56
Bibliografia 58
Índice Remissivo 59

(cc) Licença Creative Commons 2008 - 2018 Apostilaz.com.br