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

Páginas: 74 (18291 palavras) Publicado: 25 de junho de 2011
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.5Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . .. . . . . . . . . . . . . . . . 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 termostécnicos 54
B Alfabeto grego 56
Bibliografia 58
Índice Remissivo 59
Prefácio
Este texto é uma breve introdução à Teoria dos Grafos. Para embarcar nessa introdução,
o leitor1 só precisa ter alguma familiaridade com demonstrações matemáticas
formais e com a notação básica da teoria dos conjuntos elementar.
A teoria dos grafos estuda objetos combinatórios—os grafos—que são umbom
modelo paramuitos problemas em vários ramos da matemática, da informática, da
engenharia e da indústria. Muitos dos problemas sobre grafos tornaram-se célebres
porque são um interessante desafio intelectual e porque têm importantes aplicações
práticas.
Nesta breve introdução, vamos nos restringir a quatro temas intimamente relacionados:
conjuntos estáveis, coloração de vértices, emparelhamentos e coloraçãode arestas. Muitos outros temas e problemas, podem ser encontrados nos livros
de Bondy–Murty [BM76], Wilson [Wil79], Diestel [Die00], Bollobás [Bol98],
Lovász [Lov93], Lovász–Plummer [LP86], Lucchesi [Luc79] e Biggs–Lloyd–Wilson
[BLW76].
Mesmo numa breve introdução como esta, é inevitável esbarrar em questões
de complexidade computacional, pois muitos dos problemas da teoria dos grafos...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Teoria y
  • Teoria de y
  • Teoria Y
  • Teoria Y
  • Teoria x e Teoria y
  • A teoria x e Teoria y
  • TEORIA X E TEORIA Y
  • A teoria x e a teoria y

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!