Livro Grafos
Livro Grafos
Livro Grafos
Edson Prestes
2020
Dedico este livro à minha famı́lia e amigos.
O importante é o ser e não o vir a ser; um não é o oposto do outro, havendo
o oposto ou a oposição, cessa o ser. Ao findar o esforço para vir-a-ser, surge
a plenitude do ser, que não é estático; não se trata de aceitação; o vir-a-ser
depende do tempo e do espaço. O esforço deve cessar; disso nasce o ser que
transcende os limites da moral e da virtude social, e abala os alicerces da
sociedade. Esta maneira de ser é a própria vida, não mero padrão social.
Lá, onde existe vida, não existe perfeição; a perfeição é uma idéia, uma
palavra; o próprio ato de viver e existir transcende toda forma de
pensamento e surge do aniquilamento da palavra, do modelo, do padrão.
Este livro é resultado das minhas notas de aulas da cadeira de Teoria dos
Grafos e Análise Combinatória que ministro desde 2005 no Instituto de In-
formática na Universidade Federal do Rio Grande do Sul. Ao longo dos anos,
tenho observado a necessidade de um livro nesta área escrito em português
com linguagem acessı́vel. Assim nas minhas horas vagas detive-me a escrever
este livro. Esta primeira versão demorou vários anos para ser finalizada de-
vido aos meus inúmeros compromissos dentro e fora do Paı́s. Ela contou com
o apoio dos meus alunos Renata Neuland e Gean Stein, à Jéssica Dagostini,
Vinı́cius Lazzari no processo de revisão.
Espero que este livro motive os alunos da graduação em ciência da com-
putação e também de áreas correlatas a se interessarem pela área de teoria
dos grafos. É claro que esta área é muito mais ampla e densa do que o
conteúdo discutido nas páginas seguintes, porém penso neste livro como um
passaporte de entrada para esta área magnı́fica. Além das notas, este livro
foi ancorado em obras magnı́ficas listadas abaixo :
Edson Prestes
1 Fundamentação Teórica 1
1.1 Conceitos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Relação de Vizinhança . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Matrizes de Adjacência e de Incidência . . . . . . . . . . . . . 11
1.4 Passeios e Circuitos . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Grafos Eulerianos e Hamiltonianos . . . . . . . . . . . . . . . 18
1.6 Isomorfismo e Automorfismo . . . . . . . . . . . . . . . . . . . 22
1.7 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1 Associação de Tarefas . . . . . . . . . . . . . . . . . . 26
1.7.2 Robótica . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.7.3 Nichos Ecológicos . . . . . . . . . . . . . . . . . . . . . 27
1.7.4 Rede de Telefonia Móvel . . . . . . . . . . . . . . . . . 28
1.7.5 Reconhecedores de sentenças . . . . . . . . . . . . . . . 29
1.7.6 Redes Neurais Artificiais . . . . . . . . . . . . . . . . . 29
1.8 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Conectividade 51
3.1 Relação de Vizinhança Estendida e Fechamento Transitivo . . 52
3.2 Grafos Conexos e Desconexos . . . . . . . . . . . . . . . . . . 55
3.3 Vértice de Corte . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4 Aresta de Corte . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5 Conectividade em Dı́grafos . . . . . . . . . . . . . . . . . . . . 61
3.6 Cálculo de Componentes . . . . . . . . . . . . . . . . . . . . . 67
3.7 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4 Relacionamentos V-A 73
4.1 Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 Conjunto Independente . . . . . . . . . . . . . . . . . . . . . . 77
4.3 Cobertura de Vértices . . . . . . . . . . . . . . . . . . . . . . 81
4.4 Conjunto Dominante . . . . . . . . . . . . . . . . . . . . . . . 84
4.5 Emparelhamento . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.6 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5 Enumeração 97
5.1 Método de Maghout . . . . . . . . . . . . . . . . . . . . . . . 97
5.2 Enumeração em Grafos . . . . . . . . . . . . . . . . . . . . . . 101
5.2.1 Coberturas de Vértices e Conjuntos Independentes . . 101
5.2.2 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.2.3 Conjuntos dominantes . . . . . . . . . . . . . . . . . . 104
5.2.4 Emparelhamentos . . . . . . . . . . . . . . . . . . . . . 106
5.3 Enumeração em Dı́grafos . . . . . . . . . . . . . . . . . . . . . 111
5.3.1 Coberturas de Vértices e Conjuntos Independentes . . 111
5.3.2 Coberturas de Fonte e Sumidouro . . . . . . . . . . . . 114
5.3.3 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.3.4 Conjuntos Dominantes . . . . . . . . . . . . . . . . . . 116
5.3.5 Emparelhamentos . . . . . . . . . . . . . . . . . . . . . 121
5.4 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6 Árvores 125
6.1 Conceitos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2 Árvores Enraizadas . . . . . . . . . . . . . . . . . . . . . . . . 128
7 Planaridade 147
7.1 Multigrafos Planares . . . . . . . . . . . . . . . . . . . . . . . 147
7.2 Teorema de Euler . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.3 Teorema de Kuratowski . . . . . . . . . . . . . . . . . . . . . 154
7.4 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
8 Coloração 157
8.1 Grafos Colorı́veis . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.2 Grafos Aresta-Colorı́veis . . . . . . . . . . . . . . . . . . . . . 162
8.3 Polinômio Cromático . . . . . . . . . . . . . . . . . . . . . . . 163
8.4 O teorema das quatro cores . . . . . . . . . . . . . . . . . . . 168
8.5 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Fundamentação Teórica
(a) (b)
A Figura 1.2 mostra um (a) grafo simples e um (b) pseudografo, onde as li-
nhas representam as arestas e os cı́rculos escuros representam os vértices. Em
(a), cada aresta une um par de vértices distintos e não existem múltiplas ares-
tas unindo um mesmo par. Logo, cada aresta é representada pelos vértices
os quais incide, por exemplo, a aresta unindo os vértices 1 e 2 é representada
por {1, 2}. Assim, φ({1, 2}) = {1, 2}, i.e., φ({x, y}) = {x, y}, ∀{x, y} ∈ A.
Em (b) existem múltiplas arestas unido os vértices 1 e 2, e os vértices 3 e 4.
Para distingui-las, as arestas são rotuladas com as letras de a a h. Observe
que φ(f ) = φ(g) = φ(h) = {3, 4} e φ(a) = φ(b) = {1, 2}, porém f 6= g 6= h
2
Alguns autores usam |G| e ||G|| para indicar a ordem e o tamanho de G, respectiva-
mente
(a) (b)
Figura 1.3: Exemplo de (a) pseudografo e seu (b) grafo simples subjacente.
precisamos ter uma forma de indicar esta restrição no grafo. Isto é feito
determinando uma direção para cada aresta.
A inserção desta informação faz com que o grafo se torne orientado. As-
sociando pares ordenados de vértices às arestas do grafo, teremos um grafo
direcionado ou dı́grafo. Cada par ordenado3 (x, y) define um arco com ori-
gem em (ou adjacente em) x e destino em (ou adjacente para) y, ou seja,
(x, y) 6= (y, x). É comum dizermos que o vértice x domina y, e que o vértice
y é dominado por x. De forma similar ao exposto anteriormente para grafos, Dominância
um dı́grafo pode conter laços e múltiplos arcos entre um mesmo par ordenado
de vértices. Quando um dı́grafo não possui laços tão pouco múltiplos arcos
entre um mesmo par ordenado de vértices, ele é chamado dı́grafo simples ou
grafo direcionado simples. Quando um dı́grafo possui múltiplos arcos de um Dı́grafo Simples
vértice a outro, então ele é chamado de multigrafo direcionado. Quando k Multigrafo Dire-
arcos têm origem no vértice x e destino no vértice y, então dizemos que o cionado
arco (x, y) tem multiplicidade igual a k, i.e., µ(x, y) = k. Em pseudografos e
multigrafos, µ(x, y) = µ(y, x), o que não é garantido nos casos de multigrafos
direcionados. Quando o dı́grafo não possui laços, múltiplas arestas entre um
mesmo par ordenado de vértices, nem pares simétricos de arcos então ele é
chamado de grafo orientado. Quando laços são permitidos laços, o dı́grafo é Grafo Orientado
chamado de pseudografo direcionado. Pseudografo Di-
recionado
Definição 1.3. Um dı́grafo D = (Vd , Ad , φd ) é um conjunto não vazio de
vértices Vd , um conjunto de arcos Ad , e uma função de mapeamento φd :
Ad → Vd × Vd que mapeia cada arco a um par ordenado formado pelos
3
Um par ordenado formado pelos vértices x e y é representado de maneira tradicional
por (x, y), onde, (x, y) 6= (y, x).
(a) (b)
Grafo Subja- De forma similar aos grafos, um dı́grafo possui um grafo subjacente. Ele
cente ao Dı́grafo é obtido substituindo cada arco por uma aresta, i.e., removendo a orientação
de cada arco. Por exemplo, a Figura 1.2(b) mostra o grafo subjacente ao
dı́grafo ilustrado na Figura 1.4(b).
Definição 1.4. Um grafo G1 = (V1 , A1 ) é um subgrafo de G2 = (V2 , A2 ),
denotado por G1 ⊆ G2 se e somente se V1 ⊆ V2 e A1 ⊆ A2 . Neste caso
4
Alguns autores usam |D| e ||D|| para indicar a ordem e o tamanho de D, respectiva-
mente
Figura 1.5: Exemplo de grafo induzido por vértices e por arestas. (a) grafo G,
(b) grafo induzido G[Sv ] por um conjunto de vértices Sv e (c) grafo induzido
G[Sa ] por um conjunto de arestas Sa
Note que
δ(G) ≤ d(v) ≤ ∆(G), ∀v ∈ V.
Na Figura 1.2(a),
d(1) = 2, d(2) = 2, d(3) = 3, d(4) = 1, d(5) = 0, δ(G) = 0 e ∆(G) = 3.
Enquanto que na Figura 1.2(b),
d(1) = 3, d(2) = 5, d(3) = 5, d(4) = 3, δ(G) = 3 e ∆(G) = 5.
5
O grau de um vértice é denotado por d devido a palavra grau ser em inglês chamada
degree.
Em um dı́grafo qualquer, cada vértice v possui um grau de entrada, d− (v), Graus de En-
e um grau de saı́da, d+ (v). O grau de entrada de um vértice v é o definido trada e de Saı́da
pelo número de arcos que possuem como destino v (incluindo o laço) en-
quanto que o grau de saı́da é o número de arcos que possuem como origem v
(incluindo o laço). Um laço em vértice v é contado uma única vez no grau de
entrada de v e uma única vez no grau de saı́da de v. Para dı́grafos simples
(e grafos orientados), podemos usar as funções de vizinhança τ − (v) e τ + (v)
para calcular os graus de saı́da e de entrada de cada vértice. Neste caso, para
qualquer vértice v temos d− (v) = |τ − (v)| e d+ (v) = |τ + (v)|.
De forma similar ao exposto anteriormente, podemos definir para um
dı́grafo D os graus de entrada máximo e mı́nimo, ∆− (D) e δ − (D), respecti-
vamente, e os graus de saı́da máximo e mı́nimo, ∆+ (D) e δ + (D), respectiva-
mente. Na Figura 1.4(a), o dı́grafo tem
v∈Vd v∈Vd
(a) (b)
Teorema 1.4 ([1]). Para n > 1, uma seqüência d de inteiros com n elementos
é uma seqüência gráfica se e somente se d0 é uma seqüência gráfica, onde d0 é
obtido a partir de d removendo seu maior elemento ∆ e subtraindo 1 de seus
1 2 3 4
1 0 2 1 0
2 2 1 1 0
3 1 1 0 3
4 0 0 3 0
a b c d e f g h
1 1 1 1 0 0 0 0 0
2 1 1 0 1 1 0 0 0
3 0 0 1 1 0 1 1 1
4 0 0 0 0 0 1 1 1
1 2 3 4
1 0 2 0 0
2 0 1 1 0
3 1 0 0 2
4 0 0 1 0
Por sua vez, na matriz de incidência B = [bi,j ] cada entrada bij relaciona
o vértice i à aresta j assumindo os valores
−1 , se j tem origem em i.
bi,j = 0 , se j não é incidente em i
1 , se j tem destino em i.
a b c d e f g h
1 -1 -1 1 0 0 0 0 0
2 1 1 0 -1 1 0 0 0
3 0 0 -1 1 0 1 -1 -1
4 0 0 0 0 0 -1 1 1
Passeio Direci- Se os vértices de origem e destino forem o mesmo, então o passeio direci-
onado Fechado, onado é chamado de passeio direcionado fechado; a trilha é chamada de
Circuito Dire-
cionado, Ciclo
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
Direcionado
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.4 Passeios e Circuitos 15
aresta ou arco que une dois vértices em um ciclo, mas que não pertence ao
Corda ciclo é chamada corda.
Entre um par de vértices v e w em um grafo(ou dı́grafo) G = (V, A),
podem existir inúmeros caminhos. Cada caminho representa um subgrafo(ou
subdı́grafo) de G, ou seja, considerando Pv,w = (Vp , Ap ) um caminho entre
os vértices v e w, temos Pv,w ⊆ G. O comprimento de Pv,w , denotado aqui
por |Pv,w | é igual ao seu número de arestas, i.e., |Pv,w | = |Ap |. Se não existe
caminho entre v e w, então |Pv,w | = ∞. Usando esta notação, a distância
entre v e w é igual a
d(v, w) = min |Pv,w |
Pv,w ⊆G
A partir daı́, definimos um vértice v como sendo central quando seu valor
Centro de um de excentricidade é igual ao raio do grafo, i.e., e(v) = raio(G). Por conse-
Grafo guinte, o centro de um grafo G, denotado por, C(G), é um subgrafo induzido
pelos seus vértices centrais, i.e.,
(a) (b)
(Verifique!). Se pelo menos uma das aresta de G1 não possuir uma corres-
pondente em G2 então a função escolhida não define o isomorfismo entre G1
e G2 . Notem que existem inúmeros mapeamentos possı́veis. Outro mape-
amento possı́vel que garante o isomorfismo entre G1 e G2 é a partir desta
tabela alterar as linhas 3 e 4, associando o vértice 2 ao vértice f e o vértice
3 ao vértice a.
(a) (b)
Assim entre os requisitos básicos para que dois grafos sejam isomorfos
é que eles possuam a mesma quantidade de vértices e a mesma quantidade
de arestas, i.e., |V1 | = |V2 | e |A1 | = |A2 |. Porém verificar se dois grafos
são ou não isomorfos nem sempre é uma tarefa trivial. Suspeita-se que este
problema seja NP-Completo.
V1 V2
0 e
1 b
2 a
3 f
4 c
5 d
(a) (b)
1 2 3 4
1 0 1 0 0
2 1 0 1 0
3 0 1 0 1
4 0 0 1 0
4 3 2 1
4 0 1 0 0
3 1 0 1 0
2 0 1 0 1
1 0 0 1 0
1.7 Aplicações
Esta seção apresenta alguns exemplos de aplicações do mundo real que en-
volvem Grafos.
4 2 3 1
4 0 1 0 0
2 1 0 1 0
3 0 1 0 1
1 0 0 1 0
1.7.2 Robótica
Vários problemas da área de robótica estão associados às tarefas de navegação
de robôs em ambientes do tipo escritório. Neste tipo de tarefa, o robô pos-
sui um mapa do ambiente e deve planejar um caminho que o leve de uma
posição a outra evitando colisões com obstáculos. Entre os diversos tipos de
mapas, existe o mapa topológico, que consiste em uma representação do am-
biente utilizando grafos. A Figura 1.16(a) mostra um ambiente e seu grafo
subjacente. Os vértices estão associados às grandes regiões do ambiente e as
arestas indicam como navegar entre estas regiões. Neste exemplo, se o robô
precisar ir da sala A até a sala G, ele pode seguir por vários caminhos, que
podem ser visualizados através dos vértices e arestas do grafo associado. A
Figura 1.16(b) mostra um caminho possı́vel através de arestas mais grossas.
(a) (b)
1.8 Exercı́cios
Exercı́cio 1.1. Mostre usando prova por indução que a soma total dos graus
de todos os vértices de um grafo é sempre par
Exercı́cio 1.2. Mostre que para qualquer grafo, o número de vértices com
grau ı́mpar é par.
Exercı́cio 1.3. Verifique se a seqüência de graus 3, 3, 3, 3, 3, 2, 2, 1 é gráfica.
Se for desenhe o grafo simples correspondente.
Exercı́cio 1.4. Dado um grafo simples G = (V, A), com |V | = n qual é o
significado de nj=1 ai,j para uma dada linha i da matriz de adjacência de G?
P
Exercı́cio 1.11. Mostre que todo dı́grafo acı́clico(sem ciclos) possui vértice
fonte e um vértice sumidouro.
Exercı́cio 1.12. Mostre que um grafo simples G = (V, A) com δ(G) > 0 e
|A| < |V | possui pelo menos dois vértices de grau 1.
Exercı́cio 1.13. Mostre que todo grafo com dois ou mais vértices tem pelo
menos dois vértices de mesmo grau.
(a)
(b)
Grafo Trivial
Um grafo trivial é um grafo com 1 ou nenhum vértice. Quando o grafo não
possui vértices, ele é chamado de grafo vazio. Este tipo de grafo é tipicamente Grafo Vazio
usado como passo inicial em provas por indução e como contra exemplo em
alguns tipos de problemas.
Uma definição similar pode ser aplicada aos dı́grafos. Um dı́grafo é com-
Dı́grafo Com- pleto se para qualquer par de vértices x e y, como x 6= y existem os dois
pleto arcos simétricos (x, y) e (y, x). Vários autores usam a mesma notação de
grafo completo para dı́grafo completo, ou seja, Kn para um dı́grafo ou grafo
completo com n vértices. Neste livro adotaremos esta prática e enfatizaremos
Dı́grafo Semi- se Kn refere-se a um dı́grafo ou a grafo. Um dı́grafo é semicompleto se para
completo cada par de vértices distintos x e y, existe ou o arco (x, y) ou o arco (y, x)
ou ambos.
Grafo Regular
Um grafo G = (V, A) é regular de ordem r se todos os seus vértices
tiverem o grau r, ou seja, ∀v ∈ V,
Este tipo de grafo também é chamado de grafo r-regular. Note que todo
grafo completo Kn é um grafo (n − 1)-regular.
Grafo caminho
Um grafo G = (V, A) é um grafo caminho, Pn , composto por n vértices
se ele corresponder a exatamente um caminho de comprimento n − 1. Neste
caso, os vértices inicial e final do caminho possuem grau igual a 1, enquanto
que os demais possuem grau igual a 2.
Grafo Ciclo
Um grafo ciclo Cn , com n ≥ 3, é composto por n vértices e n arestas que
juntos formam um ciclo de tamanho n. Todos os vértices de Cn possuem
grau igual a 2, logo, ele é um grafo 2-regular. A Figura 2.1(b) mostra um
Grafo Roda
Um grafo roda Wn , com n ≥ 3, é igual ao grafo Cn adicionado de mais
um vértice, o qual é adjacente a todos os demais. Um grafo Wn possui n + 1
vértices e 2n arestas, onde o vértice adicionado ao Cn possui grau igual a n
e os demais vértices grau igual a 3. A Figura 2.3 mostra os grafos (a) W4 e
(b) W5 .
(a) (b)
Grafo Estrela
(a) (b)
Grafo k-cubo
Um grafo k-cubo, ou hipercubo k-dimensional, denotado por Qk , é um
grafo cujos vértices são formados por seqüências binárias de tamanho k. Dois
vértices são adjacentes neste grafo se suas seqüências correspondentes diferi-
rem em apenas uma posição. Além disso, ele é um grafo regular de grau k.
A Figura 2.5 mostra (a) um grafo Q1 (b) um grafo Q2 e (c) um grafo Q3 .
2.2.1 União
Dados dois grafos (ou dı́grafos) G1 e G2 , definimos a operação de união
por G1 ∪ G2 . O grafo resultante G = (V1 ∪ V2 , A, φ), tem seu conjunto de
vértices oriundo da união dos conjuntos de vértices dos grafos originais. Por
outro lado, o conjunto de arestas A inicialmente é igual a A1 , i.e., A = A1 e
φ(e) = φ1 (e) ∀e ∈ A1 . Cada aresta e0 ∈ A2 deve analisada cuidadosamente
antes de ser inserida em A, pois uma aresta rotulada e0 pode pertencer tanto
a A2 quanto a A1 com φ1 (e) pode ser diferente de φ2 (e). Sendo assim, para
cada e0 ∈ A2 , temos as seguintes situações
• se e0 ∈
/ A, adicionamos e0 em A e assumimos φ(e0 ) = φ2 (e0 ).
2.2.2 Junção
2.2.3 Intersecção
2.2.4 Produto
O produto de dois grafos, G1 e G2 , é denotado por G1 × G2 e gera um grafo
G = G1 × G2 , onde V = V1 × V2 é o conjunto de todos os pares formados
pelos vértices de V1 e V2 e A é o conjunto de arestas geradas da seguinte
maneira. Considere pi = (ui , wi ) e pj = (uj , wj ) dois vértices do conjunto V ,
i.e., pi , pj ∈ V , onde ui , uj ∈ V1 e wi , wj ∈ V2 . Eles são adjacentes se ui = uj
e (wi , wj ) ∈ A2 ou wi = wj e (ui , uj ) ∈ A1 . O grafo G resultante possui
|V | = |V1 ||V2 | vértices e |A| = |V1 ||A2 | + |V2 ||A1 | arestas.
A Figura 2.9 mostra (c) o grafo resultante do produto dos grafos (a) e
(b). Note que os vértices em (c) são os pares ordenados dos vértices dos
grafos (a) e (b), enquanto que as arestas foram geradas a partir da análise
dos componentes dos pares associados às suas extremidades. Por exemplo,
a aresta {(u1 , w1 ), (u1 , w2 )} existe pois os primeiros componentes dos pares
(u1 , w1 ) e (u1 , w2 ) são iguais e existe aresta entre w1 e w2 no grafo mostrado
em (b).
2.2.5 Complemento
O complemento de um grafo G = (V, A), denotado por Ḡ = (V, A1 ) é um
grafo cujo conjunto de vértices é o mesmo de G, e com um conjunto de arestas
definido da seguinte maneira A1 = {{u, v} : ({u, v} ∈ P(V ) − A) ∧ (u 6= v)},
ou seja, o conjunto A1 é formado por todas as arestas que correspondem aos
pares não ordenados que não pertencem ao conjunto de arestas de G e não
correspondem a laços. O complemento de um grafo Kn é um grafo com n
vértices totalmente desconexo, e o complemento de um grafo desconexo de n
(a) (b)
(a) (b)
Figura 2.11: Grafo autocomplementar. (a) grafo exemplo e (b) seu comple-
mento.
2.2.6 Remoção
A operação de remoção aplicada a um grafo G = (V, A) retira ou um con-
junto de arestas ou um conjunto de vértices e as arestas incidentes neste
conjunto. Para um grafo G, a remoção de um vértice v, representada por
G − v, causa a remoção tanto de v quanto das arestas incidentes a v. En-
quanto que a operação G − e, com e = {u, v}, leva à retirada da aresta
{u, v}.
Seja Sv ⊆ V , então G1 = G − Sv é o grafo resultante da retirada de todos
os vértices v ∈ Sv e de suas arestas incidentes. Logo, G1 = (V1 , A1 ) onde
V1 = V − Sv e A1 = {(u, w) ∈ A : u, w ∈ V1 }. Observe que G1 = G[V − Sv ],
ou seja, é G1 é o subgrafo de G induzido por V − Sv .
Seja Sa ⊆ A, então G2 = G − Sa é o grafo resultante da retirada das
arestas a ∈ Sa . Logo, G2 = (V2 , A2 ) onde V2 = V e A2 = A − Sa , i.e.,
G2 = G[A − Sa ] é o subgrafo de G induzido por Sa . A Figura 2.12 ilustra
(a) um grafo G e os grafos (b) G − Sv e (c) G − Sa , onde Sv = {1, 2}
e Sa = {{1, 2}, {1, 4}, {1, 5}, {4, 5}, {2, 5}}. Note que os grafos (b) e (c)
correspondem aos grafos induzidos G[V − Sv ] e G[A − Sa ], respectivamente.
2.2.7 Contração
Uma operação de contração, também chamada de arco-contração, em um
grafo G afeta uma aresta a, em particular, a transformando em um novo
vértice v. Esta operação é representada por G/a e consiste na remoção da
aresta a = {u, w} e de seus vértices u e w e subsequente inserção de um novo
divisão de a, remove a aresta a, i.e., G − {u, w}, e cria duas novas arestas
{u, v} e {v, w}. produzindo um novo grafo G0 = (V 0 , A0 ). Este grafo possui
V 0 = V ∪ {v} e A0 = A − {u, w} + A1 , com A1 = {(v, u), (v, w)}. Logo,
dizemos que G0 é uma subdivisão de G.
As Figuras 2.14(a) e (b) ilustram os resultados das operações de subdi-
visão e de supressão, respectivamente. (a) é subdivisão de (b) obtida a partir
da subdivisão da aresta {4, 3} de (b). Enquanto que (b) é um grafo reduzido
de (a), obtido a partir da supressão do vértice 7.
2.2.9 Decomposição
A operação de decomposição de um grafo G gera um conjunto de subgrafos
G1 , G2 , . . . tal que cada aresta de G aparece exatamente uma única vez em um
único subgrafo, ou seja, considerando que o conjunto de arestas do grafo Gi
é Ai , temos Ai ∩ Aj = ∅, ∀ i 6= j. Os subgrafos gerados podem compartilhar
vértices, entretanto não podem compartilhar arestas. Em algumas áreas, a
decomposição é uma ferramenta útil, pois é possı́vel isolar cada parte do
grafo, estudá-las separamente e em seguida combinar os resultados obtidos.
O grafo 3-cubo, Q3 , mostrado na Figura 2.15(a) é decomposto em 4
caminhos P4 ilustrados em (b). Estes caminhos são mostrados através de
arestas grossas e finas. Considerando apenas os vértices temos os caminhos
(1, 2, 6, 5), (3, 1, 5, 7), (2, 4, 8, 6) e (8, 7, 3, 4).
(a) (b)
(a) (b)
2.3 Exercı́cios
Exercı́cio 2.1. Determine o número de arcos de um dı́grafo completo Kn .
(a) (b)
(a) (b)
Conectividade
liga dois servidores. Identificar o(s) computador(es) que gera(m) esta des-
conexão é extremamente importante, pois é possı́vel tomar uma providência
de forma a aumentar a tolerância a este tipo de falha. No caso de um robô
móvel, este poderá ficar parado economizando energia ou retornar ao seu
ponto de partida. Este capı́tulo apresenta os aspectos teóricos subjacentes
aos questionamentos apresentados.
(a) (b)
Γ− (V1 ) = τ − (1) = ∅
Γ− (V2 ) = τ − (2) ∪ τ − (3) = {5} ∪ {1, 4} = {1, 4, 5}
Γ− (V3 ) = τ − (3) ∪ τ − (4) = {1, 4} ∪ {6} = {1, 4, 6}
Γ̂+ (2) = Γ̂+ (3) = Γ̂+ (4) = Γ̂+ (5) = Γ̂+ (6) = {2, 3, 4, 5, 6}
Como todos os vértices com exceção do vértice 1 estão dentro de um ciclo
direcionado, um pode atingir o outro dentro do ciclo através de um caminho
Γ̂− (2) = Γ̂− (3) = Γ̂− (4) = Γ̂− (5) = Γ̂− (6) = {1, 2, 3, 4, 5, 6}
De forma similar ao apresentado anteriormente, com exceção do vértice 1,
todos os vértices são atingı́veis a partir dos demais vértices do dı́grafo. Em
um dı́grafo se v é um vértice fonte então Γ̂− (v) = {v}, enquanto que se v for
um vértice sumidouro, temos Γ̂+ (v) = {v}.
(a) (b)
de forma que G[V1 ], G[V2 ],. . . G[Vn ] sejam subgrafos conexos maximais de G.
Cada G[Vi ] é um componente conexo e Ω(G) = n é o número de componentes
conexos de G. Se G é um grafo conexo então Ω(G) = 1, caso contrário se
G é desconexo, então Ω(G) > 1. Se G é um grafo vazio, então Ω(G) = 0.
Usando o exemplo anterior, temos Ω(G1 ) = 1 e Ω(G2 ) = 2.
(a) (b)
Teorema 3.4. Para uma aresta a de um grafo conexo G = (V, A), as se-
guintes afirmações são equivalentes:
1. a aresta a é uma aresta de corte de G.
2. a aresta a não está contida nos ciclos de G.
3. existem vértices w e u distintos tal que todo caminho entre w e u passa
por a.
4. existe um particionamento do conjunto de vértices V em dois subcon-
juntos V1 e V2 tal que qualquer caminho entre u ∈ V1 e w ∈ V2 passa
obrigatoriamente pela aresta a.
De forma similar ao exposto para vértices de corte, alguns grafos não
possuem aresta de corte, porém possuem um subconjunto de aresta cuja
remoção resulta ou em um grafo desconexo ou em um grafo trivial. Para um
Conjunto Desco- grafo G, este conjunto é chamado de conjunto desconector de G. Portanto,
nector um grafo é chamado k-aresta conexo se o tamanho do menor conjunto des-
Conectividade conector é k. Neste caso, dizemos que a conectividade de aresta do grafo,
de Aresta representada por λ(G), é igual a k, i.e., λ(G) = k. Por definição λ(G) = 0,
se o grafo for trivial ou desconexo e λ(G) = 1 se o grafo for conexo e possuir
Conjunto de uma aresta de corte. Os conjuntos desconectores minimais são chamados de
Corte de Ares- conjunto de corte de arestas, i.e., conjuntos desconectores que não possuem
tas um subconjunto próprio que é desconector.
O grafo G ilustrado na Figura 3.3(a) possui vários conjuntos desconecto-
res, entre eles, temos, D1 = {{2, 4}, {3, 4}, {2, 3}}, D2 = {{2, 4}, {3, 4}, {4, 5}}
e D3 = {{5, 6}}. Apenas o conjunto D3 é um conjunto de corte de arestas,
pois tanto D1 quanto D2 possuem subconjuntos próprios que são desconecto-
res. Por exemplo, D1 possui o subconjunto {{2, 4}, {3, 4}} que é desconector
e também um conjunto de corte de arestas de tamanho 2. D2 possui dois
subconjuntos {{2, 4}, {3, 4}} e {{4, 5}} que são desconectores. O primeiro
tem tamanho igual a 2 enquanto o segundo tem tamanho igual a 1. Este
último é composto por uma aresta de corte. A conectividade de aresta deste
grafo é λ(G) = 1, pois o menor conjunto de corte de arestas tem tamanho
igual a 1. Logo, este grafo é um grafo 1-aresta conexo.
Conectividade Podemos definir a conectividade de aresta entre dois vértices u e v, deno-
de Aresta entre tada por λ(u, v), como o menor número de arestas cuja remoção separa u de
Vértices v, i.e., que faz com que u não seja atingido por v (vice-versa). De forma simi-
lar ao apresentado para vértices, a conectividade de aresta está intimamente
Portanto para um grafo G = (V, A) não trivial, temos λ(G) = min λ(u, v)
para qualquer par de vértices distintos u, v ∈ V . A relação entre a conecti-
vidade de vértice, a conectividade de arestas e o menor grau de um grafo G
é dada pelo seguinte Teorema.
• fracamente conexo ou fraco se seu grafo subjacente é conexo, ou seja, Dı́grafo Fraca-
para cada par de vértices existe um semi-caminho. Note que todo mente Conexo
dı́grafo conexo é fracamente conexo.
(a) (b)
(a) (b)
(c) (d)
(a) (b)
O resultado da interseção Γ̂+ (v1 ) ∩ Γ̂− (v1 ) = V2 = {2, 8, 9} dá origem a D[V2 ]
que é segundo componente forte de D. Selecionando v3 do conjunto V −
(V1 ∪ V2 ) = {1, 4, 5, 7}, por exemplo v3 = 5, temos Γ̂+ (v3 ) = {2, 3, 5, 6, 8, 9},
Γ̂− (v3 ) = {5} e V3 = {5}, onde D[V3 ] é o terceiro componente forte. Repe-
tindo o processo anterior, selecionamos v4 de V − (V1 ∪ V2 ∪ V3 ) = {1, 4, 7},
por exemplo, v4 = 1, obtendo Γ̂+ (v4 ) = {1, 4, 7} e Γ̂− (v4 ) = {1, 4, 5, 7}. Logo
temos V4 = {1, 4, 7} e o quarto componente forte D[V4 ]. Como
V1 ∪ V2 ∪ V3 ∪ V4 = V,
o processo pára e temos D[V1 ], D[V2 ], D[V3 ], D[V4 ] como os componentes for-
tes de D.
A aplicação do método de Malgrange em um grafo é sutilmente diferente
da utilizada em dı́grafos. Se analisarmos atentamente uma aresta {a, b} em
um grafo, ela tem a mesma funcionalidade que a presença de ambos os arcos
(a, b) e (b, a) em um dı́grafo. Portanto, em grafos é usada apenas a função
de fechamento transitivo Γ̂ ao invés das funções Γ̂+ e Γ̂− usadas em dı́grafos.
Considere um grafo G = (V, A), realizamos os seguintes passos:
• selecionamos um vértice v1 ∈ V e calculamos a função de fechamento
transitivo Γ̂(v1 ). O conjunto de vértices resultante V1 dá origem ao
primeiro componente conexo G[V1 ].
• se V1 = V então o grafo é conexo tendo como único componente conexo,
o próprio grafo. Caso contrário, selecionamos um vértice v2 ∈ V − V1
e repetimos o processo. Calculando Γ̂(v2 ) que dá origem ao segundo
conjunto de vértices V2 e consequentemente ao segundo componente
G[V2 ].
• na i-ésima iteração, selecionamos
i−1
[
vi ∈ V − Vj
j=1
3.7 Exercı́cios
Exercı́cio 3.1. Mostre que se G = (V, A) é um grafo simples e δ(G) >
d|V |/2e − 1 então G é conexo.
Exercı́cio 3.17. Mostre que todo grafo simples G = (V, A) com |V | > |A|
implica Ω(G) ≥ |V | − |A|.
Exercı́cio 3.18. Mostre que um grafo simples G = (V, A) tem uma quanti-
dade de arestas que satisfaz a seguinte desigualdade
1
|V | − Ω(G) ≤ |A| ≤ (|V | − Ω(G))(|V | − Ω(G) + 1)
2
Exercı́cio 3.19. Utilize o método de Malgrange para calcular os componentes
fortes do dı́grafo ilustrado na Figura 3.11 e encontre o digrafo condensado
correspondente.
Relacionamentos V-A
4.1 Clique
O primeiro relacionamento V-A diz respeito ao relacionamento vértice-vértice
intitulado clique. Um clique em um grafo G é um subgrafo completo de
G. O fato de um clique ser um subgrafo completo implica que todos os
vértices no clique são adjacentes entre si. Um clique é maximal quando
ele não é um subgrafo próprio de outro subgrafo completo. O estudo de
cliques foca principalmente em cliques que são maximais e máximos, portanto
vários autores quando fazem referência a cliques estão considerando cliques
maximais. Adotaremos esta mesma referência neste livro. Quando um clique
não for maximal deixaremos explı́cita esta informação. Um subgrafo é um
clique em um pseudografo(ou multigrafo) se e somente se ele for um clique
no grafo subjacente ao pseudografo(ou multigrafo). Em um dı́grafo(simples
A Figura 4.1 mostra (a) um grafo e seus (b) quatro cliques formados
pelos seguintes conjuntos de vértices {1, 5}, {5, 6}, {1, 2, 3} e {2, 3, 4, 6}, e
destacados usando linhas de diferentes espessuras e formatos. Observe que
uma aresta é um subgrafo completo, e em diversos casos ela é clique não
maximal. Este é o motivo para que a aresta {1, 5} seja um clique maximal
e a {2, 3} não seja. Note que {2, 3} está contida propriamente no subgrafo
completo formado pelos vértices {1, 2, 3}, enquanto que {1, 5} não está con-
tida em nenhum subgrafo completo. Outro ponto importante é que cliques
podem compartilhar tanto arestas quanto vértices. Este é o caso dos cliques
formados pelos vértices {1, 2, 3} e {2, 3, 4, 6} que compartilham os vértices 2
e 3 e aresta {2, 3}.
(a)
(b)
(a)
(b)
(a)
(b)
(a) (b)
(a) (b)
Figura 4.5: Exemplos de (a) grafo 3-partido completo e (b) grafo biclique.
que associar pessoas e tarefas de forma que cada tarefa seja realizada e cada
pessoa esteja vinculada a uma dada tarefa. Este problema é analisado uti-
lizando grafos bipartidos, onde um conjunto de vértices está associado às
pessoas enquanto que o outro conjunto está associado às tarefas. Existem
arestas apenas entre vértices de diferentes conjuntos, já que o emparelha-
mento deve ser constituı́do por elementos de conjuntos diferentes.
Quando um grafo bipartido possui aresta entre qualquer par de vértices
Grafo Bipartido de conjuntos distintos ele é chamado de grafo bipartido completo ou biclique,
Completo sendo denotado por Kr,s , onde r e s são os tamanhos dos dois particiona-
Biclique mentos. O termo biclique é curioso e não é facilmente identificado olhando
diretamente para o grafo, porém calculando K̄r,s , observaremos que os dois
conjuntos independentes serão ambos cliques. As Figuras 4.5(a) e (b) ilus-
tram um grafo 3-partido completo K3,3,3 e um biclique K3,3 respectivamente.
Em ambos os casos, temos um particionamento do conjunto de vértices, onde
cada partição é um conjunto independente.
O seguinte Teorema permite verificar rapidamente se um grafo é ou não
bipartido.
Teorema 4.1. Um grafo G é bipartido se e somente se ele não possui ciclos
de comprimento ı́mpar.
Dı́grafo A definição de dı́grafo k-partido é similar ao exposto anteriormente para
k-partido grafos, com a diferença que estamos lidando com arcos ao invés de arestas.
Portanto, a origem e destino de cada arco devem situar-se em partições dis-
tintas. A relação entre grafos e dı́grafos k-partidos é a seguinte. Um dı́grafo
D é k-partido se e somente se seu grafo simples subjacente G é k-partido. Um
(a) (b)
Figura 4.6: Exemplos de (a) dı́grafo 3-partido e (b) dı́grafo 3-partido com-
pleto.
suas extremidades. Dado um grafo G = (V, A), sabemos que V cobre todas
as arestas no conjunto A, porém o que é de interesse prático é saber o menor
número de vértices que conseguem cobrir todas as arestas.
Cobertura Mini- Uma cobertura de vértices de um grafo G é um subconjunto S dos vértices
mal de G, S ⊆ V , que cobrem todas as arestas de G, i.e., todas as arestas são inci-
dentes a pelo menos um vértice de S. De forma similar, ao apresentado ante-
Cobertura riormente, buscamos as coberturas minimais de vértices, ou seja, coberturas
Mı́nima de vértices que não possuem subconjunto próprio que seja uma cobertura
de vértices. A menor cobertura de vértices é chamada cobertura mı́nima de
Número de vértices e sua cardinalidade define o número de cobertura de vértices, β(G).
Cobertura de O relacionamento entre cobertura de vértices e conjunto independente
Vértices é direta. Considere o conjunto independente maximal I ⊆ V . Todos os
vértices em v ∈ V − I são adjacentes a pelo menos um vértice em I, pois
se existe um vértice v que não é adjacente a outro em I, então o conjunto I
não é maximal. Portanto podemos pensar que cada aresta de G possui uma
extremidade em V − I e outra em I. Porém algumas arestas são incidentes a
vértices apenas do conjunto V − I. Logo, os vértices em I não cobrem todas
as arestas de G, porém os vértices em V − I cobrem. Este fato dá origem ao
seguinte Teorema.
β(G) = |V | − α(G)
para um grafo, porém todos os cálculos são realizados utilizando seu grafo
subjacente. Notem que nesta definição a orientação dos arcos está sendo
totalmente desconsiderada, pois o que importa é saber a menor quantidade de
vértices que cobrem todos os arcos. Em geral, esta definição de cobertura de
vértices, para dı́grafos tem pouca importância prática, já que caracterı́sticas
importantes sobre dı́grafos estão sendo desconsideradas.
Para contornar este problema, Ferro e Ferrarello [10] definem os conceitos
Cobertura de cobertura de fonte e cobertura de sumidouro. Dado um digrafo D = (V, A),
Fonte uma cobertura de fonte para D é um conjunto de vértices S ⊆ V , tal que cada
Cobertura de arco em D parte de algum vértice em S, i.e., para cada vértice v ∈ S existe
Sumidouro pelo menos um arco a = (v, u) ∈ A. De forma análoga, uma cobertura de
sumidouro para D é um conjunto de vértices S ⊆ V , tal que para cada u ∈ S
existe pelo menos um arco a = (v, u) ∈ A. Como buscamos sempre conjuntos
mı́nimais, temos que considerar a menor cobertura de fonte(ou de sumidouro)
que não está contida propriamente em outra cobertura de fonte(ou de sumi-
douro). A partir daı́ definimos para um dı́grafo D, o número de cobertura de
Número de Co- fonte, β + (D) e o número de número de cobertura de sumidouro, β − (D). O
bertura de Fonte primeiro está associado ao tamanho da cobertura mı́nima de fonte, ou seja,
Número de Co- à menor cobertura de fonte, enquanto que o segundo está associado ao ta-
bertura de Su- manho da cobertura mı́nima de sumidouro. Considerando S e S 0 coberturas
midouro de fonte e sumidouro respectivamente para um dı́grafo D, se S ∩ S 0 = ∅,
Dı́grafo Bipar- com S 6= ∅ e S 0 6= ∅, então D é um dı́grafo bipartido direcionado, conforme
tido Direcionado discutido na Seção 4.2.
Problemas de cobertura de vértices, fonte e sumidouro em dı́grafos, resi-
dem em problemas de contagem. Por exemplo, a partir de um dı́grafo quantos
ciclos direcionados de um dado comprimento são necessários para cobrir to-
dos os vértices[11] ou a quantidade de maneiras que i caminhos direcionados
podem cobrir todos os vértices do dı́grafo[12].
Um problema similar ao de cobertura de vértices, independente se é em
grafos ou não, é ao invés de focar nas arestas/arcos para serem cobertos
focar nos vértices. Isto dá origem ao conceito de conjunto dominante que
será apresentado na próxima seção.
Como é possı́vel observar neste exemplo, todos os vértices que não partici-
pam do conjunto dominante são dominados por pelo menos um vértice deste
conjunto. Por exemplo, considerando o conjunto dominante S = {e, c, i},
cada vértice em V − S = {a, b, d, f, g, h, j} possui um vizinho em S. Como
o conjunto dominante foca nos vértices, podem existir arestas descobertas,
(a) (b)
4.5 Emparelhamento
Outro relacionamento V-A importante é o emparelhamento1 , também cha-
Acoplamento mado de acoplamento ou casamento. Ele é um relacionamento aresta-aresta
Casamento 1
Emparelhamento é a tradução do inglês da palavra Matching.
(a) (b)
(a) (b)
destes problemas prova que ambos são ótimos para a instância analisada.
Neste caso, os problemas tratados são o de maximização, associado ao empa-
relhamento, e o de minimização, associado à cobertura de vértices. Portanto,
se dado um grafo obtivermos como resultado o mesmo valor para ambos os
problemas, então o que temos é um resultado ótimo. As Figuras 4.12(a) e
(b) mostram a aplicação deste Teorema. Observe que o tamanho do empa-
relhamento máximo é igual ao de cobertura mı́nima para ambos os grafos.
Logo, os resultados são ótimos.
Isto nos leva à relação min-max definida pelo Teorema 4.6, chamado
König-Egervary.
(a) (b)
4.6 Exercı́cios
Exercı́cio 4.1. Mostre que um grafo completo Kn pode ser expresso como a
união de k grafos bipartidos sse n ≤ 2k
Exercı́cio 4.2. Mostre que o grafo de Petersen não é um grafo bipartido, e
determine seu número de independência e seu número de clique.
Exercı́cio 4.3. Mostre que qualquer grafo k-cubo é um grafo bipartido.
|V |
Exercı́cio 4.4. Mostre que α(G) ≥ ∆(G)+1
para qualquer grafo G.
Exercı́cio 4.5. Mostre que qualquer árvore T tem no máximo um empare-
lhamento que é perfeito.
Exercı́cio 4.6. Encontre a menor árvore onde o número de dominância e o
número de cobertura de vértices seja diferente.
Exercı́cio 4.7. Determine o número de dominância de um grafo Cn
Exercı́cio 4.8. Prove que se o diamêtro de um grafo G é no mı́nimo igual a
3, então o número de dominância do complemento de G será menor ou igual
a 2.
Enumeração
Neste capı́tulo apresentamos o método de Maghout que é utilizado para cal- Método
cular os relacionamentos V-A discutidos no capı́tulo anterior. Este método de Maghout
usa as leis da álgebra booleana para encontrar os conjuntos minimais e ma-
ximais do problema de interesse o qual pode ter sido modelado usando tanto
grafos quanto dı́grafos. O método explora as inter-relações existentes entre
os relacionamentos V-A para a obtenção do resultado desejado. Por exemplo,
sabemos que um conjunto independente maximal em um grafo G é um clique
em Ḡ. Portanto, o mesmo método pode ser utilizado tanto para enumerar
os cliques maximais quanto os conjuntos independentes de um grafo G. O
que difere é o grafo fornecido como entrada para o método que pode ser o
próprio G ou Ḡ.
calculamos ^
(v̇i + v̇j ) (5.1)
(vi ,vj )∈A
onde rj
s
X X
Ṡ = ṡi e Ṙj = ṙj,l
i=1 l=1
In = {v ∈ V | v̇ ∈
/ Pn }
(A+B)(B+D)(B+C)⇒ distributividade
(AB+AD+BB+BD)(B+C)⇒ idempotência
(AB+B+BD+AD)(B+C)⇒ absorção
(B+AD)(B+C)⇒ distributividade
(BB+BC+ABD+ACD)⇒ idempotência
(B+BC+ABD+ACD)⇒ absorção
(B+ACD)
(B+ACD)(E+AD)(D+C)⇒ distributividade
(BE+ABD+ACDE+ACD)(D+C)⇒ absorção
(BE+ABD+ACD)(D+C)⇒ distributividade
(BDE+ABDD+ACDD+BCE+ABCD+ACCD)⇒ idempotência
(BDE+ABD+ACD+BCE+ABCD+ACD)⇒ absorção
(BDE+ABD+ACD+BCE)
Logo, temos número de cobertura de vertices β(G) = 3. O conjunto indepen- Conjuntos Inde-
dente maximal In é obtido por In = V − Cn . Portanto, temos os seguintes pendentes Maxi-
conjuntos independentes maximais mais
5.2.2 Cliques
A aplicação do método de Maghout para o cálculo de cliques é direta. Se
queremos calcular os cliques de um grafo G, devemos encontrar os conjuntos
independentes maximais presentes em Ḡ. Isto nos levará diretamente aos cli-
ques em G. Portanto dado o grafo G ilustrado na Figura 5.1, primeiramente
temos que calcular o complemento de G. O grafo Ḡ é ilustrado na Figura 5.2.
Em seguida, é realizado o mesmo processo apresentado na seção anterior.
A partir de Ḡ, realizamos as seguintes operações
(A+CD)(E+BC)⇒ distributividade
AE+ABC+CDE+BCD
Os termos encontrados correspondem às seguintes coberturas minimais de
vértices
{a, e}, {a, b, c}, {c, d, e}, {b, c, d}
A partir destas coberturas encontramos os seguintes conjuntos indepen-
dentes maximais em Ḡ,
Dado o grafo G = (V, A), ilustrado na Figura 5.1, para cada vértice
criaremos uma variável lógica. Neste caso, os vértices a − f estão associados
às variáveis lógicas A − F , respectivamente. Em seguida, para cada vértice
v criamos uma soma lógica contendo todas as variáveis dos vértices que são
dominadas por v 5 . Por exemplo, para o vértice a, criamos a seguinte soma
lógica
(A + B + E)
para o vértice b temos a seguinte soma (A + B + C + D), e assim por di-
ante. Portanto para este grafo temos o seguinte produto destacando o vértice
dominante embaixo da sua respectiva soma lógica.
(A + B + E) (A + B + C + D) (B + C + D) (B + C + D + E) (A + D + E)
| {z }| {z }| {z }| {z }| {z }
a b c d e
(A+B+E)(A+B+C+D)(B+C+D)(B+C+D+E)
(A+D+E) ⇒ Equação 5.3
(A+E+BD)(B+C+D) ⇒ distributividade
AB+AC+AD+BE+CE+DE+BD+BCD+BD ⇒ absorção
AB+AC+AD+BE+CE+DE+BD
{a, b}, {a, c}, {a, d}, {b, e}, {c, e}, {d, e}, {b, d}
5.2.4 Emparelhamentos
Na Seção 4.5, discutimos a relação entre emparelhamento maximal e conjunto
independente maximal. Vimos que um emparelhamento maximal em um
grafo G corresponde a um conjunto independente maximal no grafo linha
L(G). Usando esta relação, aplicaremos o método de Maghout no grafo linha
L(G) ao invés de utilizá-lo diretamente no grafo G original para enumerar
todos os seus emparelhamentos maximais.
Para facilitar a compreensão do método, reapresentamos o grafo G =
(V, A) da Figura 4.13 na Figura 5.3(a), dando ênfase às suas arestas. A Fi-
gura 5.3(b) mostra o grafo linha L(G) = (VL , AL ) associado a G. As arestas
de G possuem rótulos a−j que serão usados como rótulos dos vértices corres-
pondentes em L(G). Dois vértices em L(G) são adjacentes se compartilham
vértices em G. Por exemplo, as arestas a e b em G compartilham vértices,
logo os vértices correspondentes são adjacentes em L(G), como podemos ver
na Figura 5.3(b). Por outro lado, como as arestas a e c não compartilham
vértices, seus vértices a, c ∈ VL correspondentes em L(G) não são adjacentes.
(a) (b)
Figura 5.3: Grafo Roda (a) W5 e seu grafo linha (b) L(W5 ) correspondente.
F + ABGHIJ
(A+BE)(C+BD)(D+E) ⇒ distributividade
(AC+ABD+BCE+BDE)(D+E) ⇒ distributividade
ACD+ACE+ABD+ABDE+BCDE+ BCE
BDE+BDE ⇒ absorção
ACD+ACE+ABD+BCE+BDE
(F+ABGHIJ)(G+BCHIJ)(H+CDIJ)
(I+DEJ)(J+AE)⇒ distributividade
(FG+BCFHIJ+ABGHIJ+ABCGHIJ)
(H+CDIJ)(I+DEJ)(J+EA)⇒ absorção
(FG+BCFHIJ+ABGHIJ)(H+CDIJ)
(I+DEJ)(J+AE)⇒ distributividade
(FG+BCFHIJ+ABGHIJ)
(HI+DEHJ+CDIJ+CDEIJ)(J+AE) ⇒ absorção
(FG+BCFHIJ+ABGHIJ)
(HI+DEHJ+CDIJ)(J+AE) ⇒ distributividade
(FG+BCFHIJ+ABGHIJ)
(HIJ+HIEA+DEHJ+DEHJA+CDIJ+CDIJEA)⇒ absorção
(FG+BCFHIJ+ABGHIJ)
(HIJ+HIEA+DEHJ+DEHJA+CDIJ)⇒ absorção
(FG+BCFHIJ+ABGHIJ)
(HIJ+HIEA+DEHJ+CDIJ)⇒ distributividade
FGHIJ+FGHIEA+FGDEHJ+FGCDIJ+BCFHIJ+
BCFHIJEA+ BCFHIJDE+BCFHIJD+ABGHIJ
+ABGHIJE+ ABGHIJDE+ ABGHIJCD⇒ absorção
FGHIJ+FGHIEA+FGDEHJ+FGCDIJ+ BCFHIJ+
BCFHIJEA+BCFHIJDE +BCFHIJD+ABGHIJ⇒ absorção
FGHIJ+FGHIEA+FGDEHJ+FGCDIJ+ BCFHIJ+ABGHIJ
O cálculo de P1 .P2 resulta nos seguintes passos. Devido à quantidade de
termos manipulados a cada passo, omitimos o nome das operações aplicadas,
entretanto, continuamos destacados os termos usados nas operações.
(ACD+ACE+ABD+BCE+BDE)
(FGHIJ+AEFGHI+DEFGHJ+CDFGIJ+BCFHIJ+ABGHIJ)⇒
ACDFGHIJ+ACEFGHIJ+ABDFGHIJ+BCEFGHIJ+BDEFGHIJ+
ACDEFGHI+ACEFGHI+ABDEFGHI+ABCEFGHI+ABDEFGHI+
ACDEFGHJ+ACDEFGHJ+ABDEFGHJ+BCDEFGHJ+BDEFGHJ+
ACDFGIJ+ACDEFGIJ+ABCDFGIJ+BCDEFGIJ+BCDEFGIJ+
ABCDFHIJ+ABCEFHIJ+ABCDFHIJ+BCEFHIJ+BCDEFHIJ+
ABCDGHIJ+ABCEGHIJ+ABDGHIJ+ABCEGHIJ+ABDEGHIJ ⇒
ACEFGHIJ+ABDFGHIJ+BCEFGHIJ+BDEFGHIJ+
ACDEFGHI+ACEFGHI+ABDEFGHI+ABCEFGHI+ABDEFGHI+
ACDEFGHJ+ACDEFGHJ+ABDEFGHJ+BCDEFGHJ+BDEFGHJ+
ACDFGIJ+BCDEFGIJ+BCDEFGIJ+
ABCDFHIJ+ABCEFHIJ+ABCDFHIJ+BCEFHIJ+BCDEFHIJ+
ABCDGHIJ+ABCEGHIJ+ABDGHIJ+ABCEGHIJ+ABDEGHIJ⇒
ACEFGHIJ+ABDFGHIJ+BCEFGHIJ+BDEFGHIJ+
ACDEFGHI+ACEFGHI+ABDEFGHI+ABCEFGHI+
ACDEFGHJ+ACDEFGHJ+ABDEFGHJ+BCDEFGHJ+BDEFGHJ+
ACDFGIJ+BCDEFGIJ+BCDEFGIJ+
ABCDFHIJ+ABCEFHIJ+ABCDFHIJ+BCEFHIJ+BCDEFHIJ+
ABCDGHIJ+ABCEGHIJ+ABDGHIJ+ABCEGHIJ+ABDEGHIJ⇒
ACEFGHIJ+ABDFGHIJ+BCEFGHIJ+
ACDEFGHI+ACEFGHI+ABDEFGHI+ABCEFGHI+
ACDEFGHJ+ACDEFGHJ+BDEFGHJ+
ACDFGIJ+BCDEFGIJ+BCDEFGIJ+
ABCDFHIJ+ABCEFHIJ+ABCDFHIJ+BCEFHIJ+BCDEFHIJ+
ABCDGHIJ+ABCEGHIJ+ABDGHIJ+ABCEGHIJ+ABDEGHIJ⇒
ACEFGHIJ+ABDFGHIJ+BCEFGHIJ+
ACDEFGHI+ACEFGHI+ABDEFGHI+ABCEFGHI+
ACDEFGHJ+ACDEFGHJ+BDEFGHJ+
ACDFGIJ+BCDEFGIJ+
ABCDFHIJ+ABCEFHIJ+ABCDFHIJ+ BCEFHIJ+ BCDEFHIJ+
ABCDGHIJ+ABCEGHIJ+ ABDGHIJ+ABCEGHIJ+ABDEGHIJ⇒
ACEFGHIJ+ABDFGHIJ+
ACDEFGHI+ACEFGHI+ABDEFGHI+ABCEFGHI+
ACDEFGHJ+ACDEFGHJ+BDEFGHJ+
ACDFGIJ+BCDEFGIJ+
ABCDFHIJ+ABCDFHIJ+BCEFHIJ+
ABCDGHIJ+ABCEGHIJ+ABDGHIJ+ABCEGHIJ+ABDEGHIJ⇒
ACEFGHIJ+ABDFGHIJ+
ACDEFGHI+ACEFGHI+ABDEFGHI+ABCEFGHI+
ACDEFGHJ+ACDEFGHJ+BDEFGHJ+
ACDFGIJ+BCDEFGIJ+
ABCDFHIJ+BCEFHIJ+
ABCDGHIJ+ABCEGHIJ+ABDGHIJ+ABCEGHIJ+ABDEGHIJ⇒
ACEFGHIJ+ABDFGHIJ+
ACDEFGHI+ACEFGHI+ABDEFGHI+ABCEFGHI+
ACDEFGHJ+BDEFGHJ+
ACDFGIJ+ BCDEFGIJ
ABCDFHIJ+ BCEFHIJ
ABCDGHIJ+ ABCEGHIJ+ ABDGHIJ+ ABCEGHIJ+ ABDEGHIJ⇒
ABDFGHIJ+
ACEFGHI+ABDEFGHI+
ACDEFGHJ+BDEFGHJ+
ACDFGIJ+ BCDEFGIJ
ABCDFHIJ+ BCEFHIJ
ABCDGHIJ+ ABCEGHIJ+ ABDGHIJ+ ABCEGHIJ+ ABDEGHIJ⇒
ACEFGHI+ABDEFGHI+
ACDEFGHJ+BDEFGHJ+
ACDFGIJ+ BCDEFGIJ
ABCDFHIJ+ BCEFHIJ
ABCEGHIJ+ ABDGHIJ+ ABCEGHIJ⇒
ACEFGHI+ABDEFGHI+ACDEFGHJ+BDEFGHJ+ACDFGIJ+
BCDEFGIJ+ABCDFHIJ+BCEFHIJ+ABCEGHIJ+ABDGHIJ
{b, d, j}, {c, j}, {b, i}, {a, c, i}, {b, e, h}, {a, h}, {e, g}, {a, d, g}, {d, f }, {c, e, f }
(1̇+ 3̇)2 (1̇+ 5̇)2 (5̇+ 3̇)2 (2̇+ 3̇)2 (2̇+ 4̇)2 (2̇+ 6̇)2 (3̇+ 4̇)2 (3̇+ 6̇)2 (4̇+ 6̇)2 (1̇+ 2̇)(5̇+ 6̇)
onde
(1̇ + 3̇)(1̇ + 5̇)(5̇ + 3̇)(2̇ + 3̇)(2̇ + 4̇)(2̇ + 6̇)(3̇ + 4̇)(3̇ + 6̇)(4̇ + 6̇)(1̇ + 2̇)(5̇ + 6̇)
˙ 1̇ + 5̇) ⇒
(3̇ + 1̇2̇4̇5̇6̇)(6̇ + 2̇4̇5̇)(2̇ + 14)( distributividade
˙ 1̇ + 5̇) ⇒
(3̇6̇ + 2̇3̇4̇5̇ + 1̇2̇4̇5̇6̇ + 1̇2̇4̇5̇6̇)(2̇ + 14)( idempotência
Após este processo, obtivemos cinco termos indicando que temos as se-
guintes coberturas de vértices minimais
5.3.3 Cliques
O cálculo de cliques maximais em dı́grafos é similar ao cálculo realizado para
grafos. Inicialmente calculamos o complemento do dı́grafo e encontramos
seu grafo simples subjacente, pelos motivos apresentados na Seção 5.3.1. Em
seguida aplicamos o método de maghout. Considere, o dı́grafo D, ilustrado na
Figura 4.2. O Complemento deste dı́grafo D̄ e seu grafo simples subjacente,
são ilustrados nas Figuras 5.6(a) e (b), respectivamente.
(a) (b)
1̇5̇ + 2̇4̇6̇
Os termos encontrados correspondem às seguintes cobertura de vértices
minimais
{1, 5}, {2, 4, 6}
Usando este resultado encontramos os seguintes conjuntos independentes
maximais em D̄,
{2, 3, 4, 6}, {1, 3, 5}
que correspondem aos cliques maximais em D. Logo, o número de clique
do dı́grafo é ω(D) = 4.
(A + B + C) (B + C + D) (A + B + C + E) (B + D + F )
| {z }| {z }| {z }| {z }
a b c d
(C + D + E + F ) (B + F )
| {z }| {z }
e f
(A+B+C)(B+C+D)(A+B+C+E)(B+D+F)
(C+D+E+F)(B+F)⇒ Equação 5.4
(B+CF+ADF)(C+D+E+F)⇒ distributividade
BC+BD+BE+BF+CF+CDF+CEF+ CF+ACDF+
+ADF+ADEF+ADF⇒ absorção
BC+BD+BE+BF+CF+ADF+ADEF+ADF⇒ absorção
BC+BD+BE+BF+CF+ ADF
(A + C) (A + B + C + D + F ) (A + B + C + E) (B + D + E)
| {z }| {z }| {z }| {z }
a b c d
(C + E) (D + E + F )
| {z }| {z }
e f
(C+AE)(D+E+BF)⇒ distributividade
CD+CE+CBF+ADE+AE+ABEF⇒ absorção
CD+CE+CBF+AE
BCD+BCE+BCF+ABCE+BCD+BCDE+BCDF+
ABDE+BCDE+BCE+BCEF+ABE+BCDF+BCEF+
BCF+ABEF+CDF+CEF+BCF+ACEF+ACDF+
ACDEF+ABCDF+ADEF⇒ absorção
BCD+BCE+BCF+ABCE+
ABDE+BCE+BCEF+ABE+BCEF+
BCF+ABEF+CDF+CEF+BCF+ACEF+ACDF+
ACDEF+ADEF⇒ absorção
BCD+BCE+BCF+
ABDE+ABE+
BCF+ABEF+CDF+CEF+BCF+ACEF+ACDF+
ACDEF+ADEF⇒ absorção
BCD+BCE+BCF+
ABDE+ABE+
ABEF+CDF+CEF+ACEF+ACDF+
ACDEF+ADEF⇒ absorção
BCD+BCE+BCF+
ABE+CDF+CEF+ACEF+ACDF+
ACDEF+ADEF⇒ absorção
BCD+BCE+BCF+ABE+
+CDF+CEF+ACDF+ADEF⇒ absorção
BCD+BCE+BCF+ABE+
CDF+CEF+ADEF
5.3.5 Emparelhamentos
Na Seção 5.2.4, vimos explicitamente o relacionamento entre emparelhamento
maximal e conjunto independente maximal através da relação entre um grafo
G e seu grafo linha L(G). Observamos que os emparelhamentos de G po-
deriam ser obtidos calculando os conjuntos independentes em L(G). Isto
permitiu o uso do método de Maghout em L(G) para enumerar todos os
emparelhamentos maximais de G.
Na Seção 4.5, discutimos que o conceito de emparelhamento para gra-
fos e dı́grafos era o mesmo, porém com a diferença de que para o primeiro
considerávamos arestas enquanto para o último considerávamos arcos. En-
tretanto, em ambos os casos, o emparelhamento buscava sempre um conjunto
de arcos ou arestas que não compartilhavam vértices e não correspondiam a
laços.
Nesta seção iremos usar os resultados obtidos anteriormente para grafos
e apresentados na Seção 5.2.4. Considerando o dı́grafo D = (V, A) mostrado Grafo Subja-
na Figura 5.7, a enumeração dos emparelhamentos é feita a partir do grafo cente ao Dı́grafo
subjacente a D, o qual chamaremos de D0 . Usando D0 , aplicamos o método Grafo Linha
de Maghout no grafo linha L(D0 ). O grafo D0 é o grafo da Figura 5.3 que foi
utilizado na Seção 5.2.4 para exemplificar o cálculo dos emparelhamentos ma-
ximais. Portanto os passos mostrados naquela seção assim como o resultado
obtido são também válidos para o dı́grafo D. Assim, os emparelhamentos
maximais para D correspondem aos seguintes conjuntos de arcos
{b, d, j}, {c, j}, {b, i}, {a, c, i}, {b, e, h}, {a, h}, {e, g}, {a, d, g}, {d, f }, {c, e, f }
5.4 Exercı́cios
Exercı́cio 5.1. Liste todos os conjuntos independentes do grafo ilustrado na
Figura 4.1(a) e determine seu número de independência.
Exercı́cio 5.14. Mostre que para qualquer k > 0, todo grafo k-regular bipar-
tido tem um emparelhamento perfeito.
Árvores
Qualquer grafo simples conexo que não possui ciclos é uma árvore. Quando
o grafo é simples e apenas acı́clico, temos uma floresta, onde cada componente Floresta
conexo é uma árvore. Se ele possui apenas um único componente conexo,
então ele é uma árvore que consiste em uma floresta conexa. A Figura 6.1
ilustra vários grafos acı́clicos que representam árvores, em particular, (a) é
um grafo caminho P6 e (b) é um grafo estrela S6 . Observe que em todos os
casos, o número de arestas é uma unidade a menos que o número de vértices.
A união de todas as árvores nesta figura compõe uma floresta com 3 compo-
nentes conexos. O fato de uma árvore ser um grafo acı́clico leva ao seguinte
Teorema.
Figura 6.1: Exemplo de árvores. O grafo resultante da união das árvores (a),
(b) e (c) corresponde a uma floresta.
Teorema 6.1. Em uma árvore, existe um único caminho entre qualquer par
de vértices.
Corolário 6.1. Cada aresta de uma árvore é uma aresta de corte (Verifique!).
(a) (b)
(a)
(b) (c)
Figura 6.3: Exemplo de árvores enraizadas. (b) e (c) são árvores enraizadas
geradas a partir de (a), com raı́zes a e e respectivamente
(a) (b)
sada de forma eficiente. Nestes casos, elas são chamadas de árvores binárias
de pesquisa.
A árvore mostrada na Figura 6.3(c) é um exemplo de árvore 3-ária,
também chamada de ternária. Esta árvore é completa pois todos os vértices
internos possuem exatamente 3 vértices filhos. Por outro lado, embora a
árvore mostrada na Figura 6.3(b) seja uma árvore ternária, ela não é com-
pleta, pois o vértice e possui apenas dois filhos. Outro exemplo pode ser
visto na Figura 6.1(b) se considerarmos o vértice central como sendo um
vértice raiz. Neste caso, teremos uma árvore 6-ária. A árvore ilustrada na
Figura 6.1(c) pode também ser vista como árvore completa 3-ária se consi-
derarmos que o vértice do topo como vértice raiz.
O comprimento do caminho do vértice raı́z até um vértice v qualquer
define o nı́vel do vértice v, denotado por l(v)1 . O nı́vel de um vértice é Nı́vel de um
também chamado de altura do vértice na árvore. Por exemplo, considere a vértice
árvore T = (V, A) ilustrada na Figura 6.3(c). Os vértices de T possuem os
seguintes nı́veis l(a) = 2, l(b) = 1, l(c) = 2, l(d) = 1, l(e) = 0 e l(f ) = 2. Note
que o nı́vel do vértice raiz e é igual a 0, por outro lado o nı́vel do vértice a
é igual a 2. A partir desta informação é possı́vel calcular a altura da árvore Altura de uma
T , denotada por h(T )2 . Ela é definida pelo maior valor de nı́vel encontrado Árvore
considerando todos os vértices de T , i.e.,
h(T ) = max l(v).
v∈V
Uma árvore p-ária de altura h é chamada balanceada se todos os vértices Árvore Balance-
1 ada
l é a inicial da palavra level que corresponde à palavra nı́vel em inglês
2
h é a inicial da palavra height que corresponde à palavra altura em inglês
(a)
(b)
Figura 6.5: Exemplo de árvore balanceada. (a) é uma árvore ternária balan-
ceada, enquanto que (b) é binária porém não balanceada.
(a)
(b) (c)
Ph−1 i ph −1
folha e no máximo i=0p = p−1
vértices internos.
G. Uma solução simples e elegante para este problema foi dada por Cayley
através do seguinte Teorema.
2 −1 0
0
1+1
−1 4 −1 −1
T (G) = (−1) det = 9.
0 −1 2 −1
0 −1 −1 2
onde estas árvores podem ou não ser isomórficas entre si. Isomorfismo será
discutido no Capı́tulo 1.6.
Se considerarmos o conjunto de vértices de Kn sendo definido por N =
{1, 2, . . . , n} notaremos que nn−2 corresponde ao número de sequências de
tamanho n − 2 que podemos formar com os elementos definidos no conjunto
N . A relação entre estas seqüências e as possı́veis árvores geradoras associa-
das ao grafo Kn é devido também ao trabalho de Prüfer. Prüfer [22] mostrou
que existe uma correspondência direta entre o conjunto de árvores de espa-
lhamento de Kn e o conjunto de todas as seqüências de tamanho n − 2, de
maneira que cada árvore seja identificada de forma unı́voca por uma dada
Código Prüfer seqüência. A esta seqüência é dado o nome código prüfer.
O código Prüfer é obtido através do seguinte processo. Considere uma
árvore T = (V, A) com n vértices rotulados de 1 a n. Por conveniência
denotaremos a árvore no instante i > 0 por Ti , o vértice selecionado no
instante i por si e o vértice vizinho a si por ti . Note que T1 = T , i.e., no
instante 1 a árvore T1 é exatamente igual a árvore original T .
Os vértices vizinhos assumem papel fundamental na construção do código,
pois eles compõem o código Prüfer. Por exemplo, para a árvore T , o código
Prüfer é dado por (t1 , t2 , t3 , . . . , tn−2 ). A questão principal é como escolher
si . Esta escolha é fácil pois o vértice si corresponde sempre ao vértice folha
de menor ı́ndice na árvore Ti . Os passos abaixo descrevem o processo de
obtenção do código Prüfer:
Tabela 6.1: Passos realizados para obter o código Prüfer da árvore na Fi-
gura 6.10
aparece no código d(v) − 1 vezes, onde d(v) é o grau do vértice v. Isso ocorre
por alguns motivos. Primeiro é importante enfatizar que os vértices folha
são usados apenas para a seleção dos vértices que irão compor o código, os
quais correspondem aos vértices internos da árvore. Cada vértice interno v
possuirá no máximo d(v) − 1 folhas, o que fará com que este vértice apareça
no código exatamente d(v) − 1 vezes. Quando todas as suas d(v) − 1 folhas
forem removidas ele próprio se tornará folha. Neste momento, ele apenas
contribuirá com o processo informando o seu vértice vizinho que irá compor
o código.
A partir de um código Prüfer P , podemos recuperar a árvore associada da
seguinte maneira. Primeiro, criamos um conjunto de vértices S que contenha
todos os vértices da árvore que não aparecem no código P . Como para uma
árvore com n vértices, temos sempre os rótulos de 1 a n, basta verificar
quais rótulos não aparecem no código e adicioná-los a S. À cada iteração,
o conjunto S sofrerá alterações na quantidade de seus elementos, por isso,
usaremos o termo Si para representar o conjunto S no instante i. No primeiro
passo de iteração, quando i = 1, o conjunto S1 contém todos os vértices
originais de S. De forma análoga, temos o código intermediário Pi definido na
iteração i, e quando i = 1, P1 é exatamente igual ao código original P . Além
deles, usamos os termos si , que corresponde ao elemento de menor rótulo do
conjunto Si , e o pi que corresponde sempre ao primeiro elemento do código
Pi , i.e, o elemento mais à esquerda de Pi . A partir destas informações,
a recuperação da árvore associada ao código Prüfer é feita pelos seguintes
passos:
1. No passo inicial, i = 1, selecionamos o vértice s1 , de menor ı́ndice do
conjunto S1 , e o primeiro elemento p1 do código P1 para compor a
primeira aresta {s1 , p1 } da árvore que está sendo recuperada.
2. Em seguida, removemos s1 de S1 , gerando o conjunto S2 , e o primeiro
elemento p1 de P1 , gerando o código P2 .
Os passos seguintes seguem a mesma lógica, porém com uma sutil diferença.
1. Na iteração i, selecionamos o vértice si do conjunto Si e o primeiro
elemento pi do código Pi . Estes elementos irão compor a aresta {si , pi }.
Após isto, removemos si de Si e o elemento pi de Pi . Isto gerará o
conjunto Si+1 e o código Pi+1 .
2. Se pi não aparecer mais em Pi+1 , então ele é adicionado a Si+1 .
Iteração i Pi pi Si si Aresta
1 (4, 4, 5, 2, 2, 4, 5) 4 {1, 3, 6, 7, 8, 9} 1 {1, 4}
2 (4, 5, 2, 2, 4, 5) 4 {3, 6, 7, 8, 9} 3 {3, 4}
3 (5, 2, 2, 4, 5) 5 {6, 7, 8, 9} 6 {5, 6}
4 (2, 2, 4, 5) 2 {7, 8, 9} 7 {2, 7}
5 (2, 4, 5) 2 {8, 9} 8 {2, 8}
6 (4, 5) 4 {2, 9} 2 {2, 4}
7 (5) 5 {4, 9} 4 {4, 5}
8 () {5, 9} {5, 9}
Como existe uma função bijetora entre a árvore e seu respectivo código
Prüfer, cada permutação dos elementos do código levará a uma árvore distinta
da original, porém mantendo a mesma seqüência de graus. Ou seja, as duas
árvores possuem os mesmos vértices com os mesmos graus por vértice porém
com conjuntos distintos de arestas, já que existirão conexões diferentes entre
os vértices. Por exemplo, se considerarmos o código P 0 = (2, 4, 5, 4, 2, 4, 5),
que corresponde a uma permutação do código P = (4, 4, 5, 2, 2, 4, 5), encon-
traremos uma árvore distinta da árvore mostrada na Figura 6.10. A árvore
associada ao código P 0 , mostrada na Figura 6.11, é recuperada através dos
seguintes passos, mostrados na Tabela 6.3
A partir deste resultado concluı́mos que : Dada uma seqüência de inteiros
positivos d1 , d2 , . . . , dn totalizando 2n − 2, existem
(n − 2)!
Πni=1 (di
− 1)!
Iteração i Pi pi Si si Aresta
1 (2, 4, 5, 4, 2, 4, 5) 2 {1, 3, 6, 7, 8, 9} 1 {1, 2}
2 (4, 5, 4, 2, 4, 5) 4 {3, 6, 7, 8, 9} 3 {3, 4}
3 (5, 4, 2, 4, 5) 5 {6, 7, 8, 9} 6 {5, 6}
4 (4, 2, 4, 5) 4 {7, 8, 9} 7 {4, 7}
5 (2, 4, 5) 2 {8, 9} 8 {2, 8}
6 (4, 5) 4 {2, 9} 2 {4, 2}
7 (5) 5 {4, 9} 4 {4, 5}
8 () {5, 9} 8 {5, 9}
(n − 2)!
Πni=1 (d(vi )
− 1)!
0 1 1 0 2 0 0 0
0 0 1 0 0 2 0 0
L= eM =
1 1 0 1 0 0 3 0
1 0 1 0 0 0 0 1
por
2 −1 −1 0
0 2 −1 0
Q=
−1 −1 3 −1
−1 0 −1 1
0 −1 1
6.4 Exercı́cios
Exercı́cio 6.1. Determine o número de vértices de uma árvore enraizada
p-ária completa de altura h.
Exercı́cio 6.5. Mostre que toda árvore com exatamente dois vértices de grau
1 é um caminho.
Planaridade
Figura 7.1: Grafo K3,2 desenhado no plano. (b) e (c) correspondem a exem-
plos de realização planar de K3,2 .
(a) (b)
(a) (b)
n−m+f =p+1
Figura 7.5: Exemplo de Grafo Planar com todas as faces com grau 3.
3f = 2m
onde f é o número de faces de G e m = |A|. Se em G, algumas faces tiverem
grau maior que 3, sabemos que
3f ≤ 2m
f =2−n+m
3(2 − n + m) ≤ 2m
resultando na seguinte desigualdade
m ≤ 3n − 6
10 ≤ 3.5 − 6 → 10 ≤ 9.
o que é falso e mostra que K5 não é planar. Note que K5 possui 5 vértices e
10 arestas. Este resultado nos leva ao seguinte teorema.
9 ≤ 3.6 − 6 → 9 ≤ 12
o que nos leva a uma conclusão errada, pois K3,3 não é um grafo planar.
Esta conclusão errada foi oriunda da desigualdade que aplicamos. Anterior-
mente assumimos que os grafos possuiriam faces delimitadas por no mı́nimo
3 arestas, porém o grafo K3,3 não possui faces triangulares. Ele é um grafo
bipartido e cada uma de suas faces é delimitada por no mı́nimo 4 arestas.
Assim, a nossa desigualdade inicial deve ser alterada para considerar grafos
com faces que tenham grau no mı́nimo igual a 4. Isso nos leva a
4f ≤ 2m → 2f ≤ m
f =2−n+m
2(2 − n + m) ≤ m
resultando na seguinte desigualdade
m ≤ 2n − 4
9 ≤ 2.6 − 4 → 9 ≤ 8
7.4 Exercı́cios
Exercı́cio 7.1. Mostre que se G = (V, A) é um grafo planar conexo onde
cada face de G é um t-cı́rculo então
t(n − 2)
m=
(t − 2)
onde n = |V | e m = |A|.
(a) (b)
Coloração
(a) (b)
Figura 8.1: Exemplo de Coloração. (b) é uma possı́vel coloração dos vértices
do grafo em (a).
A partir deste grafo devemos colorir seus vértices. Cada cor estará associ-
ado a um horário especı́fico. A solução mais direta seria atribuir um horário
para cada vértice, porém não seria a melhor solução possı́vel. Cada horário
pode implicar em custos. Assim concentrar os encontros dos comitês, fazendo
com que alguns sejam realizados em sessões paralelas, fará com que a quan-
tidade de horários usados seja menor impactando possivelmente a logı́stica
do evento. Como dito, as arestas impõem restrições ao nosso problema. Por
exemplo, a aresta entre os vértices 1 e 2 informa que pelo menos uma pessoa
participa destes dois comitês. Assim eles devem ser reunir em horários dife-
rentes. Note que este não é o caso para os comitês 5 e 6 ou 9 e 3. Portanto,
uma possı́vel coloração do grafo ilustrado na Figura 8.1(a) é mostrada em
(b). Note que foram usadas apenas 3 cores, ou seja, 3 horários diferentes é
o suficiente para que todos os comitês consigam se reunir de forma que cada
Teorema 8.1. Um grafo G é k-partido sse seu número cromático for igual
a k, i.e., χ(G) = k.
0 ≤ d(v) ≤ n − 1
o que indica que um dado vértice v pode ter nenhum vizinho ou ser vizinho
de todos os outros vértices no grafo. O primeiro caso pode ser facilmente
ilustrado por um grafo totalmente desconexo, enquanto que o último por um
grafo totalmente conexo. No primeiro caso, a quantidade mı́nima de cores
para colorir propriamente este grafo é igual a 1. Enquanto que no último,
a quantidade seria igual a quantidade de vizinhos de v, já que cada vértice
é adjacente aos demais, mais uma unidade, que seria a cor atribuı́da a v.
Assim, temos o seguinte teorema.
Teorema 8.3. Para qualquer grafo G = (V, A), χ(G) ≥ ω(G) onde ω(G) é
o número de clique1 de G;
Porém, sabemos que esta situação ideal é bem especı́fica e é bem provável
que existam mais conjuntos independentes com tamanhos inferiores à α(G).
Um exemplo direto é o grafo ciclo C5 , destacado em vermelho na Figura 8.2.
O tamanho do maior conjunto independente é igual a 2 e qualquer particio-
namento dos vértices em conjuntos independentes resultará em 3 conjuntos
independentes maximais. A partir desta análise, temos o seguinte teorema
como resultado.
Teorema 8.4. Para qualquer grafo G = (V, A), χ(G) ≥ |V |/α(G), onde
α(G) é o número de independência2 de G.
mesmo vértice devem ser coloridas com cores diferentes, podemos concluir di-
retamente que para qualquer grafo G = (V, A), χ0 (G) ≥ ∆(G). Os teoremas
abaixo definem mais precisamente a relação entre χ0 (G) e ∆(G).
χ(K̄n ; k) = k n
3
O conceito multiplicidade de aresta é definido na Seção 1.1.
(a) (b)
Figura 8.3: Coloração de Grafos. (a) árvore com 3 vértices. (b) grafo com-
pleto K3 .
restrição às possibilidades de cores que podem ser atribuı́das aos vértices u
e v. A operação G − a leva a um grafo onde os vértices u e v podem assumir
quaisquer cores inclusive a mesma cor. A operação G/a, como definida an-
teriormente na Seção 2.2.7, contrai a aresta a unindo os vértices u e v. No
cálculo do polinômio cromático, a intenção é fazer como que u e v tenham
a mesma cor. Assim, neste cálculo temos χ(G − a; k) como o polinômio
cromático onde u e v podem ter a mesma cor, o que não é permitido em G,
pela própria presença de a, e o χ(G/a; k) como o polinômio cromático onde
u e v possuem a mesma cor. Embora a expressão recursiva definida pelo
teorema possa ser trabalhosa para grafos genéricos, ela facilita a obtenção do
polinômio cromático de maneira mais sistemática.
O exemplo seguinte mostrará a aplicação da equação de recorrência cromática.
Considere o grafo G ilustrado na Figura 8.5(a). Selecionando a aresta a em
vermelho e calculando G − a e G/a obtemos os grafos ilustrados em (b) e
(c). Embora o resultado em (c) seja um multigrafo, como comentando ante-
riormente, podemos desconsiderar as múltiplas arestas entre um mesmo par
de vértices e focar nossa atenção a apenas na adjacência entre os vértices.
Neste caso, o grafo em (c) seria visto como uma árvore e portanto
χ(G/a) = k(k − 1)2 .
no grafo dual. Como o grafo dual é planar, pelo Teorema 8.10, os vértices
deste grafo podem ser coloridos propriamente com no máximo 4 cores. Por
conseguinte, as regiões do mapa também poderão ser coloridas propriamente
com no máximo 4 cores. Note que o grafo dual resultante não será um
pseudografo, i.e., ele não possuirá laços, pois não existirão no mapa uma
aresta fazendo fronteira com apenas uma única face, como nos exemplos
ilustrados nas Figuras 7.3 e 7.4.
8.5 Exercı́cios
Exercı́cio 8.1. Prove que χ(G) = ∆(G) + 1 sse G é ou um grafo completo
ou um ciclo de comprimento ı́mpar
Exercı́cio 8.2. Mostre que se G contém exatamente um ciclo de compri-
mento ı́mpar então χ(G) = 3
Exercı́cio 8.3. Mostre que para um grafo simples G, se χ(G) = 2 então G
é bipartido
Exercı́cio 8.4. Qual é o número cromático de um grafo Km,n,p ?
Exercı́cio 8.5. Dê exemplo de grafos que possuem número cromático igual
a 1.
Exercı́cio 8.6. O que podemos dizer sobre um grafo que possui um subgrafo
isomórfico a Kn ?
Exercı́cio 8.7. Mostre que qualquer grafo G com cintura g(G) = 2p, para
p ∈ N tem χ(G) ≥ 3.
Exercı́cio 8.8. Dados os grafos abaixo
(a) (b)
(c) (d)
Número de Clique, 64
Grafo (m, n)-Ramsey, 73
Número de Cobertura de Fonte, 75
Grafo Bipartido Completo, 70
Número de Cobertura de Sumidouro,
Grafo Caminho, 20
75
Grafo Ciclo, 20
Número de Cobertura de Vértices, 73
Grafo completo, 19
Número de Dominância, 76
Grafo Conexo, 43
Número de Independência, 67
Grafo Desconexo, 43
Número de Ramsey, 72
Grafo Direcionado Simples, 5
Números de Dominância de Entrada
Grafo Estrela, 21
e de Saı́da, 78
Grafo Homeomorficamente Reduzido,
Números de Dominância Gêmea, 79
28
Nı́vel de um vértice, 121
Grafo Induzido, 7
Grafo K-Cubo, 21 Operação Complemento, 25
Grafo k-partido, 67 Operação de Contração, 27
Grafo K-partido Completo, 69 Operação de Decomposição, 29
Grafo Linha, 30 Operação de Intersecção, 24
Grafo não separável, 45 Operação de Junção, 23
Grafo Orientado, 5 Operação de Remoção, 27
Grafo Reduzido, 28 Operação de União, 23
Grafo Regular, 20 Operação Produto, 25
Grafo Roda, 21 Operador Linha, 30
Raio, 16
Relação de Dominância em Dı́grafos,
77
Relação de Dominância em Grafos,
76
Relação de Dominância Gêmea, 79
Semi-Caminho, 14
Semi-Passeio, 14
Semi-Trilha, 14
Seqüência de Graus, 9
Seqüência Gráfica, 10
Subárvore, 120
Subárvore Direita, 120
Subárvore Esquerda, 120
Subdivisão de Grafo, 29
Subgrafo e Subdı́grafo de Espelhamento,
7
Teorema de Menger-Dı́grafos, 55
Teorema de Menger-Grafos, 47, 49
Trilha, 13
Trilha de Espalhamento, 15
Trilha Direcionada, 14
[2] G. Dirac, “Some theorems on abstract graphs,” Proc. Lond. Math. Soc.,
vol. 2, pp. 69–81, 1952.
[3] O. Ore, “Note on hamilton circuits,” Amer. Mat. Monthly, vol. 67, p. 55,
1960.
[5] K. Menger, “Zur allgemeinen kurventheorie,” Fund. Math., vol. 10, pp.
96–115, 1927.
[15] C. Berge, “Two theorems in graph theory,” Proc. Nat. Acad. Sci., vol. 43,
pp. 842–844, 1957.
[16] P. Hall, “On representatives of subsets,” J. Lond. Mat., vol. 10, pp.
26–30, 1935.
[17] D. König, “Graphen und matrizen,” Math. Lapok, vol. 38, pp. 116–119,
1931.
[18] C. Jordan, “Sur les assemblages de lignes,” J. für die Reine und An-
gewandte Mathematic, vol. 70, pp. 185–190, 1869.
[19] G. Kirchhoff, “Über die auflösung der gleichungen, auf welche man bei
der untersuchung der linearen verteilung galvanischer ströme geführt
wird,” Ann. Phys. Chem., vol. 72, pp. 497–508, 1847.
[20] ——, “Ueber die auflösung der gleichungen, auf welche man bei der un-
tersuchung der linearen vertheilung galvanischer ströme geführt wird,”
Ann. Phys. Chem., vol. 72, pp. 497–508, 1847.
[21] A. Cayley, “A theorem on trees,” Quart. J. Math, vol. 23, pp. 376–378,
1889.
[22] H. Prüfer, “Neuer beweis eines satzes über permutationen,” Arch. Math.
Phys, vol. 27, pp. 727–744, 1918.