Teória dos Grafos

Teória dos Grafos

(Parte 1 de 10)

Uma Introdução Sucinta à Teoria dos Grafos http://www.ime.usp.br/~pf/teoriadosgrafos/

P. Feofiloff

Y. Kohayakawa Y. Wakabayashi

Sumário

1.1 Grafos8
1.2 Alguns exemplos de grafos9
1.3 Isomorfismo12
1.4 Vizinhanças, cortes e graus14
1.5 Caminhos e circuitos16
1.6 Subgrafos17
1.7 Grafos conexos e componentes17
1.8 Grafos aleatórios19

1 Conceitos básicos 8

2.1 Conjuntos estáveis máximos20
2.2 Delimitações inferiores21
2.3 Delimitações superiores23
2.4 O índice de estabilidade da maioria dos grafos24
2.5 Cliques26
2.6 Coberturas27
2.7 Considerações computacionais28

2 Conjuntos estáveis, cliques e coberturas 20

3.1 Colorações mínimas29
3.2 Algumas delimitações superiores30
3.3 Algumas delimitações inferiores31
3.4 Bicoloração e grafos bipartidos3
3.5 O número cromático da maioria dos grafos35
3.6 Considerações computacionais36

3 Coloração de vértices 29 3

4.1 Emparelhamentos máximos37
4.2 Delimitação superior38
4.3 Emparelhamentos em grafos bipartidos39
4.4 Emparelhamentos em grafos arbitrários43
4.5 Considerações computacionais47
5.1 Colorações mínimas48
5.2 Delimitação inferior49
5.3 Grafos bipartidos49
5.4 Delimitação superior51
5.5 Considerações computacionais53

5 Coloração de arestas 48

A Dicionário de termos té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 um bom modelo para muitos 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ção de 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 têm motivação algorítmica. O leitor interessado em aprofundar seus conhecimentos nessa área pode consultar os livros de Garey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97].

Estas notas foram preparadas para um mini-curso na I Bienal da SBM (Sociedade Brasileira de Matemática), realizada em Salvador em outubro de 2004. Uma versão corrigida do texto, bem como bibliografia adicional e apontadores para material na internet, podem ser encontrados em http://www.ime.usp.br/~pf/teoriadosgrafos/

Exercícios

O texto contém vários exercícios. Alguns são bastante simples e servem apenas para que o leitor confira seu entendimento do assunto. Outros levantam assuntos que não serão abordados no texto propriamente dito.

Os exercícios que julgamos difíceis têm prefixo D, os muito difíceis têm prefixo D

D, e os problemas em aberto têm prefixo A. O prefixo dos exercícios particular- D A

1 No que segue, todas as ocorrências de “leitor” devem ser entendidas como “leitora e leitor”. Para nós, as leitoras são pelo menos tão importantes quanto os leitores.

mente fáceis é F. Todos os demais têm prefixo E.F

O leitor não deve sentir-se obrigado a resolver todos os exercícios de uma seção antes de começar a estudar a próxima.

Recursos na teia W

Há muito material de teoria dos grafos na teia W. A lista abaixo é um tanto arbitrária: os sítios mencionados não são necessariamente os melhores nem os mais representativos.

• Graph Theory, de Stephen Locke: http://www.math.fau.edu/locke/graphthe. htm

• Open Problems – Graph Theory and Combinatorics, de Douglas West: http://www. math.uiuc.edu/~west/openp/

• Graph Theory, no MathWorld da Wolfram Research: http://mathworld. wolfram.com/topics/GraphTheory.html

• Teoria dos Grafos, na Wikipédia: http://pt.wikipedia.org/wiki/Teoria_dos_ grafos

• Graph Theory, na Wikipedia: http://en.wikipedia.org/wiki/Graph_theory

• The MacTutor History of Mathematics Archive, sítio de história da matemática na St. Andrews University (Escócia): http://turnbull.mcs.st-and.ac. uk/~history/Indexes/HistoryTopics.html. Veja, em particular, a coleção de biografias de matemáticos em http://w-gap.dcs.st-and.ac.uk/~history/ BiogIndex.html

Os autores

Os autores do texto — Paulo Feofiloff, Yoshiharu Kohayakawa e Yoshiko Wakabayashi — são professores do Departamento de Ciência da Computação (http: //w.ime.usp.br/dcc/) do Instituto de Matemática e Estatística da Universidade de São Paulo.

Agradecimentos

Agradecemos o apoio do MCT/CNPq (Projeto PRONEX Proc. CNPq 664107/1997– 4), da FAPESP/CNPq (Projeto Temático/PRONEX Proc. FAPESP Proc. 2003/09925– 5) e do CNPq (Proc. 300334/93–1 e 304527/89–0). Também agradecemos aos organizadores da I Bienal da SBM pela boa vontade com que atenderam os sucessivos pedidos de prorrogação do prazo de entrega do texto.

Capítulo 1 Conceitos básicos

Este capítulo formaliza a definição de grafo1 e introduz os conceitos de isomorfismo, caminho, circuito, subgrafo, conexão, componente e grafo aleatório. Esses conceitos são necessários para estudar os demais capítulos.

Sugerimos que o leitor faça uma primeira leitura superficial deste capítulo e avance imediatamente para o capítulo 2. Mais tarde, ele poderá voltar a este capítulo para rever pontos específicos quando houver necessidade.

1.1 Grafos

Para qualquer conjunto V , denotaremos por V (2) o conjunto de todos os pares não-V(2) ordenados de elementos de V . Se V tem n elementos então V (2) tem ( n

elementos. Os elementos de V (2) serão identificados com os subconjuntos de V que têm cardinalidade 2. Assim, cada elemento de V (2) terá a forma {v,w}, sendo v e w dois elementos distintos de V .

Um grafo é um par (V,A) em que V é um conjunto arbitrário e A é um subcon-(V,A) junto 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.2

Uma aresta como {v,w} será denotada simplesmente por vw ou por wv. Dire-vw mos que a aresta vw incide em v e em w e que v e w são as pontas da aresta. Se vw é uma aresta, diremos que os vértices v e w são vizinhos ou adjacentes.

De acordo com nossa definição, um grafo não pode ter duas arestas diferentes com o mesmo par de pontas (ou seja, não pode ter arestas “paralelas”). Também não pode ter uma aresta com pontas coincidentes (ou seja, não pode ter “laços”). Há quem goste de enfatizar esse aspecto da definição dizendo que o grafo é “simples”.

Muitas vezes é conveniente dar um nome ao grafo como um todo. Se o nome do

1 A palavra “grafo” é um neologismo derivado da palavra graph em inglês. Ela foi usada pela primeira vez no sentido que nos interessa aqui pelo matemático inglês James Joseph Sylvester ( − ). 2 Além disso, suporemos quase sempre, tacitamente, que V 6= ∅.

1.2 Alguns exemplos de grafos 9

w yx z

Figura 1.1: Esta figura é um desenho do grafo cujos vértices são t, u, v, w, x, y, z e cujas arestas são vw, uv, xw, xu, yz e xy.

grafo for G, o conjunto dos seus vértices será denotado por V (G) e o conjunto das V(G) suas arestas por A(G). O número de vértices de G é denotado por n(G) e o número A(G) n(G)de arestas por m(G); portanto,

O complemento de um grafo (V,A) é o grafo (V,V (2) r A). O complemento de um grafo G será denotado por G. G

(Parte 1 de 10)

Comentários