Exercícios de Teoria dos Grafos - Rede Linux IME-USPdaniloss/antes-2012/Exercicios_Grafos.pdf · Prefácio A teoria dos grafos estuda objetos combinatórios — os grafos — que

Exercícios deTeoria dos Grafos

http://www.ime.usp.br/~pf/grafos-exercicios/

teceira edição

Paulo FeofiloffDepartamento de Ciência da Computação

Instituto de Matemática e Estatística

Universidade de São Paulo

23 de fevereiro de 2011


FEOFILOFF 2

Sumário

1 Conceitos básicos 7

1.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Grafos bipartidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3 Vizinhanças e graus de vértices . . . . . . . . . . . . . . . . . . . . . . . 18

1.4 Caminhos e circuitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.5 União e interseção de grafos . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.6 Grafos planares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.7 Subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.8 Caminhos e circuitos em grafos . . . . . . . . . . . . . . . . . . . . . . . 30

1.9 Cortes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

1.10 Grafos conexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

1.11 Componentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

1.12 Florestas e árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

1.13 Pontes e grafos aresta-biconexos . . . . . . . . . . . . . . . . . . . . . . 45

1.14 Articulações e grafos biconexos . . . . . . . . . . . . . . . . . . . . . . . 47

1.15 Menores de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

1.16 Mapas planos e suas faces . . . . . . . . . . . . . . . . . . . . . . . . . . 52

1.17 Grafos aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2 Isomorfismo 59

3 Síntese de grafos a partir dos graus 65

4 Caracterização de grafos bicromáticos 67

3

FEOFILOFF 4

5 Conjuntos estáveis 71

6 Cliques 77

7 Cobertura por vértices 81

8 Coloração de vértices I 83

9 Emparelhamentos 93

10 Emparelhamentos em grafos bipartidos I 99

11 Emparelhamentos em grafos bipartidos II 103

12 Emparelhamentos em grafos arbitrários 107

13 Coloração de arestas 111

14 Coloração de vértices II 117

15 Circuitos e caminhos hamiltonianos 121

16 Decomposição em circuitos 127

17 Conectores mínimos 133

18 Conjuntos acíclicos máximos 137

19 Caminhos e circuitos mínimos 141

20 Caracterização da planaridade 145

A O alfabeto grego 149

Bibliografia 152

Índice Remissivo 153

Prefácio

A teoria dos grafos estuda objetos combinatórios — os grafos — que são umbom modelo para muitos problemas de matemática, de computação, e deengenharia. A teoria dos grafos não é propriamente uma teoria mas umacoleção de problemas. Muitos desses problemas são um interessante desafiointelectual e têm importantes aplicações práticas.

O presente texto é uma coleção de exercícios de teoria dos grafos. A mai-oria dos exercícios foi extraída dos livros de Bondy e Murty [BM08, BM76],Wilson [Wil79], Diestel [Die00, Die05], Bollobás [Bol98], Lovász [Lov93], Mel-nikov et alii [MST+98], Lucchesi [Luc79] e Lovász e Plummer [LP86]. Algunsoutros são subproduto de projetos de pesquisa. Autros ainda nasceram deconversas com professores, colegas e alunos.

O texto tem muitos links que levam de uma parte do texto a outra e apontampara material complementar. Para tirar proveito desses links é preciso ler otexto na tela do seu computador (e não impresso em papel).

O sítio www.ime.usp.br/~pf/grafos-exercicios/ tem informações adicionais, alémde uma versão atualizada do texto.

Organização. O capítulo 1 trata de conceitos básicos. Cada um dos outroscapítulos aborda um problema clássico. Muitos desses problemas têm cará-ter computacional: procura-se um algoritmo eficiente que receba um grafo eextraia dele uma certa informação. Alguns dos problemas são fáceis, outrossão difíceis; alguns já foram resolvidos, outros não.1

Em que ordem os capítulos devem ser examinados? Depois de estudar aprimeira seção do capítulo 1, sugiro que o leitor avance imediatamente para ocapítulo 2 e os seguintes, voltando ao capítulo 1 somente quando isso se fizernecessário. Há um bom índice remissivo que ajuda a localizar as definiçõesdos vários conceitos.

1 Para vários desses problemas não se conhece (ainda?) um algoritmo rápido, ou seja,não se conhece um algoritmo substancialmente melhor que examinar, pacientemente, umaenorme lista de candidatos a solução. Em termos técnicos, um problema desse tipo é NP-completo ou NP-difícil. Veja os livros de Garey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97].

5

http://pt.wikipedia.org/wiki/Teoria_dos_grafos


FEOFILOFF 6

Classificação dos exercícios. Os números dos exercícios têm prefixos. Oprefixo E é genérico. Outros prefixos são mais específicos:

EF . . . exercício particularmente fácil ou rotineiroED . . . exercício difícilEDD . . . exercício muito difícilEI . . . exercício importanteEID . . . exercício importante e difícilEIF . . . exercício importante mas fácilEU . . . exercício útil como ferramenta técnicaDD . . . desafio, problema em aberto

Terminologia técnica em inglês. Boa parte da literatura da teoria dos gra-fos está escrita em inglês. Por isso, a definição de cada termo técnico emportuguês é acompanhada, entre parênteses, do correspondente termo eminglês. O termo em inglês também é listado no índice remissivo.

O idioma inglês determinou a escolha de muitos símbolos. Assim, por exem-plo, o conjunto das arestas (= edges) de um grafo é denotado por “E” e nãopor “A”, como seria mais natural em português.

Agradecimentos. Agradeço a Rogério Brito por resolver várias dificulda-des tipográficos.

IME–USP, São Paulo, dezembro de 2010P. F.

Capítulo 1

Conceitos básicos

Este capítulo formaliza a noção de grafo, dá vários exemplos, e introduz al-guns conceitos básicos da teoria (grau de vértice, corte, subgrafo, conexão,componente, menor etc.). O capítulo também introduz vários tipos impor-tantes de grafos, como

• caminhos,• circuitos,• árvores,• grafos bipartidos,• grafos planares, etc.

Sugiro que depois de estudar a primeira seção deste capítulo o leitor avanceimediatamente para os capítulos seguintes. Mais tarde, quando houver ne-cessidade, o leitor poderá voltar a este capítulo para rever conceitos e enten-der as sutilezas de algumas definições. Use o índice remissivo para encontraras definições dos vários conceitos.

Eis as seções deste capítulo:

1.1 Grafos1.2 Grafos bipartidos1.3 Vizinhanças e graus de vértices1.4 Caminhos e circuitos1.5 União e interseção de grafos1.6 Grafos planares1.7 Subgrafos1.8 Caminhos e circuitos em grafos1.9 Cortes e pontes

1.10 Grafos conexos

7

FEOFILOFF Conceitos básicos 8

1.11 Componentes1.12 Florestas e árvores1.13 Pontes e grafos aresta-biconexos1.14 Articulações e grafos biconexos1.15 Menores de grafos1.16 Mapas planos e suas faces1.17 Grafos aleatórios

FEOFILOFF Grafos 9

1.1 Grafos

Um grafo (= graph)1 é uma estrutura formada por dois tipos de objetos: vér-tices (= vertices) e arestas (= edges). Cada aresta é um par não ordenado devértices, ou seja, um conjunto com exatamente dois vértices.2 Uma arestacomo v, w será denota simplesmente por vw ou wv; diremos que a aresta vw

incide em v e em w; diremos também que v e w são as pontas da aresta; di-remos, ainda, que os vértices v e w são vizinhos (= neighbors), ou adjacentes(= adjacent).

EXEMPLO: os vértices do grafo são t, u, v, w, x, y, z e as arestassão vw, uv, xw, xu, xy e yz. A figura abaixo é uma representaçãográfica desse grafo.

r r rr rr rPPPPPPPPPP

PPPv

u

w yx

z

t

De acordo com nossa definição, um grafo não pode ter duas arestas diferen-tes com o mesmo par de pontas (ou seja, não pode ter arestas “paralelas”).Além disso, as duas pontas de qualquer aresta são diferentes (ou seja, nãohá “laços”). Alguns livros gostam de enfatizar esse aspecto da definição di-zendo que o grafo é “simples”; nós não usaremos este adjetivo. simples

Um grafo com conjunto de vértices V e conjunto de arestas E é denotadopor (V,E). Muitas vezes é conveniente dar um nome ao grafo como um todo. (V,E)

Se o nome do grafo é G, o conjunto dos seus vértices é denotado por VG e o VG, EG

conjunto das suas arestas por EG. O número de vértices de G é denotado por n(G)n(G) e o número de arestas por m(G); portanto,

m(G)

n(G) := |VG| e m(G) := |EG| .

O complemento de um grafo (V,E) é o grafo (V, V (2) rE), onde V (2) é o con- V (2)

junto de todos os pares não ordenados3 de elementos de V . O complementode G é usualmente denotado por G. G

Um grafo G é completo se EG = V(2)G . A expressão “G é um Kn” é uma Kn

abreviatura de “G é um grafo completo com n vértices”. Um grafo G é vaziose EG = ∅. A expressão “G é um Kn” é uma abreviatura de “G é um grafo Kn

1 O termo foi usado pela primeira vez (no sentido que nos interessa aqui) por JamesJoseph Sylvester (− ). (Veja verbete na Wikipedia.)

2 Suporemos sempre que os conjuntos de vértices e de arestas de qualquer grafo sãofinitos e mutuamente disjuntos. Suporemos também, em geral, que o conjunto de vérticesnão é vazio.

3 Diestel [Die05] escreve “[V ]2”. Há quem escreva “(V2

)”.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Sylvester.html

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Sylvester.html

http://en.wikipedia.org/wiki/James_Joseph_Sylvester

FEOFILOFF Grafos 10

vazio com n vértices”.

Exercícios

E 1.1 Faça uma lista de todos os grafos que tenham a, b, c por conjuntode vértices.4 Faça a lista de modo que cada grafo apareça ao lado do seucomplemento.

E 1.2 Faça uma figura de um K5 e outra de um K5. Quantas arestas temum Kn? E um Kn?

E 1.3 A matriz de adjacências de um grafo G é a matriz A definida da se-guinte maneira: para quaisquer dois vértices u e v,matriz de

adjacências

A[u, v] =1 se uv ∈ EG ,0 em caso contrário.

É claro que a matriz é indexada por VG × VG. (A matriz de adjacência é umaespécie de “figura” do grafo. Ela tem certas vantagens sobre a figura pontos-e-linhas que usamos acima.)

Escreva a matriz de adjacências do grafo definido no exemplo que apa-rece na página 9. Escreva a matriz de adjacências de um K4. Qual a relaçãoentre a matriz de adjacências de um grafo e matriz de adjacências do seucomplemento?

E 1.4 A matriz de incidências de um grafo G é a matriz M definida da se-guinte maneira: para todo vértice u e toda aresta e,matriz de

incidências

M [u, e] =1 se u é uma das pontas de e ,0 em caso contrário.

É claro que a matriz é indexada por VG × EG. (A matriz de incidência é umaespécie de “figura” do grafo. Ela tem certas vantagens sobre a figura pontos-e-linhas que usamos acima.)

Escreva a matriz de incidências do grafo definido no exemplo que apa-rece na página 9. Escreva a matriz de incidências de um K4. Quanto vale asoma de todos os elementos da matriz de incidências de um grafo? Qual arelação entre a matriz de incidências de um grafo e matriz de incidências doseu complemento?

E 1.5 Os hidrocarbonetos conhecidos como alcanos têm fórmula químicaalcanos

4 Num conjunto, a ordem em que os elementos são apresentados é irrelevante. Assim,a, b, c = b, c, a = c, b, a.

FEOFILOFF Grafos 11

CpH2p+2, onde C e H representam moléculas de carbono e hidrogênio res-pectivamente. As moléculas de alcanos podem ser representadas por grafoscomo os da figura 1.1.

Faça uma figura de uma molécula de metano C1H4. Quantas moléculas“diferentes” de C3H8 existem?

r rrr r rrr rr r r rr r rrrrr rrr rrr

rr rrrrrrr r

Figura 1.1: Etano (C2H6), butano (C4H10) e isobutano (C4H10). Os vérti-ces em que incide uma só aresta representam átomos de hidrogênio (H);os demais representam átomos de carbono (C). (Veja o exercício 1.5.)

E 1.6 Seja V o produto cartesiano 1, 2, . . . , p×1, 2, . . . , q, isto é, o conjuntode todos os pares ordenados5 (i, j) com i em 1, . . . , p e j em 1, . . . , q. Di-gamos que dois elementos (i, j) e (i′, j′) de V são adjacentes se

i = i′ e |j − j′| = 1 ou j = j′ e |i− i′| = 1 .

Essa relação de adjacência define um grafo sobre o conjunto V de vértices.Esse grafo é conhecido como grade (= grid) p-por-q. grade

Quantas arestas tem a grade p-por-q? Escreva as matrizes de adjacênciae incidência de uma grade 4-por-5.

r r rrrrr r rrr r

Figura 1.2: Uma grade 3-por-4 (veja exercício 1.6).

E 1.7 Dados números inteiros p e q, seja V o conjunto 1, 2, 3, . . . , pq−2, pq−1,pq. Digamos que dois elementos k e k′ de V , com k < k′, são adjacentes sek′ = k + q ou6

k mod q 6= 0 e k′ = k + 1.

Essa relação de adjacência define um grafo com conjunto de vértices V .

5 Um par ordenado é uma sequência de comprimento 2. Numa sequência, a ordem doselementos é essencial. Assim, (1, 2) 6= (2, 1) e (1, 2, 1) 6= (1, 1, 2).

6 A expressão “k mod q” denota o resto da divisão de k por q, ou seja, k/q − bk/qc.

FEOFILOFF Grafos 12

Faça uma figura do grafo com parâmetros p = 3 e q = 4. Faça uma figurado grafo com parâmetros p = 4 e q = 3. Qual a relação entre esses grafos e agrade definida no exercício 1.6?

E 1.8 O grafo dos movimentos da dama, ou simplesmente grafo da dama, édamadefinido assim: os vértices do grafo são as casas de um tabuleiro de xadrezcom t linhas e t colunas (no tabuleiro usual temos t = 8) e dois vértices sãoadjacentes se uma dama (= queen) do jogo de xadrez pode saltar de um delespara o outro em um só movimento. Para deixar claro o número de linhas ecolunas do tabuleiro, podemos dizer que esse é o grafo da dama t-por-t. (Vejafigura 1.3.)

Faça uma figura do grafo da dama 4-por-4. Escreva as matrizes de adja-cência e incidência do grafo da dama 4-por-4. Quantas arestas tem o grafo dadama 8-por-8? Quantas arestas tem o grafo da dama t-por-t?

E 1.9 O grafo do cavalo t-por-t é definido assim: os vértices do grafo são ascavalocasas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices sãoadjacentes se um cavalo (= knight) do jogo de xadrez pode saltar de um delespara o outro em um só movimento. (Veja figura 1.3.)

Faça uma figura do grafo do cavalo 3-por-3. Escreva as matrizes de ad-jacência e incidência do grafo do cavalo 3-por-3. Quantas arestas tem o grafodo cavalo 8-por-8? Quantas arestas tem o grafo do cavalo t-por-t?

Figura 1.3: Tabuleiros de xadrez 8-por-8. A figura esquerda indica todosos vizinhos do vértice • no grafo da dama (veja exercício 1.8). A da direitaindica todos os vizinhos do vértice • no grafo do cavalo (veja exercício 1.9).

E 1.10 O grafo do bispo t-por-t é definido assim: os vértices do grafo são asbispocasas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices sãoadjacentes se um bispo (= bishop) do jogo de xadrez pode saltar de um delespara o outro em um só movimento.

Faça uma figura do grafo do bispo 4-por-4. Escreva as matrizes de adja-cência e incidência do grafo do bispo 4-por-4. Quantas arestas tem o grafo dobispo 8-por-8? Quantas arestas tem o grafo do bispo t-por-t?

E 1.11 O grafo da torre t-por-t é definido assim: os vértices do grafo são astorrecasas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices são

FEOFILOFF Grafos 13

adjacentes se um torre (= rook) do jogo de xadrez pode saltar de um delespara o outro em um só movimento.

Faça uma figura do grafo da torre 4-por-4. Escreva as matrizes de adja-cência e incidência do grafo da torre 4-por-4. Quantas arestas tem o grafo datorre 8-por-8? Quantas arestas tem o grafo da torre t-por-t?

E 1.12 O grafo do rei t-por-t é definido assim: os vértices do grafo são as reicasas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices sãoadjacentes se um rei (= king) do jogo de xadrez pode saltar de um deles parao outro em um só movimento.

Faça uma figura do grafo do rei 4-por-4. Escreva as matrizes de adjacên-cia e incidência do grafo do rei 4-por-4. Quantas arestas tem o grafo do rei8-por-8? Quantas arestas tem o grafo do rei t-por-t?

E 1.13 O grafo das palavras é definido assim: cada vértices é uma palavra da palavraslíngua portuguesa e duas palavras são adjacentes se diferem em exatamenteuma posição. (Esse grafo é uma adaptação do ladders do Stanford Graph-Base [Knu93].) Por exemplo, rato e ralo são adjacentes, enquanto ralo erota não são. Faça uma figura da parte do grafo definida pelas palavrasabaixo:

caiado cavado cavalo girafa girava ralo ramo rata ratoremo reta reto rota vaiado varado virada virado virava

Escreva as matrizes de adjacência e incidência do grafo.

E 1.14 Para qualquer inteiro positivo k, um cubo de dimensão k (ou k-cubo) cuboé o grafo definido da seguinte maneira: os vértices do grafo são todas assequências7 b1b2 · · · bk de bits8; dois vértices são adjacentes se e somente sediferem em exatamente uma posição. Por exemplo, os vértices do cubo dedimensão 3 são 000, 001, 010, 011, 100, 101, 110, 111; o vértice 000 é adjacenteaos vértices 001, 010, 100 e a nenhum outro; e assim por diante.

Faça uma figura do 1-cubo, do 2-cubo e do 3-cubo. Escreva as matrizesde adjacência e incidência de um 3-cubo. Quantos vértices tem o k-cubo?Quantas arestas tem o k-cubo?

E 1.15 Seja X o conjunto 1, 2, 3, 4, 5 e V o conjunto X(2) (portanto, V é oconjunto de todos os subconjuntos de X que têm exatamente 2 elementos).Digamos que dois elementos v e w de V são adjacentes se v ∩ w = ∅. Essarelação de adjacência sobre V define o grafo de Petersen.9 Faça uma figura Petersendo grafo. Escreva as matrizes de adjacência e incidência do grafo. Quantosvértices e quantas arestas tem o grafo?

7 A expressão “b1b2 · · · bk” é uma abreviatura de “(b1, b2, . . . , bk)”.8 Portanto, cada bi pertence ao conjunto 0, 1.9 Referência ao dinamarquês Julius Petersen (− ). (Veja verbete na Wikipedia.)

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Petersen.html

http://en.wikipedia.org/wiki/Julius_Petersen

FEOFILOFF Grafos 14

E 1.16 Seja V o conjunto de todos os subconjuntos de 1, 2, . . . , n que têmexatamente k elementos, sendo k ≤ n/2. Digamos que dois elementos v e wde V são adjacentes se v ∩w = ∅. Essa relação de adjacência sobre V define ografo de Kneser K(n, k).10 Em particular, K(5, 2) é o grafo de Petersen. FaçaKneserfiguras de K(n, 1), K(n, n), K(n, n−1), K(4, 2), K(5, 3), K(6, 2) e K(6, 3).

E 1.17 O grafo dos estados do Brasil é definido assim: cada vértice é um dosestadosestados da República Federativa do Brasil; dois estados são adjacentes se têmuma fronteira comum. Faça um desenho do grafo. Quantos vértices tem ografo? Quantas arestas?

E 1.18 Considere as grandes cidades e as grandes estradas do estado de SãoPaulo. Digamos que uma cidade é grande se tem pelo menos 300 mil habitan-tes. Digamos que uma estrada é grande se tiver pista dupla (como a SP300,por exemplo). Digamos que duas grandes cidades são adjacentes se umagrande estrada ou uma concatenação de grandes estradas liga as duas cida-des diretamente (ou seja, sem passar por uma terceira grande cidade). Façacidadesuma figura do grafo das grandes cidades definido pela relação de adjacênciaque acabamos de descrever.

E 1.19 Seja V um conjunto de pontos no plano. Digamos que dois dessespontos são adjacentes se a distância entre eles é menor que 2. Essa relaçãode adjacência define o grafo dos pontos no plano (sobre o conjunto V ). Façapontos

no plano uma figura do grafo definido pelos pontos abaixo.

(0, 2) (1, 2) (2, 2)(0, 1) (1, 1) (2, 1)(0, 0) (1, 0) (2, 0)

Escreva as matrizes de adjacência e incidência do grafo.

E 1.20 Dado um conjunto V , seja E o conjunto definido da seguinte maneira:para cada par não ordenado de elementos de V , jogue uma moeda; se o resul-tado for cara, acrescente o par a E. O grafo (V,E) assim definido é aleatórioaleatório(= random).

Pegue sua moeda favorita e faça uma figura do grafo aleatório com vér-tices 1, . . . , 6. Agora repita o exercício com uma moeda viciada que dá caracom probabilidade 1/3 e coroa com probabilidade 2/3.

E 1.21 Seja S uma matriz de números inteiros. Suponha que as linhas de Ssão indexadas por um conjunto V e que as colunas são indexadas pelo mesmoconjunto V . O grafo da matriz S é definido da seguinte maneira: o conjuntomatriz

10 Lásló Lovász usou esse grafo em 1978 para provar uma conjectura proposta por M. Kne-ser em 1955.

FEOFILOFF Grafos 15

de vértices do grafo é V e dois vértices i e j são adjacentes se S[i, j] 6= 0.O grafo de S está bem definido? Que condições é preciso impor sobre a

matriz para que o grafo esteja bem definido?

E 1.22 Suponha dados k intervalos de comprimento finito, digamos I1, I2,. . . , Ik, na reta real. Digamos que dois intervalos Ii e Ij são adjacentes seIi ∩ Ij 6= ∅. Essa relação de adjacência define um grafo com conjunto devértices I1, I2, . . . , Ik. Esse é um grafo de intervalos. intervalos

Faça uma figura do grafo definido pelos intervalos [0, 2], [1, 4], [3, 6], [5, 6]e [1, 6]. Escreva as matrizes de adjacência e incidência do grafo.

E 1.23 Seja uma relação de ordem parcial sobre um conjunto finito V . Por-tanto, a relação é transitiva (se x y e y z então x z), antissimétrica(se x y e y x então x = y) e reflexiva (x x para todo x). Digamosque dois elementos distintos x e y de V são adjacentes se forem comparáveis,ou seja, se x y ou y x. Essa relação de adjacência define o grafo decomparabilidade da relação . compara-

bilidadeFaça uma figura do grafo de comparabilidade da relação usual de inclu-são ⊆ entre a coleção de todos os subconjuntos de 1, 2, 3.

E 1.24 Duas arestas de um grafoG são adjacentes se têm uma ponta comum.Essa relação de adjacência define o grafo das arestas de G. De modo maisformal, o grafo das arestas (= line graph) de um grafo G é o grafo (EG, A) em das arestasque A é o conjunto de todos os pares de arestas adjacentes de G. (Há quemdiga [Per09] grafo lineal no lugar de grafo das arestas.) O grafo das arestas deG será denotado por L(G). (Veja a figura 1.4.) L(G)

Faça uma figura de L(K3). Faça uma figura de L(K4). Escreva as matri-zes de adjacência e incidência de L(K4). Quantos vértices e quantas arestastem L(Kn)? Faça uma figura do grafo L(P ), sendo P o grafo de Petersen (vejaexercício 1.15).

PPPPPPPPPP

PPPr r rr rr r

v

u

w yx

z

tHHH

vu

yzvw wx

uxxy

ss s

s s sFigura 1.4: Um grafo (esquerda) e o seu grafo das arestas (direita).

FEOFILOFF Grafos bipartidos 16

1.2 Grafos bipartidos

Sejam U e W dois conjuntos mutuamente disjuntos (isto é, U ∩W = ∅). SejaE um conjunto de pares não ordenados da forma (u,w) com u ∈ U e w ∈ W .Dizemos então que

(U ∪W,E)

é um grafo bipartido (= bipartite graph). Para explicitar U eW , podemos dizerque o grafo é (U,W )-bipartido. Podemos dizer também que o par (U,W ) éuma bipartição11 do grafo.

Há quem goste de dizer que o objeto (U,W,E) é um bigrafo (= bigraph)[LP86]. O termo é apropriado, mas não vamos usá-lo.

Um grafo (U,W )-bipartido é completo se, para todo u em U e todo w em W ,o par uw é uma aresta. Se |U | = p e |W | = q, dizemos que o grafo é um Kp,q.Kp,q

Todo K1,q é uma estrela (= star). Se q ≥ 2, o centro da estrela é o único vérticeestrelaque incide em duas ou mais arestas. (Se q < 2, a estrela não tem centro.)

Figura 1.5: Um grafo bipartido completo.

Exercícios

EF 1.25 Uma pequena fábrica tem cinco máquinas — 1, 2, 3, 4 e 5 — e seisoperários — A, B, C, D, E e F . A tabela especifica as máquinas que cadaoperário sabe operar:

A 2, 3 B 1, 2, 3, 4, 5C 3 DE 2, 4, 5 F 2, 5

Faça uma figura do grafo bipartido que representa a relação entre operáriose máquinas.

11 O termo bipartição aplica-se usualmente a conjuntos. Uma bipartição de um conjunto Vé um par (U,W ) de subconjuntos não vazios de V tal que U ∪ W = V e U ∩ W = ∅. Abipartição é o par (U,W ). Não faz sentido dizer “U é uma das bipartições de V ”. Diga “U éuma das partes da bipartição”.

FEOFILOFF Grafos bipartidos 17

EF 1.26 Quantas arestas pode ter um grafo bipartido com bipartição (U,W )?

EF 1.27 Quantas arestas tem um Kp,q? Quantas arestas tem um Kp,q?

E 1.28 Faça uma figura de um K3,4. Escreva as matrizes de adjacência e inci-dência de um K3,4. Faça uma figura de uma estrela com 6 vértices.

E 1.29 Que aparência tem a matriz de adjacências de um grafo bipartido?

E 1.30 A matriz da bipartição de um grafo (U,W )-bipartido é definida as-sim: cada linha da matriz é um elemento de U , cada coluna da matriz é umelemento de W e no cruzamento da linha u com a coluna w temos um 1 se uwé uma aresta e temos um 0 em caso contrário.

Escreva a matriz da bipartição do grafo do exercício 1.25. Adote a bipar-tição óbvia: U = A, . . . , F e W = 1, . . . , 5.

FEOFILOFF Vizinhanças e graus de vértices 18

1.3 Vizinhanças e graus de vértices

A vizinhança (= neighborhood) de um vértice v em um grafo G é o conjuntode todos os vizinhos de v. Este conjunto será denotado por

NG(v)

ou simplesmente por N(v).12 O grau (= degree) de um vértice v em um grafoN(v)

G é o número de arestas que incidem em v. O grau de v será denotado por

dG(v)

ou simplesmente por d(v). É evidente que d(v) = |N(v)| para todo vértice v.d(v)

Um vértice v é isolado se d(v) = 0.

O grau mínimo dos vértices de um grafo13 G é o númeroδ(G)

δ(G) := minv∈VG

dG(v)

e o grau máximo dos vértices é o número ∆(G) := maxv∈VGdG(v).∆(G)

A densidade de um grafo G é o número m(G)/n(G).14 Como veremos noexercício 1.42, a densidade de um grafo é igual à metade do seu “grau mé-dio”.

Um grafo é regular se todos os seus vértices têm o mesmo grau, ou seja, seδ = ∆. Um grafo é r-regular se d(v) = r para todo vértice v. Um grafo cúbicoé o mesmo que um grafo 3-regular.

Exercícios

EF 1.31 Quais são os graus dos vértices de uma estrela (veja a seção 1.2)?

EF 1.32 Se G é um Kn, quanto valem δ(G) e ∆(G)? Quanto valem os parâ-metros δ e ∆ de um Kp,q (veja a seção 1.2)?

EF 1.33 Para r = 1, 2, 3, faça uma figura de um grafo r-regular com 12 vérti-ces.

12 Alguns livros dizem “Adj (v)” em lugar de “N(v)”. Outros dizem “Γ(v)”.13 A expressão “grau mínimo de um grafo” não é muito gramatical, uma vez que “grau

de um grafo” não faz sentido.14 Este uso do termo “densidade” é usual mas um tanto forçado. Faria mais sentido dizer

que a densidade de um grafo G é o número m(G)/(n(G)2

).


E 1.34 Quais são os graus dos vértices de uma molécula de alcano (veja exer-cício 1.5)?

E 1.35 Calcule os valores dos parâmetros δ e ∆ no k-cubo (veja exercício 1.14)e no grafo de Petersen (veja exercício 1.15 ou figura 1.6).

r rrr r rrr

rrXXQQQCCCC

JJ A

AAA

ZZZZ

Figura 1.6: Grafo de Petersen. Veja exercícios 1.15 e 1.35.

E 1.36 Calcule os valores dos parâmetros δ e ∆ no grafo dos estados do Brasil(veja exercício 1.17).

E 1.37 Calcule os valores dos parâmetros δ e ∆ no grafo da dama (veja exer-cício 1.8) e no grafo do cavalo (veja exercício 1.9).

E 1.38 Seja A a matriz de adjacências (veja exercício 1.3) eM a matriz de inci-dências (veja exercício 1.4) de um grafoG. Quanto vale a soma dos elementosda linha v de A? Quanto vale a soma dos elementos da linha v de M?

EU 1.39 Seja G um grafo bipartido com bipartição (U,W ). Suponha que G ér-regular, com r > 0. Mostre que |U | = |W |.

E 1.40 É verdade que todo grafo com pelo menos dois vértices tem dois vér-tices com o mesmo número de vizinhos? Em outras palavras, se um grafotem mais de um vértice, é verdade que tem dois vértices distintos v e w taisque |N(v)| = |N(w)|? (Uma maneira informal de dizer isso: é verdade que emtoda cidade com pelo menos dois habitantes residem duas pessoas que têmexatamente o mesmo número de amigos na cidade?)

EI 1.41 Mostre15 que, em todo grafo, a soma dos graus dos vértices é igual aodobro do número de arestas. Ou seja, todo grafo (V,E) satisfaz a identidade∑

v∈V d(v) = 2|E| . (1.1)

EF 1.42 O grau médio de um grafo (V,E) é o número 1|V |∑

v∈V d(v). Mostre graumédioque o grau médio de qualquer grafoG é igual a 2ρ, sendo ρ a densidade deG.

15 Mostre = prove.


EF 1.43 Mostre que todo grafoG tem um vértice v tal que d(v) ≤ 2m(G)/n(G)e um vértice w tal que d(w) ≥ 2m(G)/n(G). É verdade que todo grafo G temum vértice x tal que d(x) < 2m(G)/n(G)?

E 1.44 Mostre que em qualquer grafo tem-se δ ≤ 2m/n ≤ ∆. Mostre tambémque δ ≤ 2ρ ≤ ∆, sendo ρ a densidade do grafo.

E 1.45 Mostre que todo grafo com n vértices tem no máximo n(n− 1)/2 ares-tas.

EU 1.46 Mostre que em qualquer grafo o número de vértices de grau ímparé necessariamente par.

E 1.47 Quantas arestas tem o grafo da dama 8-por-8 (veja exercício 1.8)?Quantas arestas tem o grafo da dama t-por-t?

E 1.48 Quantas arestas tem o grafo do cavalo 4-por-4 (veja exercício 1.9)?Quantas arestas tem o grafo do cavalo t-por-t?

E 1.49 Quantas arestas tem um grafo r-regular com n vértices?

E 1.50 Quantas arestas tem o cubo de dimensão k?

E 1.51 Quantas arestas tem o grafo das arestas (veja exercício 1.24) de umgrafo G?

E 1.52 Seja G o complemento de um grafo G. Calcule δ(G) e ∆(G) em funçãode δ(G) e ∆(G).

E 1.53 Seja G um grafo tal que m(G) > n(G). Mostre que ∆(G) ≥ 3.

E 1.54 Suponha que um grafo G tem menos arestas que vértices, ou seja, quem(G) < n(G). Mostre que G tem (pelo menos) um vértice de grau 0 ou (pelomenos) dois vértices de grau 1.

ED 1.55 Escolha dois números naturais n e k e considere o seguinte jogo paradois jogadores,A eB. Cada iteração do jogo começa com um grafoG que temn vértices (no início da primeira iteração tem-se EG = ∅). Em cada iteraçãoímpar (primeira, terceira, etc.), o jogador A escolhe dois vértices não adjacen-tes u e v e acrescenta uv ao conjunto de arestas do grafo. Em cada iteraçãopar (segunda, quarta, etc.), o jogador B faz um movimento análogo: escolhedois vértices não adjacentes u e v e acrescenta uv ao conjunto de arestas do


grafo. O primeiro jogador a produzir um grafo G tal que δ(G) ≥ k perde ojogo. Problema: determinar uma estratégia vencedora para A e uma estraté-gia vencedora para B.

FEOFILOFF Caminhos e circuitos 22

1.4 Caminhos e circuitos

Esta seção introduz dois tipos muito simples mas muito importantes de gra-fos. Para quaisquer objetos v1, v2, v3, . . . , vn distintos dois a dois, o grafo(

v1, v2, v3, . . . , vn , v1v2, v2v3, . . . , vn−1vn)

é um caminho (= path). Por exemplo, o grafo (x, y, w, z, xy, yw,wz) é umcaminho.16

Portanto, um grafo é um caminho se seus vértices podem ser ordenados detal maneira que o primeiro seja adjacente ao segundo, o segundo adjacenteao terceiro, etc., o penúltimo adjacente ao último e que não haja outras adja-cências entre os vértices além dessas. Em outras palavras, um grafo G é umcaminho se VG admite uma permutação17 (v1, v2, . . . , vn) tal que

vivi+1 : 1 ≤ i < n = EG .

Os vértices v1 e vn são os extremos do caminho; os demais vértices são inter-nos.18 Diremos que esse caminho liga v1 a vn.

O caminho que acabamos de descrever pode ser denotado simplesmente porv1v2 · · · vn. Por exemplo, se dissermos “o caminho xywz” estaremos nos refe-v1v2 · · · vnrindo ao grafo (x, y, w, z, xy, yw,wz).

Para quaisquer objetos v1, v2, v3, . . . , vn distintos dois a dois, com n ≥ 3, ografo (

v1, v2, v3, . . . , vn , v1v2, v2v3, . . . , vn−1vn, vnv1)

é um circuito (= circuit = polygon).19 Em outras palavras, um grafo G éum circuito20 se VG tem 3 ou mais elementos e admite uma permutação(v1, v2, . . . , vn) tal que

vivi+1 : 1 ≤ i < n ∪ vnv1 = EG .

Esse circuito pode ser denotado simplesmente por v1v2 · · · vnv1. As-v1v2 · · · vnv1 sim, se dissermos “o circuito xyzx”, estaremos nos referindo ao grafo

(x, y, z, xy, yz, zx).

16 Convém insistir que, para nós, caminhos são grafos. Em alguns livros, caminhos sãotratados como sequências de vértices e não como grafos.

17 Uma permutação de um conjunto X é uma sequência em que cada elemento de Xaparece uma e uma só vez.

18 Alguns autores [Per09] dizem que um caminho só é caminho se tiver 2 ou mais vértices.Para nós, entretanto, o grafo (v, ∅) é um caminho. Esse detalhe não é tão irrelevante quantopode parecer.

19 Alguns livros dizem “ciclo” (= cycle) no lugar de “circuito”.20 Observe que, para nós, um circuito é um grafo. Em alguns livros, circuitos são tratados

como sequências (de um certo tipo) e não como grafos.


r r r r r rrrr rr SSSS

##cc##cc

Figura 1.7: Um caminho e um circuito.

O comprimento de um caminho ou circuito G é o número m(G). É claro queum caminho de comprimento m tem m + 1 vértices e um circuito compri-mento m tem m vértices.

Um triângulo, quadrado, pentágono e hexágono é o mesmo que um circuitode comprimento 3, 4, 5 e 6 respectivamente.

Exercícios

EF 1.56 Faça uma figura de um caminho de comprimento 0, de um caminhode comprimento 1 e de um caminho de comprimento 2. Faça uma figura deum circuito de comprimento 3 e de um circuito de comprimento 4. Por que adefinição de circuito tem a restrição “n ≥ 3”?

EF 1.57 Seja V o conjunto a, b, c, d, e e E o conjunto de, bc, ca, be. Verifi-que que o grafo (V,E) é um caminho. Agora suponha que F é o conjuntobc, bd, ea, ed, ac e verifique que o grafo (V, F ) é um circuito.

EF 1.58 Faça um figura do caminho 1 2 4 3 5. Faça um figura do caminho1 3 2 4 3 5. Faça um figura do circuito 1 2 4 3 5 1.

EF 1.59 Verifique que o caminho u v w x y z também pode ser denotado porz y xw v u. Verifique que essas duas expressões representam o mesmo cami-nho.

EF 1.60 Considere o circuito u v w x y z u. Mostre que z y xw v u z também éum circuito. Mostre que qualquer permutação cíclica — como w x y z u v w,por exemplo — também é um circuito. Mostre que todas essas expressõesrepresentam o mesmo circuito.

EF 1.61 Exiba as matrizes de adjacências e incidências de um caminho decomprimento 4. Exiba as matrizes de adjacências e incidências de um circuitode comprimento 5.

EF 1.62 É verdade que o grafo do cavalo 3-por-3 é um circuito?


EF 1.63 Verifique que a grade 1-por-n é um caminho de comprimento n− 1.Quais grades são circuitos?

EF 1.64 Suponha que P é um caminho de comprimento n−1 e O um circuitode comprimento n. Quanto valem δ(P ), ∆(P ), δ(O) e ∆(O)?

EF 1.65 Faça uma figura do complemento de um caminho de comprimento 3.Faça uma figura do complemento de um caminho de comprimento 4. Façauma figura do complemento de um circuito de comprimento 5. Faça umafigura do complemento de um circuito de comprimento 6.

E 1.66 Quantos caminhos diferentes existem com conjunto de vértices1, 2, 3? Quantos circuitos diferentes existem com conjunto de vértices1, 2, 3? Quantos circuitos diferentes existem com conjunto de vértices1, 2, 3, 4?

E 1.67 É verdade que todo grafo 2-regular é um circuito?

E 1.68 Seja G um grafo com n(G) ≥ 3, ∆(G) = 2 e δ(G) = 1. Se G temexatamente dois vértices de grau 1, é verdade que G é um caminho?

FEOFILOFF União e interseção de grafos 25

1.5 União e interseção de grafos

A união de dois grafos G e H é o grafo (VG∪VH , EG∪EH). É natural denotaresse grafo por G ∪H . G ∪H

A interseção de dois grafos G e H é o grafo (VG ∩ VH , EG ∩ EH). É naturaldenotar esse grafo por G ∩H . G ∩H

Dois grafos G e H são disjuntos se os conjuntos VG e VH são disjuntos, ouseja, se VG ∩ VH = ∅. É evidente que EG e EH também são disjuntos nessecaso.

Exercícios

EF 1.69 Seja G um grafo completo com conjunto de vértices 1, 2, 3, 4, 5 e Hum grafo completo com conjunto de vértices 4, 5, 6, 7, 8. Faça figuras dosgrafos G ∪H e G ∩H .

E 1.70 SejaG o grafo do bispo eH o grafo da torre (veja exercícios 1.10 e 1.11).Mostre que G ∪H é o grafo da dama.

EF 1.71 Seja G o circuito 1 2 3 4 5 6 1 e H o caminho 4 7 8 5. Faça figuras dosgrafos G ∪H e G ∩H .

E 1.72 Seja P um caminho com extremos u a v eQ um caminho com extremosv e w. Mostre que se VP ∩ VQ = v então o grafo P ∪Q é um caminho.

E 1.73 Suponha que os caminhos P e Q têm os mesmos extremos, digamos ue v. Suponha ainda que VP ∩ VQ = u, v. Em que condições o grafo P ∪Q éum circuito?

E 1.74 Sejam A, B e C os conjuntos 1, 2, 3, 4, 5, 6, 7 e 9, 10, 11. Seja Go grafo bipartido completo com bipartição (A,B). Seja H o grafo bipartidocompleto com bipartição (B,C). Faça figuras dos grafos G ∪H e G ∩H .

E 1.75 Uma roda (= wheel) é qualquer grafo da forma G ∪ H , onde G é umcircuito eH é uma estrela (veja a seção 1.2) com centro v tal que VHrv = VG.Faça figuras de rodas com 4, 5 e 6 vértices. Quanto valem os parâmetros m, δe ∆ de uma roda com n vértices?

FEOFILOFF Grafos planares 26

1.6 Grafos planares

Um grafo é planar se pode ser desenhado no plano sem que as curvas querepresentam arestas se cruzem. Esta definição é imprecisa, mas suficiente porenquanto. Daremos um definição melhor na seção 1.16.

Exercícios

EF 1.76 Verifique que todo caminho é planar. Verifique que todo circuito éplanar.

EF 1.77 Mostre que toda grade (veja exercício 1.6) é planar.

E 1.78 Mostre que o grafo dos estados do Brasil (veja exercício 1.17) é planar.

E 1.79 O grafo dos pontos no plano descrito no exercício 1.19 é planar?

E 1.80 Mostre que todo K4 é planar. É verdade que todo K5 é planar?

E 1.81 Mostre que todo K2,3 é planar. É verdade que todo K3,3 é planar?

E 1.82 Mostre que o 3-cubo (veja exercício 1.14) é planar. O 4-cubo também éplanar? O 5-cubo é planar?

E 1.83 O grafo da dama t-por-t (veja exercício 1.8) é planar? O grafo do bispot-por-t é planar? O grafo do cavalo t-por-t (veja exercício 1.9) é planar?

FEOFILOFF Subgrafos 27

1.7 Subgrafos

Um subgrafo de um grafo G é qualquer grafo H tal que VH ⊆ VG e EH ⊆ EG.É conveniente escrever “H ⊆ G” para dizer que H é subgrafo de G. H ⊆ G

Um subgrafo H de G é gerador (= spanning) se VH = VG. (Há quem digaabrangente no lugar de gerador [Per09].)

Um subgrafo H de G é próprio se VH 6= VG ou EH 6= EG. Às vezes é conveni-ente escrever “H ⊂ G” para dizer que H é subgrafo próprio de G.21 H ⊂ G

O subgrafo de G induzido por uma parte22 X de VG é o grafo (X,F ) onde Fé o conjunto EG ∩X(2). Esse subgrafo é denotado por G[X]

G[X] .

Para qualquer subconjunto X de VG, denotaremos por G − X o sub- G−Xgrafo G[VG r X]. Se v é um vértice de G então G − v é uma abreviatura G− vde G− v.

Se e é uma aresta de G então G − e é o grafo (VG, EG r e). De modo mais G− egeral, se A é uma parte de EG então G−A é o grafo (VG, EGrA). É claro que G−AG− A é um subgrafo gerador de G.

Se um caminho v1 · · · vp é subgrafo de G, dizemos simplesmente que v1 · · · vpé um caminho em G ou que G contém o caminho v1 · · · vp. Por exem-plo, se dissermos que u v w z é um caminho em G, devemos entender que(u, v, w, z, uv, vw,wz) é um subgrafo de G. Convenção análoga vale paracircuitos que são subgrafos de G.23

Um caminho P em um grafo G é máximo se G não contém um caminho de máximocomprimento maior que o de P . Um caminho v1 v2 · · · vp em G é maximal se maximalnão faz parte de um caminho maior, ou seja, se não existe vértice u em G talque u v1 v2 · · · vp é um caminho e não existe vértice w tal que v1 v2 · · · vpw éum caminho em G.

Exercícios

EF 1.84 Suponha que H é um subgrafo de G. Se VH = VG, é verdade queH = G? Se EH = EG, é verdade que H = G?

21 De modo geral, escreveremos “X ⊂ Y ” ou “Y ⊃ X” para dizer que o conjunto X ésubconjunto próprio de Y , ou seja, que X ⊆ Y mas X 6= Y .

22 Uma parte de um conjunto é o mesmo que um subconjunto do conjunto.23 Eu gostaria de dizer “subcaminho de G” e “subcircuito de G”. Infelizmente, essas

expressões não são usadas na literatura.


EF 1.85 Seja G um grafo, V ′ uma parte de VG e E ′ uma parte EG. É verdadeque (V ′, E ′) é um subgrafo de G?

EF 1.86 SejaG um grafo bipartido com bipartição (U,W ). Mostre que os sub-grafos G[U ] e G[W ] são vazios.

E 1.87 Repita o exercício 1.41: Use indução24 no número de arestas do grafopara provar que todo grafo (V,E) satisfaz a identidade∑

v∈V d(v) = 2|E| .

EF 1.88 Mostre que todo subgrafo induzido de um grafo completo é com-pleto. É verdade que todo subgrafo induzido de um caminho é um caminho?É verdade que todo subgrafo induzido de um circuito é um caminho?

EF 1.89 Seja v um vértice e e uma aresta de um circuitoO. Mostre que o grafoO − v é um caminho. Mostre que o grafo O − e é um caminho.

E 1.90 Mostre que todo subgrafo de um grafo planar é planar. Em outraspalavras, se um grafo G tem um subgrafo não planar então G não é planar.

E 1.91 Sejam v e w dois vértices de um grafo G. Suponha que d(v) = δ(G) ed(w) = ∆(G). É verdade que δ(G−v) = δ(G)−1? É verdade que ∆(G−w) =∆(G)− 1?

EF 1.92 Verifique que o grafo do bispo t-por-t é um subgrafo do grafo dadama t-por-t. Verifique que o grafo da torre t-por-t é um subgrafo do grafoda dama t-por-t.

E 1.93 O 3-cubo é subgrafo do 4-cubo?

EF 1.94 Seja G o grafo representado na figura 1.8 e X o conjunto a, b, f, e,g, l. Faça uma figura de G[X].

E 1.95 (BOM!) Seja H o grafo das arestas (veja exercício 1.24) de um grafo G(portanto, H = L(G)). Mostre que H não contém K1,3 como subgrafo in-duzido, ou seja, mostre que não existe subconjunto X de VH tal que H[X] éum K1,3. Mostre que a recíproca não é verdadeira.

24 Indução é a arte de reduzir um problema a uma versão menor dele mesmo.


r r rrrrr

r r r rr b d

f g h

k l

a

e

i j

c

Figura 1.8: Veja exercícios 1.94, 1.102 e 1.103.

E 1.96 Seja H o grafo das arestas (veja exercício 1.24) de um grafo G (por-tanto, H = L(G)). Seja H ′ um subgrafo induzido de H . Mostre que H ′ é ografo das arestas de algum grafo G′.

E 1.97 Dado grafo G e inteiro k, encontrar um subconjunto máximo X de VGtal que δ(G[X]) ≥ k.

E 1.98 Seja G um grafo tal que n(G) > 1 e ρ(G) ≥ δ(G), onde ρ(G) é a densi-dade de G. Mostre que G tem um vértice x tal que

ρ(G− x) ≥ ρ(G) .

Em outras palavras, mostre que é possível retirar um vértice sem com issoreduzir a densidade do grafo.

E 1.99 Seja ρ a densidade de um grafo G (portanto, ρ = m(G)/n(G)). Mostreque G tem um subgrafo H tal que

δ(H) > ρ/2

e m(H)/n(H) ≥ ρ.

E 1.100 Mostre que todo grafo G com pelo menos uma aresta tem um sub-grafo H tal que

ρ(H) < δ(H) mas ρ(H) ≥ ρ(G) ,

onde ρ(G) é a densidade de G.

E 1.101 Mostre que para todo grafo G existe uma bipartição X, Y de VG talque m(G[X]) +m(G[Y ]) ≤ 1

2m(G).

FEOFILOFF Caminhos e circuitos em grafos 30

1.8 Caminhos e circuitos em grafos

Esta seção trata de subgrafos que são caminhos ou circuitos.

Exercícios

EF 1.102 Seja G o grafo representado na figura 1.8. É verdade que e a b f g k éum caminho em G? É verdade que e a b f c d é um caminho em G? É verdadeque e a b f g k j i e é um circuito em G?

E 1.103 Seja G o grafo da figura 1.8. É verdade que G contém um circuitode comprimento 6? É verdade que G contém um circuito induzido de com-primento 6? (Ou seja, é verdade que existe um subconjunto X de VG tal queG[X] é um circuito de comprimento 6?) Exiba um caminho induzido de com-primento 3 em G. (Ou seja, exiba um conjunto X de vértices tal que G[X] éum caminho de comprimento 3.) Exiba um caminho de comprimento 3 emG que não seja induzido.

EU 1.104 Sejam P um caminho com extremos x e x′ e seja Q um caminhocom extremos y e y′. Suponha que VP ∩ VQ 6= ∅. Mostre existe um caminhocom extremos x e y no grafo P ∪Q (veja seção 1.5).

Pergunta adicional: Se z é um vértice em VP ∩ VQ, é verdade que existe,no grafo P ∪Q, um caminho de x a y que passa por z?

E 1.105 Encontre um circuito de comprimento mínimo no grafo de Petersen(veja exercício 1.15 ou figura 1.6). Encontre um circuito de comprimento má-ximo no grafo de Petersen. Encontre um caminho de comprimento máximono grafo de Petersen.

EF 1.106 Verifique que o grafo do cavalo 3-por-3 contém um circuito. Encon-tre o circuito mais longo que puder no grafo do cavalo 4-por-4.

E 1.107 Encontre o mais longo caminho que puder no grafo da dama. En-contre o mais longo circuito que puder no grafo da dama.

E 1.108 O grafo de Heawood25 tem conjunto de vértices 0, 1, 2, . . . , 13.HeawoodCada vértice i é vizinho de (i+ 1) mod 14 e de (i+ 13) mod 14.26 Além disso,cada i é vizinho de um terceiro vértice, que depende da paridade de i: se

25 Percy John Heawood (− ). (Veja verbete na Wikipedia.)26 A expressão “i mod j” denota o resto da divisão de i por j.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Heawood.html

http://en.wikipedia.org/wiki/Heawood


i é par então ele é vizinho de (i + 5) mod 14 e se i é ímpar então ele é vizi-nho de (i + 9) mod 14. Faça uma figura do grafo. Encontre um circuito decomprimento mínimo no grafo de Heawood.

E 1.109 Suponha que um grafo G tem um circuito ímpar. Mostre que G tam-bém tem um circuito ímpar induzido, ou seja, que existe um conjunto X devértices tal que G[X] é um circuito ímpar. Algo análogo vale para circuitospares?

E 1.110 Dê um exemplo de um grafoG e um caminho emG que seja maximalmas não seja máximo.

EU 1.111 (BOM!) Suponha que d(v) ≥ k para todo vértice v de um grafo.Mostre que o grafo tem um caminho de comprimento pelo menos k. (Suges-tão: Tome um caminho maximal.)

O problema poderia ter sido formulado assim: mostre que todo grafo Gcontém um caminho de comprimento pelo menos δ(G).

EU 1.112 Seja G um grafo tal que δ(G) ≥ 2. Prove que G tem um circuito.

E 1.113 Seja G um grafo tal que δ(G) ≥ 3. Prove que G tem um circuito decomprimento par.

E 1.114 Seja k um número natural maior que 1. Suponha que d(v) ≥ k paratodo vértice v de um grafoG. Mostre queG tem um circuito de comprimentopelo menos k + 1. Em outras palavras, mostre que G tem um circuito decomprimento não inferior a δ(G) + 1, desde que δ(G) > 1. (Sugestão: Vejaexercício 1.111.)

E 1.115 Mostre que todo grafo G com pelo menos k n(G) arestas contém umcaminho de comprimento k. (Sugestão: Combine os exercícios 1.100 e 1.111.)

1.8.1 Passeios

Um passeio (= walk) em um grafo é qualquer sequência finita (v0, v1, v2, . . . ,vk−1, vk) de vértices tal que vi é adjacente a vi−1 para todo i entre 1 e k. (Noteque os vértices do passeio podem não ser distintos dois a dois.) Dizemos queo vértice v0 é a origem do passeio e que vk é o término do passeio.

Um passeio (v0, . . . , vk) é fechado (= closed) se sua origem coincide com otérmino, ou seja, se v0 = vk.


Uma trilha (= trail) é um passeio sem arestas repetidas, isto é, um passeiocujas arestas são distintas duas a duas. Um ciclo (= cycle) é uma trilha fechadade comprimento não nulo.

EU 1.116 Seja (v0, v1, v2, . . . , vk) um passeio com origem r e término s emum grafo G. Mostre que G tem um caminho com extremos r e s. Maisespecificamente, mostre há um caminho com extremos r e s no subgrafo(v0, v1, v2, . . . , vk , v0v1, v1v2, . . . , vk−1vk) de G.

E 1.117 Suponha que (v0, . . . , vk) é uma passeio fechado em um grafo G. Éverdade que G tem um circuito?

EU 1.118 Seja (v0, v1, v2, . . . , vk) um ciclo em um grafo G. Mostre que há umcircuito no subgrafo (v1, v2, . . . , vk, v0v1, v1v2, . . . , vk−1vk) de G.

FEOFILOFF Cortes 33

1.9 Cortes

Suponha que X é um conjunto de vértices de um grafo G. O corte associadoa X é o conjunto de todas as arestas que têm uma ponta em X e outra emVG rX . O corte associado a X será denotado por ∂(X)

∂G(X)

ou simplesmente por ∂(X).27 (Alguns livros preferem escrever δ(X) ouaté∇(X).)

É evidente que ∂(∅) = ∂(VG) = ∅. É claro que |∂(v)| = d(v) para todovértice v. Para qualquer conjunto X de vértices, diremos que |∂(X)| é o graude X e denotaremos esse número por d(X): d(X)

d(X) := |∂(X)| .

Um corte (= cut = coboundary) em um grafo G é qualquer conjunto daforma ∂(X), onde X é uma parte28 de VG. (Um corte é, portanto, um con-junto de arestas e não de vértices.)

Uma ponte (= bridge) ou istmo (= isthmus) ou aresta de corte (= cut edge) emum grafo é qualquer aresta a tal que a é um corte.

Exercícios

EF 1.119 Seja X um conjunto de vértices de um grafo G. Mostre que(VG, ∂(X)) é um subgrafo gerador bipartido de G.

E 1.120 Suponha que um grafo G tem uma ponte uv. Que aparência tem amatriz de adjacências deG? Que aparência tem a matriz de incidências deG?

E 1.121 Seja e uma ponte de um grafo G. Mostre que G é planar se e somentese G− e é planar.

E 1.122 Seja G o grafo representado na figura 1.8. É verdade que o conjuntoae, ef, fj, jk, cd, dh é um corte?

E 1.123 Encontre o menor corte que puder no grafo da dama 8-por-8. Encon-tre o maior corte que puder no grafo da dama.

27 Não confunda ∂ com a letra grega δ.28 Uma parte de um conjunto é o mesmo que um subconjunto do conjunto.

FEOFILOFF Cortes 34

E 1.124 Encontre o menor corte que puder no grafo do bispo t-por-t. O grafodo bispo tem pontes?

E 1.125 Encontre o menor corte que puder no grafo de Petersen. Encontre omaior corte que puder no grafo de Petersen.

EF 1.126 Para qualquer conjunto X de vértices, denotamos por N(X), o con-N(X)

junto dos vértices em VG rX . É verdade que d(X) = |N(X)| para todo X?

EI 1.127 Mostre que para qualquer grafo G e qualquer parte X de VG tem-se∑x∈X dG(x) = 2m(G[X]) + dG(X) . (1.2)

(Isso é uma generalização do exercício 1.41.)

E 1.128 Suponha que todos os vértices de um grafo G têm grau par. É ver-dade d(X) é par para todo subconjunto X de VG?

Suponha que todos os vértices de um grafoG têm grau ímpar. É verdaded(X) é ímpar para todo subconjunto próprio e não vazio X de VG?

E 1.129 Suponha que todos os vértices de um grafo G têm grau par. Mostreque G não tem pontes.

E 1.130 (CORTE GRANDE) Mostre que em todo grafo existe um corte quecontém pelo menos a metade das arestas do grafo. Em outras palavras, mos-tre que todo grafo G tem um corte ∂(X) tal que d(X) ≥ 1

2m(G).

E 1.131 (BOM!) Mostre que todo grafo G tem um subgrafo gerador bipar-tido H que satisfaz a condição dH(v) ≥ dG(v)/2 para todo vértice v.

E 1.132 (DIFERENÇA SIMÉTRICA) Mostre que ∂(X ⊕Y ) = ∂(X)⊕ ∂(Y ) paraquaisquer conjuntos X e Y de vértices de um grafo. Aqui, A ⊕ B denota aA⊕Bdiferença simétrica29 dos conjuntos A e B.

E 1.133 (SUBMODULARIDADE) Mostre que em qualquer grafo G, paraquaisquer subconjuntos X e Y de VG, tem-se

d(X ∪ Y ) + d(X ∩ Y ) ≤ d(X) + d(Y ) .

29 A diferença simétrica de dois conjuntos A e B é o conjunto (A r B) ∪ (B r A). É fácilverificar que A⊕B = (A ∪B) r (A ∩B).

FEOFILOFF Cortes 35

1.9.1 Interação de cortes com caminhos e circuitos

Dizemos que um corte ∂(X) separa um vértice x de um vértice y se x ∈ X ey /∈ X .

E 1.134 Seja P um caminho num grafo G. Seja X um conjunto de vérticesque contém um e apenas um dos extremos de P . Mostre que EP ∩ ∂(X) 6= ∅.

E 1.135 Seja D um corte e O um circuito em um grafo G. Mostre que |D∩EO|é par.

E 1.136 Seja D um conjunto de arestas de um grafo G. Suponha que |D∩EO|é par para todo circuito O em G. Mostre que D é um corte.

E 1.137 Seja D um corte e P um caminho em um grafo G. O que se podedizer sobre a paridade de |D ∩ EP |?

EI 1.138 Prove que, para qualquer par (x, y) de vértices de qualquer grafo,vale uma e apenas uma das seguintes afirmações: (1) um caminho liga x a you (2) um corte vazio separa x de y. (Outra maneira de formular a mesmaquestão: prove que existe um caminho de x a y se e somente se nenhum cortevazio que separa x de y.)

E 1.139 (ALGORITMO) Construa um algoritmo eficiente que receba vérticesv e w de um grafo G e encontre um caminho com extremos v e w ou mostreque tal caminho não existe.

E 1.140 Seja G o grafo que tem vértices a, b, . . . , g e arestas ab, bc, cd, de, ec,bf , gb, ag. Quais das arestas pertencem a circuitos de G? Quais das arestassão pontes?

EI 1.141 (CIRCUITOS VERSUS PONTES) Prove que, em qualquer grafo, toda ponte vscircuitoaresta é de um e apenas um de dois tipos: ou ela pertence a um circuito do

grafo ou é uma ponte. (Outra maneira de propor a questão: prove que umaaresta é ponte se e somente se não pertence a um circuito.)

E 1.142 Suponha que toda aresta de um grafo G é uma ponte. Que aparênciatem G? (Veja antes o exercício 1.141.)

Suponha agora que toda aresta de G pertence a um circuito. Que apa-rência tem G? (Veja seções 1.12 e 1.13.)

FEOFILOFF Grafos conexos 36

1.10 Grafos conexos

Em qualquer grafo G, dizemos um vértice v está ligado a um vértice w se Gcontém um caminho com extremos v ew. É evidente que a relação é simétrica:se v está ligado a w então também w está ligado a v.

Um grafo é conexo (= connected) se seus vértices são ligados dois a dois. Emoutras palavras, um grafo é conexo se v é ligado a w para cada par (v, w) deseus vértices.

Exercícios

E 1.143 Mostre que todo grafo completo é conexo. Mostre que todo caminhoé um grafo conexo. Mostre que todo circuito é um grafo conexo.

EIF 1.144 Seja e uma aresta e v um vértice de um circuito O. Mostre que ografo O − e é conexo. Mostre que O − v é conexo.

EF 1.145 Seja e uma aresta e v um vértice de um caminho P . Em que condi-ções P − e é conexo? Em que condições P − v é conexo?

E 1.146 O grafo do cavalo 3-por-3 é conexo? O grafo do bispo t-por-t é co-nexo?

E 1.147 Mostre que o k-cubo é conexo (qualquer que seja k).

EF 1.148 Suponha que um subgrafo geradorH de um grafoG é conexo. Mos-tre que G é conexo.

EU 1.149 Seja e uma ponte de um grafo G. Mostre que o grafo G − e não éconexo.

E 1.150 Seja G um grafo e X uma parte própria e não vazia de VG (isto é,∅ ⊂ X ⊂ VG). Mostre que o grafo G− ∂(X) não é conexo.

EI 1.151 Mostre que um grafo G é conexo se e somente se ∂(X) 6= ∅ paratodo subconjunto próprio e não vazio X de VG (ou seja, para todo X tal que∅ ⊂ X ⊂ VG).

EF 1.152 Quais das seguintes afirmações são verdadeiras para qualquergrafo G? 1. Se G é conexo então ∂(X) 6= ∅ para todo X tal que ∅ ⊂ X ⊂ VG.


2. Se G é conexo então ∂(X) 6= ∅ para algum X tal que ∅ ⊂ X ⊂ VG. 3. Se∂(X) 6= ∅ para todo X tal que ∅ ⊂ X ⊂ VG então G é conexo. 4. Se ∂(X) 6= ∅para algum X tal que ∅ ⊂ X ⊂ VG então G é conexo.

E 1.153 (ALGORITMO) Construa um algoritmo eficiente que decida se umgrafo é conexo. O que o seu algoritmo devolve (ou seja, qual a “saída” doalgoritmo)?

E 1.154 Seja G um grafo bipartido com bipartição (U,W ) tal que |U | ≤ k e|W | ≤ k. Mostre que se δ(G) > k/2 então G é conexo.

E 1.155 Sejam x, y e z três vértices de um grafo conexo G. É verdade que Gtem um caminho que contém x, y e z?

E 1.156 Mostre que dois vértices v ew de um grafo estão ligados se e somentese existe um passeio de v a w. (Veja subseção 1.8.1.)

EF 1.157 Seja X um conjunto de vértices de um grafo conexo G. É verdadeque G[X] é conexo?

EU 1.158 Sejam P e Q dois caminhos tais que VP ∩ VQ 6= ∅. Mostre que ografo P ∪Q (veja seção 1.5) é conexo.

E 1.159 (BOM!) Sejam G e H dois grafos conexos tais que VG ∩VH 6= ∅. Mos-tre que o grafo G ∪H (veja seção 1.5) é conexo.

EF 1.160 Sejam G e H dois grafos. Quais das seguinte implicações são ver-dadeiras? 1. Se VG ∩ VH = ∅ então G ∪H não é conexo. 2. Se G ∪H é conexoentão VG ∩ VH 6= ∅. 3. Se G ∪H não é conexo então VG ∩ VH = ∅.

EU 1.161 (BOM!) Suponha que um certo vértice x de um grafo G é ligado acada um dos demais vértice. Mostre que G é conexo.

EU 1.162 Seja O um circuito em um grafo conexo G. Mostre que G − e éconexo para toda aresta e de O.

E 1.163 Seja v um vértice de grau 1 num grafo conexo G. Mostre que o grafoG− v é conexo.

E 1.164 Suponha que G é um grafo conexo com pelo menos uma aresta. Éverdade que existe uma aresta a tal que G− a é conexo?


E 1.165 Seja G um grafo conexo e X uma parte de VG tal que |∂(X)| = 1.Mostre que os grafos induzidos G[X] e G[X] são ambos conexos.

EF 1.166 Seja G um grafo conexo e seja v um dos extremos de um caminhomaximal (veja página 27) em G. É verdade que G[N(v)] é conexo?

E 1.167 (BOM!) Mostre que todo grafo conexo G com dois ou mais vérticestem um vértice v tal que G− v é conexo.

EF 1.168 Quais das seguintes afirmações valem para qualquer grafo G? 1. SeG é conexo então G− v é conexo para todo vértice v. 2. Se G tem um vérticev tal que G− v é conexo então G é conexo.

EI 1.169 Prove que todo grafo conexo com n vértices tem pelo menos n − 1arestas. Em outras palavras, mostre que em todo grafo conexo G tem-se

m(G) ≥ n(G)− 1 .

E 1.170 Seja G um grafo tal que δ(G) ≥ n(G)/2. Mostre que G é conexo.

E 1.171 Seja G um grafo tal que δ(G) ≥ bn(G)/2c.30 Mostre que G é conexo.(Mostre que o resultado é o melhor possível no seguinte sentido: existemgrafos desconexos com d(v) ≥ bn/2c − 1 para todo vértice v.)

E 1.172 Suponha que d(v) + d(w) ≥ n−1 para todo par (v, w) de vértices nãoadjacentes de um grafo G. Mostre que G é conexo.

E 1.173 Mostre que todo grafo com n vértices e mais que 12(n − 1)(n − 2)

arestas é conexo.

E 1.174 Prove que se um grafo G não é conexo então seu complemento G éconexo.

E 1.175 Prove que se um grafo G é conexo então o grafo das arestas L(G)também é conexo.

E 1.176 Sejam P ∗ e Q∗ dois caminhos de comprimento máximo em um grafoconexo G. Mostre que P ∗ e Q∗ têm um vértice em comum.

30 Por definição, bxc é o único inteiro i tal que i ≤ x < i+ 1.

FEOFILOFF Componentes 39

1.11 Componentes

Um subgrafo conexoH de um grafoG é maximal (com relação à propriedadede ser conexo) se não faz parte de um subgrafo conexo maior, ou seja, se nãoexiste grafo conexo H ′ tal que H ⊂ H ′ ⊆ G.

Um componente de um grafo G é qualquer subgrafo conexo maximal de G.O número de componentes de um grafo G será denotado por c(G)

c(G) .

É claro que um grafo é conexo se e somente se tem um só componente.

Exercícios

E 1.177 Quantos componentes tem o grafo do cavalo 3-por-3? Quantos com-ponentes tem o grafo do bispo t-por-t?

E 1.178 Seja a uma aresta e v um vértice de um caminho P . Mostre que P −atem exatamente dois componentes. Mostre que P − v tem um ou dois com-ponentes.

E 1.179 Seja a uma aresta e v um vértice de um circuito O. Mostre que O − atem um só componente. Mostre que O − v tem um só componente.

E 1.180 Seja P um caminho e S uma parte própria de VP . Prove que c(P −S) ≤ |S|+ 1.

E 1.181 Seja O um circuito e S uma parte de VO tal que 0 < |S| < n(O). Proveque c(O − S) ≤ |S|.

EU 1.182 Seja G um grafo tal que ∆(G) ≤ 2. Descreva os componentes de G.

E 1.183 Seja G um grafo 2-regular. Mostre que cada componente de G é umcircuito.

EF 1.184 Mostre que, em qualquer grafo, todo vértice pertence a um e apenasum componente. Em outras palavras, mostre que em qualquer grafo G osconjuntos de vértices de todos os componentes formam uma partição de VG.

E 1.185 Seja H um componente de um grafo G. Mostre que ∂G(VH) = ∅.


EF 1.186 Seja X um conjunto de vértices de um grafo G. Prove ou desprovea seguinte afirmação: Se ∅ ⊂ X ⊂ VG e ∂G(X) = ∅ então G[X] é um compo-nente de G.

E 1.187 SejaX um conjunto não vazio de vértices de um grafoG. Mostre queG[X] é um componente de G se e somente se G[X] é conexo e ∂G(X) = ∅.

EI 1.188 Seja x um vértice de um grafo G. Seja X o conjunto de todos osvértices ligados a x. Mostre que G[X] é um componente de G.

E 1.189 (ALGORITMO) Construa um algoritmo eficiente que receba um vér-tice x de um grafo G e calcule o conjunto de vértices do componente de Gque contém x.

E 1.190 (ALGORITMO) Construa um algoritmo eficiente que calcule o nú-mero de componentes de qualquer grafo dado.

EF 1.191 Seja X um conjunto de vértices de um grafo G. Suponha quec(G−X) > |X|+ 1. É verdade que G não é conexo?

E 1.192 SejaH um subgrafo gerador de um grafoG. Mostre que c(H) ≥ c(G).

E 1.193 Seja a uma aresta de um grafo G. Mostre que c(G) ≤ c(G − a) ≤c(G) + 1 para qualquer aresta a de G. Mostre a é uma ponte se e somente sec(G− a) = c(G) + 1.

E 1.194 Seja v um vértice de um grafo conexo G. Mostre que o número decomponentes de G− v não passa de d(v).

E 1.195 Seja G um grafo conexo e suponha que d(v) é par para todo vértice vde G. Mostre que, para qualquer vértice v, o número de componentes deG− v não passa de 1

2d(v).

E 1.196 (ALGORITMO) Construa um algoritmo eficiente para o seguinte pro-blema: Dado um grafo G e um número natural k, encontrar um conjunto Xde não mais que k vértices que maximize o número de componentes deG−X .

EI 1.197 Mostre que em todo grafo G tem-se

m(G) ≥ n(G)− c(G) .


E 1.198 Sejam n, m e c os números de vértices, de arestas e de componentes,respectivamente, de um grafo G. Mostre que

m ≤ 12(n− c)(n− c+ 1) .

FEOFILOFF Florestas e árvores 42

1.12 Florestas e árvores

Esta seção trata de duas espécies importantes de grafos: as florestas e as ár-vores. Árvores podem ser entendidas como uma generalização de caminhos(veja os exercícios 1.201 e 1.202).

Uma floresta (= forest), ou grafo acíclico, é um grafo sem circuitos. Essa de-finição pode ser reformulada assim: um grafo é uma floresta se cada uma desuas arestas é uma ponte (veja exercício 1.203).

Uma árvore (= tree) é uma floresta conexa. É claro que cada componente deuma floresta é uma árvore.31

Uma folha (= leaf ) de uma floresta é qualquer vértice da floresta que tenhagrau 1.

Exercícios

EF 1.199 Mostre que todo caminho é uma árvore.

EF 1.200 Mostre que toda estrela (veja a seção 1.2) é uma árvore.

E 1.201 Seja (v1, v2, v3, . . . , vn) uma sequência de objetos distintos dois a dois.Para cada j, seja i(j) um índice em 1, . . . , j−1. Mostre que o grafo

(v1, v2,

v3, . . . , vn , v2vi(2), v3vi(3), . . . , vnvi(n))

é uma árvore. (Compare a maneiracomo o grafo foi definido com a definição de caminho na seção 1.4.) (Com-pare com o exercício 1.202.)

E 1.202 Seja T uma árvore. Mostre que existe uma permutação (v1, v2, . . . , vn)de VT dotada da seguinte propriedade: para j = 2, . . . , n, o vértice vj é ad-jacente a exatamente um dos vértices do conjunto v1, . . . , vj−1. (Comparecom o exercício 1.201.)

EI 1.203 Mostre que um grafo é uma floresta se e somente se cada uma desuas arestas é uma ponte. (Veja o exercício 1.141.)

E 1.204 Seja e uma das arestas de uma floresta F . Mostre que F − e tem pelomenos dois componentes. Mostre que c(F − e) = c(F ) + 1.

31 Em algumas disciplinas, a palavra “árvore” traz imediatamente à mente as ideias depai e filho. No presente contexto, entretanto, as expressões “pai de um vértice” e “filho deum vértice” não fazem sentido. Eles só adquirem sentido se um dos vértices da árvore forescolhido para fazer o papel de “raiz”. (Se r é a raiz da árvore então o pai de qualquer outrovértice v é o vértice adjacente a v no único caminho (veja exercício 1.206) que liga v a r. Todovizinho de v que não seja o pai de v é filho de v.)


EI 1.205 Uma grafo G é conexo minimal (ou minimamente conexo) se G éconexo mas, para toda aresta e, o grafo G − e não é conexo. Mostre quetoda árvore é um grafo conexo minimal. Mostre a recíproca: que todo grafoconexo minimal é uma árvore.

EI 1.206 Seja (x, y) um par de vértices de uma floresta F . Mostre que existeno máximo um caminho em F com extremos x e y.

E 1.207 (RECÍPROCA DE 1.206) Suponha que um grafo G tem a seguintepropriedade: para todo par (x, y) de vértices, existe no máximo um caminhoem G com extremos x e y. Mostre que G é uma floresta.

E 1.208 (ALGORITMO) Construa um algoritmo eficiente que decida se umgrafo dado é uma árvore.

E 1.209 Seja v uma folha de uma árvore T . Mostre que T − v é uma árvore.

EU 1.210 Mostre que toda árvore com pelo menos uma aresta tem pelo me-nos duas folhas.

E 1.211 Mostre que toda floresta F tem pelo menos ∆(F ) folhas.

EI 1.212 (IMPORTANTE) Prove que em toda árvore T tem-se

m(T ) = n(T )− 1 .

(Compare com o exercício 1.169.)

EI 1.213 Seja G um grafo conexo G tal que m(G) = n(G) − 1. Prove que G éuma árvore.

E 1.214 Seja F uma floresta tal que m(F ) = n(F ) − 1. Prove que F é umaárvore.

EI 1.215 Mostre que um grafo F é uma floresta se e somente se

m(F ) = n(F )− c(F ) .

(Compare com o exercício 1.197.)

E 1.216 Seja T uma árvore com dois ou mais vértices. Seja X o conjunto dosvértices de T cujo grau é maior que 2. Mostre que T tem 2 +

∑x∈X (d(x)− 2)

folhas.


E 1.217 Seja T uma árvore com vértices 1, . . . , n. Suponha que os grausdos vértices 1, 2, 3, 4, 5, 6 são 7, 6, 5, 4, 3, 2 respectivamente e que os vértices7, . . . , n são folhas. Determine n (e portanto o número de folhas da árvore).

E 1.218 Seja T uma árvore com p + q vértices. Suponha que p dos vérticestêm grau 4 e q são folhas. Mostre que q = 2p+ 2.32

E 1.219 Seja T uma árvore com pelo menos três vértices. É verdade que ocomplemento T de T é conexo a menos que T seja um estrela?

E 1.220 Sejam P,Q,R três caminhos em uma árvore e T . Suponha que VP ∩VQ 6= ∅, VQ ∩ VR 6= ∅ e VP ∩ VR 6= ∅. Prove que VP ∩ VQ ∩ VR 6= ∅.

E 1.221 Mostre que toda floresta é planar.

32 Imagine que os vértices de grau 4 são átomos de carbono e os de grau 1 são átomosde hidrogênio. O grafo representa então a molécula do hidrocarboneto CpHq . Veja o exercí-cio 1.5.

FEOFILOFF Pontes e grafos aresta-biconexos 45

1.13 Pontes e grafos aresta-biconexos

Um grafo é aresta-biconexo (= edge-biconnected) se for conexo e não tiver pon-tes (veja seção 1.9).33 Grafos aresta-biconexos também são conhecidos como2-aresta-conexos (= 2-edge-connected). 2-aresta-

conexoUm grafo é aresta-biconexo se e somente se possui a seguinte propriedade:para todo par r, s de vértices, existem dois caminhos com extremos r e ssem arestas em comum. (Veja exercício 1.232 abaixo.)

Exercícios

E 1.222 Mostre que cada componente do grafo do bispo 3-por-3 é um grafoaresta-biconexo.

E 1.223 O grafo do bispo t-por-t tem dois componentes. É verdade que cadaum deles é aresta-biconexo?

EF 1.224 Seja G um grafo conexo. Mostre que G é aresta-biconexo se e so-mente se o grafo G− e é conexo qualquer que seja a aresta e.

E 1.225 SejaG um grafo conexo. Mostre queG é aresta-biconexo se e somentese cada aresta de G pertence a um circuito. (Veja exercício 1.141.)

EF 1.226 Mostre que um grafoG é aresta-biconexo se e somente se |∂(X)| ≥ 2para toda parte não vazia e própria X de VG.

E 1.227 Seja r um número natural maior que 1. Seja G um grafo bipartidor-regular. Prove que G não tem pontes.

E 1.228 Seja G um grafo bipartido conexo r-regular, com r ≥ 2. Prove que Gé aresta-biconexo (veja exercício 1.227).

E 1.229 Considere o grafo do bispo 5-por-5. Seja r o vértice de coordenadas(1, 2) e s o vértice de coordenadas (5, 4). Encontre dois caminhos, sem arestasem comum, de r a s. Agora encontre dois caminhos de r a s sem arestas emcomum mas com pelo menos um vértice interno em comum.

33 Embora K1 seja aresta-biconexo de acordo com nossa definição, muitos livros não con-sideram K1 aresta-biconexo.

FEOFILOFF Pontes e grafos aresta-biconexos 46

E 1.230 Suponha que um grafo G tem a seguinte propriedade: para cada parr, s de vértices de G, existem dois caminhos, sem arestas em comum, comextremos r e s. Mostre que G é aresta-biconexo.

EI 1.231 (RECÍPROCA DE 1.230) Seja G um grafo aresta-biconexo. Mostreque para cada par r, s de vértices de G existem dois caminhos, sem arestasem comum, com extremos r e s.

EI 1.232 (COROLÁRIO DE 1.230 E 1.231) Mostre que um grafo G é aresta-biconexo se e somente se para cada par r, s de seus vértices existem doiscaminhos de r a s sem arestas em comum.

E 1.233 (ALGORITMO) Construa um algoritmo que receba um grafo G e de-cida se G é aresta-biconexo.

E 1.234 (ALGORITMO) Construa um algoritmo que receba dois vértices r es de um grafo G e devolva (1) dois caminhos de r a s sem arestas em comumou (2) um conjunto X de vértices tal que r ∈ X , s /∈ X e |∂(X)| ≤ 1.

FEOFILOFF Articulações e grafos biconexos 47

1.14 Articulações e grafos biconexos

Uma articulação (= articulation) ou vértice de corte (= cut vertex) num grafoG é um vértice v tal que G− v tem mais componentes que G.

Um grafo é biconexo (= biconnected) se for conexo e não tiver articulações.34

Grafos biconexos também são conhecidos como 2-conexos e como vértice- 2-conexobiconexos. vértice-

biconexoUm grafo é biconexo se e somente se tem a seguinte propriedade fundamen-tal: para todo par r, s de vértices, existem dois caminhos de r a s sem vér-tices internos em comum. (Veja o exercício 1.242 abaixo.)

Exercícios

E 1.235 Seja v uma articulação de um grafo G. Que aparência tem a matrizde adjacências de G? Que aparência tem a matriz de incidências de G?

E 1.236 Seja v um vértice de um grafo conexo G. Mostre que v é uma articu-lação se e somente se existem grafos G1 e G2 tais que G = G1∪G2, n(G1) ≥ 2,n(G2) ≥ 2 e VG1 ∩ VG2 = v.

E 1.237 Seja G um grafo conexo. Mostre que G é biconexo se e somente se,para todo vértice v, o grafo G− v é conexo.

EF 1.238 Seja v uma articulação de um grafo G. Mostre que G− v é conexo.

EF 1.239 Suponha que um grafo G tem a seguinte propriedade: para todopar r, s de vértices, existem dois caminhos de r a s sem vértices internosem comum (ou seja, cada vértice em VG r r, s pertence a no máximo umdos caminhos). Mostre que G é biconexo.

EF 1.240 Sejam v e w dois vértices de um grafo biconexo G. Seja P um cami-nho em G com extremos v e w. Seja X o conjunto dos vértices internos de P .É verdade que G−X tem um caminho com extremos v e w?

EI 1.241 (RECÍPROCA DE 1.239) Seja G um grafo biconexo. Mostre que Gtem a seguinte propriedade: para todo par r, s de vértices, existem doiscaminhos de r a s sem vértices internos em comum (ou seja, cada vértice emVG r r, s pertence a no máximo um dos caminhos).

34 Muitos livros não consideram K1 e K2 biconexos, embora ambos sejam biconexos deacordo com nossa definição. Para fugir dessa discussão, suporemos implicitamente que to-dos os nossos grafos têm três ou mais vértices.

FEOFILOFF Articulações e grafos biconexos 48

EI 1.242 (COROLÁRIO DE 1.241 E 1.239) Mostre que um grafo G é biconexose e somente se, para todo par r, s de vértices, G tem dois caminhos de ra s sem vértices internos em comum.

E 1.243 (ALGORITMO) Construa um algoritmo que decida se um grafo dadoé biconexo.

E 1.244 (ALGORITMO) Construa um algoritmo que receba dois vértices r es de um grafo conexo G e devolva (1) dois caminhos de r a s sem vérticesinternos em comum ou (2) uma articulação v tal que r e s pertencem a com-ponentes distintos de G− v.

EI 1.245 Mostre que um grafo G é biconexo se e somente se todo par de vér-tices pertence a um circuito.

E 1.246 Seja G um grafo conexo com 3 ou mais vértices. Mostre que se G temuma ponte então G tem uma articulação. A recíproca é verdadeira?

E 1.247 Seja G um grafo biconexo. Mostre que G é aresta-biconexo. A recí-proca é verdadeira?

E 1.248 Seja v uma articulação de G. Mostre que G é planar se e somente seG− v é planar.

FEOFILOFF Menores de grafos 49

1.15 Menores de grafos

Grafos dentro de grafos, dentro de grafos.

Esta seção introduz duas generalizações do conceito de subgrafo. Essas gene-ralizações têm um papel importante no estudo da planaridade (capítulo 20),da coloração de vértices (capítulo 14) e de diversos outros problemas sobregrafos.

Um grafo H é um menor (= minor), ou subcontração, de um grafo G se VH é menorminoruma subpartição35 V1, . . . , Vp de VG tal que

• cada G[Vi] é conexo e• Vi é adjacente a Vj em H somente se há alguma aresta de Vi a Vj em G.

A expressão “H é menor de G” também é usada, num sentido mais geral,para dizer que H é isomorfo a um menor de G.

Figura 1.9: O grafo à direita é um menor do grafo à esquerda.

Um grafo H é um menor topológico (= topological minor) de um grafo G se menortopológicoVH ⊆ VG e existe uma função P que associa um caminho em G a cada aresta

de H de tal modo que

• para cada aresta xy de H , o caminho P (xy) tem extremos x e y e nãotem vértices internos em VH e• se xy e uv são duas arestas distintas de H então P (xy) e P (uv) não têm

vértices internos em comum.

A expressão “H é menor topológico de G” também é usada, num sentidomais geral, para dizer que H é isomorfo a algum menor topológico de G.

Se H é um menor topológico de G, diz-se também que G “contém uma sub- subdivisãodivisão” de H .

(O conceito de menor e menor topológico é poderoso. Se um grafoG não tem

35 Uma subpartição de um conjunto V é uma coleção V1, . . . , Vp de subconjuntos nãovazios de V tal que Vi ∩ Vj = ∅ sempre que i 6= j.


subgrafo isomorfo a um determinado grafo H , não é possível inferir quasenada sobre a estrutura de G. Mas se G não tem um menor isomorfo a H ,então pode-se dizer muita coisa interessante sobre G.)

Exercícios

EF 1.249 Seja H um subgrafo de um grafo G. Mostre que H é um menortopológico de G.

EF 1.250 Seja H um subgrafo de um grafo G. Mostre que H é isomorfo a ummenor de G.

E 1.251 Mostre que um grafo G tem um menor topológico isomorfo a K3 see somente se G contém um circuito.

E 1.252 Mostre que um grafo G tem um menor isomorfo a K3 se e somentese G contém um circuito. Procure fazer afirmações análogas com K4 no lugarde K3.

E 1.253 Mostre que o grafo de Petersen tem um menor isomorfo a K5 (masnão tem subgrafo isomorfo a K5).

E 1.254 Mostre que o grafo de Petersen tem um menor topológico isomorfoa K3,3.

E 1.255 Mostre que o 4-cubo tem um menor topológico isomorfo aK3,3. Mos-tre também que K5 é isomorfo a um menor topológico do 4-cubo.

E 1.256 Seja H um menor topológico de G. Mostre que H é isomorfo a ummenor de G. Mostre que a recíproca não é verdadeira.

E 1.257 Seja H um menor de um grafo G. Suponha que ∆(H) ≤ 3. Prove queH é isomorfo a um menor topológico de G.

E 1.258 Dê bons exemplos para mostrar que a condição “∆(H) ≤ 3” é essen-cial no exercício 1.257.

EF 1.259 Seja G um grafo biconexo com pelo menos 4 vértices. Mostre quepara toda aresta a de G tem-se que G− a é conexo ou G/a é conexo.


E 1.260 Prove que a relação é-menor-de é uma relação de ordem. Mais pre-cisamente, prove que (1) G é um menor de G, (2) se H é um menor de G e Gé um menor de H então H é G, (3) se H é um menor de G e G é um menor deF então H é um menor de F . (Em todas essas afirmações, “é um menor de”deve ser entendido com o “é isomorfo a um menor de”.)

Prove que a relação é-menor-topológico-de é uma relação de ordem.

FEOFILOFF Mapas planos e suas faces 52

1.16 Mapas planos e suas faces

Já dissemos na seção 1.6 que, grosso modo, um grafo é planar se pode ser de-senhado no plano36 sem que as arestas se cruzem. A definição exata envolveos conceitos de curva e mapa plano, que passamos a discutir.

Uma curva37 é qualquer conjunto de pontos no plano R2 que seja homeo-morfo ao intervalo fechado [0, 1] da reta. Em outras palavras, um subcon-junto c de R2 é uma curva se existe uma bijeção contínua (estou me referindoà continuidade topológica) do intervalo [0, 1] em c. As imagens de 0 e 1 sobessa bijeção contínua são os extremos da curva.38

Um mapa plano39 é um par (P,C) de conjuntos finitos, sendo P um conjuntode pontos do plano e C um conjunto de curvas tal que

• os extremos de cada curva são elementos de P ,• o interior de cada curva é disjunto de P ,• o interior de cada curva é disjunto de todas os demais curvas,• duas curvas diferentes têm no máximo um extremo em comum.

Os elementos de P são os pingos40 do mapa e os de C são as curvas dopingosmapa.41curvas

Figura 1.10: O mapa da esquerda não é plano. O mapaplano da direita representa um K4.

O grafo de um mapa plano (P,C) é definido da maneira óbvia: o conjuntode vértices do grafo é P e dois vértices v e w são adjacentes no grafo se existeuma curva em C com extremos v e w.

Dizemos que um mapa plano (P,C) representa um grafo G se o grafo de

36 Do ponto de vista técnico, seria mais cômodo usar a superfície da esfera no lugar doplano. Mas os resultados são equivalentes.

37 Teria sido tecnicamente mais correto dizer “arco” ou até “arco poligonal”.38 Por definição, os dois extremos são distintos.39 Alguns livros dizem “grafo plano”. Não confunda esta expressão com “grafo planar”.40 Prefiro não dizer “vértices” para evitar confusão com os vértices de um grafo.41 Prefiro não dizer “aresta” para evitar confusão com as arestas de um grafo.


(P,C) é isomorfo (veja capítulo 2) a G. Em geral, um grafo pode ser repre-sentado por muitos mapas planos diferentes.

Um grafo G é planar se for representável por um mapa plano, ou seja, seexistir um mapa plano cujo grafo é isomorfo a G. Esta é a versão precisa dadefinição vaga que demos na seção 1.6.

Exercícios

E 1.261 Veja o “jogo de planaridade” em www.planarity.net.

E 1.262 O grafo de Petersen (veja figura 1.6) é planar?

E 1.263 Seja G um K5 (isto é, um grafo completo com 5 vértices). Mostre queG− e é planar qualquer que seja a aresta e de G. Repita o exercício com K3,3

(veja figura 20.1) no lugar de K5.

E 1.264 Seja e uma ponte de um grafo G. Mostre que G é planar se e somentese G− e é planar.

Seja v uma articulação de G. Mostre que G é planar se e somente se G−vé planar.

1.16.1 Faces e dualidade planar

O suporte de um mapa plano (P,C) é o conjunto P ∪⋃C (trata-se, obvia-

mente, de um subconjunto de R2).42 Em outras palavras, o suporte do mapaé o conjunto de todos os pontos de R2 que são pingos do mapa ou pertencema curvas do mapa.

Uma face (= face) de um mapa plano (P,C) é qualquer região do comple-mento do suporte do mapa, ou seja, qualquer componente conexo — no sen-tido topológico43 — do conjunto R2 r

(P ∪

⋃C). A fronteira de cada face é

formada por curvas do mapa; o número de curvas na fronteira de uma face fé o grau de f .

Se o grafo de um mapa plano com 3 ou mais pingos é aresta-biconexo (ouseja, o grafo é conexo e não tem pontes) então as faces do mapa são “bemcomportadas”:

42 Se X = X1, X2, . . . , Xk então⋃X denota o conjunto X1 ∪X2 ∪ · · · ∪Xk.

43 O conceito topológico de conexão é formalmente análogo ao conceito de conexão dateoria dos grafos: uma parte X do plano é conexa se, para quaisquer pontos x e x′ em X ,existe uma curva com extremos em x e x′ cujos pontos estão todos em X .

http://www.planarity.net/


cada face é homeomorfa a um disco;a fronteira de cada face corresponde a um circuito no grafo do mapa;cada curva pertence à fronteira de exatamente duas faces diferentes.

O grafo das faces, ou grafo dual, de um mapa plano (P,C) é definido daseguinte maneira: os vértices do grafo são as faces do mapa e duas faces sãoadjacentes se suas fronteiras têm pelo menos uma curva em comum. (Noteque o grafo dual é definido a partir de um mapa e não a partir do grafodo mapa. Um grafo planar pode ser representado por vários mapas planosdiferentes, e cada um desses mapas tem o seu grafo dual.)44

Um exemplo: o grafo dos estados do Brasil que examinamos no exercício 1.17é o grafo dual do mapa do Brasil.

Exercícios

E 1.265 Seja (P,C) um mapa plano e suponha que o grafo do mapa é umcaminho. Mostre que (P,C) tem apenas uma face.

Seja (P,C) um mapa plano e suponha que o grafo do mapa é um circuito.Mostre que (P,C) tem exatamente duas faces (e as duas faces têm a mesmafronteira).

E 1.266 Mostre que um mapa plano tem uma e uma só face se e somente seo grafo do mapa é uma floresta.

E 1.267 Quantas faces tem um mapa plano que representa uma grade p-por-q?

E 1.268 Quantas faces tem um mapa plano que representa um 3-cubo?

E 1.269 Seja (P,C) um mapa plano que representa uma grade 3-por-4. Façauma figura do grafo das faces (ou seja, do grafo dual) de (P,C).

E 1.270 Faça uma figura dos grafos das faces de cada um dos mapas planosdesenhados nas figuras 1.11 e 1.12.

44 O estudo da dualidade planar fica mais “limpo” se a definição de grafo é liberalizadapara permitir “arestas paralelas” (ou seja, duas ou mais arestas diferentes com o mesmo parde pontas) e “laços” (ou seja, uma aresta com duas pontas iguais). É claro que a definiçãode mapa plano deve ser liberalizada de acordo. Prefiro não adotar essa liberalização nopresente texto. Para compensar, será necessário evitar ocasionalmente grafos que têm pontesou vértices de grau 2.


Figura 1.11: Faça uma figura do grafo dualde cada um dos mapas planos da figura.

Figura 1.12: Faça uma figura do grafo dualde cada um dos mapas planos da figura.

E 1.271 Seja G um K5 e e uma aresta de G. Seja M um mapa plano querepresenta G− e. Seja G∗ o grafo das faces (ou seja, o grafo dual) de M . Façauma figura de G∗. Verifique que G∗ é planar. Exiba uma representação plana,digamos M∗, de G∗. Faça uma figura do grafo das faces de M∗.

E 1.272 Dê um exemplo de um grafo conexo planar que possa ser represen-tado por dois mapas planos com diferentes números de faces.

EI 1.273 (FÓRMULA DE EULER45) Seja (P,C) um mapa plano cujo grafo éconexo. Mostre que

|P | − |C|+ |F | = 2 , (1.3)

onde F é o conjunto das faces do mapa.46 (Verifique que a fórmula é falsaem mapas cujos grafos não são conexos.)

E 1.274 Seja F o conjunto das faces de um mapa plano (P,C). Suponha queo grafo do mapa é conexo e não tem pontes. Mostre que

∑f∈F d(f) = 2|C|,

sendo d(f) o grau da face f .

45 Leonhard Euler (− ). Veja verbete na Wikipedia.46 Muitos livros usam “V ” e “E” no lugar dos nossos “P” e “C” e portanto escrevem a

fórmula de Euler assim: “|V | − |E|+ |F | = 2”.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Euler.html

http://en.wikipedia.org/wiki/Euler


EI 1.275 Seja G um grafo planar com 3 ou mais vértices. Mostre que

m(G) ≤ 3n(G)− 6 . (1.4)

(Comece tratando do caso em que G é conexo e não tem pontes.) Como sãoas faces de um mapa plano (P,C) tal que |C| = 3|P | − 6?

EF 1.276 É verdade que todo grafo G com m(G) ≤ 3n(G)− 6 é planar?

E 1.277 Deduza da desigualdade (1.4) que K5 não é planar.

E 1.278 Seja G um grafo com 3 ou mais vértices e cintura (veja capítulo 19)não inferior a 4. Mostre que seG é planar entãom(G) ≤ 2n(G)−4. (Comparecom o exercício 1.275.) Deduza daí que K3,3 não é planar.

E 1.279 Seja G um grafo bipartido com 3 ou mais vértices. Mostre que se G éplanar então m(G) ≤ 2n(G)− 4.

E 1.280 Seja G um grafo (U,W )-bipartido. Mostre que se G é planar entãom(G) ≤ 2|U |+ 2|W | − 4.

E 1.281 SejaG um grafo e k um número natural não inferior a 3. Suponha queG tem pelo menos 1

2(k+2) vértices e cintura não inferior a k. Mostre que seG

é planar então m(G) ≤ (n(G)− 2)k/(k− 2). (Compare com o exercício 1.278.)

EI 1.282 Mostre que todo grafo planar tem pelo menos um vértice de graunão superior a 5. Em outras palavras, mostre que δ(G) ≤ 5 para todo grafoplanar G.

E 1.283 Dê exemplo de um grafo planar que não contém vértices de graumenor que 5.

E 1.284 Seja G um grafo bipartido planar. Mostre que δ(G) ≤ 3.

E 1.285 Seja G um grafo com 11 ou mais vértices. Mostre que G e o seucomplemento G não podem ser ambos planares.

E 1.286 Um mapa plano é auto-dual (= self-dual) se o seu grafo for isomorfoao seu grafo dual. Mostre que se (P,C) é auto-dual então 2|P | = |C| + 2.Mostre que nem todo mapa plano (P,C) tal que 2|P | = |C|+ 2 é auto-dual.


EI 1.287 Seja G o grafo de um mapa plano M . Suponha que G é conexo, nãotem pontes e não tem vértices de grau 2 (ou seja, δ(G) ≥ 3). Seja G∗ o grafodas faces (isto é, o grafo dual) do mapa M . Mostre que G∗ é planar.

Seja M∗ um mapa plano que representa G∗. Seja G∗∗ o grafo das facesde M∗. Mostre que G∗∗ ∼= G, ou seja, que G∗∗ é isomorfo a G.

FEOFILOFF Grafos aleatórios 58

1.17 Grafos aleatórios

Seja V o conjunto 1, . . . , n e seja G(n) a coleção de todos os grafos comV

G(n) conjunto de vértices V . É claro que

|G(n)| = 2N , com N :=(n2

).

Qualquer propriedade de grafos (como, por exemplo, a propriedade de serN

conexo)47 define uma subcoleção de G(n). Assim, convém confundir os con-ceitos de “propriedade” e “subcoleção” de G(n). Diremos que quase todografo tem determinada propriedade P(n) se

limn→∞

|P(n)||G(n)|

= 1 .

Uma maneira de estudar o conjunto G(n) é baseada na introdução de umamedida de probabilidade nesse conjunto. Seja p um número no intervalo(0, 1) e escolha cada elemento de V (2), independentemente, com probabili-dade p. (Veja exercício 1.20.) Se A é o conjunto dos pares escolhidos, então(V,A) é um grafo aleatório em G(n). A probabilidade de que o grafo (V,A)assim construído seja idêntico a um determinado elemento de G(n) que tenham arestas é

pm (1− p)N−m .

Se p = 12

então todos os 2N grafos em G(n) são equiprováveis: a probabilidadede obter qualquer um deles é 1/2N .

Exercícios

EF 1.288 Mostre que quase todo grafo em G(n) tem mais que 10000 arestas.

E 1.289 Prove que quase todo grafo G em G(n) é conexo. (Veja a seção 1.17.)

47 Naturalmente, só estamos interessados em propriedades invariantes sob isomorfismo(veja o capítulo 2).

Capítulo 2

Isomorfismo

Dois grafos são isomorfos se têm a mesma “estrutura”. A definição precisado conceito é um pouco trabalhosa, como veremos a seguir.

Um isomorfismo (= isomorphism) entre dois grafos G e H é uma uma bijeção1

f de VG em VH tal que, para todo par (v, w) de elementos de VG, v e w sãoadjacentes em G se e somente se f(v) e f(w) são adjacentes em H .

Dois grafos G e H são isomorfos (= isomorphic) se existe um isomorfismoentre eles. A expressão “G ∼= H” é uma abreviatura de “G é isomorfo a H”. ∼=Em outras palavras, dois grafos são isomorfos se é possível alterar os nomesdos vértices de um deles de tal modo que os dois grafos fiquem iguais.

PROBLEMA DO ISOMORFISMO: Decidir se dois grafos dados são iso-morfos.

Exercícios

E 2.1 Os grafos G e H descritos a seguir são iguais?

VG = a, b, c, d EG = ab, bc, cd, daVH = a, b, c, d EH = ab, bd, dc, ca

E 2.2 Os grafos G e H descritos a seguir são isomorfos?

VG = a, b, c, d, e, f, g EG = ab, bc, cd, cf, fe, gf, ga, gbVH = h, i, j, k, l,m, n EH = hk, nj, jk, lk, lm, li, ij, in

E se trocarmos hk por hn em EH?

1 Uma bijeção é uma função f de um conjunto A em um conjunto B tal que (1) f(a) 6=f(a′) sempre que a 6= a′ e (2) para todo b em B existe a em A tal que b = f(a).

59

FEOFILOFF Isomorfismo 60

E 2.3 Os grafos da figura 2.1 são isomorfos?

Figura 2.1: Os grafos da figura são isomorfos? Veja exercício 2.3.

E 2.4 Mostre que dois caminhos são isomorfos se e somente se têm o mesmocomprimento. Mostre que dois circuitos são isomorfos se e somente se têm omesmo comprimento.

E 2.5 Faça uma lista de todos os grafos sobre o conjunto de vértices 1, 2, 3, 4que sejam dois a dois não isomorfos.

E 2.6 Para n = 1, 2, 3, . . . , faça uma lista de todas as árvores sobre o conjuntode vértices 1, 2, 3, . . . , n que sejam duas a duas não isomorfas.

E 2.7 Os grafos da figura 2.2 são isomorfos dois a dois?

rr

rr

r rr

rrr

ZZZZZZ

A

AAAAA

CCCCCC

Q

QQQ

XXX

J

J

rrr

r rrr

rrraaa

JJJ

EEEE

AAAAAAAAA

!!!

bbbbb

"""

""

ZZZ

rr r r r

rrr

r r

TTTTT

TTTTT

@@@@

CCCCC

aa!!PPPPP

Figura 2.2: Os grafos são dois a dois isomorfos? Veja exercício 2.7.

E 2.8 Os grafos da figura 2.3 são isomorfos? Justifique.

E 2.9 Os grafos da figura 2.4 são isomorfos? Justifique.

E 2.10 SejaG a grade 3-por-4 eH a grade 4-por-3. Os grafosG eH são iguais?são isomorfos?

E 2.11 Mostre que a grade p-por-q e o grafo definido no exercício 1.7 são iso-morfos.


rr

rrr

r r rrrXXX

QQQQCCCCC

JJA

AAAA

ZZZZZ

r rr

r r

rrr

rrXXX

JJA

AAAA

ZZZZZ

@

@@

AAA

Figura 2.3: Veja exercício 2.8.r rrr rr rr.

@@

@@

r rrr rr rr.

@@

Figura 2.4: Os grafos são isomorfos? Veja exercício 2.9.

E 2.12 Mostre que o 3-cubo é isomorfo a algum subgrafo do 4-cubo.

DD 2.13 Caracterize os grafos que são isomorfos a um subgrafo do k-cubo.

E 2.14 Suponha que os grafos G e H são isomorfos. Mostre que n(G) = n(H)e m(G) = m(H). Mostre que para qualquer isomorfismo f de G em H tem-sedG(v) = dH(f(v)) para todo v em VG. Mostre que se G tem um circuito decomprimento k então H também tem um circuito de comprimento k.

E 2.15 (ALGORITMO) O seguinte algoritmo se propõe a decidir se dois gra-fos, G e H , são isomorfos:

examine todas as bijeções de VG em VH ;se alguma delas for um isomorfismo, então G ∼= H ;caso contrário, G e H não são isomorfos.

Discuta o algoritmo.

E 2.16 (ALGORITMO) O seguinte algoritmo se propõe a decidir se dois gra-fos, G e H , são isomorfos:

se n(G) 6= n(H) então G e H não são isomorfos;se m(G) 6= m(H) então G e H não são isomorfos;se | v ∈ VG : dG(v) = i | 6= | v ∈ VH : dH(v) = i | para algum i

então G e H não são isomorfos;em todos os demais casos, G ∼= H .

Discuta o algoritmo.


E 2.17 Sejam G e H dois grafos e f uma bijeção de VG em VH tal que dG(v) =dH(f(v)) para todo v em VG. É verdade que G ∼= H?

EF 2.18 Certo ou errado? Para mostrar que dois grafos G e H com mesmonúmero de vértices não são isomorfos basta exibir uma bijeção f de VG emVH e um par de vértices u e v em VG tal que (1) uv ∈ EG mas f(u)f(v) /∈ EH

ou (2) uv /∈ EG mas f(u)f(v) ∈ EH .

E 2.19 Seja C o conjunto de todos grafos que representam os alcanos que têmfórmula C4H10. (Veja exercício 1.5.) Cada um desses alcanos tem 4 vérticesde grau 4 e 10 vértices de grau 1. Quantos grafos dois-a-dois não isomorfoshá em C?

E 2.20 Mostre que o grafo das arestas (veja o exercício 1.24) de um K5 é iso-morfo ao complemento do grafo de Petersen.

E 2.21 É verdade que todo grafo é isomorfo ao grafo das arestas (veja exercí-cio 1.24) de algum outro grafo?

E 2.22 Seja X um conjunto de vértices de um grafo G. Suponha que o sub-grafo induzido G[X] é uma estrela (veja a seção 1.2) com 4 vértices. Mostreque G não é isomorfo ao grafo das arestas (veja exercício 1.24) de outro grafo,ou seja, que não existe grafo H tal que G ∼= L(H).

E 2.23 Seja G o grafo de Petersen. Dados quaisquer dois vértices u e v de G,mostre que existe um isomorfismo de G em G (isomorfismos desse tipo sãoconhecidos como automorfismos) que leva u em v. Dadas quaisquer duasarestas uv e xy de G, mostre que existe um isomorfismo de G em G que levauv em xy (ou seja, leva u em x e v em y ou leva u em y e v em x).

E 2.24 Um grafo é auto-complementar se for isomorfo ao seu complemento.Mostre que se G é um grafo auto-complementar então n(G) := 0 (mod 4) oun(G) := 1 (mod 4).2

DD 2.25 Encontre uma caracterização eficiente de grafos não isomorfos. Emoutras palavras, encontre uma propriedade X que seja fácil de verificar e quetorne verdadeira a seguinte afirmação: “Dois grafos G e H não são isomorfosse e somente se X”.

2 A expressão “x := i (mod 4)” significa que o resto da divisão de x por 4 e o resto dadivisão de i por 4 são iguais, ou seja, que x mod 4 = i mod 4. Em outras palavras, x − i édivisível por 4.


DD 2.26 (ALGORITMO) Esboce um algoritmo rápido que resolva o pro-blema do isomorfismo (isto é, decida se dois grafos dados são isomorfos).


Capítulo 3

Síntese de grafos a partir dos graus

Um grafo G realiza uma sequência (g1, g2, . . . , gn) de números naturais1 se osvértices do grafo são 1, 2, . . . , n e d(i) = gi para todo i.

Uma sequência (g1, g2, . . . , gn) de números naturais é gráfica se existe um sequênciagráficagrafo que a realize.

PROBLEMA DA SÍNTESE: Dada uma sequência de números naturais,decidir se ela é ou não gráfica.

Esse problema é às vezes chamado de graph design problem.

Exercícios

E 3.1 Considere as sequências (2, 2, 0), (1, 1, 2, 2), (0, 3, 1, 0), (0, 1, 2, 2, 3),(3, 3, 2, 2, 1), (6, 6, 5, 4, 3, 3, 1) e (7, 6, 5, 4, 3, 3, 2). Quais delas são gráficas?

E 3.2 Suponha que (g1, g2, . . . , gn) é uma sequência gráfica. Mostre que gi ≤n− 1 para todo i e que

∑gi é par. Formule a recíproca; ela é verdadeira?

E 3.3 Mostre que uma sequência (g1, g2, . . . , gn) é gráfica se e somente sea sequência (n−g1−1, n−g2−1, . . . , n−gn−1) é gráfica. (Este fato pode serusado como base de um algoritmo que reconhece sequências gráficas.)

E 3.4 Prove que para cada n ≥ 5 existe um grafo 4-regular com n vértices.

1 O conjunto dos números naturais é 0, 1, 2, . . ..

65

FEOFILOFF Síntese de grafos a partir dos graus 66

E 3.5 É verdade que para cada número r existe um grafo r-regular? É ver-dade que para cada par (r, n) de números tal que r < n existe um grafor-regular com n vértices?

E 3.6 Suponha que (g1, g2, . . . , gn) é uma sequência gráfica e k é um númeronatural ≤ n. Mostre que a sequência

(k, g1+1, g2+1, . . . , gk+1, gk+1, . . . , gn)

também é gráfica. Formule a recíproca deste fato; ela é verdadeira?

EI 3.7 (TEOREMA DE HAVEL E HAKIMI2) Seja (k, g1, g2, . . . , gn) uma sequên-cia de números naturais tal que k ≥ g1 ≥ g2 ≥ . . . ≥ gn. Suponha que asequência

(g1 − 1, g2 − 1, . . . , gk − 1, gk+1, . . . , gn)

é gráfica. Mostre que a primeira sequência também é gráfica.

EI 3.8 (TEOREMA DE ERDOS3 E GALLAI4) Mostre que uma sequência(g1, g2, . . . , gn) de números naturais é gráfica se e somente se

∑i gi é par e

k∑i=1

gi ≤ k(k − 1) +n∑

i=k+1

min (k, gi)

para cada k tal que 1 ≤ k ≤ n.

E 3.9 (ALGORITMO) Esboce um algoritmo eficiente que resolva o problemade síntese enunciado acima, ou seja, decida se uma dada sequência de nú-meros naturais é gráfica. Busque inspiração nos exercícios 3.6 e 3.7 ou noexercício 3.8.

E 3.10 Sejam g1, . . . , gn números inteiros positivos. Suponha que∑n

i=1 gi =2(n − 1). Mostre que existe uma árvore (veja seção 1.12) T com vértices 1,. . . , n tal que d(i) = gi para cada i.

2 Publicado em 1955 por Václav Havel e em 1962 por S. Louis Hakimi.3 Paul Erdos (− ). (Veja verbete na Wikipedia.)4 Tibor Gallai (− ).

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Erdos.html

http://en.wikipedia.org/wiki/Paul_Erds

http://en.wikipedia.org/wiki/Tibor_Gallai

Capítulo 4

Caracterização de grafosbicromáticos

Uma bicoloração de um grafo G é uma bipartição1 (U,W ) de VG tal que todaaresta de G tem uma ponta em U e outra em W . (Você pode imaginar quetodos os vértices em U são vermelhos e todos os vértices em W são azuis.) Oprincipal objetivo deste capítulo é resolver o seguinte

PROBLEMA DA BICOLORAÇÃO: Encontrar uma bicoloração de umgrafo dado.

É claro que todo grafo bipartido (veja seção 1.2) admite uma bicoloração.2

Também é claro que alguns grafos não admite bicoloração.

Um grafo G é bicromático se admite uma bicoloração.3 Faz parte do pro-blema decidir se o grafo dado é bicromático.4

Como veremos adiante (exercício 4.14), um grafo é bicromático se e somentese não contém circuito ímpar. Dizemos que um circuito é ímpar se seu com-primento é um número ímpar.

1 Uma bipartição de um conjunto V é um par (U,W ) de subconjuntos não vazios de Vtal que U ∪W = V e U ∩W = ∅. A bipartição é o par (U,W ). Não faz sentido dizer “U éuma das bipartições de V ”. Diga “U é uma das partes da bipartição”.

2 A expressão “admite uma bicoloração” significa o mesmo que “tem uma bicoloração”.3 Note a sutil distinção entre as expressões “G é bicromático” e “G é bipartido”: um grafo

bicromático só se torna bipartido depois que uma de suas bicolorações for explicitamentedada.

4 Muitos problemas na teoria dos grafos envolvem questões do seguinte tipo: “Comoé possível mostrar que um grafo não tem uma certa propriedade?”. No presente caso, aquestão é “Como é possível mostrar que um dado grafo não tem bicoloração?”. A resposta“Tente todas as possíveis bipartições de VG” não é satisfatória. De fato, se G tem n vérticesentão há 2n−1 diferentes bipartições de VG e esse número cresce explosivamente com n.

67

FEOFILOFF Caracterização de grafos bicromáticos 68

Exercícios

EI 4.1 Mostre que um grafo G é bicromático se e somente se EG é um corte.

E 4.2 Mostre que o grafo do cavalo t-por-t é bicromático.

E 4.3 É verdade que o grafo do bispo t-por-t é bicromático?

E 4.4 Mostre que todo k-cubo é bicromático.

E 4.5 Mostre que toda grade é bicromática.

EF 4.6 Mostre que todo caminho é bicromático. Mostre que todo circuito decomprimento par é bicromático.

E 4.7 Mostre que um grafo pode ter duas ou mais bicolorações diferentes.Mostre que grafos conexos têm no máximo uma bicoloração.

EU 4.8 Mostre que toda floresta é bicromática.

EF 4.9 Suponha que um grafo G é bicromático. É verdade que todo subgrafoinduzido de G é bicromático?

E 4.10 Os grafos da figura 4.1 são bicromáticos?

r r rr r rr r r

HHHHH

HHHHH

HHHH

r r r rrr rrr r r r

ZZZZZZZ

ZZZZZZZ

Figura 4.1: Exercício 4.10. Esses grafos são bicromáticos?

E 4.11 (BOM!) Quantas arestas pode ter um grafo bicromático com n vérti-ces?

EF 4.12 Mostre que grafos que têm circuitos ímpares não são bicromáticos.

EI 4.13 Mostre que todo grafo sem circuitos ímpares é bicromático.


EI 4.14 (CARACTERIZAÇÃO) Deduza de 4.12 e 4.13 que um grafo é bicromá-tico se e somente se não tem circuitos ímpares.5

E 4.15 Dizemos que um grafo G tem um circuito induzido se existe X ⊆ VGtal que G[X] é um circuito. Mostre que um grafo é bicromático se e somentese não tem circuitos ímpares induzidos.

E 4.16 (ALGORITMO) Construa um algoritmo eficiente que decida se umgrafo dado é bicromático. O algoritmo deve devolver uma bicoloração dografo ou um circuito ímpar.

E 4.17 (CAMINHO PAR/ÍMPAR) Sejam r e s dois vértices de um grafo bico-nexo G. Existe um caminho de comprimento par de r a s e um caminhode comprimento ímpar de r a s (os dois caminhos não são necessariamentedisjuntos) se e somente se G não é bicromático.

E 4.18 (CIRCUITO ÍMPAR) Seja G um grafo biconexo. Suponha que G temum circuito de comprimento ímpar. Mostre que todo vértice de G faz partede um circuito de comprimento ímpar.

Caracterização de cortes

E 4.19 Caracterize os conjuntos de arestas de um grafo que são cortes, ouseja, estabeleça as condições em que um conjunto de arestas de um grafo éum corte.

E 4.20 (ALGORITMO) Esboce um algoritmo eficiente que execute a seguintetarefa: Dado um grafo G e uma parte6 C de EG, o algoritmo decide se C é ounão um corte. Em caso afirmativo, o algoritmo deve devolver um conjuntoX de vértices tal que ∂(X) = C. Que coisa o seu algoritmo deve devolver emcaso negativo?

E 4.21 Digamos que um grafo-com-sinais é um terno (G,P,N) em que G é umgrafo e (P,N) é uma partição do conjunto EG. As arestas em P são positi-vas e as outras são negativas. Um grafo-com-sinais (G,P,N) é equilibrado setodo circuito em G tem um número par de arestas negativas. Prove que um

5 Portanto, um circuito ímpar é um certificado da inexistência de bicoloração do grafo.Reciprocamente, uma bicoloração do grafo é um certificado da ausência de circuitos ímpa-res.

6 Uma parte de um conjunto é o mesmo que um subconjunto do conjunto.


grafo-com-sinais (G,P,N) é equilibrado se e somente se existe uma biparti-ção (U,W ) de VG tal que ∂(U) = N .

Capítulo 5

Conjuntos estáveis

Um conjunto X de vértices de um grafo é estável (= stable = independent) seseus elementos são dois a dois não adjacentes. Em outras palavrasX é estávelse nenhuma aresta do grafo tem ambas as pontas em X , ou seja, se o grafoinduzido G[X] é vazio. Por exemplo, se G é um grafo (U,W )-bipartido entãoos conjuntos U e W são estáveis.

Um conjunto estável X∗ é máximo se não existe conjunto estável X tal que máximo|X| > |X∗|. Em outras palavras, X∗ é máximo se |X∗| ≥ |X| para todo con-junto estável X .

PROBLEMA DO CONJUNTO ESTÁVEL MÁXIMO: Encontrar um con-junto estável máximo num grafo dado.

É importante não confundir máximo com maximal. Um conjunto estável X ′

é maximal se não faz parte1 de um conjunto estável maior, ou seja, se não maximalexiste conjunto estável X tal que X ⊃ X ′.2

Eis uma variante do problema: Dado um grafo e um número natural k, en-contrar um conjunto estável com k ou mais vértices. (É claro que essa vari-ante nem sempre tem solução.)

O tamanho de um conjunto estável máximo em um grafo G é denotado por

α(G) .

Em inglês, esse parâmetro é conhecido como stability number ou independencenumber. Quem sabe deveríamos chamar α de índice de estabilidade dografo.

1 Uma parte de um conjunto é o mesmo que um subconjunto do conjunto.2 A expressão “A ⊃ B” significa “B é subconjunto próprio de A”, ou seja, B ⊆ A mas

B 6= A.

71

FEOFILOFF Conjuntos estáveis 72

Exercícios

E 5.1 Mostre que o índice de estabilidade é invariante sob isomorfismo. Emoutras palavras, se G e H são grafos isomorfos então α(G) = α(H).

EF 5.2 Encontre um conjunto estável máximo em um Kn. Encontre um con-junto estável máximo em um Kn.

EF 5.3 Exiba um grafo e um conjunto estável maximal que não seja máximo.

EF 5.4 Suponha que X e Y são conjuntos estáveis maximais de um grafo. Éverdade que X e Y são disjuntos (ou seja, que X ∩ Y = ∅)?

E 5.5 Seja G um grafo (U,W )-bipartido e suponha que |U | ≥ |W |. É verdadeque U é um conjunto estável máximo?

EF 5.6 Calcule um conjunto estável máximo em um caminho. Calcule umconjunto estável máximo em um circuito.

E 5.7 Encontre um conjunto estável máximo na grade p-por-q.

E 5.8 Exiba um conjunto estável máximo num k-cubo.

E 5.9 Encontre um conjunto estável máximo no grafo do cavalo.

E 5.10 Encontre um conjunto estável máximo no grafo do bispo.

E 5.11 Encontre um conjunto estável máximo no grafo da dama. (Em outraspalavras, disponha o maior número possível de damas no tabuleiro de modoque elas não se ataquem mutuamente.)

E 5.12 Encontre um conjunto estável máximo no grafo de Petersen.

E 5.13 Encontre um conjunto estável máximo no grafo de Kneser K(n, k)(veja exercício 1.16).

E 5.14 Encontre um conjunto estável máximo no grafo dos estados do Brasil(veja exercício 1.17).

EF 5.15 Seja H um subgrafo de um grafo G. Qual a relação entre α(H)e α(G)?


EF 5.16 SejamG eH dois grafos tais que VG∩VH = ∅. Mostre que α(G∪H) =α(G) + α(H).

EF 5.17 SejaA a matriz de adjacências de um grafoG (veja exercício 1.3). SejaX um conjunto estável de G. Que aparência tem a restrição de A a X ×X?

E 5.18 (ALGORITMO) Discuta o seguinte algoritmo para o problema do con-junto estável máximo:

dado um grafo G, examine cada um dos subconjuntos de VG;descarte os subconjuntos que não forem estáveis;escolha o maior dos que sobrarem.

DD 5.19 (ALGORITMO) Invente um algoritmo rápido que resolva o pro-blema do conjunto estável máximo. Invente, pelo menos, um algoritmo queproduza um conjunto estável grande.3

E 5.20 No grafo da figura 5.1, exiba um conjunto estável maximal que nãoseja máximo.

r r r rr r r rS

SS

SSS

SSS

SSS

Figura 5.1: Veja exercício 5.20.

E 5.21 Suponha que um grafo G admite bipartição. É verdade que todo con-junto estável maximal de G é máximo? E se G for uma árvore?

EF 5.22 (ALGORITMO) Construa um algoritmo que encontre um conjuntoestável maximal em qualquer grafo dado. (Sugestão: use uma estratégia“gulosa”: em cada iteração, escolha qualquer vértice que seja razoável.4)

E 5.23 (ALGORITMO) O seguinte algoritmo guloso (= greedy) recebe umgrafo G e devolve um conjunto estável X :

X ← ∅H ← G

enquanto VH 6= ∅ faça

3 Não se conhece um algoritmo rápido para encontrar um conjunto estável máximo emqualquer grafo. Em termos técnicos, esse problema é NP-difícil. Veja observação na página 5.

4 De um modo geral, algoritmos gulosos abocanham o objeto que lhes parece mais sabo-roso na iteração corrente, sem medir as consequências “de longo prazo”.


escolha v em VH de modo que |NH(v)| seja mínimoX ← X ∪ vZ ← v ∪NH(v)

H ← H − Zdevolva X

É verdade que esse algoritmo devolve um conjunto estável máximo paraqualquer grafo G dado? E se G for bipartido? E se G for uma árvore?

E 5.24 (BOM!) Prove que todo conjunto estável maximal de qualquer grafoG tem pelo menos ⌈ n(G)

∆(G) + 1

⌉vértices.5 Deduza daí que α(G) ≥ n(G)

∆(G)+1para todo grafo G.

E 5.25 (BOM!) Prove que todo grafo G satisfaz a desigualdade

α(G) ≥∑v∈VG

1

d(v) + 1.

Ou seja, prove que G tem um conjunto estável com⌈∑

1d(v)+1

⌉vértices.

E 5.26 Seja Gt o grafo da dama t-por-t. Use o exercício 5.25 para esti-mar α(Gt).

E 5.27 Seja X o conjunto estável produzido pelo algoritmo do exercício 5.23.Mostre que |X| ≥

∑v∈VG

1/(d(v) + 1).

E 5.28 Prove que todo grafo G satisfaz a desigualdade

α(G) ≥ n2

2m+ n,

sendo n := n(G) e m := m(G).

E 5.29 Digamos que uma cobertura-por-caminhos de um grafo G é umacoleção P1, . . . , Pk de caminhos em G tal que VP1 ∪ · · · ∪ VPk

= VG.Seja P1, . . . , Pk uma cobertura-por-caminhos e suponha que não existecobertura-por-caminhos com menos que k caminhos. Mostre que α(G) ≥ k.Em outras palavras, mostre que G tem um conjunto estável com pelo menosk vértices.

5 Por definição, dxe é o único inteiro j tal que j − 1 < x ≤ j.


E 5.30 (ALGORITMO) Esboce um algoritmo eficiente que receba um grafobipartido e devolva um conjunto estável máximo.6

E 5.31 Seja G um grafo sem vértices isolados. Mostre que

α(G) ≤ m(G)/δ(G) .

Em outras palavras, mostre que G não tem conjuntos estáveis com mais que α ≤bm(G)/δ(G)c vértices.7

E 5.32 Sejam n e a dois inteiros positivos. Seja k := bn/ac e r := n − ka.Seja H o grafo que resulta da união de r cópias do Kk+1 e a− r cópias do Kk

(os conjuntos de vértices das cópias são dois a dois disjuntos). Observe que

n(H) = n, m(H) = r(k+1

2

)+ (a− r)

(k2

)e α(H) = a .

Mostre que α(G) > α(H) para qualquer grafo G tal que n(G) = n e m(G) <m(H).8

E 5.33 Mostre que o índice de estabilidade da maioria dos grafos não passade pouco mais que 2 log2 n(G). Mais precisamente, mostre que para qualquernúmero real positivo ε tem-se

α(G) < (2 + ε) log2 n

para quase todo grafo G em G(n). (Veja a seção 1.17.)

E 5.34 Prove que, por menor que seja o número positivo ε, temos α(G) <n/(2 log2 n + 1 + ε) para quase todo grafo G em G(n). (Veja o exercício 5.33,com ε = (1 + ε)/ log2 n.)

6 Discutiremos esse algoritmo em detalhe no capítulo 10.7 Por definição, bxc é o único inteiro i tal que i ≤ x < i+ 1.8 Pode-se provar que H é o único grafo (a menos de isomorfismo) com n vértices,

m(H) arestas e índice de estabilidade a. Este fato é um conhecido teorema de Paul Turán(− ). (Veja verbete na Wikipedia.) O complemento de H é conhecido como grafode Turán.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Turan.html

http://en.wikipedia.org/wiki/Pl_Turn


Capítulo 6

Cliques

Uma clique1 (= clique) ou conjunto completo num grafo é qualquer conjuntode vértices dois a dois adjacentes. Em outras palavras X é uma clique se ografo induzido G[X] é completo.

PROBLEMA DA CLIQUE MÁXIMA: Encontrar uma clique máximanum grafo dado.

Eis uma variante do problema: dado um grafo e um número natural k, en-contrar uma clique com k ou mais vértices.

O tamanho de uma clique máxima de um grafo G é denotado por

ω(G) .

Em inglês, esse parâmetro é conhecido como clique number.

Exercícios

EF 6.1 Encontre uma clique máxima em um Kn. Encontre uma clique má-xima em um Kn.

EF 6.2 Encontre uma clique máxima em um caminho. Encontre uma cliquemáxima em um circuito.

E 6.3 Exiba um grafo e uma clique que seja maximal mas não máxima.

1 A palavra clique é um neologismo emprestado do inglês. A palavra denota uma “pa-nelinha” ou pequeno clube que não aceita novos membros facilmente. Nesse contexto, apalavra não tem qualquer relação com “estalido” e com expressões como “dê um clique como botão esquerdo do mouse”.

77

FEOFILOFF Cliques 78

E 6.4 Encontre uma clique máxima no grafo do cavalo.

E 6.5 Encontre uma clique máxima no grafo do bispo.

E 6.6 Encontre uma clique máxima no grafo da dama.

E 6.7 Exiba uma clique máxima num k-cubo.

E 6.8 Mostre que toda clique maximal do grafo de Kneser K(n, k) (veja exer-cício 1.16) tem bn/kc vértices. Exiba uma clique máxima em K(n, k).

E 6.9 Qual a relação entre o problema da clique máxima e o problema do con-junto estável máximo (veja capítulo 5)? Como é possível usar um algoritmoque resolve um dos problemas para resolver o outro?

E 6.10 Prove a seguinte relação, válida para qualquer conjunto X de vérticesde um grafo G: X é uma clique em G se e somente se X é um conjuntoestável em G. Deduza daí que ω(G) = α(G).

E 6.11 Suponha que um grafo G admite uma bipartição. Quantos vérticestem uma clique máxima em G?

E 6.12 Suponha que um grafo G tem a seguinte propriedade: para cada vér-tice v, os conjunto N(v) é uma clique. Mostre que cada componente de G éuma clique.

E 6.13 Mostre que ω(G) ≥ 3 para todo grafoG com mais que n(G)2/4 arestas.(Veja exercício 4.11.)

E 6.14 Suponha que ω(G) ≤ k. Quantas arestas G pode ter no máximo (emrelação ao número de vértices)?

E 6.15 É verdade que toda clique maximal em uma árvore é máxima?

EF 6.16 (ALGORITMO) Construa um algoritmo que encontre uma cliquemaximal em qualquer grafo dado.

DD 6.17 (ALGORITMO) Invente um algoritmo rápido que resolva o pro-blema da clique máxima. Invente, pelo menos, um algoritmo que produzauma clique grande.


E 6.18 Seja L(G) o grafo das arestas (veja exercício 1.24) de um grafo G. Mos-tre que para cada vértice v de G, o conjunto ∂G(v) é uma clique em L(G).Mostre que o conjunto das arestas de qualquer triângulo em G é uma cliqueem L(G). Mostre que qualquer clique de cardinalidade diferente de 3 emL(G) é parte de algum conjunto da forma ∂G(v).

E 6.19 Dado um grafo G, calcule uma clique máxima no grafo das ares-tas L(G). (Veja exercício 6.18.)


Capítulo 7

Cobertura por vértices

Uma cobertura por vértices1 (= vertex cover), ou simplesmente cobertura, deum grafo é qualquer conjunto de vértices que contenha pelo menos uma daspontas de cada aresta. Em outras palavras, um conjunto X de vértices é umacobertura se toda aresta tem pelo menos uma de suas pontas em X .

PROBLEMA DA COBERTURA MÍNIMA: Encontrar uma cobertura mí-nima num grafo dado.

A cardinalidade de uma cobertura mínima de um grafo G é denotada por

β(G) .

Há uma relação simples e íntima entre coberturas por vértices e conjuntosestáveis (veja o exercício 7.6). Essa relação torna o problema da coberturamínima equivalente ao problema do conjunto estável máximo.

Exercícios

E 7.1 Uma galeria de arte consiste em um grande número de corredores retosque interligam pequenas praças. Um guarda postado numa praça é capaz devigiar todos os corredores que saem da praça. Qual o número mínimo deguardas necessário para vigiar a galeria toda?

E 7.2 Encontre uma cobertura mínima no grafo do cavalo. Encontre umacobertura mínima no grafo do bispo.

1 Quem sabe seria melhor dizer “cobertura das arestas por vértices”.

81

FEOFILOFF Cobertura por vértices 82

E 7.3 Encontre uma cobertura mínima no k-cubo.

EF 7.4 Mostre que um grafo G é bicromático se e somente se VG tem umsubconjunto U que é, ao mesmo tempo, um conjunto independente e umacobertura.

EF 7.5 O que é uma cobertura minimal? Use o grafo da figura 5.1 para darum exemplo de uma cobertura minimal. É verdade que toda cobertura mi-nima é minimal? É verdade que toda cobertura minimal é minima?

E 7.6 Prove a seguinte relação entre coberturas e conjuntos estáveis: em qual-quer grafo G, um conjunto X de vértices é uma cobertura se e somente seVG rX é estável. Deduza daí que β(G) = n(G)− α(G).

E 7.7 Mostre que o problema da cobertura mínima é equivalente ao pro-blema do conjunto estável máximo. (Em outras palavras, mostre que qual-quer algoritmo para um dos problemas pode ser convertido num algoritmopara o outro.)

E 7.8 Suponha que T é uma árvore. É verdade que toda cobertura minimalde T é mínima?

EF 7.9 SejaG um grafo (U,W )-bipartido, X,X ′ uma partição deU e Y, Y ′uma partição de W . Suponha que N(X) ⊆ Y . Mostre que Y ∪ X ′ é umacobertura.

E 7.10 (SOLUÇÃO APROXIMADA) Especifique um algoritmo que dê uma so-lução aproximada do problema da cobertura mínima: ao receber um grafoG,o algoritmo deve devolver uma cobertura X tal que |X| ≤ 2|X∗|, sendo X∗uma cobertua mínima.

E 7.11 Considere a equivalência discutida no exercício 7.7 e a solução aproxi-mada discutida no exercício 7.10. É possível obter uma solução aproximadasemelhante para o problema do conjunto estável máximo (veja capítulo 5)?

Capítulo 8

Coloração de vértices I

Uma coloração dos vértices de um grafo é uma coleção de conjuntos estáveisque cobre o conjunto de vértices. Mais precisamente, uma coloração dos vér-tices de um grafo G é uma coleção X1, X2, . . . , Xk de conjuntos estáveis talque X1 ∪X2 ∪ · · · ∪Xk = VG.

Embora isso não seja essencial, é cômodo supor que os conjuntos X1, . . . , Xk

são disjuntos dois a dois. Podemos dizer então que uma coloração dos vérti-ces de G é uma partição de VG em conjuntos estáveis. Cada vértice do grafoestará em um e apenas um desses conjuntos.

Se imaginarmos que cada conjunto estável Xi corresponde a uma cor, po-demos dizer que uma coloração de vértices é uma atribuição de cores aosvértices tal que vértices adjacentes recebem cores diferentes.

Dizemos que uma coloração X1, X2, . . . , Xk usa k cores.1 Dizemos tambémque esta é uma k-coloração. Se um grafo tem uma k-coloração então tambémtem uma k′-coloração para todo k′ > k. Uma bicoloração é o mesmo queuma 2-coloração.

O conceito de coloração de vértices é uma generalização do conceito de bi-partição (veja capítulo 4): toda bipartição de um grafo é uma bicoloração dosseus vértices, e toda bicoloração é uma bipartição.

Uma coloração de vértices é mínima se o seu número de cores é o menorpossível, ou seja, se não existe outra que use menos cores.

PROBLEMA DA COLORAÇÃO DE VÉRTICES: Encontrar uma colora-ção mínima dos vértices de um grafo dado.

O número cromático (= chromatic number) de um grafoG é o número de cores

1 Mesmo que algum Xi seja vazio.

83

FEOFILOFF Coloração de vértices I 84

em uma coloração mínima dos vértices de G. Esse número é denotado por

χ(G) .

Um grafo G é k-colorível (= k-colorable) se χ(G) ≤ k. Em particular, “2-colorível” é o mesmo que “bicromático”, conforme o capítulo 4.

Veja o sítio WWW Graph Coloring Page de Joseph Culberson na Universidadede Alberta, Canadá.

A propósito, é preciso mencionar o problema da cobertura por cliques: en-contrar a menor partição X1, . . . , Xk de VG tal que cada Xi é uma clique.É claro que isso equivale a uma coloração dos vértices do grafo complemen-tar G.

Exercícios

E 8.1 Mostre que o número cromático é invariante sob isomorfismo. Em ou-tras palavras, se G e H são grafos isomorfos então χ(G) = χ(H).

EF 8.2 Seja X1, . . . , Xk uma coloração dos vértices de um grafo G. Mos-tre que existe uma coloração Y1, . . . , Yk tal que os conjuntos Y1, . . . , Yk sãodisjuntos dois a dois.

EF 8.3 É verdade que, para todo grafo G, toda coloração dos vértices de Gusa pelo menos ∆(G) cores? Em outras palavras, é verdade que χ(G) ≥∆(G)?

EF 8.4 Encontre uma coloração mínima dos vértices de um caminho. Repitacom um circuito no lugar do caminho. Repita com uma grade no lugar docaminho.

E 8.5 Encontre uma coloração mínima dos vértices do grafo do cavalo t-por-t.

E 8.6 Seja Tt o grafo da torre t-por-t. Encontre uma coloração mínima dosvértices de Tt.

E 8.7 Seja Bt o grafo do bispo t-por-t. Encontre uma coloração mínima dosvértices de Bt.

E 8.8 Seja Bt o grafo do bispo t-por-t. Encontre uma cobertura por cliquesmínima do grafo Bt.

http://web.cs.ualberta.ca/~joe/Coloring/


E 8.9 Seja Ct o grafo do cavalo t-por-t. Encontre uma cobertura mínima deCt por cliques. Considere inicialmente os casos t = 2, . . . , 6.

E 8.10 Seja Dt o grafo da dama t-por-t. Encontre uma coloração mínima dosvértices de Dt. Trate inicialmente dos casos t = 2, . . . , 6.

E 8.11 Seja Rt o grafo do rei t-por-t. Encontre uma coloração mínima dosvértices de Rt.

E 8.12 Encontre uma coloração mínima do grafo dos estados do Brasil (vejaexercício 1.17).

E 8.13 Encontre uma coloração mínima de um k-cubo.

E 8.14 Encontre uma cobertura por cliques mínima de um k-cubo.

E 8.15 Encontre uma coloração mínima dos vértices do grafo de Petersen.

E 8.16 Encontre uma coloração mínima dos vértices do grafo G definido daseguinte maneira: comece com cinco cópias mutuamente disjuntas, digamosB1, . . . , B5, de um grafo completo com 3 vértices; para cada i, acrescente ares-tas ligando todos os elementos de Bi a todos os de Bi+1; finalmente, acres-cente arestas ligando todos os elementos de B5 a todos os de B1. (Este grafo grafo

de Catlinfoi usado por Catlin2 como contraexemplo para a conjectura de Hajós. Vejaexercício 14.13.)

E 8.17 Uma indústria precisa armazenar um certo conjunto de reagentes quí-micos. Por razões de segurança, certos pares de reagentes não devem ficarnum mesmo compartimento do armazém. Quantos compartimentos o arma-zém deve ter no mínimo?

E 8.18 São dadas máquinas 1, . . . , n e intervalos de tempo I1, . . . , In. Paracada i, um operador deve cuidar da máquina i durante o intervalo Ii. Se Ii ∩Ij 6= ∅, um mesmo operador não pode cuidar de i e j. Qual o número mínimode operadores suficiente para operar as máquinas? (Veja o exercício 1.22.)

EF 8.19 Exiba um grafo com duas colorações mínimas diferentes.

EF 8.20 Suponha que um grafoG tem uma coloração de vértices com k cores.É verdade que G tem uma coloração X1, . . . , Xk tal que X1 é um conjuntoindependente máximo?

2 P. A. Catlin, 1979.


EF 8.21 SejamG eH dois grafos tais que VG∩VH = ∅. Mostre que χ(G∪H) =maxχ(G), χ(H).

E 8.22 Seja e uma ponte de um grafo G com duas ou mais arestas. Mostreque χ(G− e) = χ(G).

E 8.23 Seja v uma articulação (veja seção 1.14) de um grafo G. Mostre queχ(G) = χ(G− v).

EF 8.24 Seja H um subgrafo de um grafo G. Qual a relação entre χ(H)e χ(G)?

E 8.25 Seja α a cardinalidade de um conjunto estável máximo de um grafoG.Mostre que toda coloração dos vértices usa pelo menos dn(G)/αe cores. Emχ ≥outras palavras, mostre que χ(G) ≥ n(G)/α(G).

E 8.26 (GENERALIZAÇÃO DE 8.25) Para cada vértice v de um grafo G, sejaαv a cardinalidade de um conjunto estável máximo dentre os que contêm v.Mostre que χ(G) ≥

∑v 1/αv.χ ≥

E 8.27 Mostre que todo grafo com n vértices e número cromático k tem nomáximo 1

2(n2 − n2/k) arestas. Deduza daí que χ(G) ≥ n2/(n2 − 2m), paraχ ≥

todo grafo G com n vértices e m arestas.3 Deduza daí que χ(G) ≥ n/(n − r)se G é r-regular.4

E 8.28 Mostre que χ(G) ≤ 12

+√

2m(G) + 14

para todo grafo G.

E 8.29 (ALGORITMO) O algoritmo que descreveremos a seguir resolve oproblema da coloração de vértices? Ao receber um grafo G, o algoritmo fazo seguinte:

Escolhe um conjunto estável máximo5, digamos X1, em G. Em seguida,escolhe um conjunto estável máximo X2 em G − X1. Depois, escolhe umconjunto estável máximoX3 em (G−X1)−X2. E assim por diante, até quenão haja mais vértices a escolher.

E 8.30 (ALGORITMO) O seguinte algoritmo guloso (= greedy) recebe umgrafo G e devolve uma coloração dos vértices X1, . . . , Xk. Cada iteração

3 Alguns exemplos: se m > 0 então χ > 1, se m > n2/4 então χ > 2, se m > 4n2/9então χ > 9.

4 Exemplos: se r > 0 então χ > 0, se r > n/2 então χ > 2, se r > 2n/3 então χ > 3.5 Não me pergunte como se faz isso!


começa com um coleção X1, . . . , Xk de conjuntos estáveis; a primeira podecomeçar com a coleção vazia, isto é, com k = 0. Cada iteração consiste noseguinte:

CASO 1: X1 ∪ . . . ∪Xk = VG.Devolva X1, . . . , Xk e pare.

CASO 2: X1 ∪ . . . ∪Xk 6= VG.Escolha um vértice v em VG r (X1 ∪ . . . ∪Xk).Se Xi ∪ v é estável para algum i entre 1 e kentão comece nova iteração com Xi ∪ v no papel de Xi.Caso contrário, faça Xk+1 = v ecomece nova iteração com k + 1 no papel de k.

Este algoritmo resolve o problema da coloração de vértices?

E 8.31 Seja v um vértice um grafo G. Suponha que d(v) < χ(G) − 1. Mostreque χ(G) = χ(G− v).

E 8.32 (BOM!) Prove que todo grafo G admite uma coloração de vérticescom apenas ∆(G) + 1 cores. Em outras palavras, prove que χ(G) ≤ ∆(G) + 1para todo grafo G.

E 8.33 Mostre que a diferença ∆(G)−χ(G) pode ser arbitrariamente grande.(Compare com o exercício 8.32.)

E 8.34 (GENERALIZAÇÃO DE 8.32) Seja v1, v2, . . . , vn os vértices de umgrafo G e suponha que d(v1) ≥ d(v2) ≥ · · · ≥ d(vn). Mostre que χ(G) ≤max1≤i≤n mini, d(vi) + 1. Sugestão: o lado direito da desigualdade é iguala max i : d(vi) + 1 ≥ i .

E 8.35 (BOM!) Seja P um caminho de comprimento máximo em um grafoG.Mostre que χ(G) ≤ n(P ). (Em outras palavras, se um grafo não tem caminhocom mais que k vértices então pode ser colorido com apenas k cores. Emoutras palavras, se um grafo não tem coloração com menos que k cores entãotem um caminho com pelo menos k vértices.)

E 8.36 Seja G um grafo dotado da seguinte propriedade: todo par de circui-tos ímpares tem (pelo menos) um vértice em comum. Prove que G admiteuma 5-coloração dos vértices.

EI 8.37 Suponha que um grafo G tem uma clique com k vértices. Mostre quetoda coloração de vértices de G usa pelo menos k cores. Em outras palavras,mostre que χ ≥

χ(G) ≥ ω(G)


para todo grafo G.6

E 8.38 Suponha que um grafo G tem uma clique com k vértices e uma colo-ração dos vértices em k cores. Prove que a clique é máxima e que a coloraçãoé mínima.7

E 8.39 Mostre que, para todo k, existe um grafo sem cliques de tamanho kque não admite coloração com k (ou menos) cores. Em outras palavras, mos-tre que existem grafos G tais que χ(G) > ω(G). Mostre que para cada k existeum grafo G tal que χ(G) = k e ω(G) = 2.

E 8.40 Prove que χ(G) = ω(G) para todo grafo bicromático G.

E 8.41 Suponha que um grafo G tem um conjunto estável com k vértices.Mostre que toda cobertura de VG por cliques usa pelo menos k cliques. De-duza daí que χ(G) ≥ α(G).

E 8.42 Prove que todo grafoG admite uma cobertura por cliques de tamanhono máximo n(G)−δ(G). Em outras palavras, mostre que χ(G) ≤ n(G)−δ(G).

E 8.43 Suponha que um grafo G não tem subgrafo induzido isomorfo a umcaminho com 4 vértices. Mostre que χ(G) = ω(G).

E 8.44 Suponha que um grafo G não tem subgrafo induzido isomorfo a K1,3

nem a K4 − e. Mostre χ(G) ≤ ω(G) + 1.

E 8.45 Seja G um grafo (não necessariamente bicromático) e seja U,W umapartição de VG. Suponha ainda que d(U) < k (ou seja, há menos que k arestascom uma ponta em U e outra em W ). Suponha que os grafos G[U ] e G[W ]admitem colorações de vértices com k cores apenas. Mostre que G admiteuma coloração de vértices com k cores.

E 8.46 Mostre que um grafo H é isomorfo ao grafo das arestas (veja exercí-cio 1.24) de um outro grafo G se e somente se existe uma coleção de cliquesde H tal que cada aresta de H tem ambas as pontas em uma e apenas umadas cliques e todo vértice de H pertence a no máximo duas das cliques.

6 Um grafo é perfeito se não só χ(G) = ω(G) mas também χ(G[X]) = ω(G[X]) para todosubconjunto X de VG. (Veja exercício 14.10.)

7 Uma tal clique pode ser usada como certificado da minimalidade de uma coloração.Reciprocamente, uma tal coloração pode ser usada como certificado da maximalidade daclique.


E 8.47 Seja ε um número real positivo (por exemplo, 0.1). Mostre que

χ(G) >1

2 + ε

n

log2 n

para quase todo grafo G em G(n). (Veja a seção 1.17.)

ED 8.48 Mostre que por menor que seja o número ε no intervalo aberto (0, 2),tem-se

χ(G) <1

2− εn

log2 n

para quase todo grafo G em G(n). (Compare com o exercício 8.47.)

EDD 8.49 (TEOREMA DA QUATRO CORES) Mostre que χ(G) ≤ 4 para todografo planar G. (Veja exercício 14.7.)

DD 8.50 (ALGORITMO) Invente um algoritmo rápido que resolva o pro-blema da coloração de vértices.8

Coloração com número dado de cores

Se o número de cores disponíveis estiver fixo, temos a seguinte variante doproblema da coloração:

PROBLEMA DA COLORAÇÃO COM NÚMERO DADO DE CORES: Dadoum número natural k e um grafoG, encontrar uma k-coloração deG.

É evidente que o problema nem sempre tem solução. O problema da 2-coloração, por exemplo, equivale ao problema de decidir se um dado grafoadmite bipartição. Veja exercício 4.14.

E 8.51 O seguinte algoritmo recebe um grafo G e (pelo menos aparente-mente) devolve uma bicoloração de G. Cada iteração começa com um par(X1, X2) de conjuntos estáveis; a primeira pode começar com X1 = X2 = ∅.Cada iteração consiste no seguinte:

CASO 1: X1 ∪X2 = VG.Devolva X1, X2 e pare.

CASO 2: X1 ∪X2 6= VG.Escolha um vértice v em VG r (X1 ∪X2).

8 Não se conhece um algoritmo rápido para o problema da coloração de vértices. Emtermos técnicos, esse problema é NP-difícil. Veja observação na página 5.


Escolha i em 1, 2 tal que Xi ∪ v é estável.Comece nova iteração com Xi ∪ v no papel de Xi.

Este algoritmo produz uma 2-coloração dos vértices do grafo?

E 8.52 Calcule o número cromático do grafo dos estados do Brasil (veja exer-cício 1.17).

E 8.53 O seguinte algoritmo guloso recebe um grafoG e (pelo menos aparen-temente) devolve uma 3-coloração de G. Cada iteração começa com conjun-tos estáveis X1, X2 e X3; a primeira pode começar com X1 = X2 = X3 = ∅.Cada iteração consiste no seguinte:

CASO 1: X1 ∪X2 ∪X3 = VG.Devolva X1, X2, X3 e pare.

CASO 2: X1 ∪X2 ∪X3 6= VG.Escolha um vértice v em VG r (X1 ∪X2 ∪X3).Escolha i em 1, 2, 3 tal que e Xi ∪ v é estável.Comece nova iteração com Xi ∪ v no papel de Xi.

Este algoritmo produz uma 3-coloração?

E 8.54 Considere o seguinte algoritmo guloso, que recebe um grafo G e (pelomenos aparentemente) produz uma 3-coloração:

W ← VGenquanto W 6= ∅ faça

escolha w em W

i← 1

enquanto N(w) ∩Xi 6= ∅ faça i← i+ 1

Xi ← Xi ∪ wW ←W rXi

devolva X1, X2, X3

Este algoritmo produz uma 3-coloração?

E 8.55 Mostre que o grafo de Petersen (figura 1.6) não admite 3-coloração.

E 8.56 Quantas arestas no máximo pode ter um grafo com n vértices queadmite uma 3-coloração dos vértices?

DD 8.57 (ALGORITMO) Invente um algoritmo rápido que resolva o pro-blema da 3-coloração de vértices. 9

9 Não se conhece um algoritmo rápido que decida se um grafo é 3-colorível. Em termostécnicos, esse problema de decisão é NP-completo. Veja observação na página 5.


DD 8.58 (ALGORITMO) Invente um algoritmo rápido que resolva o pro-blema da k-coloração de vértices.

Coloração de grafos planares

Grafos planares podem ser coloridos com poucas cores.

E 8.59 Mostre que χ(G) ≤ 6 para todo grafo planar G. (Veja os exercí-cios 1.282 e 8.32.)

E 8.60 Mostre que χ(G) ≤ 5 para todo grafo planar G. (Veja exercícios 1.282,14.3 e 14.5.)

EDD 8.61 (TEOREMA DAS QUATRO CORES10) Mostre que todo grafo planaradmite uma coloração de vértices com 4 ou menos cores. Em outras palavras,mostre que

χ(G) ≤ 4

para todo grafo planar G.

E 8.62 Mostre que existem grafos planares que não admitem coloração devértices com 3 cores apenas.

E 8.63 (ALGORITMO) Construa um algoritmo que produza uma 5-coloraçãodos vértices de qualquer grafo planar dado.

EDD 8.64 (ALGORITMO) Construa um algoritmo que produza uma4-coloração dos vértices de qualquer grafo planar dado.

E 8.65 Mostre que α(G) ≥ 14n(G) para todo grafo planar G. (Seria muito

interessante ter uma prova desse fato que não dependesse do teorema dasquatro cores, exercício 8.61.)

10 Demonstrado em 1976 por Kenneth Appel e Wolfgang Haken. Demonstração simplifi-cada em 1997 por Neil Robertson, Daniel P. Sanders, Paul D. Seymour e Robin Thomas. Vejaas páginas “The four color theorem” e “Four-Color Theorem”.

http://www.math.gatech.edu/~thomas/FC/fourcolor.html

http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html

http://mathworld.wolfram.com/Four-ColorTheorem.html


Capítulo 9

Emparelhamentos

Duas arestas de um grafo são adjacentes se têm uma ponta comum.1 Umemparelhamento (= matching) é um conjunto de arestas duas a duas não ad-jacentes. (Há quem diga [Per09] acomplamento onde nós dizemos empare-lhamento.)

Em outras palavras, um emparelhamento num grafo é um conjunto M dearestas tal que |M ∩ ∂(v)| ≤ 1 para cada vértice v.

PROBLEMA DO EMPARELHAMENTO MÁXIMO: Encontrar um empa-relhamento máximo num grafo dado.

Um emparelhamento M∗ é máximo se não existe um emparelhamento M talque |M | > |M∗|. A cardinalidade de um emparelhamento máximo num grafoG é denotada por

α ′(G) .

A propósito, um emparelhamento M ′ é maximal se não faz parte de um em-parelhamento maior, ou seja, se não existe um emparelhamento M tal queM ⊃M ′.

De acordo com o exercício 9.13, o problema do emparelhamento é um casoparticular do problema do conjunto estável. Mas ao contrário do que ocorrecom esse último, sabemos muito bem como resolver o primeiro.

Um emparelhamento M é perfeito (= perfect matching) se cada vértice dografo é ponta de algum elemento de M . Eis uma especialização interessantedo problema acima:

PROBLEMA DO EMPARELHAMENTO PERFEITO: Encontrar um empa-relhamento perfeito num grafo dado.

1 Alguns livros preferem dizer que duas tais arestas são independentes.

93

FEOFILOFF Emparelhamentos 94

É claro que nem todo grafo tem um emparelhamento perfeito; a dificuldadedo problema está em decidir se o grafo dado tem ou não tem um emparelha-mento perfeito.

A seguinte terminologia é útil no estudo de emparelhamentos:

1. Um emparelhamento M satura um vértice v se ∂(v)∩M 6= ∅, ou seja, sealguma aresta de M incide em v.

2. Um emparelhamento M satura um conjunto X de vértices se M saturacada vértice em X .

3. Um caminho é alternante (= alternating) em relação a um emparelha-mento M se suas arestas estão alternadamente em M e fora de M . (Àsvezes é cômodo dizer “M -alternante” no lugar de “alternante em rela-ção a M”.)

4. Um caminho de aumento (= augmenting path) para um emparelha-mento M é um caminho alternante de comprimento não nulo cujos ex-tremos não estão saturados por M .

5. Como já dissemos no capítulo 7, uma cobertura (= vertex cover) de umgrafo é qualquer conjunto de vértices que contenha pelo menos umadas pontas de cada aresta do grafo.

Exercícios

EF 9.1 Quantas arestas tem um emparelhamento máximo num grafo com-pleto com n vértices?

EF 9.2 Quantas arestas tem um emparelhamento máximo em um grafo bi-partido completo?

EF 9.3 Calcule um emparelhamento máximo em um caminho. Calcule umemparelhamento máximo em um circuito.

EF 9.4 Suponha que um grafo G tem um emparelhamento perfeito. Mostreque n(G) é par.

E 9.5 Calcule um emparelhamento máximo em um grafo 3-regular dotadode circuito hamiltoniano (veja capítulo 15).

EF 9.6 É verdade que todo grafo regular tem um emparelhamento perfeito?

EF 9.7 Encontre um emparelhamento máximo no grafo da dama t-por-t.


E 9.8 Encontre um emparelhamento máximo no grafo do bispo t-por-t.

E 9.9 Encontre um emparelhamento máximo no grafo do cavalo t-por-t.

E 9.10 Quantas arestas tem um emparelhamento máximo num cubo de di-mensão k?

E 9.11 (BOM!) Exiba um grafo e um emparelhamento maximal que não sejamáximo.

E 9.12 É verdade que em qualquer árvore todo emparelhamento maximal émáximo?

E 9.13 Mostre que o problema do emparelhamento máximo é um caso parti-cular do problema do conjunto estável máximo.

E 9.14 Seja G um grafo com n(G) ≥ 2k e δ(G) ≥ k. Mostre que G tem umemparelhamento com pelo menos k arestas.

E 9.15 É verdade que, em qualquer grafo, todo vértice não isolado é saturadopor algum emparelhamento máximo?

EU 9.16 (BOM!) Sejam M e M ′ dois emparelhamentos num grafo G. Des-creva o grafo (VG,M ∪M ′). Descreva o grafo (VG,M ⊕M ′).2 Que acontece se M ⊕M ′

os emparelhamentos M e M ′ são perfeitos?

E 9.17 Suponha que um grafo G tem uma ponte a. Mostre que ou todosos emparelhamentos perfeitos de G contêm a ou nenhum emparelhamentoperfeito de G contém a.

E 9.18 Prove que toda floresta tem no máximo um emparelhamento perfeito.

EF 9.19 Seja M um emparelhamento em um grafo e seja P um caminho M -alternante. Mostre que qualquer segmento de P é um caminhoM -alternante.

E 9.20 Seja M um emparelhamento em um grafo e seja P um caminho M -alternante maximal. Suponha que as duas arestas extremas de P não estãoem M . É verdade que P é um caminho de aumento?


EI 9.21 Suponha que P é um caminho de aumento para um emparelha-mento M . Prove que caminho de

aumentoM ⊕ EP

é um emparelhamento. Prove que |M ⊕ EP | > |M |.

EI 9.22 (TEOREMA DE BERGE3) Seja M um emparelhamento num grafo G.Suponha que M não é máximo. Prove que existe um caminho de aumentoteorema

de Berge para M .

EI 9.23 Prove que um emparelhamento M é máximo se e somente se nãoexiste caminho de aumento para M . (Veja exercícios 9.21 e 9.22.)

ED 9.24 Seja G um grafo e M um emparelhamento em G. Seja V (M) o con-junto dos vértices saturados por M . Sejam r e s dois vértices em VG r V (M).Escreva um algoritmo que encontre um caminho alternante com origem r etérmino s (ou constate que um tal caminho não existe).

E 9.25 (BOM!) Um passeio (= walk) em um grafo é qualquer sequência finita(v0, v1, v2, . . . , vk−1, vk) de vértices tal que vi é adjacente a vi−1 para todo ientre 1 e k.

SejaM um emparelhamento. Seja (v0, v1, . . . , vk) um passeio cujas arestasestão alternadamente em M e fora de M e suponha que v0 e vk não estãosaturados por M . Seja A o conjunto das arestas do passeio. Mostre que oconjunto M ⊕A não é necessariamente um emparelhamento. (Compare como exercício 9.21.)

E 9.26 Dois jogadores, digamos A e B, se alternam escolhendo vértices numgrafoG. Primeiro,A escolhe um vértice v0. Em seguida,B escolhe um vérticev1 adjacente a v0. Depois, A escolhe um vértice adjacente a v1 mas diferentede v0 e de v1. E assim por diante. (Esse jogo é conhecido como slink ou slither.)slink

slither Eis uma maneira mais limpa de descrever o jogo: Os vértices escolhidosformam um caminho v0v1v2 · · · vk. Se k é ímpar, A escolhe um vértice vk+1

distinto dos demais mas adjacente a vk. Se k é par, B faz um jogada análoga.O último jogador que puder fazer um movimento vence o jogo.

Prove que B tem uma estratégia vencedora se G tem um emparelha-mento perfeito. Prove que A tem uma estratégia vencedora em caso contrá-rio.

E 9.27 SejaM um emparelhamento eX um conjunto de vértices de um grafo.Mostre que se X é saturado por M então X também é saturado por algumemparelhamento máximo.

2 Por definição, K ⊕ L é o conjunto (K ∪ L)− (K ∩ L), igual a (K − L) ∪ (L−K).3 Publicado em 1957 por Claude Berge (− ).

http://en.wikipedia.org/wiki/Claude_Berge


E 9.28 Sejam X e Y dois conjuntos de vértices de um grafo G. Suponha queX é saturado por algum emparelhamento e Y é saturado por algum empare-lhamento (não necessariamente o mesmo). Se y é um elemento de Y r X , éverdade que X ∪ y é saturado por algum emprelhamento?

E 9.29 Sejam X e Y dois conjuntos de vértices de um grafo G. Suponha queX é saturado por algum emparelhamento e Y é saturado por algum empare-lhamento (não necessariamente o mesmo). Se |Y | > |X|, é verdade que existey em Y rX , tal que X ∪ y é saturado por algum emprelhamento?

EI 9.30 Mostre que, em qualquer grafo, para qualquer emparelhamento M equalquer cobertura K (veja capítulo 7), emparelha-

mentosversuscoberturas

|M | ≤ |K| .

Deduza daí que se |M | = |K| então M é um emparelhamento máximo e Ké uma cobertura mínima.4 Dê um exemplo de um grafo que não possui umpar (M,K) tal que |M | = |K|. (Veja também o exercício 9.33.)

EI 9.31 Mostre que α ′(G) ≤ β(G) para todo grafo G. α ′ ≤

EF 9.32 Seja K uma cobertura minimal de um grafo. É verdade que todaaresta de qualquer emparelhamento tem apenas uma pontas em K?

E 9.33 Seja M um emparelhamento e K uma cobertura tais que |M | = |K|.Mostre que M satura K e que cada elemento de M tem apenas uma daspontas em K. (Veja o exercício 9.30.)

E 9.34 Suponha que M é um emparelhamento maximal num grafo. SejaV (M) o conjunto dos vértices saturados por M . Mostre que V (M) é umacobertura.

Escolha uma das pontas de cada aresta em M . Seja W o conjunto resul-tante. É verdade que W é uma cobertura?

E 9.35 (EMPARELHAMENTO QUASE MÁXIMO) Seja M um emparelhamentomaximal e M∗ um emparelhamento máximo em um grafo. É evidente que emparelha-

mentomaximal

|M | ≤ |M∗|. Mostre que |M | ≥ 12|M∗|. É verdade que |M | > 1

2|M∗| qualquer

que seja o grafo?

E 9.36 Suponha que um grafo G tem um emparelhamento perfeito. Mostreque, para todo vértice v, o grafo G− v tem exatamente um componente comnúmero ímpar de vértices.

4 Assim, se uma cobertura tem o mesmo tamanho que um emparelhamento, ela serve decertificado da maximalidade do emparelhamento.


Capítulo 10

Emparelhamentos em grafosbipartidos I

O problema do emparelhamento máximo (veja capítulo 9) é relativamentefácil quando restrito a grafos bipartidos.

Dado um conjunto X de vértices de um grafo G, denotaremos por NG(X), ou N(X)

simplesmente N(X), o conjunto dos vértices em VG rX que têm um ou maisvizinhos em X . (Em geral, N(X) é um subconjunto próprio de

⋃x∈X N(x).)1

Exercícios

E 10.1 Exiba um emparelhamento máximo no grafo da figura 10.1.

r r r r r rr r r r r rAAAAA

@@@@@

AAAAA

AAAAA

@@@@@

Figura 10.1: Exercício 10.1. Encontre um em-parelhamento máximo.

E 10.2 Encontre um emparelhamento máximo num k-cubo.

E 10.3 Exiba um emparelhamento máximo no grafo da figura 10.2.

1 SeX = x1, x2, . . . , xk então⋃

x∈X N(x) denota o conjunto N(x1)∪N(x2)∪· · ·∪N(xk).

99

FEOFILOFF Emparelhamentos em grafos bipartidos I 100

r r r r rr r r r r

BBBBB

@@@@@

BBBBB

BBBBB

@@@@@

BBBBB

Figura 10.2: Exercício 10.3. Encontre empare-lhamento máximo.

U

W

Figura 10.3: Um grafo (U,W )-bipartido. A área cinza indica umacobertura. As linhas coloridas indicam um emparelhamento.

EF 10.4 Seja G um grafo (U,W )-bipartido, X,X ′ uma partição de U eY, Y ′ uma partição de W . Mostre que se N(X) ⊆ Y então N(Y ′) ⊆ X ′.Mostre que se N(X) ⊆ Y então Y ∪X ′ é uma cobertura.

E 10.5 (BOM!) Seja G um grafo (U,W )-bipartido e M um emparelhamentoem G. Seja V (M) o conjunto dos vértices que M satura. Seja X o conjuntodos vértices de todos os caminhos M -alternantes que têm um dos extremosem U r V (M). Prove que (W ∩X) ∪ (U rX) é uma cobertura de G.

E 10.6 (ALGORITMO) Construa um algoritmo eficiente que receba um grafobipartido G, uma bipartição U,W do grafo, e um emparelhamento M e de-volva

(1) um emparelhamento M ′ tal que |M ′| > |M | ou(2) uma cobertura K tal que |K| = |M |.

(No caso (2), de acordo com o exercício 9.30, o emparelhamento M é má-ximo.) (Veja o exercício 10.5.)

E 10.7 (ALGORITMO) Construa um algoritmo eficiente que receba um grafobipartido G e uma bipartição U,W de G e devolva um emparelhamentoalgoritmo

húngaro máximo em G. (O famoso Algoritmo Húngaro2 faz exatamente isso.) Suges-tão: Use o resultado do exercício 10.6.

E 10.8 Seja G um grafo (U,W )-bipartido e M um emparelhamento em G.Seja V (M) o conjunto dos vértices saturados por M . Seja r um vértice em

2 Referência aos húngaros König, Egerváry e outros.


U r V (M) e s um vértice em W r V (M). Escreva um algoritmo que encontreum caminho alternante com origem r e término s (ou constate que um talcaminho não existe).

EI 10.9 (TEOREMA DE KÖNIG–EGERVÁRY3) Mostre que todo grafo bipar-tido tem um emparelhamento M e uma cobertura K tais que |M | = |K|.(Compare com o exercício 9.30.)

EI 10.10 Mostre que, em todo grafo bicromático, um emparelhamento M∗ émáximo se e somente se existe uma cobertura K∗ tal que

|M∗| = |K∗| .

(Veja o exercício 10.9.) Outra maneira de formular isso: se M∗ é um um em-parelhamento máximo e K∗ é uma cobertura mínima em um grafo bipartidoentão |M∗| = |K∗|.

E 10.11 Seja G um grafo bicromático. Mostre que α ′(G) = β(G).

E 10.12 Mostre como encontrar um conjunto estável máximo num grafo bi-partido.

E 10.13 Seja G um grafo bicromático. Prove que χ(G) = ω(G).

E 10.14 Encontre um emparelhamento máximo e uma cobertura mínima nografo da figura 10.1.

E 10.15 Dê uma condição necessária e suficiente para que um grafo bipartidotenha um emparelhamento com k arestas.

E 10.16 Seja G um grafo (U,W )-bipartido. Suponha que |U | = |W | e m(G) >(k − 1) |U | para algum k inteiro positivo. Prove que G tem um emparelha-mento de cardinalidade k.

E 10.17 SejaH um grafo (não necessariamente bicromático) e seja R, S umapartição de VH . Suponha ainda que há menos que k arestas com uma pontaem R e outra em S (ou seja, d(R) < k). Suponha que os grafos H[R] e H[S]admitem colorações de vértices (veja capítulo 8) com k cores. Mostre que Hadmite uma coloração de vértices com k cores.

3 Publicado em 1931 por Dénes König (− ). O teorema também é atribuído aEugene Egerváry (1931).

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Konig_Denes.html

http://www.cs.elte.hu/egres/www/mf_intro.html


Capítulo 11

Emparelhamentos em grafosbipartidos II

Em que condições um grafo (U,W )-bipartido possui um emparelhamentoperfeito? Uma condição necessária óbvia: |U | = |W |. Outro condição neces-sária óbvia: o grafo deve admitir um emparelhamento que satura U . Essasobservações sugerem o seguinte

PROBLEMA: Dado um grafo (U,W )-bipartido, encontrar um empa-relhamento que sature o conjunto U .

Exercícios

E 11.1 Seja G um grafo (U,W )-bipartido. Suponha que |N(Z)| < |Z| paraalguma parte Z de U . Mostre que G não tem um emparelhamento que sa-tura U .

Outra maneira de formular a questão: se algum emparelhamento sa-tura U então |N(Z)| ≥ |Z| para toda parte Z de U .

E 11.2 (TEOREMA DE HALL1) Seja G um grafo (U,W )-bipartido. Suponhaque teorema

de Hall|N(Z)| ≥ |Z|

para toda parte Z de U . Mostre queG tem um emparelhamento que satura U .(Sugestão: Use o teorema de König–Egerváry, exercício 10.9.)

1 Publicado em 1935 por Philip Hall (− ). (Veja verbete na Wikipedia.)

103

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Hall.html

http://en.wikipedia.org/wiki/Philip_Hall

FEOFILOFF Emparelhamentos em grafos bipartidos II 104

EI 11.3 Mostre que um grafo (U,W )-bipartido tem um emparelhamento quesatura U se e somente se |N(Z)| ≥ |Z| para toda parte Z de U . (Veja osexercícios 11.1 e 11.2.)

E 11.4 Quais das afirmações a seguir valem para todo grafo (U,W )-bipartido G? (1) Se G tem um emparelhamento que satura U então|N(Z)| ≥ |Z| para toda parte Z de U . (2) Se G tem um emparelhamento quesatura U então |N(Z)| ≥ |Z| para alguma parte Z de U . (3) Se |N(Z)| < |Z|para alguma parte Z de U então G não tem um emparelhamento quesatura U . (4) Se |N(Z)| < |Z| para toda parte Z de U então G não tem umemparelhamento que satura U .

E 11.5 Deduza o teorema de König–Egerváry (exercício 10.9) do teorema deHall (exercício 11.2).

E 11.6 Seja H um conjunto de homens, M um conjunto de mulheres e k uminteiro positivo. Suponha que cada homem conhece no máximo k mulheres ecada mulher conhece no mínimo k homens. Prove que é possível casar cadamulher com um homem que ela conhece.

E 11.7 Prove que se G é um grafo (U,W )-bipartido com pelo menos umaaresta e d(u) ≥ d(w) para todo u em U e w em W , então existe em G umemparelhamento que cobre U .

E 11.8 Seja G um grafo bipartido r-regular com r > 0. Mostre que o grafotem um emparelhamento perfeito.

E 11.9 Prove que um grafo bicromático G tem um emparelhamento perfeitose e somente se |N∗(Z)| ≥ |Z| para todo subconjunto Z de VG, sendo N∗(Z)o conjunto

⋃z∈Z N(z). Dê um exemplo de um grafo (não bicromático) que

não tem emparelhamento perfeito mas satisfaz a desigualdade |N∗(Z)| ≥ |Z|para todo conjunto Z de vértices.

E 11.10 Seja G um grafo (U,W )-bipartido e X uma parte de U . Dê uma con-dição necessária e suficiente para que existe um emparelhamento em G quesatura X .

E 11.11 Seja G um grafo (U,W )-bipartido. Seja X uma parte de U e Y umaparte de W . Seja M um emparelhamento que satura X e N um empare-lhamento que satura Y . Mostre que existe um emparelhamento que saturaX ∪ Y .


E 11.12 Seja G um grafo (U,W )-bipartido com pelo menos uma aresta. SejaX o conjuntos dos vértices em U que têm grau ∆(G). Mostre que G tem umemparelhamento que satura X .

E 11.13 (BOM!) Seja G um grafo bicromático com pelo menos uma aresta.Mostre que existe um emparelhamento que satura todos os vértices degrau ∆(G).

E 11.14 SejaK um grafo (U,W )-bipartido completo. Suponha que |U | = |W |.Seja G um subgrafo de K e r o número ∆(G). Mostre que existe um grafo r-regular H tal que G ⊆ H ⊆ K.

E 11.15 Seja G um grafo bicromático e seja r o número ∆(G). Mostre que G ésubgrafo de algum grafo bicromático r-regular.

EI 11.16 Seja G um grafo (U,W )-bipartido. Prove que todo emparelhamentomáximo em G tem cardinalidade

minZ⊆U |U | − |Z|+ |N(Z)| .

(Isto é uma generalização do exercício 11.3.)


Capítulo 12

Emparelhamentos em grafosarbitrários

Um componente de um grafo é ímpar (= odd component) se tem um númeroímpar de vértices. O número de componentes ímpares de um grafo G serádenotado nesta seção por o(G). o(G)

Exercícios

E 12.1 Seja T uma árvore e suponha que o(T − v) = 1 para cada vértice vde T . Mostre que T tem emparelhamento perfeito. (Veja antes exercício 9.36.)

E 12.2 Suponha que um grafo G tem um emparelhamento perfeito. Mostreque o(G− S) ≤ |S| para todo conjunto S de vértices.

EF 12.3 Suponha que um grafo G satisfaz a condição o(G − S) ≤ |S| paratodo conjunto S de vértices. Prove que n(G) é par.

EID 12.4 (TEOREMA DE TUTTE1) Suponha que um grafo G tem a seguintepropriedade:

o(G− S) ≤ |S|

para todo conjunto S de vértices. (Compare com o exercício 12.2.) Mostreque G tem um emparelhamento perfeito.

1 O teorema foi publicado em 1947 por William T. Tutte (− ). (Veja verbete naWikipedia.)

107

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Tutte.html

http://en.wikipedia.org/wiki/Tutte

http://en.wikipedia.org/wiki/Tutte

FEOFILOFF Emparelhamentos em grafos arbitrários 108

EI 12.5 Mostre que um grafo G tem um emparelhamento perfeito se e so-mente se o(G − S) ≤ |S| para todo conjunto S de vértices. (Veja exercí-cios 12.2 e 12.4.)

ED 12.6 (ALGORITMO) Esboce um algoritmo eficiente que decida se umgrafo tem ou não tem um emparelhamento perfeito.

E 12.7 Deduza o teorema de Hall (exercício 11.2) do teorema de Tutte (exer-cício 12.4).

EI 12.8 Seja M um emparelhamento e S um conjunto de vértices de umgrafo G. Prove que o número de vértices não saturados por M é pelo me-nos o(G− S)− |S|. Deduza daí que

|M | ≤ γ(G,S) ,

sendo γ(G,S) o número 12n(G)− 1

2

(o(G− S)− |S|

).γ( , )

E 12.9 Seja M um emparelhamento e S um conjunto de vértices de umgrafo G. Suponha que |M | = γ(G,S), sendo γ(G,S) o número definido noexercício 12.8. Mostre que o emparelhamento M é máximo.2

EID 12.10 Mostre que em qualquer grafo G existe um emparelhamento M euma parte S de VG tais que M deixa de saturar apenas o(G−S)−|S| vértices,ou seja, tais que

|M | ≥ γ(G,S) ,

sendo γ(G,S) o número definido no exercício 12.8.

EID 12.11 (TEOREMA DE TUTTE–BERGE3) Prove que, em qualquer grafo G,

α ′(G) = γ(G) ,

sendo γ(G) o valor mínimo de γ(G,S) para todas as partes S de VG, ondeγ(G,S) é a expressão definida no exercício 12.8. (Veja os exercícios 12.8e 12.10.)

E 12.12 Deduza o exercício 9.30 do exercício 12.8. Deduza o teorema deKönig–Egerváry (exercício 10.9) do teorema de Tutte–Berge (exercício 12.11).

2 O conjunto S serve de certificado da maximalidade do emparelhamento.3 Trata-se de uma combinação do teorema de Tutte (exercício 12.4) com um teorema de

Claude Berge (− ) publicado em 1958.

http://www.ecp6.jussieu.fr/GT04/Berge/Berge.html


E 12.13 Seja G um grafo 3-regular sem pontes. Mostre que G tem um empa-relhamento perfeito. Mostre que nem todo grafo 3-regular tem um empare-lhamento perfeito.

EID 12.14 (DECOMPOSIÇÃO DE GALLAI–EDMONDS4) Seja G um grafo e Do conjunto dos vértices de G que não são saturados por algum emparelha-mento máximo. Seja A o conjunto N(D). Seja C o conjunto VG r (D ∪ A).Mostre que para todo emparelhamento máximo M∗ em G tem-se

2|M∗| = n(G)− c(G[D]) + |A| ,

onde c(H) denota o número de componentes do grafo H .

ED 12.15 (ALGORITMO) Esboce um algoritmo eficiente que encontre umemparelhamento máximo em qualquer grafo dado. (O Algoritmo de Ed-monds5 faz exatamente isso.)

ED 12.16 Uma cobertura por arestas (= edge cover)6 de um grafo é um con-junto F de arestas tal que todo vértice do grafo é ponta de algum elementode F . (Não confunda com o conceito de cobertura por vértices.) Invente umalgoritmo eficiente que produza uma cobertura por arestas mínima.

ED 12.17 (ALGORITMO DO EMPARELHAMENTO DE PESO MÁXIMO) Seja Kum grafo completo e π uma função de EK em N := 0, 1, 2, 3, . . .. Para cadaaresta e do grafo, diremos que π(e) é o peso de e. O peso de um subconjunto emparelhamento

de pesomáximo

F de EK é∑

e∈F π(e). Esboce um algoritmo para encontrar um emparelha-mento de peso máximo em K.

4 Publicada em 1963 e 1964 por Tibor Gallai (− ) e em 1965 por Jack Edmonds.5 Jack Edmonds.6 Quem sabe eu deveria dizer “cobertura de vértices por arestas”.

http://en.wikipedia.org/wiki/Tibor_Gallai

http://en.wikipedia.org/wiki/Jack_Edmonds

http://en.wikipedia.org/wiki/Jack_Edmonds


Capítulo 13

Coloração de arestas

Uma coloração das arestas de um grafo é uma coleção de emparelhamentosque cobre o conjunto de arestas. Mais precisamente, uma coloração das ares-tas de um grafoG é uma coleçãoM1, M2, . . . ,Mk de emparelhamentos tal queM1 ∪M2 ∪ · · · ∪Mk = EG. (Podemos exigir que os emparelhamentos sejamdisjuntos dois a dois; essa disjunção é cômoda mas não é essencial.)

Se imaginarmos que cada emparelhamento Mi corresponde a uma cor, po-deremos dizer que uma coloração das arestas de um grafo é uma atribuiçãode cores às arestas que satisfaz a seguinte propriedade: arestas adjacentesrecebem cores diferentes.

SeM1, . . . ,Mk é uma coloração de arestas, dizemos que k é o número de coresda coloração. Dizemos também que esta é uma k-coloração. Uma coloraçãode arestas é mínima se o seu número de cores é o menor possível, ou seja, senão existe outra que use menos cores.

PROBLEMA DA COLORAÇÃO DE ARESTAS: Encontrar uma coloraçãomínima das arestas de um grafo dado.

O índice cromático (= chromatic index) de um grafo G é o número mínimo decores necessário para colorir as arestas de G. Esse número será denotado por

χ ′(G) .

Exercícios

EF 13.1 Seja M1, . . . , Mk uma coloração das arestas de um grafo. Mostre queexiste uma coloração M ′

1, . . . , M ′k tal que os emparelhamentos M ′

1, . . . , M ′k são

disjuntos dois a dois.

111

FEOFILOFF Coloração de arestas 112

E 13.2 Um processo industrial consiste em um certo conjunto de tarefas.Cada tarefa é executada por um operário em uma máquina e cada tarefa temduração de 1 dia. Cada operário está qualificado para operar apenas algumasdas máquinas. Quantos dias são necessários para completar o processo?1

E 13.3 Uma escola pode ser representada por um grafo (U,W )-bipartido:cada vértice em U é um professor, cada vértice em W é uma turma de alu-nos e um professor é adjacente às turmas para as quais deve dar aulas. Umasemana letiva é dividida em períodos (segunda-feira das 8h às 10h, segunda-feira das 10h às 12h, etc.) e cada período é representado por uma cor. Umacoloração das arestas do grafo é uma programação das aulas da semana.Quantos períodos são necessários e suficientes para cumprir o programa deaulas?2

E 13.4 Mostre que o problema da coloração mínima das arestas é um casoparticular do problema da coloração de vértices mínima.

EF 13.5 Calcule uma coloração mínima das arestas de um grafo completo.Calcule uma coloração mínima das arestas de um grafo bipartido completo.

E 13.6 Calcule o índice cromático do grafo de Petersen.

E 13.7 Exiba um grafo com duas colorações mínimas diferentes.

E 13.8 Mostre que χ ′(G) ≥ m(G)/α ′(G) para todo grafo G.

EI 13.9 Mostre que qualquer coloração das arestas de um grafo G usa pelomenos ∆(G) cores. Em outras palavras, mostre queχ ′ ≥

χ ′(G) ≥ ∆(G)

para todo grafo G. Mostre que essa desigualdade é um caso particular dadesigualdade χ ≥ ω do exercício 8.37.

E 13.10 SejaG um grafo k-regular com um número ímpar de vértices. Mostreque χ ′(G) > k.

E 13.11 Seja G um grafo 3-regular dotado de circuito hamiltoniano. (Um cir-cuito C em G é hamiltoniano se VC = VG. Veja a capítulo 15.) Prove queχ ′(G) = 3.

1 Sugestão: Cada operário é um vértice do meu grafo; cada máquina também é um vér-tice; cada aresta é uma tarefa, que associa um operário com uma máquina; cada cor é um diade trabalho.

2 Este é o “problema da grade de horários” (timetabling problem).


E 13.12 SejaG um grafo r-regular com r ≥ 2. Suponha queG tem uma ponte.Mostre que χ ′(G) ≥ r + 1.

E 13.13 Seja G um grafo r-regular, r ≥ 1. Suponha que G tem uma articula-ção, ou seja, um vértice v tal que G− v tem mais componentes que G. Mostreque χ ′(G) ≥ r + 1.

E 13.14 Suponha que n(G) é ímpar e m(G) > 12∆(G)

(n(G)− 1

). Mostre que

χ ′(G) > ∆(G).

E 13.15 Seja G um grafo r-regular, r ≥ 1, com um número ímpar de vértices.Seja H um grafo obtido de G pela remoção de no máximo (r − 1)/2 arestas.Mostre que χ ′(H) > ∆(H).

E 13.16 (BOM!) Mostre que o conjunto das arestas de toda árvore T pode sercolorido com (apenas) ∆(T ) cores. (Compare com o exercício 13.9.)

E 13.17 Considere o seguinte algoritmo guloso de coloração das arestas deum grafoG. Cada iteração do algoritmo começa com uma coleçãoM1, . . . ,Mj

de emparelhamentos. Em cada iteração,

escolha uma aresta e que não esteja em M1 ∪ · · · ∪Mj ; se existe i talqueMi∪e é um emparelhamento então comece nova iteração comM1, . . . , Mi−1, Mi ∪ e, Mi+1, . . . , Mj ; senão, comece nova iteraçãocom a coleção M1, . . . , Mj , e.

Mostre que o algoritmo usa no máximo 2∆(G)−1 emparelhamentos. Mostreque o algoritmo usa no máximo 2χ ′(G) − 1 emparelhamentos. O algoritmoproduz uma coloração mínima?

E 13.18 Considere o seguinte algoritmo guloso de coloração das arestas deum grafo G:

a j-ésima iteração começa com uma coleçãoM1,M2, . . . ,Mj−1 de em-parelhamentos e calcula um emparelhamento maximal Mj no grafoG− (M1 ∪M2 ∪ · · · ∪Mj−1).

Mostre que o algoritmo usa no máximo 2∆(G)− 1 cores. Mostre que o algo-ritmo usa no máximo 2χ ′(G) − 1 cores. O algoritmo produz uma coloraçãomínima?

E 13.19 Considere o seguinte algoritmo de coloração das arestas de umgrafo G:


a j-ésima iteração começa com uma coleçãoM1,M2, . . . ,Mj−1 de em-parelhamentos e calcula um emparelhamento máximo Mj no grafoG− (M1 ∪M2 ∪ · · · ∪Mj−1).

O algoritmo produz uma coloração mínima?

E 13.20 Considere a seguinte heurística3 da “troca de cores em caminhos al-ternantes”, que tenta resolver o problema da coloração de arestas:heurística

da troca decores No começo de cada iteração tem-se uma coloração parcial, ou seja,

uma coleção M1, M2, . . . , Mk de emparelhamentos disjuntos dois adois. Seja vw uma aresta ainda não colorida, isto é, uma aresta quenão está em M1∪ · · · ∪Mk. Seja Mi uma cor “ausente” em v e seja Mj

uma cor “ausente” emw. Seja P o componente do grafo (VG,Mi∪Mj)que contém v. Troque Mi por Mi ⊕ EP . Em seguida, troque Mi porMi ∪ vw e comece nova iteração.

Complete os detalhes e discuta a heurística. Ela resolve o problema da colo-ração de arestas?

E 13.21 Mostre que todo grafo bipartido r-regular admite uma coloração dasarestas com apenas r cores.

E 13.22 Escolha 16 casas em um tabuleiro de xadrez 8-por-8 de forma quecada linha e cada coluna do tabuleiro contenha exatamente duas das casasescolhidas. Prove que é possível colocar 8 peões brancos e 8 pretos nas 16casas escolhidas de tal forma que cada linha e cada coluna contenha contenhaexatamente um peão branco e um preto.

EI 13.23 (TEOREMA DE KÖNIG4) Seja G um grafo bicromático. Mostre quegrafosbipartidos o conjunto de arestas de G pode ser colorido com (apenas) ∆(G) cores. (Su-

gestão: Veja a heurística 13.20 ou o exercício 11.13.)

EI 13.24 Seja G um grafo bicromático (isto é, um grafo que admite uma bi-partição). Mostre quegrafos

bicromáticos χ ′(G) = ∆(G) .

(Veja os exercícios 13.9 e 13.23.)

E 13.25 Exiba colorações mínimas das arestas dos grafos das figuras 10.1e 10.2.

3 Wilf diz (em Algorithms and Complexity, Prentice-Hall, 1986) que heurísticas são methodsthat seem to work well in practice, for reasons nobody understands.

4 Dénes König (− ). (Veja verbete na Wikipedia.)

http://en.wikipedia.org/wiki/Heuristic_(computer_science)

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Konig_Denes.html

http://en.wikipedia.org/wiki/Dnes_Knig


E 13.26 Sejam M e N dois emparelhamentos de um grafo G. Suponha que∣∣|M | − |N |∣∣ ≥ 2. Mostre que existem emparelhamentos M ′ e N ′ tais queM ∪N = M ′ ∪N ′ e

∣∣|M ′| − |N ′|∣∣ < ∣∣|M | − |N |∣∣.

E 13.27 Seja G um grafo e k := χ ′(G). Mostre que existe uma k-coloraçãodas arestas M1, M2, . . . , Mk tal que

∣∣|Mi| − |Mj|∣∣ ≤ 1 para todo par i,j de

cores. Escreva uma “fórmula” para |Mi| em termos de m(G). (Sugestão: Vejaexercício 13.26.)

EI 13.28 (TEOREMA DE VIZING5) Mostre que

χ ′(G) ≤ ∆(G) + 1

para todo grafo G.6 Se combinarmos isso com o exercício 13.9, poderemosdizer que ∆ ≤ χ ′ ≤ ∆ + 1 para todo grafo.

E 13.29 Mostre que a heurística de troca de pares de cores sugerido no exer-cício 13.20 não é suficiente para demonstrar o teorema de Vizing (exercí-cio 13.28).

DD 13.30 (ALGORITMO) Invente um algoritmo rápido que calcule χ ′(G)para qualquer grafo G dado.

DD 13.31 (ALGORITMO) Invente um algoritmo rápido que resolva o pro-blema da coloração de arestas.

E 13.32 Seja X o conjunto dos vértices de um grafo G que têm grau ∆(G).Suponha que G[X] é uma floresta. Mostre que χ ′(G) = ∆(G).

DD 13.33 Um grafo G é t-duro (= t-tough) se, para todo conjunto S de vérti-ces, c(G − S) ≤ |S|/t, sendo c(G − S) o número de componentes de G − S.Prove a seguinte conjectura:7 Se G tem um número par de vértices e χ ′(G) =∆(G) + 1 então χ ′(G− v) = χ ′(G) para algum vértice v.

DD 13.34 Uma coloração total (= total coloring) de um grafo G é uma parti-ção de VG ∪ EG (estamos supondo que VG e EG são disjuntos) tal que, doisquaisquer elementos de um mesmo bloco da partição não são adjacentes nem

5 Publicado em 1964–1965 por Vadim G. Vizing (−). O fato também foi descoberto,independentemente, por Ram Prakash Gupta em 1966.

6 É tentador comparar essa desigualdade com a desigualdade χ ≤ ∆+1 do exercício 8.32.Mas as razões para as duas desigualdades são muito diferentes.

7 A conjectura foi proposta por I. T. Jakobsen, L. W. Beineke e R. J. Wilson em 1973.

http://en.wikipedia.org/wiki/Vadim_G._Vizing


mutuamente incidentes. O número de blocos da partição é o número de co-res da coloração. Prove a seguinte conjectura8: Todo grafo G admite umcoloração total com ∆(G) + 2 ou menos cores.

EDD 13.35 Mostre que χ ′(G) = 3 para todo grafo planar 3-regular G. (Estefato é equivalente ao teorema das Quatro Cores, exercício 8.61.)

8 A conjectura foi proposta por M. Behzad em 1965.

Capítulo 14

Coloração de vértices II

Voltamos a considerar o problema da coloração de vértices, já discutido nocapítulo 8:

PROBLEMA DA COLORAÇÃO DE VÉRTICES: Encontrar uma colora-ção mínima dos vértices de um grafo dado.

Exercícios

E 14.1 Seja G um grafo conexo não regular. Mostre que χ(G) ≤ ∆(G). (Com-pare com o exercício 8.32; mas não confunda com o exercício 13.28.)

E 14.2 (TEOREMA DE BROOKS1) Seja G um grafo conexo não completo di-ferente de um circuito ímpar. Mostre que χ(G) ≤ ∆(G). Compare com oexercício 14.1.)

E 14.3 Imagine uma grade em que todos os vértices exceto um estão colo-ridos. Cada vértices colorido tem uma de 3 possíveis cores. Invente uma“heurística da troca de cores em componentes bicoloridas” (compare com oexercício 13.20) para obter, a partir da coloração parcial dada, uma coloração(total) com apenas 3 cores.

E 14.4 Sejam I e J conjuntos estáveis num grafo G e suponha I ∩ J = ∅. SejaX o conjunto dos vértices de um componente do grafo bipartido G[I ∪ J ].Mostre que o conjunto I ⊕X é estável no grafo G.

1 Publicado por R. L. Brooks em 1941.

117

http://en.wikipedia.org/wiki/Heuristic_(computer_science)

FEOFILOFF Coloração de vértices II 118

E 14.5 (ALGORITMO) Descreva uma heurística de coloração de vértices ba-seada no exercício 14.4. (No início de cada iteração temos uma coloraçãoparcial dos vértices; cada iteração escolhe um vértice não colorido e procuraatribuir a ele uma das cores já usadas.)

EI 14.6 (ALGORITMO2) Sejam v1, x2, . . . , vn os vértices de um grafo e supo-nha que, para i = 2, . . . , n, o conjuntoperfect

eliminationscheme v1, . . . , vi−1 ∩ N(vi)

é uma clique. Escreva formalmente um algoritmo que calcule uma coloraçãode vértices mínima e uma clique máxima no grafo.

EDD 14.7 (TEOREMA DAS QUATRO CORES3) Mostre que todo grafo planaradmite uma coloração de vértices com 4 ou menos cores. Em outras palavras,mostre que

χ(G) ≤ 4

para todo grafo planar G.

E 14.8 Mostre que existem grafos planares que não admitem coloração devértices com 3 cores apenas.

EDD 14.9 Mostre que χ ′(G) = 3 para todo grafo planar 3-regular G. (Estefato é equivalente ao teorema das Quatro Cores, exercício 14.7.)

EDD 14.10 (TEOREMA DE LOVÁSZ4) Um grafo é perfeito (= perfect) segrafoperfeito χ(G[X]) = ω(G[X]) para todo subconjunto X de VG. Mostre que o com-

plemento de todo grafo perfeito é perfeito.

EDD 14.11 (TEOREMA FORTE DO GRAFO PERFEITO5) Um buraco ímpar(= odd hole) é um circuito induzido com um número ímpar ≥ 5 de vértices.

Prove que um grafo G é perfeito (veja o exercício 14.10) se e somentese nem G nem G contêm um buraco ímpar.6 (Esta caracterização de grafosperfeitos havia sido conjecturada por Claude Berge em 1960.)

2 Perfect Elimination Scheme.3 Demonstrado em 1976 por Kenneth Appel e Wolfgang Haken. Demonstração simplifi-

cada em 1997 por Neil Robertson, Daniel P. Sanders, Paul D. Seymour e Robin Thomas. Vejaas páginas “The four color theorem” e “Four-Color Theorem”.

4 Publicado por Lásló Lovász em 1972.5 Strong Perfect Graph Theorem.6 Este teorema foi provado em 2002 por Maria Chudnovsky e Paul D. Seymour como

base em trabalho prévio de Neil Robertson e Robin Thomas.

http://www.math.gatech.edu/~thomas/FC/fourcolor.html

http://en.wikipedia.org/wiki/Claude_Berge

http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html

http://mathworld.wolfram.com/Four-ColorTheorem.html

http://en.wikipedia.org/wiki/Lszl_Lovsz

http://www.cs.concordia.ca/~chvatal/perfect/spgt.html


EI 14.12 (TEOREMA DE GALLAI E ROY7) Para qualquer orientação acíclica8

D de um grafo G, seja k(D) o comprimento de um caminho orientado9 má-ximo em D. Então

χ(G) = 1 + minD

k(D) .

ED 14.13 Prove que a seguinte conjectura de Hajós10 é falsa: Para todo grafoG, se χ(G) = k então Kk é um menor topológico (veja seção 1.15) de G.

E 14.14 Teorema de Ore: Todo grafo que tenha número cromático k é homo-morfo a um Kk.

DD 14.15 Prove que a seguinte conjectura: Para todo grafo G, se χ(G) ≥ kentão Kk é imersível em G.

DD 14.16 Prove a seguinte conjectura de Hadwiger11: Para todo grafo G, seχ(G) = k então G tem um menor isomorfo a Kk.

7 Publicado em 1966 por Tibor Gallai e em 1967, independentemente, por Bernard Roy.8 Uma orientação de um grafo consiste na substituição de cada aresta vw pelo par orde-

nado (v, w) ou pelo par ordenado (w, v). Um tal par ordenado é chamado arco. O resultadoé um grafo dirigido. Um grafo dirigido D é acíclico se não tem circuitos orientados. Umcircuito é orientado se todos os seus arcos são dirigidas no mesmo sentido.

9 Um caminho é orientado se todos os seus arcos são dirigidas no mesmo sentido.10 A conjectura foi proposta por G. Hajós, em 1961.11 A conjectura foi proposta por H. Hadwiger, em 1943.


Capítulo 15

Circuitos e caminhoshamiltonianos

Um circuito num grafo é máximo se o grafo não contém um circuito maiscomprido. A circunferência de um grafo é o comprimento de um circuito decomprimento máximo no grafo.

PROBLEMA DO CIRCUITO MÁXIMO: Encontrar um circuito máximonum grafo dado.

O problema de encontrar um caminho máximo é formulado de maneira aná-loga. Um caminho num grafo é máximo se o grafo não contém um caminhomais comprido.

Um circuito é hamiltoniano1 se contém todos os vértices do grafo. É evi-dente que todo circuito hamiltoniano é um circuito máximo. O problema docircuito máximo tem a seguinte especialização óbvia:

PROBLEMA DO CIRCUITO HAMILTONIANO: Decidir se um dadografo tem um circuito hamiltoniano.

O conceito de caminho hamiltoniano e o problema do caminho hamiltoni-ano são definidos de maneira análoga.

Alguns dos exercícios abaixo envolvem a condição “δ(G) ≥ k”. Convémlembrar que esta condição equivale a “|N(v)| ≥ k para todo vértice v”, umavez que |N(v)| = d(v) para todo vértice v.

1 Referência a William Rowan Hamilton (− ). (Veja verbete na Wikipedia.) Teriasido mais justo homenagear o inglês Thomas P. Kirkman (− ). (Veja verbete naWikipedia.)

121

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Hamilton.html

http://en.wikipedia.org/wiki/William_Rowan_Hamilton

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Kirkman.html

http://en.wikipedia.org/wiki/Thomas_Kirkman

http://en.wikipedia.org/wiki/Thomas_Kirkman

FEOFILOFF Circuitos e caminhos hamiltonianos 122

Exercícios

EF 15.1 É verdade que todo grafo completo tem um circuito hamiltoniano?

EF 15.2 Dê condições necessárias e suficientes para que um grafo bipartidocompleto tenha um circuito hamiltoniano.

E 15.3 Encontre um circuito máximo no grafo da figura 15.1.

Figura 15.1: Encontre um circuito máximo. Veja exercício 15.3.

E 15.4 Encontre um circuito máximo no grafo de Petersen. Encontre um ca-minho máximo no grafo de Petersen.

E 15.5 Prove que para todo k ≥ 2 o k-cubo tem um circuito hamiltoniano.(Sugestão: Use indução em k.)2

E 15.6 Dê uma condição necessária e suficiente para que uma grade tenhaum circuito hamiltoniano.

E 15.7 Encontre um circuito hamiltoniano no grafo do cavalo t-por-t.

EF 15.8 SejaG um grafo 3-regular dotado de um circuito hamiltoniano. Mos-tre que χ ′(G) = 3.

E 15.9 (ALGORITMO) Discuta o seguinte algoritmo para o problema do cir-cuito hamiltoniano. Ao receber um grafo G,

(1) gere uma lista de todas as permutações de VG; (2) descarte as permu-tações que não correspondem a circuitos hamiltonianos; (3) devolva qual-quer uma das permutações restantes.

2 Indução é a arte de reduzir um problema a uma versão menor d’ele mesmo.


E 15.10 Mostre que todo grafo G tem um caminho de comprimento δ(G).(Veja exercício 1.111.)

E 15.11 Mostre que todo grafo G tem um circuito de comprimento não infe-rior a δ(G) + 1, desde que δ(G) > 1. (Veja exercício 1.114.)

E 15.12 Mostre que todo grafo G tem um caminho com pelo menos χ(G)vértices, sendo χ(G) o número cromático (veja capítulo 8) de G. (Veja o exer-cício 8.35).

E 15.13 Sejam P ∗ e Q∗ dois caminhos máximos em um grafo conexo G. Mos-tre que P ∗ e Q∗ têm um vértice em comum.

EF 15.14 Seja G um grafo dotado de circuito hamiltoniano. Mostre G nãotem pontes. Mostre que G não tem articulações.

E 15.15 Seja G um grafo dotado de circuito hamiltoniano. Mostre que todaaresta de G pertence a um circuito.

E 15.16 SejaG um grafo (U,W )-bipartido tal que |U | 6= |W |. Prove queG nãotem circuito hamiltoniano. (Outra maneira de formular a questão: para todografo (U,W )-bipartido dotado de circuito hamiltoniano tem-se |U | = |W |.)

E 15.17 Suponha que um grafo G tem um conjunto estável com mais quen(G)/2 vértices. Mostre que G não tem circuito hamiltoniano.

É verdade que todo grafo G com α(G) ≤ n(G)/2 tem um circuito hamil-toniano?

E 15.18 Seja G um grafo dotado de um caminho hamiltoniano. Mostre que condiçãonecessária

c(G− S) ≤ |S|+ 1

para toda parte própria S de VG.

EI 15.19 Seja S um conjunto de vértices de um grafo G. Suponha que 0 < condiçãonecessária|S| < n(G) e

c(G− S) > |S| ,sendo c(G − S) o número de componentes de G − S. Prove que G não temcircuito hamiltoniano. (Sugestão: Comece por analisar os casos |S| = 1 e|S| = 2.)

(Outra maneira de formular a questão: se um grafo G tem um circuitohamiltoniano então c(G − S) ≤ |S| para toda parte própria e não vazia Sde VG.)

Mostre que a condição “c(G− S) ≤ |S|” é uma generalização dos exercí-cios 15.14, 15.16 e 15.17.


E 15.20 Suponha que um grafoG satisfaz a desigualdade c(G−S) ≤ |S| paratodo conjunto S de vértices tal que 0 < |S| < n(G). É verdade que G tem umcircuito hamiltoniano?

DD 15.21 Um grafo G é t-duro (= t-tough) se, para todo conjunto S de vérti-ces, c(G − S) ≤ |S|/t. Prove a seguinte conjectura:3 Todo grafo 2-duro temum circuito hamiltoniano.

E 15.22 Mostre que existem grafos que não têm circuitos hamiltonianos massatisfazem a condição necessária discutida no exercício 15.19. Em outras pa-lavras, mostre que existe um grafo G desprovido de circuito hamiltoniano talque c(G− S) ≤ |S| para todo conjunto S de vértices tal que 0 < |S| < n(G).

E 15.23 Seja G um grafo conexo e O um circuito em G tal que, para todoaresta e de O, o grafo O − e é um caminho máximo em G. Prove que G temum circuito hamiltoniano.

E 15.24 Suponha que um grafo G satisfaz as desigualdades n(G) ≥ 4 eδ(G) ≥ n(G)− 2. Mostre que G tem um circuito hamiltoniano.

E 15.25 Seja G um grafo com n vértices e m arestas. Suponha que m ≥ 2 +12(n− 1)(n− 2). Prove que G tem um circuito hamiltoniano.

E 15.26 Seja G um grafo conexo tal que δ(G) ≥ k para algum número naturalk ≥ 2. Prove que G contém (1) um circuito hamiltoniano ou (2) um caminhocom mais que 2k vértices.4

EI 15.27 (TEOREMA DE DIRAC5) Suponha que um grafo G satisfaz as con-dições n(G) ≥ 3 econdição

suficiente δ(G) ≥ n(G)/2 .

Mostre que G tem um circuito hamiltoniano. (Sugestão: veja o exercí-cio 15.26.)

E 15.28 Seja G um grafo com a seguinte propriedade: para cada par u,v devértices não adjacentes,

d(u) + d(v) ≥ n(G) + 1 .

Prove que, para cada par u,v de vértices, G tem um caminho hamiltonianocom extremos u e v.

3 A conjectura foi proposta por Vašek Chvátal em 1971.4 Note que as duas alternativas não são mutuamente exclusivas.5 Publicado em 1952 por Gabriel Andrew Dirac.


E 15.29 Seja G um grafo e V1, V2, V3 uma partição de VG em partes não va-zias. Suponha que (1) cada vértice em V1 é adjacente a todos os vértices deV2 ∪ V3 e (2) cada vértice de V2 é adjacente a todos os vértices de V3.

Se |V2| = 2|V1| e |V3| = 3|V1|, prove que G tem um circuito hamiltoniano.Se |V2| = 2|V1| e |V3| = 3|V1|+ 1, prove que G não tem circuito hamiltoniano.

E 15.30 Seja A um algoritmo que decide se um grafo dado tem um circuitohamiltoniano. Use A para formular um algoritmo que decide se um grafodado tem um caminho hamiltoniano.

Seja B um algoritmo que decide se um grafo dado tem um caminho ha-miltoniano. Use B para formular um algoritmo que decide se um grafo dadotem um circuito hamiltoniano.

DD 15.31 Descubra uma condição necessária e suficiente para que um grafotenha um circuito hamiltoniano. Descubra uma condição necessária e sufici-ente para que um grafo tenha um caminho hamiltoniano.

DD 15.32 (ALGORITMO) Invente um algoritmo rápido que receba um grafoe devolva um circuito hamiltoniano no grafo (ou constate que o grafo nãotem um tal circuito).6

DD 15.33 (ALGORITMO) Invente um algoritmo rápido que encontre um cir-cuito máximo em qualquer grafo dado (que não seja uma floresta).7

DD 15.34 (ALGORITMO) Invente um algoritmo rápido que receba um grafoe devolva um caminho hamiltoniano no grafo (ou constate que o grafo nãotem um tal caminho).8

DD 15.35 (PROBLEMA DO CAIXEIRO VIAJANTE9) SejaK um grafo completoe ϕ uma função de EK em 0, 1, 2, 3, . . .. Para cada aresta e do grafo, dire-mos que ϕ(e) é o custo de e. O custo de um subgrafo H de K é

∑e∈EH

ϕ(e).Invente um algoritmo para encontrar um circuito hamiltoniano de custo mí-nimo em K.10

6 Um tal algoritmo ainda não foi encontrado. Em termos técnicos, o problema de de-cidir se um grafo tem um circuito hamiltoniano é NP-completo. Veja os livros de Garey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97].

7 Um tal algoritmo ainda não foi encontrado. O problema de encontrar um circuito má-ximo é NP-completo. Veja os livros de Garey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97].

8 Um tal algoritmo ainda não foi encontrado. O problema de decidir se um grafo tem umcaminho hamiltoniano é NP-completo. Veja os livros de Garey–Johnson [GJ79], Harel [Har92]e Sipser [Sip97].

9 Traveling Salesman Problem ou TSP).10 O problema é NP-difícil. Veja os livros de Garey–Johnson [GJ79], Harel [Har92] e Sip-

ser [Sip97].


(A propósito, veja o sítio A History of the Traveling Salesman Problem, man-tido por Bill Cook na Georgia Tech University.)

http://www.tsp.gatech.edu/

Capítulo 16

Decomposição em circuitos

(Este capítulo poderia também ser chamada “Ciclos eulerianos”.)

Uma cobertura por circuitos (= circuit cover) de um grafo G é qualquer cole-ção C de circuitos deG tal que

⋃C = EG.1 Em outras palavras, uma cobertura

por circuitos é uma coleção de circuitos tal que cada aresta do grafo pertencea pelo menos um dos circuitos do coleção.

Seria natural dedicar esta seção ao problema da cobertura mínima por circui-tos. Mas o problema é muito difícil. (Veja fim desta seção.) Trataremos entãodo problema, bem mais simples, da decomposição em circuitos.

Uma decomposição em circuitos (= circuit decomposition) de um grafo é qual-quer cobertura por circuitos sem arestas comuns, ou seja, qualquer coleção decircuitos tal que toda aresta do grafo pertence a exatamente um dos circuitosda coleção.

PROBLEMA DA DECOMPOSIÇÃO EM CIRCUITOS: Encontrar uma de-composição em circuitos de um grafo dado.

Exercícios

EF 16.1 Mostre que um grafo tem uma decomposição em circuitos se e so-mente se não tem pontes.

E 16.2 Exiba uma decomposição em circuitos de cada um dos grafos da fi-gura 16.1.

1 Se C = C1, C2, . . . , Ck então⋃C denota o conjunto C1 ∪ C2 ∪ · · · ∪ Ck.

127

FEOFILOFF Decomposição em circuitos 128

r r

rrrr

rr

@@

@@

aaaaa

aaaa

a

Figura 16.1: Encontre uma decomposição em circuitos. Veja exercício 16.2.

E 16.3 Para que valores de p e q uma grade p-por-q tem uma decomposiçãoem circuitos?

E 16.4 Para que valores de k o k-cubo tem uma decomposição em circuitos?

E 16.5 Considere as 21 peças não duplas do jogo de dominó. Cada umadessas peças corresponde a um subconjunto de cardinalidade 2 do conjunto0, 1, 2, . . . , 6. A regra básica do jogo de dominó permite “encostar” umapeça da forma i, j numa peça da forma j, k de forma que a produzir asequência (i, j, j, k). É possível formar um “roda” que contenha todas as 21peças? E se eliminarmos todas as peças que contêm “6”?

E 16.6 Dê uma condição necessária e suficiente para que um grafo completotenha uma decomposição em circuitos.

E 16.7 Encontre uma decomposição em circuitos do grafo do cavalo.

E 16.8 Suponha que um grafo G tem uma decomposição em circuitos. Mos-tre que o grafo das arestas L(G) tem um circuito hamiltoniano (veja exercí-cio 1.24).

Mostre que a recíproca não é verdadeira: L(G) pode ter um circuito ha-miltoniano sem que G tenha uma decomposição em circuitos.

E 16.9 Suponha que um grafo G tem uma decomposição em circuitos. Mos-tre que todos os vértices deG têm grau par. (Outra maneira de dizer a mesmacoisa: se um grafo tem um vértice de grau ímpar então não tem decomposi-ção em circuitos.)2

E 16.10 Seja G um grafo sem vértices de grau ímpar. Mostre que G não tempontes.

2 Portanto, um vértice de grau ímpar é um certificado da inexistência de decomposiçãoem circuitos.


E 16.11 Seja F um conjunto de arestas de um grafo G. Suponha que o grafo(VG, F ) é conexo e tem uma decomposição em circuitos. Mostre que G éaresta-biconexo. A recíproca é verdadeira?

EI 16.12 (TEOREMA DE VEBLEN3) Mostre que todo grafo sem vértices degrau ímpar tem uma decomposição em circuitos.4

E 16.13 Mostre que um grafo tem uma decomposição em circuitos se e so-mente se o grau de cada um de seus vértices é par. Em outras palavras,mostre que a ausência de vértices de grau ímpar é condição necessária e su-ficiente para que um grafo tenha uma decomposição em circuitos. (Veja osexercícios 16.9 e 16.12.)

E 16.14 Mostre que um grafo tem uma decomposição em circuitos se e so-mente se todos os seus cortes são pares.

E 16.15 Grafos que têm decomposição em circuitos não têm vértices ímpa-res. Grafos bicromáticos não têm circuitos ímpares. Há algo por trás desseparalelo? Veja exercício 16.29.

E 16.16 (ALGORITMO) Construa um algoritmo que receba um grafo G e de-volva uma decomposição em circuitos de G (ou prove que tal decomposiçãonão existe).

EI 16.17 (CICLOS EULERIANOS5) Um ciclo (= cycle) em um grafo é qual-quer sequência (v0, v1, v2, . . . , vk−1, vk) de vértices dotada de três proprieda-des: (1) vk = v0 , (2) vi é adjacente a vi−1 para todo i de 1 a k e (3) as arestasv0v1, v1v2, . . . , vk−1vk são distintas duas a duas (ou seja, o ciclo não tem arestas“repetidas”). Um ciclo é euleriano se passa por todas as arestas do grafo. 6

Assim, um ciclo (v0, v1, . . . , vk−1, vk) é euleriano se e somente se k é igual aonúmero de arestas do grafo.

Mostre que todo grafo dotado de um ciclo euleriano tem uma decompo-sição em circuitos.

Mostre que todo grafo conexo dotado de uma decomposição em circuitostem um ciclo euleriano.

E 16.18 Encontre um ciclo euleriano no grafo da figura 16.2.

3 Oswald Veblen (− ). Veja verbete na Wikipedia.4 O teorema também pode ser atribuído a Leonhard Euler (− ). Veja verbete na

Wikipedia.5 Referência a Leonhard Euler (− ). Veja verbete na Wikipedia.6 Alguns livros não exigem que o ciclo passe por todos os vértices do grafo. A diferença

entre as duas definições é superficial.

http://www-history.mcs.st-andrews.ac.uk/Biographies/Veblen.html

http://en.wikipedia.org/wiki/Oswald_Veblen







rr rr r

rr r

AA

TTTTTT

TTT

c

d

g

e

a h

b

f

Figura 16.2: Encontre um ciclo euleriano.Veja exercício 16.18.

E 16.19 Sejam xy e yz duas arestas de um grafo conexo G sem vértices degrau ímpar. É verdade que G tem um ciclo euleriano na qual xy e yz apare-cem consecutivamente?

E 16.20 Seja G um grafo conexo cada um de cujos vértices tem grau par. Su-ponha que m(G) é par. Prove que EG admite uma partição F1, F2 tal que|F1 ∩ ∂v| = |F2 ∩ ∂v| para cada vértice v, ou seja, v incide no mesmonúmero de arestas de F1 e F2.

Coberturas por circuitos

Como já dissemos acima, uma cobertura por circuitos de um grafo G é qual-quer coleção C de circuitos de G tal que

⋃C = EG. Os problemas que en-

volvem coberturas por circuitos parecem mais naturais que o problema dadecomposição em circuitos, mas são muito mais difíceis.

Uma cobertura por circuitos C é mínima se não existe cobertura por circuitosD tal que |D| < |C|.

O comprimento total de uma cobertura por circuitos C é a soma∑

C∈C |EC |.

A espessura de uma cobertura por circuitos C de um grafo G é o númeromaxe∈EG

|C ∈ C : EC 3 e |. Assim, se uma cobertura tem espessura kentão toda aresta do grafo pertence no máximo k dos circuitos da cobertura.Reciprocamente, se cada aresta do grafo pertence a k ou menos circuitos dacobertura então a cobertura tem espessura ≤ k.

Exercícios

EF 16.21 Mostre que um grafo tem uma cobertura por circuitos se e somentese não tem pontes.


DD 16.22 (COBERTURA POR CIRCUITOS MÍNIMA) Resolva o seguinte pro-blema: Encontrar uma cobertura por circuitos mínima de um grafo sem pon-tes.

E 16.23 Encontre uma cobertura por circuitos mínima do grafo de Petersen.

DD 16.24 (COBERTURA DE COMPRIMENTO TOTAL MÍNIMO) Resolva o se-guinte problema: Dado um grafo sem pontesG, encontrar uma cobertura porcircuitos de G que tenha comprimento total mínimo.7

EF 16.25 Mostre que toda decomposição em circuitos de um grafo G é umacobertura de comprimento total mínimo.

E 16.26 Encontre uma cobertura por circuitos do grafo de Petersen que tenhacomprimento total mínimo.

EI 16.27 Mostre que todo grafo aresta-biconexo planar G (veja seção 1.6) temuma cobertura por circuitos de comprimento total ≤ 2m(G).

DD 16.28 (COBERTURA DE ESPESSURA MÍNIMA) Resolva o seguinte pro-blema: Dado um grafo sem pontes G, encontre uma cobertura por circuitosde G que tenha espessura mínima.

(Segundo a célebre conjectura da Cobertura Dupla por Circuitos8 (= Cir-cuit Double Cover Conjecture), todo grafo sem pontes tem uma cobertura deespessura ≤ 2.)

E 16.29 (BOM!) Seja G o grafo de um mapa plano (P,C). Suponha que G Broughtfrom pla-narity.tex

é conexo, não tem pontes e não tem vértices de grau 2 (ou seja, δ(G) ≥ 3).Seja G∗ o grafo das faces (ou seja, grafo dual) do mapa (P,C). Mostre que G∗

é bicromático se e somente se G tem uma decomposição em circuitos (vejacapítulo 16).

E 16.30 Mostre que todo grafo planar sem pontes tem uma cobertura dupla Broughtfrom pla-narity.tex

por circuitos. (Veja os exercícios 16.27 e 16.33.)

EF 16.31 Mostre que toda decomposição em circuitos de um grafo G é umacobertura de espessura mínima.

7 Não se conhece um algoritmo eficiente para o problema. Em termos técnicos, o pro-blema de decidir se um grafo tem um circuito hamiltoniano é NP-completo. Veja os livros deGarey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97].

8 A conjectura é de George Szekeres e Paul Seymour.

http://en.wikipedia.org/wiki/George_Szekeres

http://en.wikipedia.org/wiki/Paul_Seymour_(mathematician)


E 16.32 Encontre uma cobertura por circuitos do grafo de Petersen que tenhaespessura mínima.

EI 16.33 Mostre que todo grafo aresta-biconexo planar (veja seção 1.6) temuma cobertura por circuitos de espessura ≤ 2.

Capítulo 17

Conectores mínimos

Uma conector1 de um grafo G é qualquer subconjunto C de EG tal que ografo (VG, C) é conexo. Um conector C∗ de um grafo é mínimo se não existeoutro conector C tal que |C| < |C∗|.

PROBLEMA DO CONECTOR MÍNIMO: Encontrar um conector mí-nimo de um grafo dado.

Convém não confundir mínimo com minimal. Um conector C ′ é minimal senão existe conector C tal que C ⊂ C ′. É evidente que todo conector mínimotambém é minimal. É um tanto surpreendente (diante do que acontece comcoberturas por vértices, por exemplo) que a recíproca seja verdadeira: todoconector minimal é mínimo. (Veja exercício 17.8.) Por isso, o problema doconector mínimo é muito fácil.

Uma árvore geradora (= spanning tree) de um grafo G é qualquer subgrafogerador de G que seja uma árvore.2 Uma árvore geradora é essencialmente omesmo que um conector minimal (veja o exercício 17.7).

Exercícios

EF 17.1 Mostre que um grafo G tem um conector se e somente se G é conexo.

EF 17.2 Seja G um grafo conexo e C um subconjunto de EG. Seja V (C) oconjunto de todos os vértices incidentes a arestas de C. Suponha que o grafo(V (C), C) é conexo. É verdade que C é um conector?

1 Cuidado! A maioria dos livros de teoria dos grafos não usa o termo “conector”.2 Uma árvore geradora de um grafo poderia ser chamada esqueleto do grafo. Em alemão,

por exemplo, diz-se Gerüst (= andaime).

133

FEOFILOFF Conectores mínimos 134

E 17.3 Seja C um conector minimal de um grafo G. Mostre que toda arestaem C é uma ponte de G.

E 17.4 Seja C um conector minimal de um grafo G. Mostre que C é acíclico,ou seja, que o grafo (VG, C) não tem circuitos. (Veja os exercícios 17.3 e 1.141.)

EF 17.5 Uma subárvore de um grafo G é qualquer subgrafo de G que sejauma árvore. Uma subárvore T ∗ de G é máxima se não existe subárvore T talque |ET | > |ET ∗|. Mostre que uma subárvore máxima de G é essencialmenteo mesmo que um conector mínimo de G.

E 17.6 Seja C um circuito num grafo conexo G. Sejam a e b duas arestasdiferentes de C. Seja Ha um conector minimal de G − a e Hb um conectorminimal de G− b. É verdade que Ha é diferente de Hb?

E 17.7 A. Seja T uma árvore geradora de um grafo G. Mostre que ET é umconector minimal de G.

B. Seja C um conector minimal de G. Mostre que o grafo (VG, C) é umaárvore geradora de G.

EI 17.8 Mostre que todo conector minimal de um grafo G tem exatamenten(G)− 1 arestas. (Veja exercício 1.212.) Deduza daí que todo conector mini-mal é mínimo.

E 17.9 (ALGORITMO) Construa um algoritmo eficiente que receba um grafoG e devolva um conector mínimo de G ou uma prova de que G não é conexo.

E 17.10 Prove que todo grafo conexo com dois ou mais vértices tem um vér-tice v tal que G− v é conexo. (Compare com o exercício 1.167.)

E 17.11 (CIRCUITOS FUNDAMENTAIS) Seja C um conector minimal de umgrafo G e b um elemento de EGrC. Mostre que o grafo (VG, C ∪b) tem umúnico circuito.

(Circuitos desse tipo são conhecidos como circuitos fundamentais de G.É claro que os circuitos fundamentais dependem do conector: para cada co-nector minimal de G teremos uma coleção diferente de circuitos fundamen-tais.)

E 17.12 Seja G um grafo conexo com n vértices e m arestas. Mostre que Gtem pelo menos m− n+ 1 circuitos.


EI 17.13 Seja C um conector minimal de um grafo G e b um elemento deEG r C. Mostre que existe a em C tal que

(C ∪ b) r a

é um conector minimal de G.

E 17.14 Seja a uma aresta em um conector minimal C de um grafo G. Dêuma condição necessária e suficiente para que exista uma aresta b em EGrCtal que (C r a) ∪ b seja um conector. (Compare com o exercício 17.13.)

E 17.15 Suponha que um grafo G tem um único conector minimal. Mostreque G é uma árvore.

E 17.16 (ALGORITMO) Suponha que cada aresta e de um grafo G tem um“peso” numérico π(e) ≥ 0. Por definição, o peso de qualquer conjunto Ade arestas é o número

∑e∈A π(e). Construa um algoritmo que encontre um

conector de G que tenha peso mínimo.3

3 Os célebres algoritmos de J.B. Kruskal e R.C. Prim resolvem o problema. Esses algorit-mos têm um caráter “guloso”. Eles estão entre os mais antigos e mais conhecidos algoritmosgulosos da teoria dos grafos. A prova da correção desses algoritmos depende do exercí-cio 17.13.


Capítulo 18

Conjuntos acíclicos máximos

Um conjunto F de arestas de um grafo G é acíclico se o grafo (VG, F ) é umafloresta, ou seja, se (VG, F ) não tem circuitos. Uma subconjunto acíclico F ∗

de EG é máximo se não existe subconjunto acíclico F tal que |F | > |F ∗|.

PROBLEMA DO CONJUNTO ACÍCLICO MÁXIMO: Dado um grafo G,encontrar um subconjunto acíclico máxima de EG.

Convém não confundir máximo com maximal. Uma subconjunto acíclico F ′

de EG é maximal se não existe subconjunto acíclico F de EG tal que F ⊃ F ′.É evidente que todo subconjunto acíclico máximo também é maximal. Éum tanto surpreendente (diante do que acontece com emparelhamentos, porexemplo) que a recíproca seja verdadeira: todo subconjunto acíclico maximalé máximo (veja exercício 18.3). Por isso, o problema do subconjunto acíclicomáximo é muito fácil.

Exercícios

E 18.1 Seja G um grafo conexo e F um subconjunto acíclico maximal de EG.Mostre que F é um conector.

EF 18.2 Uma subfloresta de um grafoG é qualquer floresta que seja subgrafode G. Uma subfloresta F ∗ de um grafo G é máxima se não existe subflorestaF tal que m(F ) > m(F ∗). Mostre que uma subfloresta máxima de G é essen-cialmente o mesmo que um subconjunto acíclico máximo de EG. (É verdadeque toda subfloresta máxima de G é geradora?)

EI 18.3 Mostre que todo conjunto acíclico maximal de arestas de um grafo Gtem exatamente n(G) − c(G) arestas, sendo c(G) o número de componentes

137

FEOFILOFF Conjuntos acíclicos máximos 138

de G. (Veja exercício 1.215.) Deduza daí que todo conjunto acíclico maximalé máximo.

E 18.4 Seja G um grafo e F um subconjunto acíclico maximal de EG. Seja Hum componente de G. Mostre que F ∩EH é um conector (veja o capítulo 17)de H . Formule e prove a recíproca deste fato.

E 18.5 (ALGORITMO) Construa um algoritmo eficiente que receba qualquergrafo G e devolva um subconjunto acíclico máximo de EG.

E 18.6 (CIRCUITOS FUNDAMENTAIS) Seja G um grafo e F um subconjuntoacíclico maximal de EG. Seja b uma aresta em EG r F . Mostre que o grafo(VG, F ∪ b) tem um único circuito.

(Circuitos desse tipo são conhecidos como circuitos fundamentais de G.É claro que os circuitos fundamentais dependem do conjunto F : para cadasubconjunto acíclico maximal F teremos uma coleção diferente de circuitosfundamentais.)

EI 18.7 Seja G um grafo e F um subconjunto acíclico maximal de EG. Seja buma aresta em EG r F . Mostre que existe a em F tal que

(F ∪ b) r a

é um subconjunto acíclico maximal de EG. (Veja o exercício 1.206.)

E 18.8 Suponha que um grafo G tem um único conjunto acíclico maximal.Mostre que G é uma floresta.

E 18.9 (ALGORITMO) Suponha que cada aresta de um grafo G tem um“custo” não negativo. Por definição, o custo de qualquer subconjunto F deEG é a soma dos custos das arestas que estão F . Construa um algoritmo queencontre um subconjunto acíclico EG que tenha custo máximo.1

Coberturas de circuitos

E 18.10 (COBERTURA DE CIRCUITOS) Uma cobertura de circuitos por ares-tas (= feedback edge set) em um grafo G é um conjunto D de arestas tal queG−D não tem circuitos. Qual a cardinalidade de uma cobertura mínima decircuitos por arestas?

1 Os célebres algoritmos de J.B. Kruskal e R.C. Prim resolvem o problema. Esses algo-ritmos são os mais antigos e mais conhecidos algoritmos “gulosos” da teoria dos grafos. Aprova da correção desses algoritmos depende do exercício 18.7.


DD 18.11 (COBERTURA DE CIRCUITOS) Uma cobertura de circuitos porvértices (= feedback vertex set) em um grafo G é um conjunto X de vérticestal que G−X não tem circuitos. Invente um algoritmo eficiente que encontreuma cobertura mínima de circuitos por vértices.


Capítulo 19

Caminhos e circuitos mínimos

Um caminho é mais curto que outro se o comprimento do primeiro é menorque o do segundo. Um caminho P∗ é mínimo se nenhum caminho mais curtotem os mesmos extremos que P∗.

PROBLEMA DO CAMINHO MÍNIMO: Dados vértices v e w de umgrafo, encontrar um caminho mínimo com extremos v e w.

Em outras palavras, o problema consiste em encontrar um caminho de com-primento mínimo dentre todos os caminhos que têm extremos v e w.

A distância entre dois vértices v e w é o comprimento de um caminho mí-nimo com extremos v e w. Se não existe caminho algum com esses extremos,dizemos que a distância entre v ew é infinita. A distância entre dois vértices ve w de um grafo G será denotada por distG(v, w). Se G estiver subentendido, dist( , )

diremos simplesmente dist(v, w).

Um circuito é mínimo se o grafo não contém outro circuito mais curto. Acintura (= girth) de um grafo é o comprimento de um circuito mínimo nografo. Se um grafo não tem circuito algum, sua cintura é infinita.

Exercícios

E 19.1 No grafo da figura 19.1, calcule a distância entre o vértice x e cada umdos outros vértices. Em seguida, exiba um caminho mínimo entre x e y.

EF 19.2 Seja k a distância entre dois vértices v e w num grafo. Mostre que(1) existe um caminho de comprimento k de v a w e (2) não existe caminhode comprimento menor que k de v a w. Mostre a recíproca: se (1) e (2) valementão a distância entre v e w é k.

141

FEOFILOFF Caminhos e circuitos mínimos 142

x

y

r r r r r r r rr r r r r r r rr r r r r r r rr r r r r r r rr r r r r r r rr r r r r r r r

r r r r rr r rr r rr r r rr rr r r r

rrrrr

rrr

rr

rrrr

rrrrr

rrrrr

@@

@@

@@

Figura 19.1: Encontre um caminho mínimoentre x e y. Veja o exercício 19.1.

E 19.3 Mostre que todo grafo com m ≥ 3n(G)/2 tem um circuito de compri-mento ≤ αn para alguma constante α.

E 19.4 Suponha que v0v1 · · · vk é um caminho mínimo (dentre os que têm ex-tremos v0 a vk). Prove que

dist(v0, vj) = j

para todo índice j.

EI 19.5 (DESIGUALDADE TRIANGULAR) Prove que para qualquer terno(x, y, z) de vértices de um grafo vale a desigualdade

dist(x, y) + dist(y, z) ≥ dist(x, z) .

E 19.6 Seja r um vértice de um grafo conexo G. Mostre que, para qualqueraresta xy, tem-se |dist(r, x)− dist(r, y)| ≤ 1.

E 19.7 (ALGORITMO DA BUSCA EM LARGURA1) Construa um algoritmo efi-ciente que receba dois vértices v e w de um grafo e calcule a distância entrev e w. Construa um algoritmo eficiente que encontre um caminho mínimoentre dois vértices dados.

E 19.8 (ÁRVORE DAS DISTÂNCIAS) Seja r um vértice de um grafo conexo G.Mostre que G tem uma árvore geradora T tal que

distG(r, x) = distT (r, x)

para todo vértice x (ou seja, a distância de r a x em G é igual à distância de ra x em T ).

1 Breadth-First Search Algorithm.


EF 19.9 É verdade que todo grafo conexo G tem uma árvore geradora T talque distG(u, v) = distT (u, v) para todo par u,v de vértices?

E 19.10 O diâmetro de um grafo G é o número maxu,v dist(u, v), sendo o má-ximo tomado sobre todos os pares u,v de vértices. Prove que o diâmetro dequase todo grafo G em G(n) (veja a seção 1.17) não passa de 2.

E 19.11 Um vértice v de um grafo é central se minimiza maxx∈V dist(v, x).Mostre que toda árvore tem no máximo dois centros e se tiver dois então elessão adjacentes.

E 19.12 O grafo de Heawood2 tem conjunto de vértices 0, 1, 2, . . . , 13. Cada Heawoodvértice i é vizinho de (i + 1) mod 14 e de (i + 13) mod 14.3 Além disso, cadai é vizinho de um terceiro vértice, que depende da paridade de i: se i é parentão ele é vizinho de (i+ 5) mod 14 e se i é ímpar então ele é vizinho de (i+9) mod 14. Faça uma figura do grafo. Encontre um circuito de comprimentomínimo no grafo de Heawood.

E 19.13 (ALGORITMO) Construa um algoritmo que calcule a cintura dequalquer grafo dado. Construa um algoritmo que encontre um circuito mí-nimo em qualquer grafo dado. (Sugestão: Veja o exercício 19.7.)

Restrições de paridade

Dizemos que um circuito ou caminho é ímpar se o seu comprimento é umnúmero ímpar. Analogamente, um circuito ou caminho é par se o seu com-primento é um número par.

A cintura ímpar de um grafo é o comprimento de um circuito ímpar mínimono grafo. A cintura par é definida analogamente.

E 19.14 Seja r um vértice de um grafo conexo G. Sejam x e y dois vérticesadjacentes tais que dist(r, x) = dist(r, y). Mostre queG tem um circuito ímpar.Mais especificamente, mostre que a cintura ímpar do grafo não é superior adist(r, x) + dist(r, y) + 1.

E 19.15 Use o conceito de distância para mostrar que um grafo é bicromáticose e somente se não tem circuitos ímpares. (Compare com o exercício 4.14.Sugestão: Veja o exercício 19.14.)

2 Percy John Heawood (− ).3 A expressão “i mod j” denota o resto da divisão de i por j.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Heawood.html


E 19.16 (ALGORITMO) Construa um algoritmo que calcule a cintura ímparde qualquer grafo dado. Construa um algoritmo que encontre um circuitoímpar mínimo em qualquer grafo dado.

E 19.17 (ALGORITMO) Construa um algoritmo que calcule a cintura par dequalquer grafo dado. Construa um algoritmo que encontre um circuito parmínimo em qualquer grafo dado.

ED 19.18 (ALGORITMO) Dados dois vértices u e v de um grafo G, encontreum caminho de comprimento mínimo na coleção de todos os caminhos decomprimento par que têm extremos u e v.

ED 19.19 (ALGORITMO) Dados dois vértices u e v de um grafo G, encontreum caminho de comprimento mínimo na coleção de todos os caminhos decomprimento ímpar que têm extremos u e v.

Capítulo 20

Caracterização da planaridade

Como já dissemos na seção 1.16, um mapa plano (P,C) representa umgrafo G se o grafo de (P,C) é isomorfo a G. Também já dissemos que umgrafo G é planar se for representável por um mapa plano, ou seja, se existirum mapa plano cujo grafo é isomorfo a G.

PROBLEMA DO MAPA PLANO: Encontrar um mapa plano que repre-sente um grafo dado.

Como nem todo grafo tem um mapa plano, uma parte importante do pro-blema consiste no seguinte:

PROBLEMA DA PLANARIDADE: Decidir se um dado grafo é planarou não.

Se um grafo não é planar, como é possível tornar isso evidente? Uma res-posta muito bonita é dada em termos de menores “proibidos”: todo grafonão planar tem um menor que é obviamente não planar.

Exercícios

EI 20.1 Mostre que K3,3 (veja figura 20.1) não é planar.

EI 20.2 Mostre que K5 (veja figura 20.1) não é planar.

E 20.3 Mostre que todo subgrafo de um grafo planar é planar. Em outraspalavras, se um grafo G tem um subgrafo não planar então G não é planar.

145

FEOFILOFF Caracterização da planaridade 146

Figura 20.1: K3,3 e K5 não são planares. Veja exercícios 20.1 e 20.2.

E 20.4 Suponha que todos os subgrafos próprios de um grafoG são planares.É verdade que G é planar?

E 20.5 Suponha que um grafo G não contém um K5 nem um K3,3. É verdadeque G é planar?

EI 20.6 Mostre que todo menor topológico (veja seção 1.15) de um grafo pla-nar é planar. (Em outras palavras, se um grafo G tem um menor topológiconão planar então G não é planar.)

EI 20.7 Mostre que todo menor de um grafo planar é planar. (Em outraspalavras, se um grafo G tem um menor não planar então G não é planar.)

E 20.8 Mostre que todo menor próprio de K5 é planar. Mostre que todo me-nor próprio de K3,3 é planar.

E 20.9 Mostre que K5 não tem menor isomorfo a K3,3. Mostre que K3,3 nãotem menor isomorfo a K5.

E 20.10 Mostre que o grafo de Petersen tem um menor (isomorfo a) K5. De-duza daí que o grafo de Petersen não é planar.

Mostre que o grafo de Petersen tem um menor topológico (iso-morfo a) K3,3.

E 20.11 Mostre que K3,3 é (isomorfo a) um menor topológico do 4-cubo. De-duza daí que o 4-cubo não é planar. Mostre também que K5 é (isomorfo a)um menor topológico do 4-cubo.

E 20.12 Suponha que um grafo G tem um menor (isomorfo a) K5 ou um me-nor (isomorfo a) K3,3. Mostre que G não é planar.

EID 20.13 (TEOREMA DE WAGNER1) Mostre que todo grafo não planar temum menor (isomorfo a) K5 ou um menor (isomorfo a) K3,3. (Compare com oexercício 20.12.)

1 Publicado em 1937 por Klaus W. Wagner (− ).

http://en.wikipedia.org/wiki/Klaus_Wagner_(mathematician)


E 20.14 Mostre que um grafo é planar se e somente se não tem um menor(isomorfo a) K5 nem um menor (isomorfo a) K3,3. (Veja os exercícios 20.12e 20.13.)

E 20.15 Suponha que algum menor topológico de um grafo G é (iso-morfo a) K5 ou (isomorfo a) K3,3. Mostre que G não é planar.

EID 20.16 (TEOREMA DE KURATOWSKI2) Mostre que todo grafo não planartem um menor topológico (isomorfo a) K5 ou um menor topológico (iso-morfo a) K3,3. (Compare com o exercício 20.15.)

E 20.17 Mostre que um grafo é planar se e somente se não tem um menortopológico (isomorfo a)K5 nem um menor topológico (isomorfo a)K3,3. (Vejaos exercícios 20.15 e 20.16.)

E 20.18 Discuta a seguinte afirmação: “Como K5 não é bicromático, pode-mos concluir que todo grafo bicromático não planar contém uma subdivisãode K3,3.”

ED 20.19 (ALGORITMO) Construa um algoritmo que decida se um dadografo é planar.

DD 20.20 Prove a seguinte conjectura:3 Todo grafo G com m(G) > 3n(G)− 6tem um menor topológico (isomorfo a) K5. (Veja o exercício 1.275.)

2 Publicado em 1930 por Kazimierz Kuratowski (− ).3 A conjectura foi proposta por G. A. Dirac em 1964.

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Kuratowski.html


Apêndice A

O alfabeto grego

A teoria dos grafos, tal como outras áreas da matemática, considera o alfabeto latinoinsuficiente e recorre frequentemente ao alfabeto grego:

α A alfa ν N nüβ B beta ξ Ξ ksiγ Γ gama o O ômicronδ ∆ delta π Π piε E epsilon ρ P rôζ Z zeta σ Σ sigmaη H eta τ T tauθ Θ teta υ Υ upsilonι I iota ϕ Φ fiκ K kapa χ X quiλ Λ lambda ψ Ψ psiµ M mü ω Ω ômega

O símbolo ∂ não pertence ao alfabeto grego. Este texto usa o símbolo para denotarcortes (seção 1.9).

149

FEOFILOFF 150

Bibliografia

[BM76] J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. Mac-millan/Elsevier, 1976. Internet: http://www.ecp6.jussieu.fr/

pageperso/bondy/books/gtwa/gtwa.html. 5

[BM08] J.A. Bondy and U.S.R. Murty. Graph Theory. Graduate Textsin Mathematics 244. Springer, 2008. Internet: http://blogs.

springer.com/bondyandmurty. 5

[Bol98] B. Bollobás. Modern Graph Theory, volume 184 of Graduate Texts inMathematics. Springer, 1998. 5

[Die00] R. Diestel. Graph Theory, volume 173 of Graduate Textsin Mathematics. Springer, second edition, 2000. In-ternet: http://www.math.uni-hamburg.de/home/diestel/books/

graph.theory/index.html. 5

[Die05] R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathema-tics. Springer, third edition, 2005. 5, 9

[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability: a Guideto the Theory of NP-Completeness. W.H. Freeman, 1979. 5, 125, 131

[Har92] D. Harel. Algorithmics: The Spirit of Computing. Addison-Wesley,second edition, 1992. 5, 125, 131

[Knu93] D.E. Knuth. The Stanford GraphBase: A Platform for CombinatorialComputing. ACM Press and Addison-Wesley, 1993. 13

[Lov93] L. Lovász. Combinatorial Problems and Exercises. North-Holland,second edition, 1993. 5

[LP86] L. Lovász and M.D. Plummer. Matching Theory, volume 29 of An-nals of Discrete Mathematics. North-Holland, 1986. 5, 16

[Luc79] C.L. Lucchesi. Introdução à Teoria dos Grafos. 12o. Colóquio Brasi-leiro de Matemática. IMPA (Instituto de Matemática Pura e Apli-cada), 1979. 5

151

http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html

http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html

http://blogs.springer.com/bondyandmurty

http://blogs.springer.com/bondyandmurty

http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/index.html

http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/index.html

FEOFILOFF BIBLIOGRAFIA 152

[MST+98] O. Melnikov, V. Sarvanov, R. Tyshkevich, V. Yemelichev, andI. Zverovich. Exercises in Graph Theory, volume 19 of Kluwer Textsin the Mathematical Sciences. Kluwer, 1998. 5

[Per09] J.M.S. Simões Pereira. Matemática Discreta: Grafos, Redes, Aplica-ções. Luz da Vida, Coimbra, Portugal, 2009. 15, 22, 27, 93

[Sip97] M. Sipser. Introduction to the Theory of Computation. PWS Pu-blishing, 1997. Internet: http://www-math.mit.edu/~sipser/

book.html. 5, 125, 131

[vL90] J. van Leeuwen. Graph algorithms. In J. van Leeuwen, editor, Al-gorithms and Complexity, volume A of Handbook of Theoretical Com-puter Science, pages 527–631. Elsevier and MIT Press, 1990.

[Wil79] R.J. Wilson. Introduction to Graph Theory. Academic Press, secondedition, 1979. 5

http://www-math.mit.edu/~sipser/book.html

http://www-math.mit.edu/~sipser/book.html

Índice Remissivo

bxc, 11, 38dxe, 74V (2), 9VG, 9EG, 9n(G), 9m(G), 9c(G), 39G, 9Kn, 9Kp,q, 16L(G), 15N(v), 18Adj , 18N(X), 34, 99d(v), 18d(X), 33δ(G), 18δ(X), 33∂(X), 33∆(G), 18∇(X), 33X ⊂ Y , 27Y ⊃ X , 27X ⊕ Y , 34G ⊆ H , 27G ∪H , 25G ∩H , 25G[X], 27G ∼= H , 59G(n), 58G− v, 27G−X , 27G− e, 27G−A, 27α, 71α ′, 93β, 81

ω, 77χ, 84χ ′, 111o, 107

abrangente (subgrafo), 27acíclico, 137acoplamento, 93adjacent, 9adjacentes

arestas, 15, 93vértices, 9

alcanos, 10aleatório, 58algoritmo

de aproximação, 82, 97guloso, 73, 86, 90, 113húngaro, 100

alternating, 94Appel, 91, 118aresta, 9

de corte, 33aresta-biconexo, 452-aresta-conexo, 45arestas

adjacentes, 15, 93múltiplas, 9, 54paralelas, 9, 54

articulação, 47, 86, 113articulation, 47árvore, 42

das distâncias, 142geradora, 133

augmenting path, 94auto-complementar, 62

β, 81Berge, 118BFS, 142

153

FEOFILOFF ÍNDICE REMISSIVO 154

bicoloração, 83de grafo, 67

biconexo, 47biconnected, 47bicromático, 67bigrafo, 16bigraph, 16bipartição

de conjunto, 16, 67de grafo, 16

bipartido, 16completo, 16

bipartite, 16bishop, 12bispo, 12Bollobás, 5breadth-first search, 142bridge, 33buraco ímpar, 118busca em largura, 142

c(G), 39caixeiro viajante, 125caminho, 22

alternante, 94de aumento, 94hamiltoniano, 121ímpar, 69ímpar mínimo, 144maximal, 27máximo, 27, 121mínimo, 141par, 69par mínimo, 144

cavalo, 12certificado, 69, 88, 97, 108, 128chromatic

index, 111number, 83

Chudnovsky, 118Chvátal, 124ciclo, 32, 129

euleriano, 129cintura, 141

ímpar, 143par, 143

circuit cover, 127

circuit decomposition, 127circuit double cover, 131circuit double cover conjecture, 131circuito, 22

fundamental, 134, 138hamiltoniano, 121ímpar, 67, 69ímpar mínimo, 143máximo, 121mínimo, 141par, 69par mínimo, 143

circunferência, 121clique, 77clique cover, 84clique number, 77closed, 31cobertura

de circuitospor arestas, 138por vértices, 139

dupla por circuitos, 131por arestas, 109por circuitos, 127por cliques, 84por vértices, 81, 94

coboundary, 33colorable, 84k-coloração, 83coloração

de arestas, 111de vértices, 83, 117mínima, 83, 111total, 115

colorível, 84k-colorível, 84comparabilidade, 15complemento, 9completo, 9componente, 39

ímpar, 107comprimento

de caminho, 23de circuito, 23

conector, 133conexo, 36


conjecturada cobertura dupla por circuitos, 131

conjectura deBerge, 118Chvátal, 124Hadwiger, 119

conjuntoestável, 71independente, 71

conjunto acíclico, 137conjunto completo, 77connected, 36corte, 33cubo, 13k-cubo, 13curva, 52custo de aresta, 138cut, 33cut edge, 33cut vertex, 47cycle, 32, 129

δ(G), 18∆(G), 18d(v), 18d(X), 33∂(X), 33dama, 12DD, 6decomposição

em circuitos, 127degree, 18densidade, 18desigualdade triangular, 142diâmetro, 143diferença simétrica, 34Dirac, 124, 147dist( ), 141distância, 1412-aresta-conexo, 452-conexo, 47dual de mapa plano, 54duro, 115, 124

EG, 9ED, 6EDD, 6

edge, 9edge cover, 109edge-2-connected, 45edge-biconnected, 45Edmonds, 109EE, 6EF, 6EI, 6EID, 6EIF, 6emparelhamento, 93

de peso máximo, 109perfeito, 93

Erdos, 66estável, 71estrela, 16EU, 6Euler, 55, 129euleriano, 129extremos de caminho, 22

face, 53face, 53fechado, 31feedback

edge set, 138vertex set, 139

filho de vértice, 42floresta, 42folha, 42forest, 42fórmula de Euler, 55fronteira de face, 53

G(n), 58Gallai, 66, 109, 119gerador (subgrafo), 27girth, 141grade, 11gráfica (sequência), 65grafo, 9

-linha, 152-conexo, 47acíclico, 42aleatório, 58aresta-biconexo, 45biconexo, 47


bicromático, 67bipartido, 16bipartido completo, 16k-colorível, 84complementar, 9completo, 9cúbico, 18da dama, 12da torre, 12das arestas, 15das faces, 54das palavras, 13de Catlin, 85de comparabilidade, 15de Heawood, 30, 143de intervalos, 15de Kneser, 14de mapa plano, 52de matriz simétrica, 14de Petersen, 13de Turán], 75do bispo, 12do cavalo, 12do rei, 13dos estados, 14dual, 54duro, 115, 124grade, 11lineal, 15perfeito, 88, 118planar, 26, 53plano, 52regular, 18simples, 9vazio, 9vértice-biconexo, 47

grafos disjuntos, 25graph, 9graph design, 65grau, 18

de conjunto, 33de face, 53máximo, 18médio, 19mínimo, 18

greedy, 73, 86

grid, 11guloso, 73

Hadwiger, 119Hajós, 119Haken, 91, 118Hall, 103Hamilton, 121hamiltoniano, 121Heawood, 30, 143heurística

da troca de cores, 114hexágono, 23hidrocarbonetos, 10

incide, 9independence number, 71independent, 71índice de estabilidade, 71indução, 28, 122interseção de grafos, 25intervalos, 15isolado (vértice), 18isomorfismo, 59isomorphism, 59isthmus, 33istmo, 33

Kn, 9Kp,q, 16Kn, 9king, 13Kirkman, 121Kneser, 14knight, 12König, 101, 114Kruskal, 135, 138Kuratowski, 147

L(G), 15laço, 9, 54leaf, 42liga u a v, 22ligado, 36line graph, 15linealbrangente (grafo), 15loop, 54loop, 9


Lovász, 5, 14, 118

m(G), 9menor, 49menor topológico, 49mapa plano, 52matching, 93

maximum weight, 109matriz

de adjacências, 10de incidências, 10

máxima, 134maximal, 71, 93, 137maximal vs máximo, 27, 93máximo, 71, 93minimal vs mínimo, 133minor, 49multiple edges, 54multiple edges, 9

n(G), 9N(v), 18N(X), 34, 99não ordenado, 9neighbor, 9neighborhood, 18NP-completo, 5NP-difícil, 5número cromático, 83número de cores, 83, 111

o(G), 107ω, 77odd component, 107odd hole, 118ordem parcial, 15origem de passeio, 31

pai de vértice, 42palavras, 13par não ordenado, 9parallel edges, 54parallel edges, 9paridade, 69parte de conjunto, 27, 28passeio, 31, 96

fechado, 31pentágono, 23

perfectelimination scheme, 118graph, 118matching, 93

perfeitoemparelhamento, 93grafo, 88, 118

permutação, 22, 42peso de aresta, 109, 135Petersen, 13planar, 26, 53ponta de aresta, 9ponte, 33, 45Prim, 135, 138problema

do caixeiro viajante, 125

quadrado, 23quase todo, 58queen, 12

raiz de árvore, 42random, 14regular, 18rei, 13Robertson, 91, 118roda, 25rook, 13Roy, 119

separa, 35sequência gráfica, 65Seymour, 91, 118, 131slink, 96slither, 96spanning, 27, 133stability number, 71stable, 71star, 16subárvore, 134subcontração, 49subdivisão, 49subfloresta, 137subgrafo, 27

abrangente, 27gerador, 27induzido, 27


maximal, 39próprio, 27

subpartição, 49suporte de mapa plano, 53Szekeres, 131

tabuleiro, 12teorema das

Quatro Cores, 91, 118teorema de

Berge, 96Brooks, 117Dirac, 124Erdos e Gallai, 66Euler, 129Gallai–Roy, 119Hall, 103Havel e Hakimi, 66König, 114König–Egerváry, 101Kuratowski, 147Turán, 75Tutte, 107Tutte–Berge, 108Veblen, 129Vizing, 115Wagner, 146

término de passeio, 31Thomas, 91, 118topological minor, 49torre, 12total coloring, 115tough, 115, 124trail, 32traveling salesman, 125tree, 42triângulo, 23trilha, 32TSP, 125Turán, 75Tutte, 107

união de grafos, 25usa k cores, 83

VG, 9vazio, 9

vertex cover, 81, 94vértice, 9

central, 143de corte, 47interno, 22isolado, 18saturado, 94

vértice-biconexo, 47vértices adjacentes, 9vizinho, 9

Wagner, 146walk, 31, 96wheel, 25

Documents

Exercícios de Teoria dos Grafos - Rede Linux IME-USPdaniloss/antes-2012/Exercicios_Grafos.pdf · Prefácio A teoria dos grafos estuda objetos combinatórios — os grafos — que