( PDF ) Decomposição em árvore de grafos com largura limitada: uma pesquisa algorítmica

Download PDF

ads:

Decomposic¸

ao em

Arvore de Grafos com Largura

Limitada — Uma Pesquisa Algor

ıtmica

Luis Eduardo Ximenes Carvalho

Departamento de Ciˆencia da Computac¸˜ao - DC/UFC

Universidade Federal do Cear´a

Fortaleza, CE, Brasil

Agosto, 2002

Vers˜ao parcial de Dissertac¸˜ao a ser apresentada ao

Mestrado em Ciˆencia da Computac¸˜ao,

UFC, como requisito parcial para a

obtenc¸ ˜ao do t´ıtulo de Mestre em

Ciˆencia da Computac¸˜ao.

 Luis Eduardo Ximenes Carvalho, 2002.

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

Sum

ario

1 Introduc¸

ao 1

2 Conceitos e Preliminares 3

2.1 Introduc¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3

Arvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.4 Conectividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.5 Emparelhamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.6 Menores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.7 Grafos Cordais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.8 L´ogica Mon´adica de Segunda Ordem . . . . . . . . . . . . . . . . . . 13

3 Decomposic¸

ao em

Arvore 17

3.1 Introduc¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2 Algumas propriedades de DEA . . . . . . . . . . . . . . . . . . . . . 20

3.3 DEA para ﬂorestas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.4 DEA para ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.5 DEA para cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.6 DEA para grafos cordais . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.7 DEA para grafos com largura no m´aximo 3 . . . . . . . . . . . . . . . 38

3.8 Conjuntos k-ligados, arbustos e novelos . . . . . . . . . . . . . . . . 43

3.9 Grades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.10 Conceitos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . 48

4 Algoritmos de Decomposic¸

ao em

Arvore 50

4.1 Introduc¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.2 DEA em grafos cordais . . . . . . . . . . . . . . . . . . . . . . . . . 52

ads:

Sum

ario

4.3 DEA usando separadores fortes . . . . . . . . . . . . . . . . . . . . . 54

4.4 DEA em tempo linear . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.5 DEA usando reduc¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.6 Algoritmos para problemas em grafos com largura em ´arvore limitada 74

5 Conclus

oes e Recomendac¸

oes 77

Refer

encias Bibliogr

aﬁcas 79

iii

Lista de Figuras

3.1 Exemplos de decomposic¸˜ao em ´arvore. . . . . . . . . . . . . . . . . . . 19

3.2 Uma aresta (i, j) de uma decomposic¸˜ao em ´arvore de um grafo G

corresponde a um separador em G. . . . . . . . . . . . . . . . . . . . . 21

3.3 Decomposic¸˜ao em ´arvore de um subgrafo . . . . . . . . . . . . . . . . 21

3.4 Decomposic¸˜ao em ´arvore de um grafo usando suas componentes. . . . . 22

3.5 Decomposic¸˜ao em ´arvore de um menor de um grafo . . . . . . . . . . . 23

3.6 Decomposic¸˜ao em ´arvore de um grafo a partir de um menor por contrac¸ ˜ao 24

3.7 Tentativa de decomposic¸˜ao em ´arvore de um ciclo. . . . . . . . . . . . 26

3.8 Qualquer ciclo possui K

como menor. . . . . . . . . . . . . . . . . . . 27

3.9 Decomposic¸˜ao em ´arvore de um ciclo. . . . . . . . . . . . . . . . . . . 28

3.10 Continˆencia de um subgrafo bipartite completo em uma DEA. . . . . . 30

3.11 Um grafo G n˜ao tem K

como menor se e somente se tem largura em

´arvore no m´aximo 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.12 Exemplo de decomposic¸˜ao em ´arvore para um grafo cordal. . . . . . . . 34

3.13 Os grafos M

, M

e M

. . . . . . . . . . . . . . . . . . . . . . . . . 38

3.14 Decomposic¸˜ao em ´arvore do grafo M

. . . . . . . . . . . . . . . . . . . 39

3.15 Casos para construc¸˜ao de uma decomposic¸˜ao em ´arvore de M

baseada

em cordalizac¸˜ao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.16 Decomposic¸˜ao em ´arvore do grafo M

, caso 1. . . . . . . . . . . . . . . 40

3.17 Decomposic¸˜ao em ´arvore do grafo M

, caso 2. . . . . . . . . . . . . . . 41

3.18 Decomposic¸˜ao em ´arvore de um menor do grafo M

. . . . . . . . . . . 42

3.19 Decomposic¸˜ao em ´arvore do grafo M

. . . . . . . . . . . . . . . . . . 43

3.20 Uma grade r × s e as cruzes C

2,2

e C

r−1,s−1

. . . . . . . . . . . . . . . . 44

4.1 Algoritmo para decomposic¸˜ao em ´arvore de grafos cordais. . . . . . . . 52

4.2 Algoritmo para decomposic¸˜ao em ´arvore baseado em cordalizac¸ ˜ao. . . . 54

4.3 Decomposic¸˜ao em ´arvore obtida pelo algoritmo de Reed. . . . . . . . . 56

Lista de Figuras

4.4 Algoritmo proposto em Reed (1992). . . . . . . . . . . . . . . . . . . . 57

4.5 Construc¸˜ao de um S-separador forte de ordem no m´aximo k + 1. . . . . 58

4.6 Exemplo de aplicac¸˜ao de regras de reduc¸˜ao. . . . . . . . . . . . . . . . 68

4.7 Regras de reduc¸˜ao para k-´arvores parciais, k ≤ 3. . . . . . . . . . . . . 69

4.8 Algoritmo para decis˜ao de uma propriedade de grafos P dado um sistema

de reduc¸˜ao especial para P , Fase 1. . . . . . . . . . . . . . . . . . . . . 72

4.9 Algoritmo para decis˜ao de uma propriedade de grafos P dado um sistema

de reduc¸˜ao especial para P , Fase 2. . . . . . . . . . . . . . . . . . . . . 73

Cap´ıtulo 1

Introduc¸

Durante cerca de uma d´ecada, Neil Robertson e Paul Seymour provaram um dos mais

importantes resultados em Matem´atica Discreta: “em todo conjunto inﬁnito de grafos,

existem dois tais que um

e menor do outro”. Tal teorema ´e conhecido como Teorema de

Menores de Grafos, e sua prova toma cerca de 500 p´aginas, sendo coberta por sua c´elebre

s´erie de artigos no Journal of Combinatorial Theory, Series B, entre 1986 e 1997.

Como resultado parcial do esforc¸o da prova do teorema, desenvolveram-se diver-

sos conceitos e t´ecnicas de grande potencial e interesse. Um desses conceitos ´e o de

decomposic¸˜ao em ´arvore. Uma decomposic¸˜ao em ´arvore para um grafo procura estabele-

cer uma relac¸ ˜ao estrutural entre as partes deste de modo que estas estejam minimalmente

conectadas, ou seja, de modo que a estrutura do grafo assemelhe-se a de uma ´arvore. Este

tipo de decomposic¸˜ao constitui, desta forma, uma boa ferramenta para o desenvolvimento

de algoritmos eﬁcientes para muitos problemas de otimizac¸˜ao combinat´oria que sejam

modelados em grafos, dado que tais grafos obedec¸am uma estrutura bastante semelhante

a uma ´arvore. O crit´erio para tal similaridade ´e conhecido como largura em ´arvore: quanto

menor a largura em ´arvore de um grafo, mais semelhante este ´e a uma ´arvore; ao contr´ario,

quanto maior a largura em ´arvore, mais conexo o grafo ser´a.

Muitos pesquisadores voltaram ent˜ao seus esforc¸os para a caracterizac¸ ˜ao de tipos

de grafos que sejam suﬁcientemente semelhantes a uma ´arvore para que essa propriedade

possa ser usada eﬁcientemente, principalmente no projeto de algoritmos espec´ıﬁcos. Tais

grafos comp˜oem a classe dos grafos que possuem largura em ´arvore limitada. No entanto,

embora este seja atualmente um assunto bastante estudado e pesquisado em todo o mundo,

´e bastante incipiente no Brasil o desenvolvimento de iniciativas e contribuic¸ ˜oes nesse

sentido.

Este texto compreende uma contribuic¸˜ao para este campo de estudo em Teoria dos

Grafos, de modo principalmente a estimular o surgimento de novos trabalhos e estudos

de profundidade, compat´ıveis com sua complexidade. Este texto pretende assumir um

car´ater introdut´orio, sendo redigido em linguagem acess´ıvel, e, na medida do poss´ıvel,

1. Introduc¸

auto-contido e de f´acil compreens˜ao. Al´em disso, ´e tamb´em intenc¸˜ao do texto ilustrar o

estado da arte em algoritmos de decomposic¸˜ao em ´arvore. Embora este tenha sido o prin-

cipal objetivo do trabalho de pesquisa, o principal produto ´e o texto, sendo este bastante

trabalhado.

Uma qualidade do texto que foi valorizada ´e o equil´ıbrio entre o formalismo ma-

tem´atico necess´ario e uma redac¸ ˜ao mais leve, introdut´oria. Tal aspecto teve como objetivo

uma assimilac¸˜ao mais suave da teoria, que pode, numa primeira impress˜ao, parecer in-

trat´avel e herm´etica. No entanto, vale ressaltar que a familiaridade crescente com o

assunto requer, invariavelmente, um bom envolvimento e compreens˜ao dos conceitos e

resultados, e principalmente das provas. De fato, buscou-se uma abordagem compreen-

siva e completa, e praticamente todos os principais resultados da teoria s˜ao demonstrados

— com algumas excec¸ ˜oes nos casos em que a prova ´e muito longa ou t´ecnica. O melhor

aprendizado passa, sem d´uvida, pela leitura minuciosa e pelo estudo judicioso dos lemas,

teoremas e deﬁnic¸ ˜oes e suas provas. Nesse sentido, procurou-se tamb´em fornecer provas

mais simples e detalhadas, principalmente dos resultados mais importantes.

O texto procura manter a simplicidade inclusive em sua organizac¸˜ao, contendo so-

mente trˆes cap´ıtulos principais. O Cap´ıtulo 2 introduz os conceitos b´asicos necess´arios em

Teoria dos Grafos. No Cap´ıtulo 3, o tema principal do texto ´e discutido: s˜ao apresentados

conceitos de decomposic¸˜ao em ´arvore e largura em ´arvore, com algumas propriedades;

em seguida casos particulares de classes de grafos com largura em ´arvore limitada e pe-

quena s˜ao tratados; e, ao ﬁnal do cap´ıtulo, ´e feita uma discuss˜ao de novos conceitos de

conectividade para que se possa estabelecer uma obstruc¸˜ao estrutural para grafos com

largura em ´arvore limitada.

O Cap´ıtulo 4 ´e dedicado aos algoritmos para obtenc¸˜ao de decomposic¸ ˜oes em ´arvore.

Nele s˜ao abordados dois paradigmas principais: algoritmos que usam m´etodos recursi-

vos e construtivos, e algoritmos baseados em reduc¸˜ao. Para tanto, s˜ao discutidos trˆes

principais algoritmos, compondo os mais importantes e atuais resultados tanto em ter-

mos de t´ecnicas como de complexidade computacional. Finalmente, no Cap´ıtulo 5, s˜ao

articuladas algumas conclus˜oes e recomendac¸ ˜oes para trabalhos futuros.

Cap´ıtulo 2

Conceitos e Preliminares

2.1 Introduc¸

O objetivo deste cap´ıtulo ´e introduzir os principais conceitos a serem usados ao longo do

texto, assim como apresentar a notac¸ ˜ao, tornando-a mais familiar para o leitor.

E assumido

que este tenha alguma familiaridade com Teoria dos Grafos e Algoritmos. Os conceitos

foram retirados de v´arias fontes, principalmente de (Bondy e Murty 1976), (Golumbic

1980), (Diestel 2000), mas compartilham a notac¸˜ao adotada por este ´ultimo.

2.2 Grafos

Deﬁnic¸

ao 1 (Grafo). Um grafo G ´e um par (V, E), onde V denota o conjunto de

ertices, e E o conjunto de arestas de G. Cada aresta ´e um par n˜ao-ordenado de v´ertices

u, v ∈ V , denotada por (u, v).

Os conjuntos de v´ertices e de arestas de um grafo G s˜ao denotados, respectivamente,

por V (G) e E(G). Um grafo ﬁnito ´e um grafo tal que seus conjuntos de v´ertices e arestas

s˜ao ﬁnitos; a cardinalidade de V (G) ´e normalmente denotada por n e a de E(G) por m.

Um lac¸o ´e uma aresta (u, v) onde u = v, e arestas que compartilham os mesmos v´ertices,

ou seja e

, . . . , e

= (u, v), s˜ao chamadas m

ultiplas entre u e v ou paralelas. Um grafo

simples G ´e um grafo sem lac¸os e arestas m´ultiplas, ou seja, para qualquer aresta (u, v)

de G, u, v ∈ V (G), u = v. Ao longo do texto, um grafo refere-se a um grafo simples

ﬁnito, a menos que seja expresso o contr´ario. Um grafo trivial ´e um que cont´em apenas

um v´ertice, ({v}, ∅), enquanto que um grafo vazio cont´em ambos os conjuntos de v´ertices

e arestas vazios.

Seja G = (V, E) um grafo. Para qualquer aresta e = (u, v) ∈ E, u e v s˜ao chamados

extremidades de e, e e ´e chamada a aresta entre u e v, ou conectando u e v. Dois v´ertices

u, v ∈ V s˜ao adjacentes se existe uma aresta (u, v) ∈ E. Se dois v´ertices u e v s˜ao

2. Conceitos e Preliminares

adjacentes, tamb´em diz-se que u ´e vizinho de v e vice versa. Um v´ertice v ∈ V e uma

aresta e ∈ E s˜ao chamados incidentes se e = (u, v) para algum u ∈ V . Duas arestas s˜ao

ditas adjacentes se compartilham uma mesma extremidade. A vizinhanc¸a de um v´ertice

v, denotada por N

(v), corresponde ao conjunto de v´ertices adjacentes a v: N

(v) =

{u ∈ V : (u, v) ∈ E}. A vizinhanc¸a de um conjunto de v´ertices S, S ⊆ V , denotada

por N

(S), corresponde ao conjunto de todos os v´ertices adjacentes a algum elemento

de S e n˜ao contidos nele: N

(S) = {v : v ∈ N

(u), u ∈ S, v ∈ S}. O grau de um

v´ertice v em G ´e o n´umero de arestas que s˜ao incidentes a v, sendo denotado por d(v). Os

graus m

ınimo e m

aximo de G, denotados por δ(G) e ∆(G), correspondem ao m´ınimo e

m´aximo dos graus dentre todos os v´ertices de G, respectivamente, δ(G) = min

v∈V

{d(v)}

e ∆(G) = max

v∈V

{d(v)}. Para um grafo G com arestas m´ultiplas, o grafo simples G



obtido pela remoc¸˜ao de arestas m´ultiplas entre quaisquer v´ertices u e v, e posterior adic¸ ˜ao

de (u, v) a E(G



), ´e conhecido como grafo subjacente a G.

Um grafo G



´e um subgrafo de um grafo G se V (G



) ⊆ V (G) e E(G



) ⊆ E(G).

Se G



´e um subgrafo de G, ent˜ao G ´e chamado um supergrafo de G



. Se um subgrafo G



de G ´e tal que V (G



) = V (G), ent˜ao G



´e dito um subgrafo gerador de G. Um grafo G



´e um subgrafo de G induzido (por v

ertices) por W , onde W ⊆ V (G), se V (G



) = W

e E(G



) = {(u, v) ∈ E : u, v ∈ W }. Diz-se tamb´em que G



´e um subgrafo induzido

de G. Para qualquer W ⊆ V (G), o subgrafo induzido por W ´e denotado por G[W ].

Analogamente, se F ⊆ E, diz-se que G



´e um subgrafo induzido em arestas por F de G

se E(G



) = F e V (G



) = {u ∈ V : (u, v) ∈ F, v ∈ V }. Da mesma forma, denota-se G



por G[F ].

A deﬁnic¸ ˜ao de subgrafo pode ser vista como uma relac¸ ˜ao entre o grafo original e

seu subgrafo. De forma semelhante, algumas operac¸ ˜oes podem ser deﬁnidas para grafos.

A uni

ao de dois grafos G

= (V

, E

) e G

= (V

, E

), G

∪ G

, resulta num grafo

G = (V, E) tal que V = V

∪ V

e E = E

∪ E

. A adic¸

ao de um v´ertice v a um grafo

G pode ser vista como um caso particular da uni˜ao entre G e um grafo trivial contendo

v, sendo denotada simplesmente por G + v; analogamente, denota-se por G + e a adic¸ ˜ao

de uma aresta e = (u, v) a G, sendo igual a G ∪ H, H = ({u, v}, {e}). Ao contr´ario

da adic¸ ˜ao, pode-se retirar um conjunto de v´ertices X de um grafo G, X ⊆ V , com base

na diferenc¸a usual entre o conjunto de v´ertices de G e X: G − X = G[V \ X]. Desta

forma, pode-se ainda denotar a retirada de um v´ertice v ou aresta e por G − v e G − e,

respectivamente. A intersec¸

ao entre dois grafos G

e G

´e deﬁnida analogamente `a uni˜ao,

resultando no grafo G = G

∩ G

onde V = V

∩ V

e E = E

∩ E

. Se G ´e um grafo

com subgrafos induzidos G

, G

e S tais que G = G

∪ G

e S = G

∩ G

, ent˜ao diz-se

que G ´e obtido pela (operac¸ ˜ao de) colagem de G

e G

ao longo de S.

Uma trilha W em um grafo G ´e uma seq¨uˆencia alternada v

, e

, v

, e

, . . . , e

p−1

, v



de v´ertices e arestas (p ≥ 1), comec¸ando e terminando em um v´ertice, tal que, para cada

i, v

∈ V , e

∈ E, e e

= (v

, v

i+1

). A trilha W ´e tamb´em chamada de trilha de v

a v

ou trilha entre v

e v

. Os v´ertices v

e v

s˜ao chamados extremidades de W , e os outros

v´ertices s˜ao chamados internos. O comprimento de uma trilha ´e o n´umero de arestas que

esta cont´em. Diz-se ainda que uma trilha W usa um v´ertice v se v = v

para algum i,

1 ≤ i ≤ p, e que W evita v se W n˜ao usa v. Se G ´e um grafo simples, ent˜ao n˜ao h´a

necessidade de referenciar as arestas em W , j´a que estas tornam-se implicitamente deter-

2.2. Grafos

minadas; neste caso, ou quando somente a seq¨uˆencia de v´ertices for relevante, pode-se

denotar W por v

, . . . , v

, de forma que para cada i, 1 ≤ i ≤ p, (v

, v

i+1

) ∈ E(G).

Um caminho P em um grafo G ´e uma trilha na qual todos os v´ertices s˜ao dis-

tintos, e logo todas as arestas s˜ao tamb´em distintas. A dist

ancia entre dois v´ertices u

e v em G ´e o comprimento do menor caminho entre u e v em G. Se P ´e o cami-

nho m´ınimo entre u e v em G, ent˜ao diz-se que P realiza a distˆancia entre u e v.

Seja P = x

, x

, . . . , x

r−1

, x

; ent˜ao denotam-se os subcaminhos de P x

, . . . , x

,

x

, . . . , x

 e x

, . . . , x

, como P x

, x

P e x

P x

, respectivamente. Analogamente, a

uni˜ao de dois caminhos P

= x

, . . . , x

 e P

= x

, . . . , x

 resultando no caminho

P = x

, . . . , x

 pode ser denotada por P = P

∪ x

, ou P = P

, ou mesmo

P = x

, P

, x

, P

, x

.

Um ciclo C em G ´e uma trilha na qual todas as arestas s˜ao distintas, e todos os

v´ertices s˜ao distintos com excec¸˜ao das extremidades, ou seja, apenas o primeiro e ´ultimo

v´ertices s˜ao iguais. Se um grafo G consiste de apenas um caminho, ent˜ao G ´e dito um

caminho em n v´ertices, sendo denotado por P

; da mesma forma, se G ´e composto de um

´unico ciclo, G ´e dito um ciclo em n v´ertices, denotado por C

Dois v´ertices s˜ao conectados em um grafo G se existe um caminho entre eles. Um

grafo G ´e dito conexo se todo par de v´ertices de G ´e conectado. Uma componente (conexa)

C de G ´e um subgrafo conexo maximal de G, ou seja, C ´e um subgrafo de G que ´e conexo,

e n˜ao existe um subgrafo de G que contenha propriamente C e seja tamb´em conexo. Um

conjunto S ⊆ V ´e um separador de G se existem dois v´ertices u, v ∈ V \ S tais que

u e v s˜ao conectados em G e desconectados em G[V \ S]; diz-se ainda que S ´e um

uv-separador em G, e que S ´e um corte em G. Se nenhum subconjunto pr´oprio de S ´e

um uv-separador, ent˜ao S ´e um separador minimal para u e v. Uma articulac¸

ao de G

´e um v´ertice v ∈ V (G) tal que {v} ´e um separador de G. Um grafo G ´e biconexo se

G ´e conexo e n˜ao cont´em articulac¸ ˜oes. Uma componente biconexa ou bloco de G ´e um

subgrafo biconexo maximal de G. Pode-se ver que os blocos de G particionam o conjunto

de arestas E de G, cada bloco ´e um subgrafo induzido de G, e um v´ertice v ∈ V ´e uma

articulac¸ ˜ao se e somente se v pertence a dois ou mais blocos de G. Uma aresta e ∈ E

´e chamada ponte de G se existem dois v´ertices u, v ∈ V que s˜ao conectados em G mas

desconectados em G



= (V, E \ {e}).

Uma partic¸

ao de um conjunto S ´e uma divis˜ao dos elementos de S em classes dis-

juntas {X

}

i∈I

tal que



i∈I

= S e X

∩ X

= ∅ para todo i, j ∈ I, i = j; uma

r-partic¸˜ao ´e uma partic¸˜ao tal que |I| = r. Um grafo G ´e dito r-particionado se admite

uma r-partic¸˜ao de seu conjunto de v´ertices V (G) tal que toda aresta de G tem extremi-

dades em classes diferentes da partic¸ ˜ao. Se um grafo G ´e 2-particionado em conjuntos

X, Y ⊆ V (G), por exemplo, ent˜ao toda aresta e = (u, v) de G satisfaz u = X e v = Y .

Normalmente se denomina G por grafo bipartite.

A pot

encia de um conjunto S ´e a fam´ılia P(S) de todos os subconjuntos de S:

P(S) = {X : X ⊆ S}. Um grafo completo ´e um grafo (simples) G onde todos os

v´ertices s˜ao adjacentes entre si, ou seja, para todo X ∈ P(V (G)), existe uma aresta de

G entre cada par de v´ertices de X. O grafo completo com n v´ertices ´e denotado por K

Uma clique de um grafo G ´e um subconjunto S ⊆ V (G) tal que G[S] ´e um subgrafo

completo de G. O n´umero clique de G, denotado por ω(G), ´e o tamanho da maior clique

2. Conceitos e Preliminares

em G. Por simplicidade, um grafo completo ´e tamb´em conhecido como uma clique. Um

grafo bipartite completo, por sua vez, ´e um grafo bipartite onde quaisquer dois v´ertices

de classes diferentes s˜ao adjacentes entre si. A partir do conceito de clique, pode-se ainda

deﬁnir uma operac¸

ao clique entre um grafo G e um subconjunto de v´ertices X de G,

denotada por G + K(X), resultando num supergrafo G



de G onde os v´ertices em X

formam uma clique.

Dois grafos G

= (V

, E

) e G

= (V

, E

) s˜ao ditos isomorfos — sendo denotado

por G

≈ G

— se existem bijec¸ ˜oes f : V

→ V

e g : E

→ E

tais que para cada

v ∈ V

e e ∈ E

, v ´e incidente a e em G

se e somente se f(v) ´e incidente a g(e) em G

O par (f, g) ´e chamado um isomorﬁsmo de G

a G

. Se G

e G

s˜ao grafos simples, um

isomorﬁsmo entre eles pode ser representado simplesmente por uma func¸ ˜ao f: G

e G

s˜ao isomorfos se e somente se existe f : V

→ V

tal que (u, v) ∈ E

se e somente se

(f(u), f (v)) ∈ E

Diz-se que um grafo ´e planar, ou embut

ıvel no plano se este pode ser desenhado no

plano de forma que suas arestas interceptam-se apenas nas extremidades.

2.3

Arvores

Uma

arvore T ´e um grafo simples conexo sem ciclos. Uma ﬂoresta F ´e um grafo simples

sem ciclos, ou seja, um grafo ´e uma ﬂoresta se e somente se cada uma de suas componen-

tes ´e uma ´arvore. Vale notar que qualquer aresta de uma ´arvore T ´e uma ponte, e logo T ´e

minimalmente conectado. Um v´ertice de uma ´arvore ´e tamb´em particularmente chamado

de n

Lema 2.1. Em uma

arvore T , quaisquer dois n

os s

ao conectados por um ´unico caminho.

Prova. Seja T uma ´arvore e u, v ∈ V (T ) n´os de T . Suponha por absurdo que existam

pelo menos dois caminhos P

e P

unindo u e v em T . Basta notar agora que a diferenc¸a

sim´etrica entre P

e P

, (P

∪ P

) \ (P

∩ P

), cont´em pelo menos um ciclo, um absurdo,

j´a que, por hip´otese, T ´e uma ´arvore. Logo, a propriedade segue. 

Pode-se ver que o lema anterior decorre naturalmente do fato de que uma ´arvore

n˜ao possui ciclos. Desta forma, ao se tomar um caminho maximal P em uma ´arvore T ,

pode-se deﬁnir como folhas os v´ertices extremidades de P . As folhas de T s˜ao os v´ertices

extremidades dos caminhos maximais de T , ou seja, todos os v´ertices de grau unit´ario.

Os n´os que n˜ao s˜ao folhas s˜ao chamados internos, j´a que tamb´em s˜ao internos a algum

caminho maximal em T. Al´em disso, pelo Lema 2.1, como o caminho P entre dois n´os u

e v de uma ´arvore T ´e bem deﬁnido, pode-se denotar uT v como simpliﬁcac¸˜ao para uP v.

Uma

arvore enraizada ´e uma ´arvore T com um n´o destacado r chamado raiz de

T . Numa ´arvore enraizada T , os descendentes de um n´o v ∈ V (T ) s˜ao os n´os u tais

que o caminho de u at´e a raiz r usa v. Os ﬁlhos de v s˜ao os descendentes de v que tˆem

distˆancia unit´aria a v. Pelo Lema 2.1, segue que se v n˜ao ´e raiz, ent˜ao existe apenas um

v´ertice u do qual v ´e ﬁlho; u ´e ent˜ao chamado pai de v. Se numa ´arvore T todos os n´os

tˆem no m´aximo dois ﬁlhos, diz-se que T ´e uma ´arvore bin

aria. Na verdade, as relac¸ ˜oes

de descendˆencia entre os n´os de uma ´arvore representam uma ordem, a ordem em

arvore

2.3.

Arvores

em V (T ) associada a T e r: u ≤ v, se u ∈ rT v. Pode-se ver que toda ordem em ´arvore

´e uma ordem parcial bem ordenada onde r ´e o elemento m´ınimo, toda folha da ´arvore ´e

um elemento maximal, as extremidades de uma aresta s˜ao compar´aveis e todo caminho

de r a um n´o v ´e uma cadeia, ou seja, um conjunto da forma {u : u ≤ v} onde todos os

elementos s˜ao compar´aveis entre si.

Propriedade Helly

Deﬁnic¸

ao 2 (Propriedade Helly). Uma fam´ılia {T

}

i∈I

de subconjuntos de um conjunto

T ´e dita como satisfazendo a propriedade Helly se J ⊆ I e T

∩ T

= ∅ para todo i, j ∈ J

implica que



j∈J

= ∅.

Lema 2.2. Uma fam

ılia {T

}

i∈I

de sub-

arvores de uma ﬂoresta T satisfaz a propriedade

Helly.

Prova. Suponha T

∩ T

= ∅ para todo i, j ∈ J ⊆ I. Considere trˆes n´os u, v e w em T .

Seja S o conjunto de ´ındices s tal que T

cont´em pelo menos dois destes trˆes n´os, e sejam

, P

e P

caminhos em T conectando u a v, v a w e u a w, respectivamente. Como

T ´e uma ´arvore, segue que P

∩ P

= ∅; mas cada T

(s ∈ S) cont´em um destes

caminhos, e logo:



s∈S

⊇ P

∩ P

= ∅.

O lema segue por induc¸ ˜ao no tamanho de J. Suponha ent˜ao que

[∀i, j ∈ J : T

∩ T

= ∅] =⇒



p∈J

= ∅

vale para toda fam´ılia J de sub-´arvores de tamanho no m´aximo k. Considere agora uma

nova fam´ılia de sub-´arvores J



= {T

, . . . , T

k+1

}. Pela hip´otese de induc¸˜ao, existem n´os

u, v e w tais que:

u ∈



i=1

, v ∈

k+1



i=2

, w ∈ T

∩ T

k+1

Pode-se notar que cada sub-´arvore T

cont´em pelo menos dois n´os entre u, v e w, e

logo, pelo exposto acima,



k+1

i=1

= ∅, o que conclui a prova. 

A relac¸ ˜ao entre ´arvores e a propriedade Helly permite inclusive uma caracterizac¸ ˜ao

daquelas em func¸˜ao desta:

Lema 2.3. Um grafo G

e uma

arvore se e somente se toda fam

ılia de caminhos em G

satisfaz a propriedade Helly.

Prova.

(⇒) Suponha que G seja uma ´arvore, e seja ent˜ao P = {P

}

i∈I

uma fam´ılia de caminhos

arbitr´aria em G. Sejam J

os subconjuntos de ´ındices de I com k elementos tais que

2. Conceitos e Preliminares

∩ P

= ∅, i, j ∈ J

. Para k = 2, claramente



q∈J

= ∅. Para k = 3, sejam

, P

e P

os elementos de J

, e v

, v

e v

n´os pertencentes a P

∩ P

, P

∩ P

, respectivamente. Suponha que P

∩ P

= ∅. Desta forma, pode-se ver

que v

 induz um ciclo em G, um absurdo, j´a que G ´e uma ´arvore; logo,



q∈J

= ∅.

A prova da condic¸ ˜ao necess´aria segue por induc¸ ˜ao em k. Suponha ent˜ao que



q∈J

= ∅, para todo J

⊆ I, p ≤ k, k < |I|, e seja P

k+1

um caminho em P tal que

k+1

∩ P

= ∅, para todo P

∈ J

. Suponha agora por absurdo, que



q∈J

∩ P

k+1

= ∅.

Sejam ent˜ao P

, . . . , P

os caminhos representantes dos ´ındices em J

. Pela hip´otese de

induc¸˜ao,



q=i

1≤q≤k

∩ P

k+1

= ∅ para 1 ≤ i ≤ k, e sejam, portanto, v

n´os arbitr´arios em

cada intersec¸˜ao



q=i

1≤q≤k

∩ P

k+1

e v

k+1

um n´o arbitr´ario em



1≤q≤k

. Se u e w s˜ao

extremidades de P

k+1

, suponha ainda, sem perda de generalidade, que os v´ertices u, v

. . ., v

, w aparecem nesta ordem em P

k+1

. Basta ver agora que existem dois caminhos

disjuntos unindo v

a v

: um composto por v

k+1

· · · P

k+1

k−1

k+1

, e outro

por v



k+1



, onde P



e P



s˜ao quaisquer caminhos P

, 1 ≤ i ≤ k com i = 1 e

i = k, respectivamente. Logo, tem-se um absurdo pela existˆencia de um ciclo unindo os

k + 1 v´ertices v

em G, o que leva a conclus˜ao de que



q∈J

∩ P

k+1

= ∅. Como a

propriedade Helly vale para qualquer fam´ılia arbitr´aria de sub-´arvores em G, equivale a

dizer que esta vale para todas.

(⇐) Considere P uma fam´ılia qualquer de caminhos em um grafo G = (V, E) que satis-

faz a propriedade Helly, e seja C = uP

u um ciclo em G, com u, v, w ∈ V , e

, P

∈ P. Como P

∩P

= {v}, P

∩P

= {w} e P

∩P

= {u}, e pela hip´otese de

suﬁciˆencia, deve-se ter P

∩ P

= ∅, e logo C n˜ao pode existir. Como tal propriedade

vale para todas as fam´ılias de caminhos em G, conclui-se que G n˜ao cont´em ciclos, sendo

uma ´arvore. 

2.4 Conectividade

A noc¸˜ao de conectividade em grafos j´a foi introduzida na Sec¸ ˜ao 2.2. No entanto, ´e ne-

cess´ario ainda deﬁnir um conceito para medic¸ ˜ao da conectividade, ou seja, de qu˜ao conexo

um grafo pode ser.

Deﬁnic¸

ao 3 (Grafo k-conexo e Conectividade). Um grafo G = (V, E) ´e k-conexo (para

k ∈ N) se |V | > k e G[V \ X] ´e conexo para todo X ⊆ V , |X| < k. O maior inteiro k

para o qual G ´e k-conexo ´e conhecido como a conectividade κ(G) de G. Por convenc¸ ˜ao,

κ(K

) = n − 1, n ≥ 1.

Em outras palavras, o conceito de conectividade implica que, em um grafo G,

quaisquer dois v´ertices n˜ao s˜ao separados por menos de κ(G) outros v´ertices.

Teorema 2.4 (Teorema de Menger). Seja G = (V, E) um grafo e A, B ⊆ V . O n

umero

ınimo de v

ertices separando A e B

e igual ao n

umero m

aximo de caminhos disjuntos

entre A e B.

2.5. Emparelhamentos

Deﬁnic¸

ao 4 (Grafo k-ligado). Um grafo G com pelo menos 2k v´ertices ´e dito k-ligado

se, para quaisquer 2k v´ertices s

, . . . , s

, t

, . . . , t

em G, este cont´em k caminhos

disjuntos P

= s

. . . t

, 1 ≤ i ≤ k.

Vale observar que a deﬁnic¸ ˜ao de grafo k-ligado implica na satisfac¸˜ao do Teorema de

Menger — e logo todo grafo k-ligado ´e tamb´em k-conexo — mas requer uma condic¸˜ao

mais forte: n˜ao apenas dois conjuntos de v´ertices devem ser conectados por k caminhos

disjuntos, mas devem existir caminhos distintos unindo cada par espec´ıﬁco s

-t

. Desta

forma, nem sempre a k-conectividade implica na k-ligac¸˜ao de um grafo. No entanto, uma

relac¸ ˜ao pode ser estabelecida entre os dois conceitos:

Teorema 2.5 (Jung [1970]; Larman e Mani [1970]). Existe uma func¸

ao f : N → N tal

que todo grafo f(k)-conexo

e k-ligado, para todo k ∈ N.

2.5 Emparelhamentos

Um emparelhamento em um grafo G = (V, E) ´e um subconjunto M ⊆ E de arestas

tal que os elementos de M n˜ao s˜ao adjacentes entre si. Cada par de extremidades de

cada aresta em M s˜ao ditas emparelhadas por M, e os v´ertices incidentes `as arestas em

M s˜ao ditos saturados, ou M-saturados. Um emparelhamento M ´e dito maximal em G

se nenhuma outra aresta em G pode ser acrescentada a M de modo a aument´a-lo; um

emparelhamento ´e dito m

aximo em G se n˜ao existe outro emparelhamento M



em G tal

que |M



| > |M|.

2.6 Menores

Seja e = (u, v) uma aresta de um grafo G = (V, E). Denota-se por G/e o grafo obtido

pela contrac¸

ao de e. A contrac¸ ˜ao de e em G resulta em um novo v´ertice v

em G/e, que

´e feito adjacente a todos os vizinhos de u e v em G. A deﬁnic¸ ˜ao formal segue.

Deﬁnic¸

ao 5 (Contrac¸ ˜ao). Uma contrac¸

ao (de arestas) ´e uma relac¸ ˜ao entre um grafo

G = (V, E), uma aresta e = (u, v) ∈ E e um novo grafo G



= (V



, E



), denotado

por G/e, onde:



= V {u, v} ∪ {v

}



= {(w, t) ∈ E : {w, t} ∩ {u, v} = ∅} ∪ {(v

, w) : (u, w) ∈ E − e ou (v, w) ∈ E − e}

onde v

´e o novo v´ertice em G



correspondente a e em G.

O conceito de contrac¸ ˜ao de arestas pode ser estendido para contrac¸

ao de v

ertices.

Seja U ⊆ V um subconjunto de v´ertices de G, deﬁnido acima. A contrac¸ ˜ao (de v´ertices)

de U em G ´e obtida pela contrac¸˜ao de todas as arestas no conjunto U

= {e = (u, v) :

u, v ∈ U}. Claramente, como todos os v´ertices em U s˜ao contra´ıdos atrav´es de arestas, U

2. Conceitos e Preliminares

induz um subgrafo conexo em G. O grafo obtido pela contrac¸ ˜ao de U em G ´e denotado

G/U. Vale notar que a contrac¸˜ao de uma aresta e = (u, v) pode ser vista como um

caso especial de uma contrac¸˜ao de v´ertices onde U = {u, v}. A contrac¸ ˜ao de um par

de v´ertices {u, v}, mesmo que n˜ao haja uma aresta entre eles, ´e tamb´em particularmente

chamada de identiﬁcac¸

ao dos v´ertices u e v em G; neste caso, o novo v´ertice obtido a

partir da contrac¸˜ao de {u, v} ´e denotado por u ∗ v.

Seja agora U = {U

}

1≤i≤k

, onde U

⊆ V para todo U

∈ U, uma fam´ılia

de subconjuntos de v´ertices de G tais que cada U

induz um subgrafo conexo em G.

Se o grafo X ´e obtido pela contrac¸ ˜ao em G de todos os subconjuntos em U (X =

G/U

/ · · · /U

), ent˜ao denota-se G = MX. Os elementos de U s˜ao chamados

ramos de X.

Deﬁnic¸

ao 6 (Menor de um grafo). Se um grafo G = MX ´e um subgrafo de Y , ent˜ao

diz-se que X ´e um menor de Y , e denota-se por X  Y .

Vale notar que, pela deﬁnic¸ ˜ao, todo subgrafo de um grafo ´e tamb´em seu menor (j´a

que G = MG para qualquer grafo G), assim como todo grafo ´e menor de si mesmo

(j´a que todo grafo ´e subgrafo de si mesmo). Pode-se notar tamb´em que todos os meno-

res de um grafo G podem ser obtidos a partir de uma s´erie de operac¸ ˜oes de eliminac¸˜ao

de v´ertices e arestas e contrac¸ ˜ao de arestas, o que se pode concluir pelo fato de que a

aplicac¸ ˜ao de qualquer uma destas operac¸ ˜oes a um grafo resulta em um menor deste, e

pela transitividade da relac¸˜ao de menor. De fato, uma conclus˜ao maior pode ser obtida:

Proposic¸

ao 2.6 (Diestel [1999]). A relac¸

ao de menor  estabelece uma ordem parcial

na classe de grafos ﬁnitos, ou seja, 

e reﬂexiva, anti-sim

etrica e transitiva.

Um conceito relacionado ao de menor ´e o de menor topol

ogico. Seja X um grafo e

G um grafo obtido de X pela substituic¸˜ao das arestas em X por caminhos independentes

entre as extremidades de cada aresta. G ´e obtido por subdivis

ao (de arestas) de X, sendo

denotado por G = T X. Analogamente, se G = T X ´e um subgrafo de Y , X ´e dito

um menor topol´ogico de Y . A Proposic¸ ˜ao 2.6 tamb´em se aplica para a relac¸ ˜ao menor

topol´ogico, sendo estabelecida uma ordem parcial na classe de grafos ﬁnitos pela relac¸ ˜ao

de menor topol´ogico. Tal caracter´ıstica pode ser melhor aceita se a relac¸ ˜ao entre menor e

menor topol´ogico for melhor deﬁnida:

Proposic¸

ao 2.7 (Diestel [1999]).

1. Para um grafo X, todo T X

e tamb

em um MX. Logo, qualquer menor topol

ogico

de um grafo

e tamb

em seu menor (convencional).

2. Se ∆(X) ≤ 3, ent

ao qualquer MX cont

em um T X. Logo, qualquer menor com

grau m

aximo no m

aximo 3 de um grafo

e tamb

em um menor topol

ogico deste.

Classes de grafos

Uma propriedade de grafos P ´e uma func¸˜ao que mapeia cada grafo (no dom´ınio de P )

a um valor verdadeiro ou falso; assume-se tamb´em que P ´e invariante com relac¸ ˜ao a

isomorﬁsmo. Uma classe de grafos C ´e um conjunto de grafos tal que cada elemento de

C satisfaz uma dada propriedade de grafos. Como exemplo, pode-se deﬁnir uma classe

2.7. Grafos Cordais

K onde cada elemento K de K ´e tal que todos os v´ertices de K s˜ao adjacentes entre si;

claramente, K ´e classe dos grafos completos.

Considere agora um conjunto ou classe de grafos H. A classe

Proib



(H) = {G : H  G para todo H ∈ H}

dos grafos que n˜ao tˆem elementos de H como menores ´e uma classe fechada com relac¸ ˜ao

a isomorﬁsmo. A classe tamb´em pode ser caracterizada pelos grafos em H, sendo estes

conhecidos como menores proibidos (ou exclu

ıdos). Se C = Proib



(H) como acima,

ent˜ao diz-se tamb´em que H ´e o conjunto de obstruc¸

ao da classe C.

Pela Proposic¸ ˜ao 2.6, a classe Proib



(H) ´e fechada tamb´em com relac¸ ˜ao a tomada

de menores — se G



 G ∈ Proib



(H), ent˜ao G



∈ Proib



(H). A proposic¸˜ao seguinte

vincula as duas deﬁnic¸ ˜oes:

Proposic¸

ao 2.8. Uma classe de grafos C pode ser expressa por menores proibidos se e

somente se C

e fechada com relac¸

ao a tomada de menores.

Como Diestel (2000) deﬁne, uma classe fechada com relac¸ ˜ao a tomada de menores

´e tamb´em chamada heredit

aria.

2.7 Grafos Cordais

Um grafo n˜ao direcionado G ´e chamado cordal se cada ciclo de tamanho estritamente

maior que 3 possui uma corda, ou seja, uma aresta unindo dois v´ertices n˜ao consecutivos

do ciclo. Como G n˜ao possui subgrafos induzidos isomorfos a C

, n > 3, o maior ciclo

de G ´e um triˆangulo, e logo G ´e tamb´em chamado triangulado.

Uma forma simples de caracterizar grafos cordais ´e atrav´es de separadores

minimais, como mostrado no lema a seguir.

Lema 2.9 (Dirac [1961]). G

e um grafo cordal se e somente se todo separador minimal

induz um subgrafo completo em G.

Prova.

(⇒) Suponha que S seja um uv-separador minimal de G = (V, E), sendo U e V as

componentes de G[V \ S] contendo u e v, respectivamente. Como S ´e minimal, todo

s ∈ S ´e adjacente pelo menos a algum v´ertice de U e a algum v´ertice de V . Logo,

para qualquer par x, y ∈ S, existem caminhos x, u

, . . . , u

, y e y, v

, . . . , v

, x, onde

∈ U, 1 ≤ i ≤ r e v

∈ V, 1 ≤ i ≤ t, que podem ser escolhidos de modo a ter o

menor comprimento poss´ıvel. Segue que x, u

, . . . , u

, y, v

, . . . , v

, x ´e um ciclo cujo

comprimento ´e no m´ınimo 4, implicando que este deve ter uma corda. Mas (u

, v

) ∈ E

pela deﬁnic¸˜ao de S, e (u

, u

) ∈ E e (v

, v

) ∈ E, pela minimalidade de r e t. Logo a

´unica corda poss´ıvel ´e (x, y). Como isso vale para qualquer par x, y ∈ S, segue que S

induz um subgrafo completo em G.

(⇐) Seja u, x, v, y

, y

, . . . , y

, u, k ≥ 1, um ciclo de G = (V, E). Como qualquer uv-

separador minimal deve conter os v´ertices x e y

, 1 ≤ i ≤ k, segue que (x, y

) ∈ E e

, y

) ∈ E, e logo o ciclo sempre ter´a uma corda. 

2. Conceitos e Preliminares

Um outro resultado auxiliar envolvendo separadores minimais pode ser encontrado

a partir da observac¸ ˜ao de que r = t = 1 na prova da condic¸ ˜ao necess´aria do lema acima, e

logo, para qualquer par de v´ertices x, y ∈ S existem v´ertices em U e V que s˜ao adjacentes

tanto a x como a y. O resultado auxiliar segue de uma condic¸˜ao mais forte deste fato:

Lema 2.10. Para qualquer separador minimal S de um grafo cordal G = (V, E), existe

um v

ertice v em cada componente conexa de G[V \ S] tal que S ⊆ N

(v).

Prova. Seja G = (V, E) um grafo cordal e S um separador minimal de G. A prova

´e por induc¸˜ao no tamanho de S. Se S = {s} ent˜ao o lema ´e trivial. Seja ent˜ao S =

, . . . , s

} e suponha que existe um v´ertice v tal que S − s

⊂ N

(v). Se s

∈ N

(v)

a prova est´a completa. Suponha ent˜ao o contr´ario, e logo deve existir um outro v´ertice

u pertencente a mesma componente de v e adjacente a s

(do contr´ario S n˜ao seria um

separador minimal). Assuma ainda, sem perda de generalidade, que u ´e adjacente a v.

Pelo Lema 2.9, s

´e adjacente a todos os outros v´ertices de S. Para cada s

, 1 ≤ i ≤

k − 1, C

= s

, v, u, s

, s

 induz um ciclo em G, e logo, como G ´e cordal e (v, s

) ∈ E,

deve existir uma corda unindo u e s

. Portanto, S ⊆ N

(u) e a prova est´a conclu´ıda. 

Uma outra caracterizac¸ ˜ao de grafos cordais, de aspecto mais algor´ıtmico, envolve

uma enumerac¸ ˜ao especial dos v´ertices do grafo. Para tanto, novos conceitos s˜ao ne-

cess´arios. Um v´ertice v de G ´e chamado simplicial se sua vizinhanc¸a N

(v) induz um

subgrafo completo de G, ou seja, N

(v) ´e uma clique. V´ertices simpliciais tˆem grande

aplicac¸ ˜ao na elaborac¸ ˜ao de algoritmos para grafos cordais. Antes de apresentar uma

caracterizac¸ ˜ao algor´ıtmica desta classe de grafos, um outro resultado auxiliar ´e necess´ario.

Lema 2.11 (Dirac [1961]). Todo grafo cordal G tem um v

ertice simplicial. Al

em disso,

se G n

e completo, ent

ao ele tem dois v

ertices simpliciais n

ao adjacentes.

Prova. Se G ´e completo, o lema torna-se trivial. Suponha ent˜ao que G = (V, E) possui

dois v´ertices u e v n˜ao adjacentes e que, por induc¸˜ao, o lema vale para todos os grafos com

menor cardinalidade de v´ertices que G. Considere agora S um separador minimal para u

e v, e as duas componentes (conexas) U e V de G[V \S] contendo u e v, respectivamente.

Pelo crit´erio de induc¸˜ao, ou G[U ∪S] tem dois v´ertices n˜ao adjacentes e simpliciais,

dos quais um deve estar em U, j´a que S induz um subgrafo completo (Lema 2.9), ou

G[U ∪ S] ´e completo e logo qualquer v´ertice deste ´e simplicial. Conseq¨uentemente, como

(U) ⊆ U ∪ S, todo v´ertice simplicial em G[U ∪ S] o ´e tamb´em em G. Como o mesmo

argumento aplica-se para V , G possui pelo dois v´ertices simpliciais, o que conclui a prova.



Usando o resultado do Lema 2.11, Fulkerson e Gross (1965) apud (Golumbic 1980)

sugeriram um procedimento iterativo para reconhecer grafos cordais: repetidamente loca-

lize um v´ertice simplicial e elimine-o do grafo at´e que ou nenhum v´ertice permanec¸a —

e o grafo seja cordal — ou nenhum v´ertice seja simplicial, e logo o grafo n˜ao ´e cordal.

Formalmente, a eliminac¸ ˜ao iterativa de v´ertices simpliciais pode ser representada por um

esquema enumerativo.

Sejam ent˜ao G = (V, E) um grafo n˜ao direcionado e σ = [v

, v

, . . . , v

] um orde-

namento de v´ertices de V . Diz-se que σ ´e um esquema perfeito de eliminac¸

ao de v

ertices,

2.8. L

ogica Mon

adica de Segunda Ordem

ou simplesmente um esquema perfeito, se cada v

´e um v´ertice simplicial do subgrafo

induzido G[{v

, . . . , v

}]. O seguinte resultado formaliza o procedimento de Fulkerson e

Gross:

Lema 2.12. G

e um grafo cordal se e somente se G admite um esquema de eliminac¸

perfeito. Al

em disso, qualquer v

ertice simplicial pode iniciar um esquema perfeito.

Prova.

(⇒) Pelo Lema 2.12, se G = (V, E) ´e cordal, ent˜ao este possui um v´ertice simplicial x.

Basta agora notar que, por induc¸˜ao, G[V − x] ´e ainda cordal e deve admitir um esquema



de eliminac¸˜ao perfeito. Um esquema σ perfeito para G ´e simplesmente σ = [x] ∪ σ



ou seja, a junc¸˜ao de x a σ



como preﬁxo.

(⇐) Sejam C um ciclo de G e x um v´ertice de C de menor ´ındice em um esquema

perfeito. Como |N

(x) ∩ C| ≥ 2, a simplicialidade de x garante uma corda em C. 

Os grafos cordais possuem caracter´ısticas especiais que ser˜ao melhor exploradas no

pr´oximo cap´ıtulo. E alguns casos, ´e interessante ent˜ao obter um grafo cordal, supergrafo

de um grafo original, acrescentando arestas a este. Um grafo H = (V, E



) ´e dito ent˜ao

uma cordalizac¸

ao de um grafo G = (V, E) se G ´e um subgrafo gerador de H e H ´e

cordal; neste caso, E



\ E ´e uma triangulac¸

ao de G resultando em H. H ´e dito uma

k-cordalizac¸ ˜ao de G se ´e uma cordalizac¸ ˜ao cujo tamanho da maior clique ´e no m´aximo k.

arvores

Deﬁnic¸

ao 7 (k-´arvore). Uma k-

arvore ´e deﬁnida recursivamente como se segue: uma

arvore com k + 1 v´ertices consiste de uma clique com k + 1 v´ertices (k + 1-clique);

dada uma k-

arvore T

com n v´ertices, n > k + 1, constr´oi-se uma k-

arvore com n + 1

v´ertices acrescentando um novo v´ertice v a T

e fazendo-o adjacente a cada v´ertice de

uma k-clique de T

e n˜ao adjacente aos n − k v´ertices restantes. Uma k-

arvore parcial ´e

um subgrafo de uma k-´arvore.

Lema 2.13. Uma k-

arvore

e um grafo cordal.

Prova. Seja T

uma k-´arvore com n v´ertices. Pela deﬁnic¸ ˜ao de k-´arvore, sempre existe

um v´ertice v

adjacente a uma k-clique, e logo, simplicial. Com a retirada de v

de T

tem-se ainda uma k-´arvore T

n−1

com n − 1 v´ertices, de onde se pode retirar outro v´ertice

simplicial (e adjacente a outra k-clique). Pode-se perceber ent˜ao que n − k v´ertices

simpliciais podem ser retirados de T

de forma iterada. Como os outros k v´ertices res-

tantes s˜ao simpliciais, tem-se que σ = [v

, v

, . . . , v

] constitui um esquema perfeito de

eliminac¸˜ao, e logo T

´e cordal. 

2.8 L

ogica Mon

adica de Segunda Ordem

Deﬁnic¸

ao 8 (Grafo terminal). Um grafo terminal ´e uma tripla (V, E, X), onde (V, E) ´e

um grafo simples e X ⊆ V ´e um conjunto ordenado de l v´ertices, 0 ≤ l ≤ |V |, denotado

2. Conceitos e Preliminares

por X = [x

, . . . , x

]. Os v´ertices em X s˜ao denominados terminais, e os v´ertices em

V \ X, internos.

Um grafo terminal G = (V, E, X) com l terminais ´e tamb´em chamado l-terminal,

e x

∈ X, 1 ≤ i ≤ l, ´e denominado o i-´esimo terminal de G. O conjunto de v´ertices

terminais de G ´e denotado por Term(G) = X — e logo, se G ´e l-terminal, |Term(G)| = l

— e o conjunto de v´ertices internos de G ´e denotado por Int(G) = V \X. Um grafo termi-

nal G ´e dito aberto se n˜ao existem arestas entre os terminais de G. De modo semelhante

a grafos convencionais, diz-se que dois grafos terminais G

= (V

, E

, [x

, . . . , x

]) e

= (V

, E

, [y

, . . . , y

]) s˜ao isomorfos se l = p e se existe um isomorﬁsmo entre



= (V

, E

) e G



= (V

, E

) mapeando cada x

a y

, 1 ≤ i ≤ l. O isomorﬁsmo entre

grafos terminais ´e denotado da mesma forma que em grafos convencionais, ou seja, se G

e G

s˜ao isomorfos, escreve-se G

≈ G

Deﬁnic¸

ao 9 (Operac¸ ˜ao de junc¸ ˜ao terminal). A operac¸

ao de junc¸

ao terminal ⊕ mapeia

dois grafos terminais G e H com o mesmo n´umero de terminais em um grafo simples

G ⊕ H tomando a uni˜ao de G e H e identiﬁcando os terminais correspondentes, ou seja,

identiﬁcando o i-´esimo terminal de G com o i-´esimo terminal de H e removendo arestas

m´ultiplas.

Deﬁnic¸

ao 10 (Propriedade de ´ındice ﬁnito). Seja P uma propriedade de grafos, e l um

n´umero natural. Para grafos l-terminais G

e G

, deﬁne-se uma relac¸ ˜ao de equivalˆencia

∼

P,l

da seguinte forma:

∼

P,l

⇔ para todo grafo l-terminal H : P (G

⊕ H) ⇔ P (G

⊕ H).

A propriedade P ´e dita de

ındice ﬁnito se, para todo l, ∼

P,l

tem ﬁnitas classes de

equivalˆencia.

De acordo com Courcelle (1990), uma classe de grafos cuja propriedade ´e de ´ındice

ﬁnito ´e chamada de estado ﬁnito. Ele deﬁniu uma ampla classe de grafos de estado ﬁ-

nito. Nos pr´oximos cap´ıtulos a aplicac¸ ˜ao desse tipo de classe ﬁcar´a mais clara, assim

como a sua grande vantagem computacional. Courcelle (1990) deﬁniu uma linguagem

para caracterizac¸ ˜ao de tais classes:

Deﬁnic¸

ao 11 (L´ogica Mon´adica de Segunda Ordem para grafos). A L

ogica Mon

adica

de Segunda Ordem (LMSO) para grafos G = (V, E) consiste de uma linguagem na qual

os predicados podem ser constru´ıdos usando:

1. Os conectivos l´ogicos ∧ (e), ∨ (ou), ¬ (negac¸ ˜ao), =⇒ (implica) e ⇔ (se e somente

se).

2. Vari´aveis que podem ser vari´aveis de v´ertices (com dom´ınio V ), de arestas (com

dom´ınio E), de conjuntos de v´ertices (com dom´ınio P(V ), a fam´ılia de todos os

subconjuntos de V ), e de conjuntos de arestas (com dom´ınio P(E), a fam´ılia de

todos os subconjuntos de E).

3. Os quantiﬁcadores existencial (∃) e universal (∀).

4. As seguintes relac¸ ˜oes bin´arias:

2.8. L

ogica Mon

adica de Segunda Ordem

• v ∈ W , onde v e W s˜ao vari´aveis de v´ertice e conjunto de v´ertices,

respectivamente;

• e ∈ F , onde e e F s˜ao vari´aveis de aresta e conjunto de arestas,

respectivamente;

• “v e w s˜ao adjacentes em G”, onde v e w s˜ao vari´aveis de v´ertices;

• “v ´e incidente a e em G”, onde v e e s˜ao vari´aveis de v´ertice e aresta,

respectivamente;

• igualdade entre vari´aveis do mesmo tipo.

Seja R um predicado LMSO tal que R n˜ao cont´em vari´aveis livres. Ent˜ao diz-se

que um grafo G satisfaz R se R resulta em verdadeiro para G. Um propriedade de grafos

P ´e MS-deﬁn

ıvel se existe um predicado R deﬁnido em LMSO para grafos sem vari´aveis

livres tal que, para todo grafo G, P (G) vale se e somente se G satisfaz R. Uma classe de

grafos ´e MS-deﬁn´ıvel se sua propriedade ´e MS-deﬁn´ıvel.

Como exemplo, a ﬁm de esclarecer melhor o conceito de MS-deﬁnibilidade, pode-

se mostrar que a classe de grafos bipartites ´e MS-deﬁn´ıvel. Para tanto, considere o

seguinte predicado LMSO R:

R = ∃U∃W (U ⊆ V ) ∧ (W ⊆ V ) ∧ (U ∩ W = ∅) ∧ (U ∪ W = V )

∧



∀u∀v



(u ∈ V ) ∧ (v ∈ V ) ∧ (u e v s˜ao adjacentes)



=⇒



(u ∈ U) ⇔ (v ∈ W )



Vale notar que as operac¸ ˜oes de continˆencia, intersec¸ ˜ao e uni˜ao entre conjuntos n˜ao

s˜ao deﬁnidas na linguagem, e constam na express˜ao de R acima apenas por simplicidade.

No entanto, pode-se deﬁnir U ⊆ W como ∀u(u ∈ U) =⇒ (u ∈ W ), e expressar:

U ∩ W = ∅ por ∀u



(u ∈ U) ∨ (u ∈ W )



=⇒ ¬



(u ∈ U) ∧ (u ∈ W )



U ∪ W = V por ∀u



(u ∈ U) ∨ (u ∈ W )



=⇒ (u ∈ V ).

Na express˜ao de R, pode-se ver que U e W representam classes de uma partic¸˜ao de

V , e logo, G ´e bipartite se e somente se G satisfaz R. Como conseq¨uˆencia direta, a propri-

edade P , “ser bipartite”, ´e MS-deﬁn´ıvel. Courcelle (1990) mostrou que toda propriedade

MS-deﬁn´ıvel caracteriza uma classe de grafos de estado ﬁnito.

A deﬁnic¸ ˜ao de propriedade de grafos pode ainda ser estendida de modo a envol-

ver outras vari´aveis. Seja ent˜ao P uma propriedade de grafos estendida com vari´aveis G,

, . . . , X

, onde G ´e um grafo e, para cada i, 1 ≤ i ≤ r, X

∈ D

para algum dom´ınio

. Ent˜ao, analogamente, diz-se que P (G, X

, . . . , X

) ´e MS-deﬁn´ıvel se existe um pre-

dicado LMSO para grafos R(Y

, . . . , Y

), com vari´aveis livres Y

, . . . , Y

, tal que, para

todo grafo G e vari´aveis X

, . . . , X

, P vale se e somente se G satisfaz R(X

, . . . , X

2. Conceitos e Preliminares

Como exemplo, considere agora X

e X

subconjuntos de v´ertices de um grafo

G. A propriedade “ser bipartite com classes X

e X

” para G, P (G, X

, X

), ´e ent˜ao

MS-deﬁn´ıvel se P (G, X

, X

) vale se e somente se G satisfaz um predicado LMSO com

parˆametros Y

e Y

. Seja R(Y

, Y

) o predicado LMSO deﬁnido por:

R(Y

, Y

) = (Y

∩ Y

= ∅) ∧ (Y

∪ Y

= V (G)) ∧



∀u∀v



(u ∈ V (G)) ∧ (v ∈ V (G)) ∧ (u e v s˜ao adjacentes)



=⇒



(u ∈ Y

) ⇔ (v ∈ Y

)



Pode-se ver que, para quaisquer G, X

e X

tais que G ´e bipartite com classes X

, G satisfaz R(X

, X

). Logo, P (G, X

, X

) vale, e ´e MS-deﬁn´ıvel.

Cap´ıtulo 3

Decomposic¸

ao em

Arvore

3.1 Introduc¸

Muitos problemas de otimizac¸˜ao combinat´oria podem ser modelados e, conseq¨uente-

mente, tratados por grafos. Dentre as diversas vantagens desta abordagem, uma das

principais reside no fato de que, para determinadas classes de grafos, algoritmos es-

pec´ıﬁcos podem ser projetados de modo a resolver o problema com complexidade

computacional bem menor, polinomial. Ou seja, como a complexidade destes problemas ´e

exponencial, a restric¸ ˜ao do problema a certos tipos de grafos o torna trat´avel praticamente.

Dentre as classes de grafos empregadas para tal estrat´egia, destacam-se as

arvores.

Uma ´arvore n˜ao possui ciclos, e logo tal caracter´ıstica mostra-se extremamente favor´avel

para aplicac¸ ˜ao de algoritmos recursivos, por exemplo. Basta notar, por exemplo, que di-

versas estrat´egias gerais de resoluc¸ ˜ao buscam o espac¸o vi´avel de soluc¸ ˜oes atrav´es de uma

´arvore, como no caso da programac¸˜ao dinˆamica e da divis˜ao e conquista; al´em disso, al-

goritmos comuns de busca em grafos, como busca em largura e busca em profundidade,

percorrem o grafo formando uma ´arvore.

Infelizmente, a maior parte dos problemas n˜ao s˜ao modelados em ´arvores, o que

inviabiliza tal abordagem. Uma estrat´egia interessante seria ent˜ao estender o tratamento

natural dado `as ´arvores para outras classes de grafos, e, ﬁnalmente, para todos os grafos.

Claramente, ´e esperado que, na medida em que o grafo seja menos semelhante a uma

´arvore, a complexidade de um algoritmo para este grafo seja maior, mais pr´oxima da

exponencial; por outro lado, a complexidade poder´a ser polinomial, ou mesmo linear,

qu˜ao mais similar a uma ´arvore o grafo seja.

A Decomposic¸

ao em

Arvore ´e uma abordagem que tem essa ﬁnalidade: estabelecer

relac¸ ˜oes estruturais num grafo de forma que este assemelhe-se a uma ´arvore. Constitui-se

da relac¸ ˜ao entre subgrafos de um grafo G e n´os de uma ´arvore de modo que o con-

junto de arestas de G seja particionado numa estrutura em ´arvore. O conceito formal foi

apresentado por (Robertson e Seymour 1986):

3. Decomposic¸

ao em

Arvore

Deﬁnic¸

ao 12 (Decomposic¸˜ao em ´arvore). Uma decomposic¸

ao em

arvore (DEA) D de

um grafo G = (V, E) ´e um par (X = {X

: i ∈ I}, T = (I, F )), sendo {X

: i ∈ I}

uma fam´ılia de subconjuntos de V , um para cada n´o de T , e T uma ´arvore, tais que:

[P1]



i∈I

= V ;

[P2] para toda aresta (v, w) ∈ E, existe um i ∈ I tal que v ∈ X

e w ∈ X

;

[P3] para todo i, j, k ∈ I, se j est´a no caminho entre i e k em T , ent˜ao X

∩ X

⊆ X

A fam´ılia X compreende as partes da decomposic¸ ˜ao em ´arvore, ou seja, cada X

i ∈ I. As duas primeiras restric¸ ˜oes implicam que X compreende uma fam´ılia de subgra-

fos de G — sendo cada subgrafo obtido pela induc¸ ˜ao de cada parte em G — enquanto

que a ´ultima restric¸˜ao garante a estrutura em ´arvore da decomposic¸˜ao. Isto pode n˜ao ser

imediato, ent˜ao, por enquanto, pode-se substituir [P3] por uma restric¸ ˜ao equivalente:

[P3’] para todo v ∈ V , T

= {i ∈ I : v ∈ X

} induz uma ´arvore.

Como cada v´ertice de um grafo ´e relacionado a uma ´arvore, claramente a uni˜ao de

todos os v´ertices resulta numa ´arvore. Embora esta propriedade de estrutura em ´arvore

seja mais clara quando [P3’] ´e considerada, [P3] ´e bem mais ´util e direta quando se deseja

construir decomposic¸ ˜oes em ´arvore. A equivalˆencia entre as duas restric¸ ˜oes ´e mostrada a

seguir.

Lema 3.1. As restric¸

oes [P3] e [P3’] da deﬁnic¸

ao de decomposic¸

ao em

arvore s

equivalentes.

Prova.

([P3’] ⇒ [P3]). Sejam i, j ∈ I n´os de T . Se X

∩X

= ∅, ent˜ao [P3] segue, j´a que qualquer

, k ∈ iT j, cont´em a intersec¸ ˜ao entre X

e X

. Suponha ent˜ao que X

∩ X

= ∅, e seja

v ∈ X

∩ X

. Claramente, por [P3’], a ´arvore T

cont´em o caminho iTj. Logo, para todo

k ∈ iT j, segue que v ∈ X

. Pelo mesmo motivo, todo v´ertice pertencente a intersec¸ ˜ao

entre X

e X

pertence a todo X

, k ∈ iT j, e logo X

⊇ X

∩ X

([P3] ⇒ [P3’]). Seja v ∈ V e T

= {i ∈ I : v ∈ X

}. Se |T

| = 1, ent˜ao T

´e um grafo

trivial, e logo uma ´arvore; se T

= {i, j}, ent˜ao, por [P3], e como X

∩ X

= ∅, existe

uma aresta entre i e j, e logo T

´e uma ´arvore. Suponha ent˜ao que |T

| ≥ 3, e sejam i, j

e k v´ertices em T

. Pela deﬁnic¸ ˜ao de T

, v ∈ X

∩ X

, e seja X

, p ∈ T

, tal que

⊇ X

∩ X

. Segue ent˜ao por [P3] que quaisquer caminhos unindo n´os diferentes

de {i, j, k} se interceptam em p. Logo, qualquer fam´ılia de caminhos em T

satisfaz a

propriedade Helly, e, pelo Lema 2.3, T

´e uma ´arvore. 

Na verdade, para cada v ∈ V , T

induz uma sub-

arvore de T . Formalmente, denota-

se ent˜ao por T

a sub-´arvore de T induzida por v ∈ V em D, T

= {i ∈ I : v ∈

Pode-se perceber tamb´em que, a partir da deﬁnic¸ ˜ao, v´arias decomposic¸ ˜oes podem

ser obtidas para o mesmo grafo. A Figura 3.1 ilustra algumas decomposic¸ ˜oes em ´arvore.

Pode-se ver que estas variam de acordo com o tamanho da ´arvore T e dos subconjuntos

. O tamanho da ´arvore pode n˜ao ser t˜ao decisivo para julgar a estrutura em ´arvore do

3.1. Introduc¸

grafo, j´a que a Deﬁnic¸ ˜ao 12 permite a inclus˜ao de subconjuntos vazios, e logo permite

tamb´em a inclus˜ao de n´os redundantes na ´arvore.

(b)(a) (c)

Figura 3.1. Exemplos de decomposic¸˜ao em ´arvore.

Claramente todo grafo G admite uma decomposic¸˜ao trivial em ´arvore, (X =

{V }, T = ({i}, ∅)), como a decomposic¸˜ao ilustrada na Figura 3.1(a). Al´em disso, ´e

poss´ıvel a existˆencia de dois n´os adjacentes i e j em uma decomposic¸˜ao em ´arvore D

para G tais que X

⊆ X

. Pode-se ver que X

´e redundante, pois pode-se obter uma nova

decomposic¸˜ao em ´arvore D



a partir da identiﬁcac¸˜ao de i e j em T . Por outro lado, se uma

decomposic¸˜ao em ´arvore D ´e tal que quaisquer n´os adjacentes i e j satisfazem X

⊆ X

e X

⊆ X

, ent˜ao D ´e dita uma boa decomposic¸˜ao em ´arvore. Decomposic¸ ˜oes triviais e

n˜ao boas s˜ao muito pouco usadas na pr´atica, tendo mais aplicac¸˜ao como base de induc¸ ˜ao

ou construc¸ ˜oes usadas nas provas de alguns resultados. Suas presenc¸as neste texto est˜ao

limitadas a tais situac¸ ˜oes, sendo as decomposic¸ ˜oes boas bem mais ´uteis.

Mesmo considerando decomposic¸ ˜oes boas, o tamanho das partes pode, no entanto,

ser ainda signiﬁcativo ao se avaliar a similaridade do grafo com uma ´arvore: qu˜ao menores

os tamanhos dos subconjuntos X

mais semelhante ´e o grafo a uma ´arvore. O efeito dos

tamanhos das partes ﬁca mais evidente ao se comparar as Figuras 3.1(b) e 3.1(c). Deste

modo, uma medida quantitativa de similaridade se faz desej´avel, e pode agora ser deﬁnida.

Deﬁnic¸

ao 13 (Largura em ´arvore). A largura em

arvore de uma decomposic¸

ao D =

(X = {X

: i ∈ I}, T = (I, F )) ´e deﬁnida como LA

(D) = max

i∈I

{|X

| − 1}. A

largura em

arvore de um grafo G ´e a largura m

ınima dentre todas as decomposic¸ ˜oes em

´arvore poss´ıveis de G, ou seja, LA(G) = min{LA

(D) : D ´e uma decomposic¸˜ao em

´arvore de G}.

3. Decomposic¸

ao em

Arvore

A menos que haja confus˜ao na notac¸˜ao, pode-se tamb´em referir `a largura de uma

decomposic¸˜ao em ´arvore D de um grafo G simplesmente como LA(D). Como exemplo,

as larguras em ´arvore das decomposic¸ ˜oes das Figuras 3.1(a), 3.1(b) e 3.1(c) s˜ao, respecti-

vamente, 10, 5 e 2. A largura em ´arvore de um grafo procura estabelecer uma medida de

similaridade a uma ´arvore para o grafo. Se a largura em ´arvore de um grafo G ´e pequena,

ent˜ao pode-se construir uma decomposic¸ ˜ao em ´arvore para G com partes pequenas, e logo

G se assemelhar´a grosseiramente a uma ´arvore. Na verdade, se LA(G) for pequeno o su-

ﬁciente, G pode inclusive ser uma ´arvore. Uma decomposic¸˜ao em ´arvore D de um grafo

G que realiza a largura de G, ou seja, tal que LA

(D) = LA(G), ´e dita m

ınima, ou

otima.

De modo a simpliﬁcar a notac¸ ˜ao ao longo do texto, (X , T ) ser´a usado como

simpliﬁcac¸˜ao para (X = {X

: i ∈ I}, T = (I, F )) sempre que n˜ao ocorrer risco de am-

big¨uidade. Nas pr´oximas sec¸ ˜oes deste cap´ıtulo ser˜ao abordadas algumas caracter´ısticas

de grafos com largura em ´arvore pequena, e outras que impedem alguns grafos de terem

largura limitada. Antes, no entanto, algumas propriedades gerais de decomposic¸ ˜oes em

´arvore s˜ao ´uteis, e algumas vezes necess´arias, para melhor compreens˜ao do que vir´a.

3.2 Algumas propriedades de DEA

A primeira propriedade de uma decomposic¸˜ao em ´arvore D = (X , T ) de um grafo G

faz com que G herde a conectividade minimal de T pelas partes de D: assim como cada

aresta (i, j) ´e uma ponte em T , X

∩ X

´e um corte em G.

Propriedade 1. Sejam G = (V, E) um grafo e D = (X = {X

: i ∈ I}, T = (I, F ))

uma decomposic¸˜ao em ´arvore de G. Seja e = (i, j) uma aresta qualquer de T , e sejam

e T

as componentes de T − e contendo i e j, respectivamente. Ent˜ao X

∩ X

separa



t∈T

de U





∈T



em G.

Prova. Como (i, j) ´e uma ponte em T, ent˜ao qualquer caminho unindo t ∈ T

e t



∈ T

passa por (i, j). Portanto, pela deﬁnic¸ ˜ao de decomposic¸˜ao em ´arvore, U

∩ U

⊆ X

∩ X

Basta mostrar agora que n˜ao existem arestas (u

, u

) com u

∈ U

e u

∈ U

para que

∩ X

seja de fato um U

-separador. Suponha ent˜ao que exista uma aresta (u

, u

Pela deﬁnic¸ ˜ao de DEA, deve existir um t ∈ T tal que u

, u

∈ X

. Mas, pela escolha de

e u

, t n˜ao pode pertencer nem a T

nem a T

, caso contr´ario existiria um ciclo em T ,

um absurdo. A Figura 3.2 ilustra a propriedade. 

Ao se considerar a largura em ´arvore de um grafo G, ´e natural questionar qual a sua

inﬂuˆencia nas larguras em ´arvore de grafos derivados de G e com menos v´ertices que G.

As propriedades seguintes abordam tais relac¸ ˜oes entre G e seus subgrafos, componentes

e menores.

Propriedade 2. Seja G um grafo e H um subgrafo de G. Ent˜ao LA(H) ≤ LA(G).

Prova. Seja D = (X , T = (I, F )) uma decomposic¸˜ao em ´arvore que realiza a largura

em ´arvore de G — ou seja, D tem largura m´ınima. Considere agora a fam´ılia W = {W =

X \ (V (G) \ V (H)) : X ∈ X }. Claramente, como X cobre V (G), assim tamb´em W

cobre V (H), e logo, como D ´e uma decomposic¸˜ao em ´arvore de G, D



= (W, T ) ´e

3.2. Algumas propriedades de DEA

∩ X

Figura 3.2. Uma aresta (i, j) de uma decomposic¸˜ao em ´arvore de um grafo G corresponde a um separador

em G.

uma decomposic¸˜ao em ´arvore de H (D



´e tamb´em chamada uma subdecomposic¸

ao em

´arvore de G limitada a H). Como para todo i ∈ I, W

⊆ X

, LA(D



) ≤ LA(D), e

conseq¨uentemente, pela minimalidade de D, LA(H) ≤ LA(G). A nova decomposic¸ ˜ao

em ´arvore pode ser vista na Figura 3.3. 



= ∅



Figura 3.3. Decomposic¸˜ao em ´arvore de um subgrafo H de G, destacado por arestas em negrito.

Propriedade 3. A largura em ´arvore de um grafo G ´e a m´axima largura em ´arvore das

componentes de G.

Prova. Sejam C

, . . . , C

as r componentes de G = (V, E), e D

, . . . , D

decomposic¸ ˜oes em ´arvore de largura m´ınima de cada componente, respectivamente. Para

cada decomposic¸ ˜ao D

= {X

, T

= (I

, F

)}, selecione aleatoriamente um v´ertice

∈ I

. Considere agora a decomposic¸˜ao em ´arvore obtida pela uni˜ao das partes em

cada X

e pela adic¸˜ao de uma parte X

∗

= ∅ com um n´o correspondente i

∗

adjacente a

cada i

, ou seja, D

∗

= (X

∗

, T

∗

= (I

∗

, F

∗

)), onde:

∗





j=1



∪ {X

∗

3. Decomposic¸

ao em

Arvore

∗





j=1



∪ {i

∗





j=1



∪ {(i

∗

, i

) : i

algum v´ertice em I

, 1 ≤ j ≤ r}).

A Figura 3.4 ilustra tal decomposic¸˜ao. A largura de D

∗

pode ser ent˜ao facilmente

encontrada:

LA(D

∗

) = max

i∈I

∗

{|X

| − 1} = max

1≤j≤r

{max

i∈I

{|X

| − 1}} = max

1≤j≤r

{LA(D

)}

e logo, pela minimalidade de cada D

, LA(G) = max

1≤j≤r

{LA(C

)}, e o lema segue. 

∗

Figura 3.4. Decomposic¸˜ao em ´arvore de um grafo usando suas componentes.

Propriedade 4. Seja G um grafo e H um menor de G. Ent˜ao LA(H) ≤ LA(G).

Prova. Por deﬁnic¸˜ao, H pode ser obtido de G por uma s´erie de contrac¸ ˜oes ou retiradas

de arestas, ou eliminac¸ ˜oes de v´ertices. Se apenas as duas ´ultimas operac¸ ˜oes foram aplica-

das, H ´e um subgrafo de G, e, pela Propriedade 2, o resultado segue. Basta ent˜ao mostrar

que a largura em ´arvore de um grafo n˜ao aumenta com a contrac¸ ˜ao de arestas deste.

Seja ent˜ao D = (X , T) uma decomposic¸˜ao em ´arvore de G. Considere ent˜ao e =

(u, v) uma aresta de G a ser contra´ıda como operac¸ ˜ao para obtenc¸ ˜ao de H, e seja w o novo

v´ertice adicionado a G



, o grafo obtido de G pela contrac¸ ˜ao de e. Uma nova decomposic¸˜ao

em ´arvore D



= (X



, T ) pode ent˜ao ser deﬁnida, onde:



= {X \ {u, v} ∪ {w} : X ∈ X , u ∈ X ou v ∈ X} ∪ {X : X ∈ X , u ∈ X e v ∈ X}.

3.2. Algumas propriedades de DEA

Claramente, como H tem menos v´ertices que G, LA



) ≤ LA

(D). Como a

desigualdade aplica-se a qualquer decomposic¸˜ao em ´arvore e qualquer menor de G, em

particular deve valer tamb´em para a decomposic¸˜ao em ´arvore m´ınima de G, e logo segue

que LA(H) ≤ LA(G), H um menor de G. Na Figura 3.5 pode-se ver uma decomposic¸˜ao

em ´arvore de um menor de um grafo G, obtido pela contrac¸ ˜ao das arestas em negrito. 

G H



= X



Figura 3.5. Decomposic¸˜ao em ´arvore de um menor H de um grafo G, obtido pela contrac¸˜ao das arestas

em negrito.

A vantagem no uso das trˆes propriedades acima ´e que, al´em da determinac¸˜ao de um

limitante superior para a largura em ´arvore de um grafo obtido a partir de outro — por

operac¸ ˜oes de subgrafo, menor e componentes — as decomposic¸ ˜oes em ´arvore dos grafos

resultantes podem tamb´em ser obtidas, como mostram as provas das propriedades. Al´em

disso, pode-se de fato obter uma decomposic¸˜ao em ´arvore para qualquer grafo a partir de

um menor deste por contrac¸ ˜ao, como mostra o lema seguinte.

Lema 3.2. Sejam G = (V, E) um grafo, H um menor de G pela contrac¸

ao dos sub-

conjuntos disjuntos de v

ertices U

, . . . , U

em G e D = (X , T ) uma decomposic¸

ao em

arvore de H. Seja f : V (H) → P(V (G)) uma func¸

ao tal que f(v) = {v} se v ∈



i=1

e f(v) = U

se v ∈ U

para algum i, 1 ≤ i ≤ r. Ent



= (W = {W

: W



v∈X

f(v), X

∈ X }, T )

e uma decomposic¸

ao em

arvore para G.

Prova. Sejam G, H, U

, . . . , U

, D e D



como no enunciado. Pode-se ver que D



satisfaz [P1] da deﬁnic¸˜ao de decomposic¸˜ao em ´arvore, j´a que



i∈I



i∈I



v∈X

f(v) = V

ou seja, a uni˜ao das partes corresponde `a uni˜ao dos v´ertices em cada U

, 1 ≤ j ≤ r, e dos

v´ertices em G n˜ao inclusos em alguma parte, e que correspondem, portanto, ao conjunto

de v´ertices de G.

3. Decomposic¸

ao em

Arvore

De modo semelhante, pode-se dividir as arestas de G em quatro classes, de acordo

com suas extremidades: uma aresta e = (u, v) pode ser tal que (1) u e v n˜ao estejam em

nenhum U

, u, v ∈



1≤j≤r

; (2) exatamente uma das extremidades esteja em algum

; (3) as extremidades pertencem a conjuntos diferentes, u ∈ U

, v ∈ U

, onde 1 ≤

i = j ≤ r; ou (4) ambas as extremidades pertencem a um mesmo U

, u, v ∈



1≤j≤r

Sejam agora v

os v´ertices em H correspondentes a contrac¸ ˜ao de U

em G. Basta agora

ver que as arestas e = (u, v) em G dos tipos (1), (2) e (3) correspondem a arestas em H

dos tipos (1) e



= (u, v); (2) e



= (u, v

), onde somente v pertence a algum U

; e (3)



= (v

, v

), onde u ∈ U

e v ∈ U

, U

= U

. As arestas em G do ´ultimo tipo s˜ao

contra´ıdas em H. Como as arestas dos trˆes primeiros tipos est˜ao cobertas por partes em

D, estas est˜ao cobertas tamb´em por partes em D



, j´a que para todo X ∈ X existe um

W ∈ W tal que X ⊆ W . As arestas em G do terceiro tipo, com ambas as extremidades

pertencentes a algum U

, tamb´em est˜ao cobertas em D



, j´a que v

pertence a algum

X ∈ X . Logo, a propriedade [P2] ´e tamb´em satisfeita. A Figura 3.6 permite uma melhor

compreens˜ao da satisfac¸˜ao das propriedades.



Figura 3.6. Decomposic¸˜ao em ´arvore de um grafo G a partir de um menor H por contrac¸˜ao. Os conjuntos

de contrac¸˜ao correspondem `as extremidades das arestas em negrito.

Para concluir a prova, resta somente satisfazer [P3]. Sejam ent˜ao i, j e k v´ertices

em T tais que k ∈ iT j, e logo, por [P3], X

∩ X

⊆ X

. De modo a facilitar a notac¸˜ao,

considere f(S), S um conjunto, como sendo f(S) =



s∈S

f(s). Claramente, f(X) = W ,

X ∈ X , W ∈ W, por esta deﬁnic¸ ˜ao. Pode-se perceber que f preserva intersec¸˜ao entre

conjuntos, ou seja:

f(A ∩ B) =



s∈A∩B

f(s) =





s∈A

f(s)









s∈B

f(s)



= f(A) ∩ f(B)

e logo, para conjuntos A, B e C, A∩ B = C se e somente se f(A)∩ f (B) = f (A ∩B) =

f(C). Mas, como para dois conjuntos A e B, A ⊆ B se e somente se A ∩ B = A, tem-

se tamb´em que A ⊆ B se e somente se f (A) ⊆ f(B), j´a que A ∩ B = A equivale a

f(A ∩ B) = f(A).

Portanto, X

∩ X

⊆ X

em D equivale a

3.3. DEA para ﬂorestas

f(X

∩ X

) ⊆ f(X

) ⇔ f(X

) ∩ f(X

) ⊆ f(X

) ⇔ W

∩ W

⊆ W

o que equivale a satisfac¸˜ao de [P3] em D



, e logo D



´e uma decomposic¸˜ao em ´arvore de

G. 

Com a ajuda das propriedades aqui demonstradas, pode-se agora dispor de mais

ferramentas para caracterizac¸ ˜ao de grafos com largura em ´arvore limitada. Inicialmente,

´e interessante estudar grafos com largura em ´arvore pequena. Se G ´e um grafo com pelo

menos uma aresta, ent˜ao claramente LA(G) ≥ 0. Com excec¸ ˜ao de tais casos extrema-

mente raros, a menor largura em ´arvore de um grafo ´e 1; tais grafos s˜ao analisados na

pr´oxima sec¸ ˜ao.

3.3 DEA para ﬂorestas

Se um grafo G ´e uma ﬂoresta, ´e natural intuir que a largura em ´arvore de G ´e muito

pequena, j´a que cada componente de G ´e, por si, uma ´arvore:

Teorema 3.3. Um grafo G

e uma ﬂoresta se e somente se G tem largura em

arvore 1.

Prova.

(⇒) Seja G uma ﬂoresta e C

, . . . , C

suas componentes. Seja C

∗

a componente de G

com maior largura em ´arvore, ou seja, pela Propriedade 3, LA(C

∗

) = LA(G). Considere

a seguinte decomposic¸˜ao em ´arvore de C

∗

1. Para cada aresta e

= (u, v) de C

∗

, seja X

= {u, v};

2. Para cada v´ertice v

∈ V (G), seja X

= {v

};

3. Seja T = (I, F ), I



|E(G)|

k=1

, I



|V (G)|

k=1

, I = I

∪ I

e F = {(i, j) :

∩ X

= ∅, i ∈ I

, j ∈ I

}. Basta ver agora que T ´e isomorfo a um grafo obtido

pela subdivis˜ao de arestas de C

∗

, e logo T cont´em um ciclo se e somente se C

∗

tamb´em cont´em. Portanto, como C

∗

´e uma componente de uma ﬂoresta, T ´e uma

arvore.

Pode-se ver ent˜ao que (X = {X

: i ∈ I}, T = (I, F )) ´e uma decomposic¸ ˜ao em

´arvore de C

∗

E f´acil ver que LA(C

∗

) = 1, j´a que qualquer X

tem tamanho m´aximo e

| = 2. Logo, pela Propriedade 3 e pela maximalidade de C

∗

, LA(G) = 1.

(⇐) Seja G um grafo com largura em ´arvore unit´aria. Suponha, por absurdo, que G

cont´em um ciclo C. Como LA(G) = 1, as partes de G tˆem no m´aximo dois v´ertices, e

considere ainda, sem perda de generalidade, uma decomposic¸˜ao em ´arvore D = (X , T =

(I, F )) com todas as partes contendo de fato dois v´ertices; isto equivale a dizer que D ´e

uma decomposic¸ ˜ao boa. A id´eia ´e mostrar que n˜ao ´e poss´ıvel construir uma decomposic¸ ˜ao

em ´arvore de G usando tais partes, ou seja, D n˜ao existe.

Considere ent˜ao um ciclo C = v

, e

, v

, e

, . . . , e

l−1

, v

l−1

, e

, v

 de G e as partes

= {u, v : e

= (u, v)}, como ilustrado na Figura 3.7.a.

3. Decomposic¸

ao em

Arvore

k+1

l−1

(a) (b)

Figura 3.7. Tentativa de decomposic¸˜ao em ´arvore de um ciclo.

Como X

e X

tˆem como intersec¸ ˜ao v

, e v

n˜ao pertence a nenhuma outra parte,

n˜ao pode haver nenhum n´o no caminho entre i

e i

— do contr´ario, a terceira condic¸˜ao

da deﬁnic¸˜ao de decomposic¸˜ao em ´arvore seria violada — e como i

e i

devem ser co-

nectados, logo (i

, i

) deve pertencer a F . Da mesma forma, como X

∩ X

k+1

= {v

}, e

nenhuma outra parte de I cont´em v

, ent˜ao (i

, i

k+1

) ∈ F . At´e a parte i

, T ´e um caminho,

ou seja, (i

, i

k+1

) ∈ F, 1 ≤ k < l, como mostra a Figura 3.7.b.

No entanto, X

∩ X

= {v

}, e como v

∈



l−1

k=2

, n˜ao pode haver n´os en-

tre i

e i

, e logo T n˜ao pode ser uma ´arvore. Mas isto ´e um absurdo, j´a que D ´e uma

decomposic¸˜ao em ´arvore por hip´otese, e logo G n˜ao cont´em ciclos, sendo portanto uma

ﬂoresta. 

Como a classe F dos grafos que s˜ao ﬂorestas ´e fechada com relac¸ ˜ao a tomada de

menores — todo menor de uma ﬂoresta ´e ainda uma ﬂoresta — ent˜ao pode-se caracterizar

F por um conjunto de menores proibidos, como permitido pela Proposic¸˜ao 2.8.

Lema 3.4. A classe dos grafos com largura em

arvore unit

aria (no m

aximo 1)

exatamente a classe de grafos que tem K

como menor proibido, Proib



({K

}).

Prova. Pelo Teorema 3.3, e pela deﬁnic¸ ˜ao de classe de menores proibidos, basta mos-

trar que um grafo G cont´em um ciclo se e somente se G tem K

como menor. A condic¸˜ao

necess´aria ´e trivial: basta tomar dois v´ertices adjacentes de um ciclo C qualquer de G,

com |C| > 3, e contrair recursivamente as arestas n˜ao incidentes a estes dois v´ertices; o

resultado ﬁnal ser´a um K

Para a prova da condic¸ ˜ao suﬁciente, suponha, sem perda de generalidade, que

G = MK

, e logo existem subconjuntos U

, U

e U

de v´ertices, cada um induzindo

um subgrafo conexo em G, tais que G/U

= K

. Considere ent˜ao trˆes pares de

v´ertices u

i,j

, 1 ≤ i, j ≤ 3, i = j, tais que existe uma aresta entre u

i,j

e u

j,i

, e

i,j

, onde u

i,j

pertence a U

e u

j,i

pertence a U

. Como cada U

induz um subgrafo conexo em G, seja

o caminho unindo cada par de v´ertices acima em U

. A Figura 3.8 mostra G e cada

elemento acima.

Basta agora ver que u

1,3

, P

, u

1,2

, e

1,2

, u

2,1

, P

, u

2,3

, e

2,3

, u

3,2

, P

, u

3,1

, e

1,3

, u

1,3



induz um ciclo em G, o que conclui a prova. 

3.4. DEA para ciclos

1,3

1,2

3,1

1,2

3,2

2,3

2,1

1,3

Figura 3.8. Um grafo G possui um ciclo se e somente se tem K

como menor.

3.4 DEA para ciclos

Pelo Teorema 3.3, viu-se que a presenc¸a de um ciclo em um grafo G inviabiliza a largura

em ´arvore unit´aria para G. No entanto, apenas a presenc¸a de um ciclo n˜ao torna a largura

em ´arvore de G grande, como se pode deduzir do pr´oximo lema.

Lema 3.5. Todo ciclo tem largura em

arvore 2.

Prova. Pelo Teorema 3.3, e por conter ao menos uma aresta, um ciclo deve ter largura

em ´arvore no m´ınimo 2. Logo, para provar o lema, basta encontrar uma decomposic¸˜ao em

´arvore de largura 2 para qualquer ciclo, j´a que esta certamente ser´a m´ınima. Na prova da

suﬁciˆencia do Teorema 3.3 utilizou-se uma construc¸˜ao de modo a demonstrar a impossi-

bilidade de se encontrar uma decomposic¸˜ao em ´arvore de largura unit´aria para um ciclo.

Tal construc¸˜ao pode ser aproveitada para se obter uma decomposic¸˜ao semelhante, mas de

largura um pouco maior.

Considere ent˜ao um ciclo C = v

, e

, v

, e

, . . . , e

l−1

, v

l−1

, e

, v

 e as partes X

{u, v : e

= (u, v)}. A diﬁculdade est´a no fato de que v

∈ X

∩ X

, mas n˜ao est´a

contido em nenhuma outra parte no caminho entre X

e X

. A resoluc¸˜ao ´e ent˜ao simples,

j´a que n˜ao h´a mais obrigac¸ ˜ao em manter a largura unit´aria: adicionar v

a cada parte X

1 < j < l. Logo,

D =







= {u, v : (u, v) = e

} ∪ {v

}



1≤k≤l+1

, T = i

, i

, . . . , i





´e uma decomposic¸˜ao em ´arvore de largura 2 de C, como mostra a Figura 3.9. Vale notar

que T ´e um caminho, neste caso. 

A partir da decomposic¸˜ao em ´arvore D encontrada na prova do Lema 3.5, pode-

se perceber que D ´e tamb´em uma decomposic¸ ˜ao em ´arvore para G = (V (C), E(C) ∪

{(v

, v

: 1 < i < l}), j´a que toda aresta adicionada a C em G est´a coberta por alguma

parte de D. De fato, a possibilidade de adicionar arestas a um grafo sem aumentar a

3. Decomposic¸

ao em

Arvore

l−1

k+1

l−1

(a) (b)

Figura 3.9. Decomposic¸˜ao em ´arvore de um ciclo.

sua largura em ´arvore — j´a que a mesma decomposic¸˜ao em ´arvore ´e usada — ´e uma

propriedade bastante ´util, e merece uma descric¸ ˜ao formal como nova ferramenta.

Propriedade 5. Se D = (X , T ) ´e uma decomposic¸˜ao em ´arvore de G = (V, E), e

∃i ∈ I : v, w ∈ X

, v = w, ent˜ao D ´e tamb´em uma decomposic¸˜ao em ´arvore de G +

(v, w) = (V, E ∪ {(v, w)}), e vice-versa.

Prova. O lema ´e trivial. Basta ver que a aresta acrescentada a G ´e coberta pela parte

em D contendo suas extremidades; logo, D ´e tamb´em uma decomposic¸˜ao em ´arvore do

novo grafo. O sentido contr´ario tamb´em vale e ´e imediato pelo simples fato de que D

´e ainda uma decomposic¸˜ao em ´arvore de qualquer subgrafo de G obtido por retirada de

arestas (embora n˜ao seja necessariamente a decomposic¸ ˜ao de menor largura). 

Considere agora um C

com conjunto de v´ertices {v

, v

}, e logo, usando o

Lema 3.5, pode-se ver que C

tem largura em ´arvore 2 e que D = ({{v

, v

}, {v

, v

}}, T = ({i

, i

}, {(i

, i

)})) ´e uma decomposic¸˜ao em ´arvore m´ınima de C

. Logo,

D ´e tamb´em uma DEA de C



= C + (v

, v

), pela Propriedade 5. Suponha agora que

se queira adicionar a aresta (v

, v

) a C



. Ap´os algumas tentativas exaustivas, conclui-

se que n˜ao se pode mais encontrar uma decomposic¸˜ao em ´arvore D de largura 2 para



= C



+ (v

, v

), pois pelo menos uma parte de uma DEA para C



deve conter todos

os v´ertices de C. Pode-se ver que C



= K

, e a pr´oxima sec¸ ˜ao mostra que os dois ´ultimos

fatos n˜ao s˜ao coincidˆencia.

3.5 DEA para cliques

A Propriedade 1 estabeleceu uma relac¸ ˜ao entre a conectividade de um grafo G e uma

´arvore T , onde T ´e deﬁnida por uma decomposic¸˜ao em ´arvore D = (X , T ) de G. A

pr´oxima propriedade abaixo estabelece uma relac¸˜ao semelhante para um subconjunto de

v´ertices de G.

Propriedade 6. Sejam D = (X = {X

: i ∈ I}, T = (I, F )) uma decomposic¸ ˜ao em

´arvore de G = (V, E), e W ⊆ V . Ent˜ao ou existe um i ∈ I tal que W ⊆ X

ou existem

v´ertices w

, w

∈ W tais que T

∩ T

= ∅.

3.5. DEA para cliques

Prova. Seja W = {w

, w

, . . . , w

}, e T

= {T

}

1≤i≤r

a fam´ılia de sub-´arvores

induzidas por cada elemento de W . Se n˜ao existem v´ertices w

, w

∈ W tais que T

∩

= ∅ ent˜ao T

satisfaz a propriedade Helly pelo Lema 2.2, e logo



= T

∗

, e

existe um X

∗

tal que W ⊆ X

∗

∈ T

∗

. 

Considere agora o problema de encontrar uma decomposic¸˜ao em ´arvore m´ınima

para uma clique. Pelo Lema 3.5, sabe-se que LA(K

) = 2, justamente pela diﬁculdade

encontrada na prova do Teorema 3.3: sendo v

, v

e v

os v´ertices de K

, n˜ao se pode

construir uma boa decomposic¸˜ao em ´arvore com X

= {v

, v

}, X

= {v

, v

}, e X

, v

}, pois X

⊇ X

∩ X

, X

⊇ X

∩ X

e X

⊇ X

∩ X

, impossibilitando a

satisfac¸˜ao de [P3]. E logo, uma decomposic¸˜ao em ´arvore m´ınima de K

deve ter uma

parte contendo todos os seus v´ertices.

Na verdade, essa diﬁculdade ´e encontrada na tentativa da construc¸˜ao de uma

decomposic¸˜ao em ´arvore de largura k − 1 para qualquer clique de tamanho k + 1. De

fato, pode-se mostrar que isso ´e imposs´ıvel, e logo toda clique W deve estar contida em

uma parte de uma decomposic¸˜ao, forc¸ando a largura em ´arvore do grafo (e da clique)

para, no m´ınimo, |W | − 1.

Suponha que se queira contornar essa diﬁculdade e encontrar uma DEA de largura

no m´aximo k − 1 para clique de tamanho k + 1, e logo suponha que exista uma DEA

D = (X , T = (I, F )) de uma clique W com V (W ) = {v

, v

, . . . , v

} tal que LA(D) ≤

|W | − 2. Seja i ∈ I um n´o de T tal que W − v

⊆ X

. Sejam ainda j, j



∈ T tais que

, v

} ⊆ X

e {v

, v

} ⊆ X



. Como os trˆes conjuntos X

, X

e X



se interceptam, ´e

necess´ario ent˜ao, pela restric¸˜ao [P3], que tenham uma intersec¸˜ao em comum, e logo ou

∈ X

ou v

∈ X



. Isso ´e f´acil de perceber porque W [{v

, v

}] = K

. Suponha,

sem perda de generalidade, que v

∈ X

, e seja agora j



um n´o tal que {v

, v

} ∈ X



Pelo mesmo motivo anterior, ou seja, pela necessidade da existˆencia de uma intersec¸˜ao

comum entre X

, X

e X



dada a intersec¸˜ao n˜ao nula entre estes, dois a dois, assume-se,

s.p.d.g., que v

∈ X

. Continuando desta forma, chega-se a X

⊇ {v

, v

, . . . , v

k−1

} e,

como existe uma aresta (v

, v

), a existˆencia de um n´o j



∈ T tal que {v

, v

} ⊆ X



O mesmo argumento da necessidade de intersec¸ ˜ao comum vale, e logo conclui-se que

W ⊆ X

Conclui-se ent˜ao que toda clique de um grafo G deve estar contida em alguma

parte de qualquer decomposic¸ ˜ao em ´arvore de G. A propriedade seguinte formaliza tal

resultado, acrescentando ainda outro bastante relacionado.

Propriedade 7. Seja D = (X = {X

: i ∈ I}, T = (I, F )) uma decomposic¸˜ao em

´arvore de G = (V, E).

1. (Contin

encia de clique). Se W ⊆ V forma uma clique em G, ent˜ao ∃i ∈ I :

W ⊆ X

2. (Contin

encia de subgrafo bipartite completo). Se A, B ⊆ V s˜ao tais que cada

v´ertice em A ´e adjacente a cada v´ertice em B, ent˜ao ∃i ∈ I : A ⊆ X

ou B ⊆ X

Prova.

1. Se |W | = 1 ou |W | = 2 ent˜ao a propriedade claramente vale como conseq¨uˆencia da

deﬁnic¸ ˜ao de decomposic¸ ˜ao em ´arvore, pelas restric¸ ˜oes [P1] e [P2], respectivamente.

3. Decomposic¸

ao em

Arvore

Suponha ent˜ao inicialmente W = K

, e seja v ∈ W . Por hip´otese de induc¸ ˜ao, seja

i ∈ T tal que W − v ⊆ X

. Seja agora T

= (I



, F



) a sub-´arvore de T cujas partes

cont´em v. Suponha i ∈ I



, caso contr´ario W ⊆ X

. Seja j o n´o em T

mais pr´oximo

de i em T . Tome um v´ertice qualquer w de W − v, e seja j



∈ I



tal que {v, w} ∈



; tal parte deve existir, j´a que (v, w) ∈ W . Mas X

∩ X



⊇ {v, w}, e, como j

est´a no caminho entre i e j



em T , por [P3] deve-se ter {v, w} ⊆ X

∩ X



⊆ X

Como X

cont´em qualquer v´ertice w ∈ W − v e v, segue que W ⊆ X

Uma prova mais curta pode ser obtida diretamente com base na propriedade Helly.

Seja T

= {T

= {i ∈ I : w

∈ X

}}

1≤i≤r

. Basta perceber que, como sempre

existe uma aresta entre quaisquer dois v´ertices u e v de W, ent˜ao T

∩ T

= ∅. Pela

Propriedade 6, tem-se W ⊆ X

∗

, X

∗

∈



2. Sejam G, D, A e B como no enunciado, e suponha B ⊆ X

para todo i ∈ I.

Sejam a

, a

∈ A, e b

, b

∈ B tais que T

e T

sejam disjuntos em v´ertices.

A existˆencia de b

e b

´e garantida pela Propriedade 6. Pela existˆencia da aresta

, b

), deve-se ter t

∈ T

tal que a

∈ X

, assim como, devido a (a

, b

), deve

existir t

∈ T

tal que a

∈ X

. Por [P3], todos os v´ertices no caminho entre t

em T cont´em a

, e logo, seja k ∈ t

T t

, e portanto a

∈ X

. Suponha ainda, sem

perda de generalidade, que t

e t

s˜ao extremidades do caminho m´ınimo (´unico) em

T unindo T

e T

, como mostra a Figura 3.10.



Figura 3.10. Se A, B ⊆ V induzem um subgrafo bipartite completo em G = (V, E), ent˜ao ou A ou B

est˜ao contidos em alguma parte de uma DEA de G.

Seja agora a

∈ A, e, de modo an´alogo a a

, sejam t



∈ T

e t



∈ T

tais que

∈ X



e a

∈ X



, e k



∈ t



T t



. Mas k



T t



T kT t



T k



formam um

ciclo a menos que t



= t

e t



= t

. Logo, a

∈ X

, e como todo v´ertice em A

deve pertencer a X

, segue que A ⊆ X



A partir da Propriedade 7, uma outra propriedade, semelhante `a Propriedade 5, pode

ser encontrada:

Propriedade 8. Sejam v e w v´ertices n˜ao adjacentes em G = (V, E) com pelo menos

k + 1 vizinhos em comum. Se a largura em ´arvore de G ´e no m´aximo k, ent˜ao a largura

3.5. DEA para cliques

em ´arvore de G + (v, w) ´e tamb´em no m´aximo k. Al´em disso, qualquer decomposic¸˜ao

em ´arvore de G com largura no m´aximo k ´e tamb´em uma decomposic¸˜ao em ´arvore de

G + (v, w) com largura no m´aximo k, e vice-versa.

Prova. Seja D = (X , T ) uma decomposic¸˜ao em ´arvore de G com largura no m´aximo

k. Pela Propriedade 7, ou existe um i ∈ I com v, w ∈ X

— e logo a propriedade segue

diretamente pela Propriedade 5 — ou existe um i ∈ I com X

contendo o conjunto W

de todos os vizinhos em comum de v e w. Neste caso, poderiam ser adicionadas arestas

unindo todos os pares de v´ertices n˜ao adjacentes em W , resultando em pelo menos duas

cliques com k + 2 v´ertices, W + v e W + w. Novamente pela Propriedade 5, essa nova

decomposic¸˜ao em ´arvore D



deve ter a mesma largura de D, um absurdo j´a que nenhuma

decomposic¸˜ao em ´arvore com largura no m´aximo k pode conter uma clique com k + 2

v´ertices. Logo, por contradic¸˜ao, o primeiro caso vale, e a propriedade segue. 

Com a ajuda da Propriedade 7, tem-se mais ferramentas para encontrar uma

caracterizac¸ ˜ao de uma nova classe de grafos de largura pequena e limitada.

Teorema 3.6. A classe dos grafos com largura em

arvore no m

aximo 2

e exatamente a

classe de grafos que tem K

como menor proibido, Proib



({K

}).

Prova. O teorema equivale a dizer que um grafo G tem largura em ´arvore no m´aximo

2 se e somente se G n˜ao possui K

como menor. A condic¸ ˜ao necess´aria ´e imediata, j´a que

se G tem largura em ´arvore no m´aximo 2 ent˜ao a maior clique de G tem tamanho 3, e

uma clique de tamanho 4 resultaria numa largura no m´ınimo 3 para G.

Suponha ent˜ao, s.p.d.g., que G = MK

e, no pior caso, ´e maximal em arestas. Pela

Proposic¸˜ao 2.7, se G = MK

ent˜ao G = T K

, j´a que ∆(K

) = 3, e logo, G n˜ao possuir

como menor ´e equivalente a G n˜ao possuir uma subdivis˜ao de K

como subgrafo. A

id´eia da prova ´e mostrar, por induc¸ ˜ao, que G pode ser montado por colagem de K

a partir

de triˆangulos, e logo, claramente LA(G) ≤ 2, j´a que desta forma a maior clique de G ´e

um K

Se G = K

, tem-se a base da induc¸ ˜ao, e suponha ent˜ao |G| ≥ 4 como passo. Como

G n˜ao ´e completo, sejam S um separador em G tal que |S| = κ(G), C

e C

componentes

de G − S, e G

= G[C

∪ S] e G

= G[C

∪ S]. Como S ´e um separador minimal,

todo v´ertice em S possui um vizinho em C

e outro em C

. Se |S| ≥ 3, ent˜ao G possui

pelo menos 3 caminhos disjuntos em v´ertices entre v

∈ C

e v

∈ C

, P

e P

. Como

κ(G) ≥ 3, existe um outro caminho P entre u e v em G\{v

, v

} tais que u e v pertencem

a caminhos diferentes entre P

, P

e P

e possam, desta forma, ter pelo menos 3 caminhos

independentes entre si. Na Figura 3.11, u ∈ P

e v ∈ P

, e logo P ´e um terceiro caminho

unindo u a v.

Mas P ∪ P

∪ P

= T K

, um absurdo, e logo κ(G) ≤ 2. Logo, |S| ≤ 2 e, pela

maximalidade de G, G[S] = K

. Como G

∩ G

= S e G

∪ G

= G, G pode ser obtido

a partir de G

e G

por colagem ao longo de S = K

, o resultado segue por induc¸˜ao. 

Como ilustrado pelos lemas sobre caracterizac¸ ˜ao de grafos com largura em ´arvore

limitada, uma boa abordagem ´e considerar sub-estruturas proibidas em um determinado

grafo e ent˜ao classiﬁc´a-lo. Infelizmente, esta abordagem pode n˜ao ser eﬁciente a medida

3. Decomposic¸

ao em

Arvore

Figura 3.11. Um grafo G n˜ao tem K

como menor se e somente se tem largura em ´arvore no m´aximo 2.

em que se aumenta a largura m´axima permitida para uma decomposic¸˜ao em ´arvore, j´a que

os conjuntos de obstruc¸ ˜ao tamb´em crescem.

Uma id´eia atraente ´e ent˜ao procurar deﬁnir algoritmos de reconhecimento de classes

dos grafos com largura em ´arvore limitada de um modo geral, que n˜ao precisem de uma

deﬁnic¸ ˜ao expl´ıcita dos menores proibidos de cada classe, para cada largura. Tais algorit-

mos ser˜ao discutidos adiante, no pr´oximo cap´ıtulo; no entanto, ao longo deste cap´ıtulo,

novos conceitos ser˜ao apresentados e discutidos de modo a amadurecer teoricamente uma

abordagem algor´ıtmica.

3.6 DEA para grafos cordais

Prosseguindo com a busca de caracterizac¸ ˜oes para grafos de largura em ´arvore limitada,

pode-se ver que a largura em ´arvore de um grafo G ´e claramente limitada inferiormente

pelo tamanho da maior clique em G, ou seja, LA(G) ≥ ω(G) − 1 como conseq¨uˆencia da

Propriedade 7. Uma classe de grafos interessante ´e ent˜ao a classe de grafos cordais, pelo

seguinte resultado:

Teorema 3.7. Um grafo G = (V, E)

e cordal se e somente se admite uma decomposic¸

arvore D = (X , T = (I, F )) onde X corresponde

a fam

ılia de cliques maximais de

Prova.

(⇒) Suponha que G seja cordal. A prova da condic¸ ˜ao necess´aria ´e feita por induc¸ ˜ao no

tamanho de G. Assuma, portanto, que a condic¸ ˜ao ´e v´alida para todos os grafos com menos

v´ertices que G. Como base da induc¸˜ao, se G ´e completo ent˜ao T ´e composta de somente

um n´o; se G ´e desconexo com componentes C

, . . . , C

, ent˜ao, pela hip´otese de induc¸˜ao,

existe uma ´arvore T

para cada componente C

, e logo, pela adic¸˜ao de um n´o i

∗

`a uni˜ao das

(sub-)´arvores T

, tal que X

∗

seja igual a alguma clique maximal de alguma componente

de G, pode-se obter uma ´arvore T para G satisfazendo `a condic¸˜ao (de forma semelhante

`a construc¸˜ao abordada na prova da Propriedade 3).

Assuma portanto, que G ´e conexo e n˜ao completo, e seja w um v´ertice simplicial de

G. Deﬁna agora W = {w} ∪ N

(w), claramente uma clique maximal de G. Sejam ainda

U = {u ∈ W : N

(u) ⊂ W } e Y = W \ U. Considere agora o grafo G



= G[V \ U], que

3.6. DEA para grafos cordais

´e tamb´em cordal, e, como tem menos v´ertices que G e pela hip´otese de induc¸˜ao, admite

uma decomposic¸˜ao em ´arvore D



= (X



, T



= (I



, F



)) satisfazendo o teorema.

Seja ent˜ao K a clique maximal de G



contendo Y . Para construc¸˜ao de uma

decomposic¸˜ao D = (X , T = (I, F )) de G a partir de D



e G



, devem-se considerar

dois casos:

1. Y = K. Neste caso, seja i ∈ I



tal que X

= K. Logo, basta substituir X

por W em



D = (X = {X

: X

∈ X



, j = i} ∪ {X

= W }, T = (I



, F



))

2. Y ⊂ K. Como no caso anterior, seja novamente i ∈ I



tal que X

= K. A nova

decomposic¸˜ao ´e obtida acrescentando-se um novo v´ertice i



adjacente a i tal que



= W :

D = (X = X



∪ {X



= W }, T = (I



∪ {i



}, F



∪ {(i, i



)}))

(⇐) Seja G = (V, E) um grafo com uma decomposic¸˜ao em ´arvore D = (X , T = (I, F ))

como no enunciado do teorema. Inicialmente, vale notar que se (u, v) ∈ E, ent˜ao as sub-

´arvores T

e T

se interceptam, j´a que a clique maximal que cont´em u e v deve estar em

e T

Suponha agora, por absurdo, que G contenha um ciclo sem cordas C =

v

, v

, . . . , v

k−1

, v

, com k > 3, e com sub-´arvores correspondentes T

, T

, . . . , T

k−1

em T . Seja P = {P

}

0≤i≤k−1

uma fam´ılia de caminhos em T tal que cada P

⊆ T

∩ P

(i−1) mod k

= ∅ e P

∩ P

(i+1) mod k

= ∅. Como T

∩ T

(i−1) mod k

= ∅ e

∩ T

(i+1) mod k

= ∅, pelas arestas em C, tais caminhos sempre existem. Vale notar que

(i−1) mod k

∩P

(i+1) mod k

= ∅, para 0 ≤ i ≤ k−1, j´a que, caso contr´ario, a intersec¸˜ao

entre os caminhos implicaria numa clique contendo v

(i−1) mod k

, v

e v

(i+1) mod k

, o que

representa uma corda em C, violando a hip´otese de absurdo. Al´em disso, pelo Lema 2.3,

P deve satisfazer a propriedade Helly, e logo, para todo i, P

(i−1) mod k

∩P

(i+1) mod k

= ∅.

Basta agora notar que a uni˜ao dos P

representa um ciclo (n˜ao induzido) em T , um

absurdo, j´a que T ´e uma ´arvore. 

A Figura 3.12 ilustra uma decomposic¸˜ao em ´arvore m´ınima D = (X , T ) para um

grafo cordal G onde todas as partes de D correspondem a cliques maximais em G; em (a)

pode-se ver o grafo G, em (b) a ´arvore T associada a D e G, em (c) as partes de D e em

(d) pode-se perceber melhor as cliques maximais de G.

Logo, a decomposic¸ ˜ao em ´arvore de um grafo cordal revela propriedades desej´aveis,

de modo que pode-se determinar prontamente a largura em ´arvore de um grafo cordal.

Corol

ario 3.8. Se G

e um grafo cordal, ent

ao LA(G) = ω(G) − 1.

Prova. O corol´ario segue diretamente do Teorema 3.7 e da Propriedade 7: basta ver

que qualquer decomposic¸˜ao em ´arvore m´ınima de um grafo G cordal tem apenas cliques

em suas partes, e logo a largura em ´arvore ´e realizada nas partes que cont´em as maiores

3. Decomposic¸

ao em

Arvore

D = (T = (I, F ), X )

= {d, e, f}

(d)

= {b, c, e}

= {b, d, e}

(c)(b)

(a)

= {a, b, d}

b c

Figura 3.12. Exemplo de decomposic¸˜ao em ´arvore para um grafo cordal.

cliques. Portanto, pela deﬁnic¸ ˜ao de largura em ´arvore, LA(G) = ω(G) − 1, o maior

tamanho de clique de G menos 1. 

Como encontrar uma decomposic¸˜ao em ´arvore para um grafo cordal H depende da

identiﬁcac¸ ˜ao de todas as cliques maximais de H, o que pode ser feito em tempo linear

usando um esquema de eliminac¸˜ao perfeito para H, tem-se um limitante superior para a

largura em ´arvore de todos os subgrafos G de H.

Lema 3.9. Sejam G um grafo e H um grafo cordal obtido a partir de uma triangulac¸

qualquer de G. Ent

ao LA(G) ≤ ω(H) − 1.

Prova. Como G ´e um subgrafo de H, segue que LA(G) ≤ LA(H) pela Propriedade 2.

Mas pelo Lema 3.9 anterior, LA(H) = ω(G) − 1, o que conclui a prova. 

Um resultado ainda mais importante pode ser obtido se, para um grafo G, obt´em-se

uma triangulac¸˜ao de G onde cada aresta da triangulac¸˜ao satisfaz a Propriedade 5.

Lema 3.10. Para todo grafo G = (V, E), existe uma triangulac¸

ao E



de G resultando

no grafo H = (V, E ∪ E



) tal que LA(G) = LA(H).

Prova. Seja D = (X , T = (I, F )) uma decomposic¸ ˜ao em ´arvore m´ınima de G. Con-

sidere o conjunto E



de arestas deﬁnido da seguinte forma: para cada par u, v de v´ertices

em G tais que (u, v) ∈ E e u ∈ X

, v ∈ X

, para algum i ∈ I, acrescente (u, v) a E



Claramente D ´e tamb´em uma decomposic¸˜ao em ´arvore de H = (V, E ∪ E



). Al´em disso,

3.6. DEA para grafos cordais

como cada parte de D em H corresponde a uma clique maximal, pelo Lema 3.7, H ´e

cordal, e logo E



´e a triangulac¸ ˜ao procurada. Pela minimalidade de D, segue tamb´em que

LA(H) = LA(G). 

Uma conseq¨uˆencia direta do Lema 3.10 ´e a equivalˆencia entre os problemas (de

otimizac¸˜ao) de encontrar uma decomposic¸˜ao em ´arvore de largura m´ınima para um grafo

G e o de encontrar uma cordalizac¸ ˜ao de G que tenha uma clique de tamanho m´ınimo

dentre todas as cordalizac¸ ˜oes poss´ıveis de G. Tal equivalˆencia ´e aqui posta explicitamente

para uso posterior.

Corol

ario 3.11. Encontrar uma decomposic¸

ao em

arvore m

ınima de um grafo G

equivalente a encontrar uma cordalizac¸

ao H de G que minimiza ω(H).

Prova. A prova ´e direta, conseq¨uˆencia dos Lemas 3.9 e 3.10. 

Outro resultado importante do Lema 3.10 ´e a possibilidade de relacionar um grafo

G com largura em ´arvore no m´aximo k a uma k-cordalizac¸ ˜ao de G. Para tanto, alguns

outros conceitos se fazem necess´arios.

Deﬁnic¸

ao 14 (Aresta necess´aria). Seja G = (V, E) um grafo.

1. Um par (u, v) ´e uma aresta necess

aria para largura em

arvore k de G se, para toda

decomposic¸˜ao em ´arvore D = (X = {X

: i ∈ I}, T = (I, F )) com largura no

m´aximo k de G, existe um j tal que u, v ∈ X

2. Um par (u, v) ´e uma aresta necess

aria para k-cordalizac¸

ao de G se, para toda

k-cordalizac¸ ˜ao H = (V, E



) de G, (u, v) ∈ E



Na verdade, os conceitos de aresta necess´aria est˜ao intimamente relacionados:

Lema 3.12. Sejam G = (V, E) um grafo de largura em

arvore no m

aximo k e u, v ∈ V .

As duas assertivas abaixo s

ao equivalentes:

1. (u, v)

e uma aresta necess

aria para largura em

arvore k em G.

2. Toda k-cordalizac¸

ao de G cont

em a aresta (u, v).

Prova. Para provar o lema, basta mostrar a relac¸ ˜ao direta entre uma decomposic¸˜ao em

´arvore de um grafo G e uma cordalizac¸ ˜ao de G. Seja ent˜ao D = (X = {X

}

i∈I

, T =

(I, F )) uma decomposic¸˜ao em ´arvore arbitr´aria de G. Seja E



= {(u, v) : u ∈ X

, v ∈

, X

∈ X , (u, v) ∈ E(G)}. Como a adic¸˜ao de E



a G resulta num novo grafo G



onde D ´e ainda uma decomposic¸˜ao em ´arvore (pela Propriedade 5). Como cada X

in-

duz uma clique maximal em G



, segue pelo Teorema 3.7 que G



´e cordal, e logo E



´e

uma triangulac¸ ˜ao. Al´em disso, se LA(D) ≤ k, ent˜ao G



´e uma k-cordalizac¸ ˜ao de G. O

sentido converso ´e tamb´em v´alido: se G



´e uma k-cordalizac¸ ˜ao de G, ent˜ao admite uma

decomposic¸˜ao em ´arvore de largura no m´aximo k, que ´e tamb´em v´alida — e de mesma

largura — para G pela Propriedade 2. Logo, se (u, v) ´e uma aresta necess´aria para largura

em ´arvore k de G, ent˜ao u e v pertencem a alguma parte de qualquer decomposic¸˜ao em

´arvore D de G, LA(D) ≤ k, e pertencem tamb´em a qualquer k-cordalizac¸ ˜ao de G. O

mesmo vale se (u, v) pertence a toda k-cordalizac¸ ˜ao G



de G, j´a que, desta forma, u e v

devem pertencer a mesma parte da decomposic¸˜ao em ´arvore de G obtida atrav´es de G



. 

3. Decomposic¸

ao em

Arvore

A utilidade de uma aresta necess´aria (u, v) ´e evidente: se G ´e um grafo com largura

em ´arvore no m´aximo k, ent˜ao a adic¸ ˜ao de (u, v) a G n˜ao aumenta sua largura em ´arvore.

Desta forma, a adic¸˜ao de arestas necess´arias para largura em ´arvore k em um grafo G

resulta numa cordalizac¸ ˜ao de G satisfazendo o Lema 3.10, uma k-cordalizac¸ ˜ao. O lema

seguinte introduz uma condic¸˜ao suﬁciente para a existˆencia de uma aresta necess´aria:

Lema 3.13. Sejam G = (V, E) um grafo e u, v ∈ V . Se existem k+1 caminhos disjuntos

em v

ertices entre u e v em G, ent

ao a aresta (u, v)

e necess

aria para largura em

arvore

k em G.

Prova. Se (u, v) ∈ E ent˜ao, claramente (u, v) ´e necess´aria. Considere ent˜ao que

(u, v) ∈ E. Seja D = (X = {X

: i ∈ I}, T = (I, F )) uma decomposic¸˜ao em ´arvore de

G com largura no m´aximo k. Suponha que existam k + 1 caminhos disjuntos em v´ertices

entre u e v, P

, . . . , P

i+1

, e identiﬁque, para cada P

, todos os v´ertices internos, tanto em

G como em D, em um v´ertice v

, 1 ≤ i ≤ k+1. A decomposic¸˜ao em ´arvore D



= (X



, T



)

resultante ´e uma decomposic¸˜ao do grafo resultante G



com largura tamb´em no m´aximo k,

pela Propriedade 4. A necessariedade de (u, v) segue ent˜ao do fato de que u e v tˆem k + 1

vizinhos em G



e pela Propriedade 8. 

O Lema 3.13 resulta numa importante ferramenta para encontrar uma decomposic¸˜ao

em ´arvore de um grafo. Se um par de v´ertices ´e separado por k + 1 caminhos disjuntos,

ent˜ao dois casos podem ocorrer: ou a aresta unindo o par ´e necess´aria e o grafo tem largura

em ´arvore no m´aximo k, ou os v´ertices internos a todos os k + 1 caminhos est˜ao em uma

mesma parte e a largura em ´arvore do grafo ´e estritamente maior que k.

Como Bodlaender (2000) aponta, ´e tamb´em poss´ıvel prover ainda uma condic¸˜ao

necess´aria e suﬁciente para a existˆencia de uma aresta necess´aria:

Lema 3.14. Seja G = (V, E) um grafo com largura em

arvore no m

aximo k, e sejam

ainda u e v v

ertices n

ao adjacentes em G. Ent

ao (u, v)

e uma aresta necess

aria se e

somente se n

ao existe um subconjunto S ⊆ V de v

ertices com |S| ≤ k +1, {u, v}∩S = ∅,

tal que S separa u e v em G e, para toda componente C de G−S, o grafo G[C∪S]+K(S)

tem largura em

arvore k.

Prova.

(⇐) Sejam S um conjunto de v´ertices satisfazendo as condic¸ ˜oes do enunciado, e

, . . . , C

as componentes de G − S. Sejam agora D

, . . . , D

as decomposic¸ ˜oes em

´arvore de largura no m´aximo k das respectivas componentes. De forma semelhante a

construc¸˜ao ilustrada na prova da Propriedade 3, seja D a decomposic¸ ˜ao em ´arvore de

G obtida pela uni˜ao disjunta das D

, 1 ≤ i ≤ r, e da adic¸ ˜ao de um novo n´o i

∗

tal

que X

∗

= S, que ´e feito adjacente aos n´os i

de cada D

tais que X

⊇ S. Como

cada decomposic¸˜ao tem largura no m´aximo k e |S| ≤ k + 1, segue que LA

(D) ≤ k.

Al´em disso, n˜ao existe em D uma parte X

∗

tal que u, v ∈ X

∗

, e logo (u, v) n˜ao ´e ne-

cess´aria. Como Bodlaender observa, essa construc¸˜ao, por sua vez, ´e semelhante a usada

por Arnborg, Corneil e Proskurowski para reconhecimento de grafos com largura em

´arvore k.

3.6. DEA para grafos cordais

(⇒) Suponha agora que (u, v) n˜ao ´e necess´aria, e seja D = (X = {X

}

i∈I

, T = (I, F ))

uma decomposic¸˜ao em ´arvore de G com largura no m´aximo k, onde, por hip´otese, u e

v pertencem a partes distintas. Sejam ainda T

e T

as sub-´arvores induzidas em T por

u e v, respectivamente, e sejam i

∈ T

e i

∈ T

os n´os que realizam o caminho P de

menor distˆancia entre algum n´o de T

e algum n´o de T

em T . Se i

e i

s˜ao adjacentes

em T , ent˜ao seja D



a decomposic¸˜ao em ´arvore obtida a partir de D pela subdivis˜ao de

, i

) com o acr´escimo de um novo n´o i

∗

tal que X

∗

= X

∩ X

. Se |P | > 1, ent˜ao

seja i

∗

um n´o arbitr´ario em i

P i

. Em ambos os casos, pode-se ver que S = X

∗

´e tal que

{u, v} ∩ S = ∅, S ´e um uv-separador, |S| ≤ k + 1 e, para qualquer componente C de

G − S, G[C ∪ S] + K(S) ´e um subgrafo de G, e logo, pela Propriedade 2, tem largura em

´arvore no m´aximo k. 

Os Lemas 3.13 e 3.14 ser˜ao bastante utilizados na pr´oxima sec¸ ˜ao, quando uma

caracterizac¸ ˜ao para grafos com largura em ´arvore no m´aximo 3 ´e apresentada.

arvores parciais

Grafos cordais, ou melhor, uma classe particular de grafos cordais, as k-´arvores, podem

ainda prover uma caracterizac¸ ˜ao interessante para grafos de largura limitada. Considere

inicialmente o seguinte resultado:

Teorema 3.15. Uma k-

arvore tem largura em

arvore k.

Prova. Uma k-´arvore ´e cordal, e, portanto, admite uma decomposic¸˜ao em ´arvore

m´ınima onde toda parte ´e uma clique. Todas as cliques da k-´arvore tem tamanho k + 1, e

logo a largura ´e tamb´em k. 

A caracterizac¸ ˜ao segue do seguinte fato:

Lema 3.16. Um grafo G tem largura em

arvore no m

aximo k se e somente se G

e uma

arvore parcial.

Prova. Se G ´e uma k-´arvore, ent˜ao a largura em ´arvore de G ´e k, pelo Teorema 3.15.

Se G ´e uma k-´arvore parcial ent˜ao deve ser subgrafo de alguma k-´arvore H, e logo, pela

Propriedade 2, LA(G) ≤ LA(H) = k. 

Atrav´es da caracterizac¸ ˜ao sugerida no Lema 3.16, pode-se encontrar ainda uma

propriedade que limita o n´umero de arestas em um grafo com largura em ´arvore limitada:

Lema 3.17. Se a largura em

arvore de G = (V, E)

e no m

aximo k, ent

ao |E| ≤ k|V | −

k(k + 1).

Prova. Seja G = (V, E) uma k-´arvore. Pelo Teorema 3.15, G admite uma

decomposic¸˜ao em ´arvore D = (X = {X

}

i∈I

, T = (I, F )) onde cada X

cont´em uma

clique de tamanho k + 1.

E f´acil ver, usando induc¸ ˜ao, que |I| = |V | − k, j´a que para

quaisquer X

e X

tais que X

∩ X

= ∅, tem-se |X

∩ X

| = k. Se |V | = k + 1, ent˜ao

T tem somente um n´o e |E| =

k(k + 1). Se T tem |I| n´os, ent˜ao foram acrescentados

|I| − 1 v´ertices a K

k+1

, feitos adjacentes a k v´ertices, de modo a obter G pela deﬁnic¸ ˜ao

de k-´arvore. Vale notar que, para cada v´ertice acrescentado, foram adicionadas k arestas.

3. Decomposic¸

ao em

Arvore

Desta forma, todo v´ertice de G tem no m´ınimo k vizinhos — contribuindo com k · |V |/2

arestas — e, considerando-se as novas arestas adicionadas ao longo da construc¸ ˜ao de G,

tem-se uma contribuic¸˜ao de k · (|V | − k − 1)/2 arestas. Logo,

|E| =

k · |V |

k · (|V | − k − 1)

= k · |V | −

k(k + 1).

Se G ´e um subgrafo de uma k-´arvore, ou seja, uma k-´arvore parcial, ent˜ao clara-

mente E(G) ≤ k · |V | −

k(k + 1). Al´em disso, pelo Lema 3.16, G tem largura em ´arvore

no m´aximo k, e o lema segue. 

3.7 DEA para grafos com largura no m

aximo 3

Antes de iniciar uma discuss˜ao sobre uma caracterizac¸ ˜ao por menores proibidos para a

classe de grafos com largura em ´arvore no m´aximo 3, ´e importante considerar inicial-

mente o fato a seguir, de modo a perceber melhor, como nas caracterizac¸ ˜oes anteriores, a

diﬁculdade em se obter uma DEA D de um grafo G tal que LA(D) < LA(G).

Lema 3.18. Os grafos M

, M

e M

da Figura 3.13 t

em largura em

arvore 4.

Figura 3.13. Os grafos M

, M

e M

tˆem largura em ´arvore 4.

Prova.

) Sejam u

, u

e u

os v´ertices de M

pertencentes ao triˆangulo interno e v

, v

e v

pertencentes ao triˆangulo externo, como na Figura 3.13.

Como v

e u

tˆem 4 vizinhos em comum, v

, v

, u

e u

, ent˜ao, pela Propriedade 8,

ou M

tem largura em ´arvore no m´aximo 3 e (v

, u

) ´e necess´aria em M

, ou S

, v

, u

} est´a contida numa parte de uma decomposic¸˜ao em ´arvore D de M

Neste ´ultimo caso, pela Propriedade 7 (continˆencia de subgrafo bipartite completo),

tanto {v

}∪S

como {u

}∪S

pertencem a uma parte de D, e logo M

tem largura

em ´arvore 4. Suponha que n˜ao, e logo (u

, v

) ´e necess´aria.

Pelo mesmo racioc´ınio, considerando agora v

e u

, tem-se que (u

, v

) ´e necess´aria

para largura em ´arvore 3 em M

, ou tanto {u

} ∪ S

como {v

∪ S

}, S

3.7. DEA para grafos com largura no m

aximo 3

, v

, u

}, forc¸am a largura em ´arvore de M

para 4. Mas, pela necessidade

de (u

, v

) e (u

, v

), tracejadas na Figura 3.14, tem-se que S

= {u

, v

, u

, v

}

deve pertencer a uma mesma parte de uma decomposic¸˜ao em ´arvore para M

, e

logo n˜ao h´a como impedir a largura em ´arvore de M

de ser 4, j´a que {v

} ∪ S

formariam uma clique de tamanho 5 em qualquer 4-cordalizac¸ ˜ao de M

A Figura 3.14 apresenta ainda uma decomposic¸ ˜ao em ´arvore de largura m´ınima 4

para M

Figura 3.14. Decomposic¸˜ao em ´arvore do grafo M

) Sejam v

, . . . , v

os v´ertices de M

como na Figura 3.13. Contraindo-se as quatro

arestas (v

, v

i+4

), 1 ≤ i ≤ 4, obt´em-se um K

, e logo M

tem largura em ´arvore no

m´ınimo 3. Al´em disso, como cada v´ertice em M

tem trˆes vizInhos, basta aplicar

o resultado do Lema 3.14 fazendo S igual a N

(v) — o conjunto de vizinhos de

qualquer v´ertice v — e logo, como LA(M

[{v} ∪ S]) ≤ 3, n˜ao existem arestas

necess´arias para largura 3 em M

entre v´ertices n˜ao adjacentes.

No entanto, com a ajuda da simetria em M

, podem-se estabelecer relac¸ ˜oes en-

tre a presenc¸a de arestas em alguma 3-cordalizac¸ ˜ao de M

e a ausˆencia de outras.

Obviamente essas relac¸ ˜oes devem ser pesquisadas entre v´ertices n˜ao adjacentes.

Considere ent˜ao C = {v

, v

} composto pelos v´ertices em negrito na Fi-

gura 3.15, e os seguintes casos para construc¸˜ao de uma decomposic¸˜ao em ´arvore

em M

(1)

(2)

(3) (4)

(5)

Figura 3.15. Casos para construc¸˜ao de uma decomposic¸˜ao em ´arvore de M

baseada em cordalizac¸˜ao.

1. N

ao existem arestas entre elementos de C. Neste caso, para an´alise de neces-

sariedade entre os pares de v´ertices n˜ao adjacentes de C



= {v

, v

deve-se encontrar, para cada par, um conjunto S satisfazendo o Lema 3.14 tal

que S n˜ao contenha dois elementos de C — caso contr´ario, seria obtida uma

decomposic¸˜ao em ´arvore cujas partes cont´em mais de dois elementos de C.

Mas M

´e 3-conexo, e logo |S| ≥ κ(M

) = 3 para que S seja um separador.

3. Decomposic¸

ao em

Arvore

Al´em disso, |S| ≤ 4 pelas condic¸ ˜oes do Lema 3.14 para k = 3, de modo

que n˜ao ´e poss´ıvel encontrar tal S para qualquer par de v´ertices em C



, j´a

que pelo menos dois v´ertices de S devem estar em C. Logo, qualquer par de

v´ertices n˜ao adjacentes em C



deve ter uma aresta necess´aria, mostradas em

tracejado na Figura 3.15(1). N˜ao ´e dif´ıcil veriﬁcar que todas as decomposic¸ ˜oes

em ´arvore de uma cordalizac¸ ˜ao de M

satisfazendo a presenc¸a de arestas ne-

cess´arias C e ausˆencia de arestas em C



tˆem largura em ´arvore no m´ınimo 4.

A Figura 3.16 ilustra uma decomposic¸˜ao em ´arvore de largura m´ınima de uma

4-cordalizac¸˜ao de M

, e logo tamb´em de M

, respeitando C e C



Figura 3.16. Decomposic¸˜ao em ´arvore do grafo M

, caso 1.

2. Existe apenas uma aresta necess

aria em C. Seja (v

, v

) essa aresta, mos-

trada em estilo trac¸o-ponto na Figura 3.15(2). Mesmo com (v

, v

) sendo

necess´aria, n˜ao ´e poss´ıvel encontrar um conjunto S com no m´aximo quatro

v´ertices separando v

de v

e de v

e que n˜ao contenha dois v´ertices de C com

excec¸˜ao de v

e v

. Logo, (v

, v

) e (v

, v

) s˜ao necess´arias, sendo indicadas

por arestas tracejadas na Figura 3.15(2). Novamente todas as cordalizac¸ ˜oes

de M

obedecendo as condic¸ ˜oes deste caso com relac¸ ˜ao a C e C



s˜ao tais

que o tamanho da maior clique ´e 5, e logo todas as decomposic¸ ˜oes em ´arvore

m´ınimas tˆem largura 4. A Figura 3.17 ilustra uma destas decomposic¸ ˜oes; to-

das as outras resultam de simetria em M

, ou seja, de variac¸ ˜oes na escolha da

´unica aresta necess´aria em C.

3. Existem duas arestas necess

arias e adjacentes em C. Sejam (v

, v

) e (v

, v

)

tais arestas, ilustradas em trac¸o-ponto na Figura 3.15(3). Considere agora o

par (v

, v

). Qualquer v

-separador S deve conter v

, j´a que este ´e vizinho

comum do par. Mas S n˜ao pode conter v

, v

e v

, j´a que apenas as arestas

entre eles s˜ao necess´arias, e logo n˜ao existe S satisfazendo as condic¸ ˜oes do

Lema 3.14 o que resulta na necessariedade de (v

, v

) (em tracejado na Fi-

gura 3.15(3)). Basta agora ver que qualquer cordalizac¸ ˜ao obtida para esta caso

ser´a um supergrafo das cordalizac¸ ˜oes obtidas no caso 2 — aqui s˜ao permitidas

arestas entre v

e v

, v

e v

, e v

e v

, ao contr´ario do caso 2, onde n˜ao existem

arestas entre v

e v

, v

e v

, e v

e v

— e logo toda decomposic¸˜ao em ´arvore

para M

obtida aqui tem largura no m´ınimo 4. A decomposic¸˜ao ilustrada na

Figura 3.17, por exemplo, satisfaz tamb´em as condic¸ ˜oes deste caso.

3.7. DEA para grafos com largura no m

aximo 3

Figura 3.17. Decomposic¸˜ao em ´arvore do grafo M

, caso 2.

4. Existem duas arestas necess

arias e n

ao adjacentes em C. Sejam (v

, v

) e

, v

) as arestas necess´arias em C, trac¸o-pontilhadas na Figura 3.15(4). Note

agora que C induz um subgrafo bipartite completo nestas cordalizac¸ ˜oes de

, e logo, pela Propriedade 7, ou v

e v

devem pertencer a uma mesma

parte em alguma decomposic¸˜ao em ´arvore de M

(satisfazendo as condic¸ ˜oes

de arestas necess´arias para este caso) ou v

e v

devem pertencer a uma mesma

parte. Logo, tem-se uma contradic¸˜ao, porque apenas v

e v

, e v

e v

podem

ser necess´arias pela hip´otese do caso, e logo este n˜ao ´e vi´avel.

5. Existem tr

es arestas necess

arias em C. Considere as arestas trac¸o-pontilhadas

na Figura 3.15(5), (v

, v

), (v

, v

) e v

, v

), como sendo necess´arias em C. Se

, v

) ´e necess´aria ent˜ao qualquer cordalizac¸˜ao de M

derivada ´e supergrafo

de uma cordalizac¸ ˜ao obtida no caso 1, tendo portanto largura em ´arvore no

m´ınimo 4. Neste caso, a decomposic¸˜ao em ´arvore da Figura 3.16 ´e valida

tamb´em para este caso.

Seja ent˜ao M



uma cordalizac¸˜ao de M

em que todos os v´ertices em C s˜ao

adjacentes entre si, com excec¸ ˜ao de v

e v

. Note que se existe uma aresta

entre v

e v

, ent˜ao as contrac¸ ˜oes de (v

, v

), (v

, v

) e (v

, v

) formam um

, e logo suponha ainda que v

e v

n˜ao s˜ao adjacentes em M



, assim como,

por simetria, v

e v

, v

e v

, e v

e v

. Mas isso n˜ao ´e poss´ıvel, pois desta

forma v

, v

e v

formam um ciclo induzido, por exemplo, e M



n˜ao ´e uma

cordalizac¸˜ao. Portanto, (v

, v

) ´e necess´aria.

Pela simetria de M

, os casos acima resultam em todas as combinac¸ ˜oes poss´ıveis

para cordalizac¸ ˜oes m´ınimas de M

. Logo, como todas s˜ao 4-cordalizac¸ ˜oes, segue

pelo Corol´ario 3.11 que LA(M

) = 4.

) Sejam v

, u

, 1 ≤ i ≤ 5, os v´ertices de M

, como mostrado na Figura 3.13. A

contrac¸ ˜ao de todos os u

e de uma aresta qualquer do ciclo externo resulta num

, e logo LA(M

) ≥ 3. Assim como no M

, todo v´ertice possui 3 vizinhos, e

logo, n˜ao ´e poss´ıvel encontrar, para qualquer par de v´ertices n˜ao adjacentes em M

um conjunto S satisfazendo as condic¸ ˜oes do Lema 3.14; desta forma, n˜ao existem

3. Decomposic¸

ao em

Arvore

arestas necess´arias entre v´ertices n˜ao adjacentes. A estrat´egia ent˜ao ´e semelhante a

utilizada para o M

, mas como a enumerac¸ ˜ao dos casos seria mais longa, ela ser´a

aqui suprimida, e ser´a apenas assumido que LA(M

) ≥ 4.

Basta portanto encontrar uma decomposic¸˜ao em ´arvore de largura m´ınima 4 para

concluir a prova. Considere ent˜ao o par de v´ertices (v

, v

), e 3 caminhos disjuntos

= v

, v

, P

= v

, u

, v

 e P

= v

, v

 em M

. Sejam

= {v

, v

}, U

= {u

, u

} e U

= {v

} conjuntos contendo os v´ertices

internos de cada caminho, respectivamente. Ent˜ao, pelo Lema 3.13 e pelo fato de

que LA(M

) > 2, existe um menor M



de M

obtido pela contrac¸ ˜ao de cada

em novos v´ertices v

, 1 ≤ i ≤ 3, tal que os v

pertencem a uma mesma

parte de uma decomposic¸˜ao em ´arvore de M



. Na Figura 3.18(a), podem-se ver os

caminhos P

, os conjuntos U

e M



(b)(a)

Figura 3.18. Decomposic¸˜ao em ´arvore de um menor do grafo M

Como a contrac¸˜ao de {u

, u

, v

} resulta num K

, ent˜ao LA(M



) > 2. Na Fi-

gura 3.18(b), pode-se ver uma decomposic¸˜ao em ´arvore m´ınima D = (W =

}

1≤i≤4

, T = (I, F )) de M



com largura 3, na qual {v

, v

} est˜ao numa

mesma parte. Pela aplicac¸ ˜ao do Lema 3.2, pode-se derivar uma decomposic¸˜ao em

´arvore D



= (W



= {W



}

i∈I

, T = (I, F )) para M

onde cada parte W



corres-

ponde a uni˜ao dos f(v) para v ∈ W

, como deﬁnido no Lema. Claramente, a largura

de D



´e 6. A partir de D



, pode-se ainda derivar uma outra decomposic¸˜ao em ´arvore

∗

para M

, eliminando o excesso de cada W



e procurando manter a estrutura

em ´arvore. As partes W



, W



e W



podem ser substitu´ıdas por X

, X

e X

com menos v´ertices cada e cobrindo os mesmos v´ertices e arestas, como ilustra a

Figura 3.19. Al´em disso, W



pode ser substitu´ıdo por X

e X

, de onde se obt´em

uma decomposic¸˜ao em ´arvore de largura 4.

3.8. Conjuntos k-ligados, arbustos e novelos

Figura 3.19. Decomposic¸˜ao em ´arvore do grafo M



A seguinte caracterizac¸ ˜ao pode ser obtida, sendo aqui exposta sem prova:

Teorema 3.19 (Arnborg et al. [1993]). A classe dos grafos com largura em

arvore no

aximo 3

e exatamente a classe de grafos que tem K

, M

e M

como menores

proibidos, Proib



({K

, M

}).

E importante notar que, ao contr´ario das classes de grafos com largura em ´arvore no

m´aximo k, k = 1, 2, n˜ao basta proibir K

k+2

como menor; ou seja, n˜ao ter um K

como

menor ´e uma condic¸ ˜ao necess´aria para que a largura de um grafo seja no m´aximo 4, mas

n˜ao suﬁciente. Os motivos dessa extens˜ao necess´aria no conjunto de obstruc¸˜ao — que est´a

longe de ser t˜ao ´obvia como nas classes de grafos com largura limitada vistas at´e agora

— apenas ser˜ao melhor compreendidos ao se analisar mais profundamente a estrutura dos

grafos com largura em ´arvore limitada, e n˜ao t˜ao pequena. Este ´e o objetivo do resto do

cap´ıtulo.

3.8 Conjuntos k-ligados, arbustos e novelos

Na Sec¸ ˜ao 2.4, foi apresentada a caracter´ıstica de um grafo ser k-ligado, e viu-se que

esta deﬁnic¸ ˜ao ´e mais forte que a de k-conectividade. Na verdade, a k-conectividade

em um grafo representa um parˆametro local do qu˜ao conexo um grafo ´e, baseado nas

regi˜oes menos conexas do grafo. Desta forma, pode-se aproveitar o conceito de k-ligado,

redeﬁnindo-o de modo a reﬂetir uma medida mais global de conectividade.

Deﬁnic¸

ao 15 (Conjunto k-ligado e componente grande). Um subconjunto de v´ertices

S de um grafo G = (V, E) ´e dito k-ligado se, para qualquer conjunto X, |X| < k,

3. Decomposic¸

ao em

Arvore

existe uma componente (´unica) de G − X contendo mais da metade dos v´ertices de S,

chamada de componente grande (de G − X).

Vale notar que para um conjunto S ser k-ligado, deve-se ter necessariamente |S| ≥

2k — caso contr´ario, basta tomar um subconjunto de S com mais de k v´ertices para que

n˜ao exista uma componente grande de S. Por outro lado, ´e f´acil ver que qualquer conjunto

S pode ser no m´aximo |S|/2-ligado.

Deﬁnic¸

ao 16 (Ligac¸˜ao). A ligac¸

ao de G, denotada por lig(G), ´e o maior inteiro para o

qual G cont´em um conjunto k-ligado.

Para perceber que a ligac¸˜ao de um grafo ´e uma medida mais global de conectividade,

considere uma grade r × s. Uma grade de ordem r × s ´e um grafo tendo como conjunto

de v´ertices {1, . . . , r} × {1, . . . , s} e conjunto de arestas deﬁnido por:

{((i, j), (i



, j



)) : |i − i



| + |j − j



| = 1}.

As cruzes da grade s˜ao os r · s conjuntos deﬁnidos por:

i,j

= {(i, l) : l = 1, . . . , s} ∪ {(l, j) : l = 1, . . . , r}

ou seja, cada cruz C

i,j

corresponde a uni˜ao, na grade, da i-´esima linha e da j-´esima co-

luna. Uma grade e duas de suas cruzes s˜ao exempliﬁcadas na Figura 3.20. Pode-se ver

facilmente que toda grade ´e planar.

(1, 1)

(2, 1)

(1, 2)

(r − 1, 2)

(r, 2)

(1, 3)

(r − 1, 1)

(r, 1)

(2, 2) (2, 3)

(r, 3) (r, s − 1)

(r − 1, s − 1)

(2, s − 1)

(1, s − 1)

(r − 1, 3)

(1, s)

(2, s)

(r − 1, s)

(r, s)

2,2

r−1,s−1

Figura 3.20. Uma grade r × s e as cruzes C

2,2

e C

r−1,s−1

Embora toda grade G de ordem r × s seja 2-conexa e de grau m´aximo 4, pode-se

ver que qualquer cruz C de G ´e um conjunto k-ligado, onde k = min{r, s}. Para tanto,

basta perceber que apenas a retirada de no m´ınimo k v´ertices pode separar C — corres-

pondentes a uma linha, se r ≤ s, ou a uma coluna, caso contr´ario. Suponha que r ≤ s,

e logo, no pior caso, a retirada de r − 1 v´ertices da linha completamente coberta por C

faz com que uma componente de G tenha pelo menos s − 1 v´ertices, ou seja, mais do

3.8. Conjuntos k-ligados, arbustos e novelos

que (r + s − 1)/2 = |C|/2. Desta forma, a ligac¸˜ao de uma grade pode ser arbitraria-

mente grande dependendo das dimens˜oes desta, em contraste ao conceito convencional

de conectividade.

Um outro conceito relacionado `a uma nova medida de conectividade ´e o de arbusto.

Deﬁnic¸

ao 17 (Arbusto). Seja G = (V, E) um grafo. Dois subconjuntos X, Y de

v´ertices de V tocam-se se eles se interceptam (X ∩ Y = ∅) ou se existe uma aresta

e = (x, y) em G entre eles (x ∈ X e y ∈ Y ). Uma fam´ılia de subconjuntos de G que se

tocam dois a dois ´e chamada um arbusto.

Os dois conceitos est˜ao bastante relacionados. Se S ´e um conjunto k-ligado, ent˜ao

pode-se ver que, para cada par de conjuntos X e Y , |X|, |Y | < k, as componentes grandes

de G − X e G − Y se interceptam. Logo, a fam´ılia B de todas as componentes grandes

com relac¸ ˜ao a S em G ´e um arbusto. Como cada conjunto X ⊆ V (G), |X| < k, gera uma

componente grande em B, n˜ao h´a como um conjunto com menos de k v´ertices interceptar

todos os elementos em B. Assim como um arbusto pode ser obtido a partir de um conjunto

k-ligado, a rec´ıproca tamb´em ´e verdadeira. Tal aspecto pode ser melhor explorado com a

introduc¸˜ao de mais um conceito:

Deﬁnic¸

ao 18 (Conjunto de acerto). Um conjunto de v´ertices U cobre um arbusto B se

os v´ertices em U encontram cada elemento de B; neste caso, U ´e dito um conjunto de

acerto para B.

Atrav´es da deﬁnic¸ ˜ao de conjunto de acerto, pode-se ainda conferir um car´ater

quantitativo a um arbusto:

Deﬁnic¸

ao 19 (N´umero de arbusto). A ordem de um arbusto B equivale a cardinalidade

do seu menor conjunto de acerto, sendo denotado por B. O n

umero de arbusto de um

grafo G, denotado por NA(G), ´e o m´aximo obtido dentre as ordens de seus arbustos.

Logo, pela deﬁnic¸˜ao de n´umero de arbusto, pode-se dar uma deﬁnic¸ ˜ao mais exata

para a relac¸˜ao entre arbusto e conjunto k-ligado. Como todo conjunto k-ligado gera um

arbusto B tal que este n˜ao pode ser coberto por nenhum conjunto X com menos de k

v´ertices, segue que B tem ordem no m´ınimo k.

Por outro lado, qualquer conjunto de acerto B

∗

m´ınimo de um arbusto B pode gerar

um conjunto no m´aximo B/2-ligado. Basta ver que um conjunto X ⊆ B

∗

, X ≤ B/2,

gera uma componente de B que deve conter os v´ertices restantes de B

∗

, sendo portanto

uma componente grande. Logo, todo arbusto gera um conjunto no m´ınimo k-ligado tal

que k ´e no m´aximo metade da ordem do arbusto. O lema seguinte vincula as relac¸ ˜oes para

todo o grafo, e segue como conseq¨uˆencia direta do que foi discutido nesta sec¸ ˜ao at´e agora.

Lema 3.20 (Reed [1997]). Para todo grafo G, lig(G) ≤ NA(G) ≤ 2lig(G).

Prova. Como conjunto S k-ligado gera um arbusto B de ordem no m´ınimo k, o maior

valor de poss´ıvel para a ordem de um arbusto em um grafo G depende do maior k para o

qual G admite um conjunto k-ligado, ou seja, NA(G) = max{B : B ´e um arbusto em

G} ≥ max{k : existe S k-ligado em G} =lig(G).

O outro lado da desigualdade ´e mostrado de modo semelhante. Seja B um arbusto

que realiza o n´umero de arbusto em G, ou seja, B = NA(G). Como todo arbusto gera

3. Decomposic¸

ao em

Arvore

um conjunto k-ligado, B garante a existˆencia de um tal conjunto com k no m´ınimo B/2.

Logo, o maior valor de k depende de NA(G), lig(G) = max{k : existe S k-ligado em

G} ≥ NA(G)/2. 

Um exemplo t´ıpico de arbusto ´e o conjunto de cruzes em uma grade. Claramente,

a uni˜ao das cruzes de uma grade forma um arbusto de ordem min{r, s}, onde qualquer

linha e qualquer coluna representa um conjunto de acerto. De forma a aproveitar o fato

de que a menor dimens˜ao de uma grade ´e a mais relevante, normalmente refere-se a uma

grade regular k × k. Claramente, uma grade k × k tem um arbusto de ordem k.

De maneira semelhante aos conceitos de arbusto e conjunto k-ligado, assim tamb´em

um arbusto em um grafo G e uma decomposic¸ ˜ao em ´arvore para G est˜ao intimamente

relacionados. O modo como essa relac¸ ˜ao se d´a ´e elucidado pelos dois lemas seguintes.

Lema 3.21 (Reed [1997]). Sejam G um grafo, B um arbusto de G e D = (X =

}

i∈I

, T = (I, F )) uma decomposic¸

ao em

arvore de G. Ent

ao existe um n

o b em T

tal que X

e um conjunto de acerto para B.

Prova. Sejam G = (V, E), D e B = {B

}

j∈J

como deﬁnidos no enunciado. Para cada

em B, seja T

= {t ∈ T : v ∈ B

e v ∈ X

, v ∈ V }. Claramente, cada T

induz uma

sub-´arvore de T , e logo, pelo Lema 2.2, T

∗



j∈J

= ∅ induz uma nova sub-´arvore

de T. Basta agora ver que qualquer n´o b de T

∗

pertence a todas as sub-´arvores T

, e logo

encontra todos os elementos de B, sendo um conjunto de acerto para este. 

Lema 3.22 (Diestel [2000]). Para todo arbusto B de um grafo G existe uma decomposi-

c¸

ao em

arvore D = (X = {X

}

i∈I

, T = (I, F )) de G tal que se |X

| > B, X

∈ X ,

ent

ao X

ao cobre B.

Uma decomposic¸˜ao em ´arvore satisfazendo o Lema 3.22 acima ´e dita B-admiss

ıvel.

A prova do lema acima ´e na verdade uma parte da prova de outro teorema central na

relac¸ ˜ao entre arbustos e DEA’s; a vers˜ao da prova fornecida por Diestel ´e mais curta que

a prova original.

Teorema 3.23 (Seymour e Thomas [1993]). Seja k ≥ 0 um inteiro. Um grafo tem lar-

gura em

arvore no m

aximo k se e somente se cont

em um arbusto de ordem (estritamente)

maior que k.

O Teorema 3.23 ´e conhecido como Teorema da Dualidade para Largura em

Arvore

sendo tamb´em usualmente expresso sob outra forma:

Teorema 3.24 (Dualidade para Largura em

Arvore, Robertson e Seymour [1986]). Para

todo grafo G, LA(G) = NA(G) − 1.

Prova. Seja G um grafo. Pelo Lema 3.21, a partir de uma decomposic¸ ˜ao em ´arvore D

de G ´e sempre poss´ıvel obter um arbusto B tal que existe uma parte de D contendo um

conjunto de acerto m´ınimo para B. Logo, LA(D) ≥ B−1. Como a largura em ´arvore de

qualquer decomposic¸ ˜ao ´e limitada pela ordem do seu arbusto derivado, segue que o menor

valor para a largura ´e no m´ınimo o maior valor para ordem, e logo LA(G) ≥ NA(G) − 1.

Por outro lado, pelo Lema 3.22, todo arbusto B gera uma decomposic¸˜ao em

´arvore B-admiss´ıvel D, e logo, como qualquer parte de D encontra todo elemento de

3.8. Conjuntos k-ligados, arbustos e novelos

B, LA(D) ≤ B − 1. Pelo mesmo motivo, a largura em ´arvore de G deve estar limitada

pelo maior valor poss´ıvel de um conjunto de acerto para um arbusto B, e logo segue que

LA(G) ≤ NA(G) − 1. 

Embora a relac¸˜ao entre arbustos e DEA’s seja bastante estreita, ela n˜ao permite uma

equivalˆencia entre os conceitos: um arbusto B pode gerar mais de uma decomposic¸˜ao em

´arvore de largura no m´aximo B−1, enquanto que uma decomposic¸˜ao em ´arvore D pode

gerar mais de um arbusto de ordem no m´aximo LA(D) + 1. Para se obter uma relac¸ ˜ao

mais estreita ainda, ´e preciso acrescentar mais condic¸ ˜oes `a formac¸˜ao de um arbusto.

Deﬁnic¸

ao 20 (Novelo). Um arbusto N ´e um novelo se, para qualquer tripla (N

, N

)

de elementos de N , uma das duas situac¸ ˜oes abaixo ocorre:

1. N

∩ N

´e n˜ao vazio;

2. existe uma aresta e tal que T

, T

e T

cont´em uma extremidade de e.

Dados um arbusto B e um grafo G, deﬁne-se a func¸ ˜ao f

: {X : X ⊆ V (G), |X| <

B} → P(V (G)) como um mapeamento de um subconjunto X satisfazendo o dom´ınio

de f

`a ´unica componente de G − X contendo um elemento de B . Diz-se ent˜ao que

dois arbustos B

e B

s˜ao distingu

ıveis em um grafo G se existe algum X ⊆ V (G),

|X| < B

, |X| < B

, tal que f

(X) = f

(X) — e, neste caso, X ´e chamado

, B

)-distintor; caso contr´ario, B

e B

s˜ao ditos indistingu

ıveis.

Um arbusto ´e dito maximal se n˜ao existe nenhum outro indistingu´ıvel dele e que

tenha maior ordem. O mesmo conceito vale para novelos; de fato, vale notar que novelos

maximais indistingu´ıveis tˆem mesma ordem.

O teorema abaixo estabelece uma relac¸ ˜ao muito pr´oxima entre os novelos maximais

de um grafo G e uma decomposic¸˜ao em ´arvore especial de G.

Teorema 3.25 (Decomposic¸˜ao em ´arvore canˆonica, Robertson e Seymour [1995]). Para

qualquer grafo G, pode-se construir uma decomposic¸

ao em

arvore D = (X , T ) que tenha

as seguintes propriedades:

1. Para cada novelo maximal N de G, existe exatamente um n

o t(N ) de T tal que

t(N )

forma um conjunto de acerto para N .

2. Se N

e N

ao novelos maximais indistingu

ıveis ent

ao t(N

) = t(N

3. Se N

e N

ao novelos maximais distingu

ıveis ent

ao t(N

) = t(N

) e existe uma

aresta st no caminho t(N

)T t(N

) tal que X

∩ X

e um (N

, N

)-distintor de

ordem m

ınima.

4. Para cada n

o t de uma decomposic¸

ao em

arvore, existe um novelo maximal tal que

t(N ) = t.

Como Reed (1997) observa, o Teorema 3.25 garante a existˆencia de uma

decomposic¸˜ao em ´arvore D para um grafo G que separa G em partes altamente cone-

xas, usando separadores que s˜ao os menores poss´ıveis. Para isto, basta ver que existe uma

relac¸ ˜ao de equivalˆencia entre D e um conjunto de novelos maximais distingu´ıveis N para

G onde, pelas restric¸ ˜oes (1) e (4) do teorema, cada parte de D ´e um conjunto de acerto

3. Decomposic¸

ao em

Arvore

para algum novelo em N. Logo, n˜ao podem existir partes X

e X

em D tais que X

⊆ X

e conseq¨uentemente D ´e uma boa decomposic¸˜ao em ´arvore.

3.9 Grades

Como mostrado na sec¸ ˜ao anterior, as grades tornam-se interessantes por apresentarem

ligac¸˜ao e n´umero de arbusto arbitrariamente grandes. Tamb´em na sec¸ ˜ao anterior foi apre-

sentada a relac¸˜ao pr´oxima entre arbustos e decomposic¸ ˜oes em ´arvore, melhor explicitada

pelos Teoremas 3.23 e 3.23. Em particular, pode-se ver que uma grade k × k tem largura

em ´arvore no m´ınimo k−1, j´a que apresenta um arbusto de ordem k. De fato, a largura em

´arvore de uma grade k×k ´e exatamente k (em (Reed 1997) ´e mostrada uma decomposic¸ ˜ao

em ´arvore de largura m´ınima).

Desta forma, uma grade k × k pode ter largura em ´arvore arbitrariamente grande,

e logo torna-se uma obstruc¸ ˜ao natural para classes de grafos com largura em ´arvore limi-

tada: se um grafo G possui uma grade k × k como menor, ent˜ao, pela Propriedade 4, a

largura em ´arvore de G ´e no m´ınimo k. Uma conseq¨uˆencia deste fato ´e que, ao se cons-

truir um conjunto de obstruc¸ ˜ao para uma classe de grafos com largura em ´arvore limitada,

as grades e seus menores tˆem importˆancia considerada. De fato, como toda grade e seus

menores s˜ao planares, qualquer classe Proib



(H), onde algum elemento H de H ´e n˜ao

planar, cont´em todas as grades, e logo n˜ao pode conter grafos com largura em ´arvore

limitada. O seguinte teorema estabelece uma equivalˆencia entre o que foi discutido:

Teorema 3.26 (Robertson e Seymour [1986]). Dado um grafo H, os grafos que n

cont

em H como menor t

em largura em

arvore limitada se e somente se H

e planar.

Uma prova do Teorema 3.26 bem mais curta que a original pode ser encontrada em

(Diestel 2000). A id´eia da prova apresentada por Diestel ´e mostrar que a proibic¸˜ao de

qualquer grafo planar como menor limita a largura em ´arvore de um grafo. Al´em disso,

basta mostrar tal proibic¸˜ao para uma grade, j´a que todo grafo planar ´e menor de alguma

grade. Logo, basta mostrar que:

Teorema 3.27 (Robertson e Seymour [1986]). Para todo inteiro r, existe um inteiro k

tal que todo grafo com largura em

arvore no m

ınimo k tem um menor de uma grade

r × r.

Com base nestes resultados, torna-se mais claro agora o motivo da extens˜ao do

conjunto de menores proibidos para a classe de grafos G tais que LA(G) ≤ 3. N˜ao se

pode proibir apenas o K

, j´a que este ´e planar e logo Proib



({K

}) cont´em todas as

grades, tendo seus grafos largura em ´arvore ilimitada.

3.10 Conceitos relacionados

Uma decomposic¸

ao em caminho de um grafo G ´e uma decomposic¸˜ao em ´arvore D =

(X = {X

}

i∈I

, T = (I, F )) onde T ´e um caminho. Analogamente `a deﬁnic¸˜ao de largura

em ´arvore, deﬁne-se a largura em caminho de uma decomposic¸˜ao em caminho D como a

3.10. Conceitos relacionados

maior cardinalidade de suas partes menos um, LC

(D) = max

i∈I

{|X

| − 1}, e a largura

em caminho de um grafo G como sendo a largura m´ınima observada dentre todas as

larguras em caminho de G.

Decomposic¸ ˜oes em caminho s˜ao, em geral, de tratamento mais f´acil, dada a sim-

plicidade de sua estrutura. Como ´e de se esperar, v´arias propriedades que valem para

decomposic¸ ˜oes em ´arvore valem tamb´em para decomposic¸ ˜oes em caminho, como as Pro-

priedades 3, 2 e 4. Como se ver´a no pr´oximo cap´ıtulo, decomposic¸ ˜oes em caminho podem

inclusive ser usadas como base para o desenvolvimento de algoritmos para decomposic¸ ˜ao

em ´arvore, assim como a pesquisa para tais algoritmos ´e enriquecida com o desenvol-

vimento de t´ecnicas de decomposic¸ ˜oes em ´arvore m´ınimas para classes espec´ıﬁcas de

grafos.

Um outro conceito interessante ´e o de decomposic¸˜ao em ´arvore ligada ou enxuta:

Deﬁnic¸

ao 21 (Decomposic¸˜ao em ´arvore ligada). Uma decomposic¸˜ao em ´arvore D =

(X = {X

}

i∈I

, T = (I, F )) de um grafo G = (V, E) ´e dita ligada se, al´em das restric¸ ˜oes

usuais de uma decomposic¸ ˜ao em ´arvore, esta satisfaz:

[P4L] dados um n´umero s ∈ N e n´os i, j ∈ I de T , ou G cont´em s caminhos disjuntos

-V

ou existe um t ∈ iT j tal que |V

| < s.

A propriedade de ser ligada pode ser vista como um fortalecimento do conceito

de ser boa: al´em de n˜ao conter partes redundantes, os ramos de uma decomposic¸˜ao em

´arvore ligada de um grafo G cont´em v´ertices de modo somente a manter a conectivi-

dade m´ınima em G. Desta forma, G ser´a sempre minimalmente conexo ao longo de cada

ramo. Decomposic¸ ˜oes em ´arvore ligadas tamb´em constituem ferramentas importantes

para encontrar a largura em ´arvore de um grafo G, devido principalmente ao seguinte

resultado:

Teorema 3.28 (Thomas [1990]). Todo grafo G admite uma decomposic¸

ao em

arvore

ligada de largura LA(G).

Intuitivamente, pode-se perceber que a busca por partes pequenas em uma

decomposic¸˜ao pode vantajosamente ser compatibilizada com a identiﬁcac¸˜ao de subgra-

fos altamente conexos em um grafo, e que comporiam um ramo numa decomposic¸˜ao em

´arvore ligada.

Cap´ıtulo 4

Algoritmos de Decomposic¸

ao em

Arvore

4.1 Introduc¸

No cap´ıtulo anterior foram vistos conceitos e resultados te´oricos envolvendo decomposic¸ ˜oes

em ´arvore de grafos; o objetivo deste cap´ıtulo ´e complementar, e concentra-se em discutir

t´ecnicas e algoritmos para obtenc¸˜ao de decomposic¸ ˜oes em ´arvore. Em particular, um dos

grandes objetivos na pesquisa de decomposic¸ ˜oes em ´arvore envolve o desenvolvimento de

m´etodos para determinac¸ ˜ao da decomposic¸˜ao em ´arvore m´ınima de um grafo. Tal objetivo

pode ser alcanc¸ado com a resoluc¸˜ao do seguinte problema de otimizac¸ ˜ao:

Problema: MIN LARGURAEM

ARVORE

Inst

ancia: Um grafo G = (V, E).

Encontrar: A largura em ´arvore de G, LA(G).

Um outro problema, mais simples, decide, dados um grafo G e um inteiro k, se a

largura em ´arvore de G ´e no m´aximo k. Este corresponde a vers˜ao de decis˜ao do problema

acima, sendo denotado por k-LARGURA EM

ARVOR E:

Problema: k-LARGURAEM

ARVORE

Inst

ancia: Um grafo G = (V, E) e um inteiro k.

Decidir: A largura em ´arvore de G, LA(G), ´e no m´aximo k?

Conforme Arnborg et al. (1987) mostraram, k-LARGURAEM

ARVORE ´e NP-

completo, mesmo quando restrito a algumas classes de grafos, como grafos bipartite,

por exemplo. No entanto, existem ainda outras classes de grafos para as quais k-

LARGURAEM

ARVOR E admite complexidade em tempo polinomial, como para as classes

de grafos cordais. O objetivo de tratar o problema restrito a algumas classes de grafos

´e a obtenc¸˜ao de heur´ısticas para limitantes superiores, como se ver´a na Sec¸ ˜ao 4.2, onde

grafos cordais s˜ao o foco.

4.1. Introduc¸

Quando o parˆametro k ´e uma constante ﬁxa, e logo n˜ao faz parte da entrada do

problema, tem-se um caso bem estudado. Neste caso, distinguem-se duas vers˜oes do pro-

blema: a vers˜ao de decis

ao, quando se deve apenas decidir se a largura em ´arvore de um

grafo G ´e no m´aximo k, retornando verdadeiro em caso aﬁrmativo e falso caso contr´ario;

e a vers˜ao de construc¸

ao, quando tamb´em uma decomposic¸˜ao em ´arvore de largura no

m´aximo k deve compor a sa´ıda, em caso aﬁrmativo.

O primeiro algoritmo em tempo polinomial para a vers˜ao construtiva de k-

LARGURAEM

ARVOR E se deve a Arnborg et al. (1987), tendo complexidade O(n

k+2

). A

partir dos resultados com menores de grafos, Robertson e Seymour fornecem uma prova

n˜ao construtiva da existˆencia de um algoritmo em tempo O(n

) para a vers˜ao de decis˜ao

(Robertson e Seymour 1995). Seu algoritmo tem uma estrutura em duas fases:

1. Na primeira fase, um algoritmo em tempo O(n

) decide se G admite uma

decomposic¸˜ao em ´arvore D com largura no m´aximo 4k + 3 ou, caso contr´ario,

se G tem largura em ´arvore maior que k. Como Bodlaender (1997) observa, na ver-

dade Robertson e Seymour usam um conceito semelhante a largura em ´arvore para

alcanc¸ar este resultado, mas a diferenc¸a ´e somente t´ecnica e n˜ao relevante.

2. A decomposic¸˜ao obtida na primeira fase ´e agora usada para veriﬁcar, em tempo

linear, se G contem algum menor pertencente ao conjunto de obstruc¸˜ao para a classe

de grafos com largura em ´arvore no m´aximo k.

Grande parte dos algoritmos empregados para o problema ainda seguem, de al-

guma forma, a estrutura em duas fases. Como a complexidade de um algoritmo deste

tipo depende da primeira fase, a grande maioria dos esforc¸os de melhoria foram orien-

tados para esta etapa. V´arios autores forneceram vers˜oes mais eﬁcientes, incluindo um

algoritmo aleat´orio de Matousek e Thomas (1992), uma vers˜ao paralela de Lagergren

(1996), e uma vers˜ao utilizando separadores com caracter´ısticas especiais de Reed (1992),

de complexidade O(n log n). Este ´ultimo algoritmo ser´a visto em maiores detalhes na

Sec¸ ˜ao 4.3.

Cada um destes algoritmos de primeira fase determina se a largura em ´arvore de um

grafo G dado como entrada ´e maior que k ou, caso contr´ario, retorna uma decomposic¸˜ao

em ´arvore de G com largura no m´aximo f(k), onde f ´e uma func¸˜ao linear de k com

coeﬁcientes pequenos. Para a segunda fase, Bodlaender e Kloks (1996) encontraram um

algoritmo em tempo linear para a vers˜ao de construc¸˜ao, ou seja, dada uma decomposic¸˜ao

em ´arvore de um grafo de entrada G com largura l > k, o algoritmo decide se G admite

uma nova decomposic¸˜ao em ´arvore de largura no m´aximo k, e a retorna. Usando este

resultado, Bodlaender (1996) encontrou uma algoritmo resolvendo as duas fases conjun-

tamente em tempo linear, para cada k constante, para a vers˜ao construtiva. Este ´e o melhor

resultado encontrado at´e agora, sendo discutido na Sec¸ ˜ao 4.4.

Uma outra abordagem interessante foi desenvolvida por Arnborg et al. (1993),

usando uma t´ecnica conhecida como reduc¸

ao em grafos. Embora os algoritmos apre-

sentados por Arnborg et al. tenham complexidade em tempo linear, sua complexidade em

espac¸o ´e exponencial. V´arios outros autores adotaram abordagens semelhantes como pa-

radigma, como por exemplo Courcelle (1990), contribuindo para o reﬁnamento da t´ecnica.

de Fluiter e Bodlaender (1996) modiﬁcaram alguns dos conceitos para obter um algo-

4. Algoritmos de Decomposic¸

ao em

Arvore

ritmo baseado em reduc¸˜ao e com complexidade linear tanto em tempo como em espac¸o.

A t´ecnica de reduc¸˜ao em grafos ´e apresentada na Sec¸ ˜ao 4.3.

Todos os algoritmos at´e agora apresentados tˆem uma constante escondida na ex-

press˜ao de complexidade que ´e, no m´ınimo, exponencial em k. Como Bodlaender (1997)

comenta, a medida em que k aumenta os algoritmos tornam-se cada vez mais inadequados

para aplicac¸ ˜oes pr´aticas. Nos casos em que k = 2, 3 ou 4, algoritmos espec´ıﬁcos foram

encontrados, sendo de complexidade linear e baseados em reduc¸ ˜ao em grafos (Matousek

e Thomas 1991; Arnborg e Proskurowski 1986; Sanders 1996).

4.2 DEA em grafos cordais

Assim como no cap´ıtulo anterior uma ˆenfase especial foi dada aos grafos cordais, de

onde algumas caracterizac¸ ˜oes importantes foram obtidas, ´e interessante discutir aqui,

inicialmente, o problema de largura em ´arvore quando restrito a esta classe de grafos.

Antes de apresentar um algoritmo para discuss˜ao, ´e necess´ario introduzir a notac¸˜ao

seguinte. Se D = (X , T ) ´e uma decomposic¸ ˜ao em ´arvore de um grafo G, ent˜ao T (D)

retorna a ´arvore da decomposic¸˜ao, ou seja, T (D) = T ; de modo an´alogo, X (D) retorna

a fam´ılia de partes de D, X (D) = X . A func¸˜ao COMPONENTES (G) retorna uma lista

contendo os conjuntos de v´ertices que induzem cada componente no grafo G, respectiva-

mente (um conjunto em cada posic¸˜ao da lista). O algoritmo DEA

CORDAL da Figura 4.1

constr´oi uma decomposic¸˜ao em ´arvore m´ınima para um grafo cordal.

 Algoritmo DEA CORDA L(G)

 Entrada: Um grafo cordal G = (V, E).

 Sa´ıda: Uma decomposic¸ ˜ao em ´arvore D = (X , T ) m´ınima de G.

1. in´ıcio

2. se G ´e completo ent

3. retorna ({V }, ({t}, ∅))

4. sen

5. selecione u, v : (u, v) ∈ E, u, v ∈ V

6. S ← SEP MIN IM AL(u, v, G)

7. D ← ({S}, ({t

}, ∅))

8. para cada C ∈ COM PO NE NT ES(G[V \ S]) fac¸a

9. D



← DEA COR DAL(G[C ∪ S])

10. selecione t



: S ⊆ X



, t



∈ T (D



), X



∈ X (D



)

11. X (D) ← X (D) ∪ X (D



)

12. T (D) ← T (D) ∪ T (D



)

13. E(T (D)) ← E(T (D)) ∪ {(t, t



)}

14. retorna D

15. ﬁm

Figura 4.1. Algoritmo para decomposic¸˜ao em ´arvore de grafos cordais.

4.2. DEA em grafos cordais

Pelo Lema 2.9, todo separador minimal de um grafo cordal ´e uma clique. Logo,

dado um separador S de um grafo cordal G, cada componente C de G − S ´e tamb´em

cordal, o que justiﬁca a recurs˜ao na linha 9. Como a base da recurs˜ao ocorre nas linhas 2

e 3, pode-se ver claramente que toda parte da decomposic¸ ˜ao ´e uma clique. Logo, como

a maior clique de G est´a exatamente contida em alguma parte da decomposic¸˜ao obtida,

esta ´e m´ınima. Resta justiﬁcar a existˆencia de t



na linha 10; isto ´e imediato a partir do

Lema 2.10, j´a que um v´ertice v tal que {v} ∪ S induz uma clique em G − S certamente

existe, e logo tamb´em existe um n´o t



em T



) contendo {v} ∪ S.

Atrav´es do algoritmo DEA CORDAL , pode-se perceber que todo grafo cordal pode

ser obtido recursivamente pela colagem de grafos cordais ao longo de subgrafos com-

pletos. Tal caracter´ıstica pode ser extremamente vantajosa no projeto de algoritmos para

alguns problemas de otimizac¸ ˜ao, j´a que algumas caracter´ısticas de cada parte de uma

decomposic¸˜ao obtida pelo algoritmo DEA

CORDAL podem ser estendidas para todo o

grafo, como, por exemplo, a n˜ao continˆencia de algum menor K

, para algum r inteiro

constante. Tal fato motiva a deﬁnic¸˜ao de uma decomposic¸˜ao em ´arvore particular:

Deﬁnic¸

ao 22 (Decomposic¸˜ao em ´arvore simplicial). Uma decomposic¸˜ao em ´arvore D =

(X = {X

}

i∈I

, T = (I, F )) de um grafo G = (V, E) ´e dita simplicial se, al´em das

restric¸ ˜oes usuais de uma decomposic¸˜ao em ´arvore, esta satisfaz:

[P4S] dados n´os i, j ∈ I de T , o separador X

∩ X

forma uma clique em G.

Logo, a decomposic¸˜ao obtida pelo algoritmo DEA CORDAL ´e simplicial. De fato,

n˜ao ´e dif´ıcil perceber que todo grafo admite uma decomposic¸˜ao em ´arvore simplicial

— embora n˜ao necessariamente m´ınima, como no caso dos grafos cordais — bastando

para tanto aplicar recursivamente o mesmo procedimento usando separadores clique at´e

que somente partes irredut´ıveis sejam obtidas. Como Diestel (2000) observa, se todos

os separadores clique usados forem minimais, ent˜ao o conjunto de partes obtido ser´a at´e

mesmo ´unico.

Al´em de motivar uma abordagem mais abrangente para todos os grafos, o estudo

de grafos cordais pode ainda fornecer elementos para a obtenc¸ ˜ao de um limitante su-

perior para a largura em ´arvore de grafos em geral. Basta perceber, com a ajuda do

Lema 3.9, que a largura em ´arvore de um grafo ´e no m´aximo a largura em ´arvore de

qualquer cordalizac¸˜ao deste. Desta forma, o algoritmo DEA CORDAL pode ser modiﬁ-

cado para encontrar uma cordalizac¸˜ao de um grafo G, e conseq¨uentemente, um limitante

para LA(G), como mostrado na Figura 4.2.

A corretude de DEA CORDAL LS segue diretamente da de DEA CORDAL . Vale

notar que, a rigor, a escolha de um v´ertice na linha 2 para construc¸˜ao de um separador

S pode ser feita arbitrariamente. A escolha de um v´ertice de grau m´ınimo ´e apenas uma

regra heur´ıstica para que as cliques na cordalizac¸˜ao resultante sejam menores.

Em (Koster et al. 2001) s˜ao mostrados outros algoritmos para limitantes inferio-

res e superiores da largura em ´arvore de um grafo G, baseados no maior grau m´ınimo

encontrado para todos os subgrafos de G, e em cordalizac¸ ˜oes de G, respectivamente.

4. Algoritmos de Decomposic¸

ao em

Arvore

 Algoritmo DEA COR DAL LS(G)

 Entrada: Um grafo G = (V, E).

 Sa´ıda: Uma decomposic¸ ˜ao em ´arvore D = (X , T ) de G.

1. in´ıcio

2. selecione v : d(v) = δ(G), v ∈ V

3. S ← N

(v) ∪ {v}

4. G



← G + K(S)

5. se G



´e completo ent

6. retorna ({V }, ({t}, ∅))

7. sen

8. D ← ({S}, ({t

}, ∅))

9. para cada C ∈ COM PO NE NT ES(G[V \ S]) fac¸a

10. D



← DEA COR DAL LS(G



[C ∪ S])

11. selecione t



: S



⊆ X



, t



∈ T (D



), X



∈ X (D



)

12. X (D) ← X (D) ∪ X (D



)

13. T (D) ← T (D) ∪ T (D



)

14. E(T (D)) ← E(T (D)) ∪ {(t, t



)}

15. retorna D

16. ﬁm

Figura 4.2. Algoritmo para decomposic¸˜ao em ´arvore baseado em cordalizac¸˜ao.

4.3 DEA usando separadores fortes

Na sec¸˜ao anterior viu-se como a noc¸˜ao de separadores pode ser extremamente ´util na

determinac¸˜ao de uma decomposic¸˜ao em ´arvore de um grafo. A introduc¸˜ao de um novo

conceito de separador permite a obtenc¸ ˜ao de uma decomposic¸˜ao em ´arvore de largura

limitada.

Deﬁnic¸

ao 23 (Separador forte). Um separador forte em um grafo G = (V, E) ´e um

conjunto X de v´ertices, X ⊆ V , tal que nenhuma componente de G − X contem mais

|V (G − X)| v´ertices. De modo semelhante, um S-separador forte para algum S ⊆ V

´e um conjunto de v´ertices X tal que nenhuma componente de G − X contem mais de

|S − X| v´ertices de S. A ordem de um separador ´e a cardinalidade de X.

Vale observar que a deﬁnic¸ ˜ao encontrada em Reed (1992) refere-se apenas a um se-

parador como sendo um conjunto satisfazendo as condic¸ ˜oes da deﬁnic¸˜ao acima; de modo

a evitar confus˜ao com o conceito tradicional de separador, a deﬁnic¸ ˜ao aqui empregada foi

modiﬁcada para separador forte.

A primeira relac¸ ˜ao entre separadores fortes e largura em ´arvore ´e estabelecida pelo

seguinte lema:

Lema 4.1 (Reed [1992]). Seja G = (V, E) um grafo. Se G tem largura em

arvore no

aximo k, ent

ao para todo conjunto S ⊆ V , G cont

em um S-separador forte de ordem

no m

aximo k + 1.

4.3. DEA usando separadores fortes

Prova. Claramente, todo conjunto S com no m´aximo k +1 v´ertices admite a si mesmo

como separador forte, e logo apenas conjuntos S com |S| > k + 1 ser˜ao considerados.

O objetivo da prova ´e mostrar que ou G tem um S-separador forte de ordem no m´aximo

k +1 ou G tem um arbusto de ordem no m´ınimo k +2, e logo, pelo Teorema da dualidade,

G tem largura em ´arvore no m´ınimo k + 1.

Considere ent˜ao a fam´ılia B

de subgrafos conexos de G tais que B ∈ B

se e

somente se |N

(B)| ≤ k + 1 e |B ∩ S| >

|S − N

(B)|. Suponha agora que existam

dois elementos B

e B

de B

que n˜ao se tocam. Logo, como B

∩ B

= ∅ e n˜ao existem

arestas entre B

e B

, tem-se que B

⊆ G − N

) − B

− N

) e B

⊆ G −

) − B

− N

). Da´ı segue que (B

∩ S) ∪ (B

∩ S) ⊆ S − N

) − N

e logo |B

∩ S| + |B

∩ S| ≤ |S − N

) − N

)|. Por outro lado, como |B

∩

S| >

|S − N

)| e |B

∩ S| >

|S − N

)| pela presenc¸a de ambos em B

e como |S − N

)| + |S − N

)| ≥ 2 · |S − N

) − N

)|, tem-se que

∩ S| + |B

∩ S| >

|S − N

) − N

)|. Da contradic¸˜ao encontrada, conclui-

se que quaisquer dois elementos de B

se tocam, e logo B

´e um arbusto. Mas se um

conjunto de acerto X para B

tem ordem no m´aximo k + 1 ent˜ao nenhuma componente

de G − X cont´em mais de

|S − X| v´ertices, caso contr´ario tal componente estaria em

S — pois X seria a vizinhanc¸a desta componente — contradizendo o fato de X ser um

conjunto de acerto. Logo, ou X ´e um S-separador forte ou B

tem ordem no m´ınimo

k + 2, o que conclui a prova. 

A relac¸ ˜ao rec´ıproca a do Lema 4.1 garante uma condic¸˜ao suﬁciente mais relaxada

para a largura em ´arvore m´axima de um grafo:

Lema 4.2 (Reed [1992]). Seja G = (V, E) um grafo. Se, para todo S ⊆ V , G cont

um S-separador forte de ordem k + 1, ent

ao G tem largura em

arvore no m

aximo 4k + 1.

Com base no Lema 4.2, pode-se ver que se um grafo G n˜ao possui S-separadores

fortes, para todo S ⊆ V , ent˜ao a largura em ´arvore de G ´e no m´aximo 4k + 1. A prova

do Lema 4.2 ´e imediata se uma rotina recursiva ´e executada com base neste fato: basta

encontrar um S-separador forte X e aplicar a rotina em cada componente de G − X.

Como |X| ≤ k + 1, tem-se que |S| ≤ 3k + 1 — o que ﬁcar´a mais claro ap´os a prova do

Lema 4.3 — e logo segue que |X ∪ S| ≤ 4k + 1. O argumento deste esboc¸o de prova ﬁca

mais claro se a rotina recursiva ´e posta em forma de um algoritmo, como proposto por

Reed (1992):

1. Encontre um S-separador forte X de ordem no m´aximo k+1. Se tal separador forte

n˜ao existe, ent˜ao pare, e retorne S. Caso contr´ario, sejam U

, . . . , U

as componentes

de G − X, G

= X ∪ U

e S

= (U

∩ S) ∪ X, 1 ≤ i ≤ l.

2. Como X ´e um S-separador forte, |S| ≤ 3k + 1, e como |X| ≤ k + 1, tem-se que

| ≤ 3k +1, 1 ≤ i ≤ l, e logo pode-se aplicar a rotina recursivamente em cada G

procurando um S

-separador forte. Caso n˜ao seja encontrado um separador forte de

ordem no m´aximo k + 1 em algum G

, pare: G tamb´em n˜ao cont´em um separador

forte de ordem no m´aximo k + 1.

3. Neste passo as rotinas recursivas para cada G

foram bem sucedidas, retornando

uma decomposic¸˜ao em ´arvore D

= (X

, T

), onde existe um n´o destacado t

4. Algoritmos de Decomposic¸

ao em

Arvore

cada T

tal que S

⊆ X

. Uma decomposic¸˜ao em ´arvore D = (X , T ) para G pode

ent˜ao ser encontrada com base nas D

, onde:

(a) V (T ) =





i=1

V (T

)



∪ {t};

(b) E(T ) =





i=1

E(T

)



∪ {(t, t

) : 1 ≤ i ≤ l};





i=1



∪ X

, X

= X ∪ S.

ou seja, D ´e uma decomposic¸˜ao formada pela uni˜ao entre as l decomposic¸ ˜oes D

pela adic¸˜ao de um n´o t que ´e feito adjacente a cada n´o destacado t

, sendo a parte

correspondente a t igual a uni˜ao entre X e S, X

(Figura 4.3). Retorne D.

Figura 4.3. Decomposic¸˜ao em ´arvore obtida pelo algoritmo de Reed: os ramos correspondentes a duas

componentes, U

e U

s˜ao mostrados, assim como os novos separadores fortes para cada componente, S

, respectivamente, em cinza, e os n´os destacados de cada ´arvore T

e T

Vale notar que a construc¸ ˜ao para obtenc¸˜ao de D no passo 3 j´a ´e familiar, sendo

encontrada uma forma semelhante na prova da Propriedade 3. N˜ao ´e dif´ıcil veriﬁcar que

D ´e realmente uma decomposic¸˜ao em ´arvore, j´a que X

sempre cont´em a intersec¸˜ao entre

quaisquer duas partes correspondentes a dois n´os destacados. Al´em disso, como a maior

parte de uma decomposic¸˜ao D

cont´em no m´aximo a uni˜ao entre seu S

-separador forte

e S

, segue que LA(D

) ≤ 4k + 1. De fato, a rotina apresentada acima ´e uma prova

algor´ıtmica do Lema 4.2. O algoritmo de Reed ´e formalizado na Figura 4.4

A an´alise de complexidade segue com a ajuda do seguinte lema:

Lema 4.3 (Reed [1997]). Dado um conjunto S ⊆ V de um grafo G = (V, E), com

|S| ≤ 3k + 1, existe uma rotina k-SEPARADOR que retorna um S-separador forte de

ordem no m

aximo k + 1, se este existe, com complexidade de tempo O(k · 3

3k+1

· |E|).

4.3. DEA usando separadores fortes

 Algoritmo k-DEA REE D(G, S)

 Entrada: Um grafo G = (V, E) e S ⊆ V tal que |S| ≤ 3k + 1.

 Sa´ıda: Se LA(G) ≤ k, uma decomposic¸ ˜ao em ´arvore D = (X , T ) de G

com largura no m´aximo 4k + 1; caso contr´ario, um subconjunto S de v´ertices

tal que G n˜ao cont´em um S-separador forte de ordem no m´aximo k + 1.

1. in´ıcio

2. se |V | ≤ 4k + 1 ent

3. retorna ({V }, ({t}, ∅))

4. sen

5. X ← k-SEPAR AD OR(S, G)

6. se X = ∅ ent

7. retorna S

8. sen

9. D ← ({X ∪ S}, ({t}, ∅))

10. para cada C ∈ COM PO NE NT ES(G[V \ X]) fac¸a

11. G



← G[C ∪ X]

12. S



← (C ∩ S) ∪ X

13. D



← k-DEA RE ED(G



, S



)

14. se D



´e um conjunto de v´ertices ent

15. retorna S



16. sen

17. selecione t



: S



⊆ X



, t



∈ T (D



), X



∈ X (D



)

18. X (D) ← X (D) ∪ X (D



)

19. T (D) ← T (D) ∪ T (D



)

20. E(T (D)) ← E(T (D)) ∪ {(t, t



)}

21. retorna D

22. ﬁm

Figura 4.4. Algoritmo proposto em Reed (1992).

Prova. Considere um conjunto S de v´ertices de um grafo G = (V, E), |S| ≤ 3k + 1,

como no enunciado. Inicialmente, deve-se mostrar que G admite um S-separador forte se

e somente se V pode ser particionado em 3 conjuntos A, B e X tais que cada componente

de G − X est´a contida em A ou B, |X| ≤ k + 1, |A ∩ S| ≤

|S − X| e |B ∩ S| ≤

|S − X|. A implicac¸ ˜ao contr´aria ´e imediata: basta tomar X como S-separador forte, e

logo, como toda componente C de G − X ´e tal que |C| ≤

|S − X|, e como A ∩ B = ∅

j´a que (A, B, X) ´e uma partic¸ ˜ao de V , segue que C ⊆ A ou C ⊆ B. Para o sentido

inverso, seja X tamb´em o S-separador forte, e sejam U

, . . . , U

as componentes de G−X

ordenadas decrescentemente de acordo com a cardinalidade da intersec¸˜ao com S, ou seja,

∩ S| ≥ |U

i+1

∩ S|. Basta agora deﬁnir A =



i=1

, onde j ´e o menor ´ındice tal que



j+1

i=1

(S ∩ U

)| ≥

|S − X|; e B = V \ A \ X.

A id´eia da prova agora ´e encontrar uma partic¸ ˜ao (A, B, X) de V de modo que X

seja um S-separador forte. Para tanto, podem-se considerar as combinac¸ ˜oes de v´ertices

4. Algoritmos de Decomposic¸

ao em

Arvore

de S nos conjuntos de uma partic¸˜ao (S

, S

) — ou seja, S

, S

e S

s˜ao disjuntos

e S

= S ∩ A, S

= S — tal que S

= S ∩ A, S

= S ∩ B e S

= S ∩ X. Desta

forma, a id´eia ´e encontrar uma partic¸˜ao em S e estendˆe-la de modo a obter uma partic¸˜ao

correspondente em G contendo um S-separador forte.

Como para cada v´ertice em S existem trˆes opc¸ ˜oes — estar em S

, S

ou S

— e

S tem no m´aximo 3k + 1, tem-se um total de no m´aximo 3

3k+1

combinac¸ ˜oes poss´ıveis

para uma partic¸˜ao de S. Este total de combinac¸ ˜oes ﬁca reduzido se as restric¸ ˜oes para a

partic¸˜ao em V forem aplicadas para S: como |X| ≤ k + 1, deve-se ter |S

| ≤ k + 1, e

como |A ∩ S| ≤

|S − X| e |B ∩ S| ≤

|S − X|, deve-se ter tamb´em |S

| ≤ 2|S

| e

| ≤ 2|S

|. Note agora que, assim como A e B s˜ao separados por no m´aximo k + 1

caminhos disjuntos em G — j´a que X ´e um separador de ordem no m´aximo k + 1, e

portanto cont´em pelo menos um v´ertice de cada um destes caminhos — assim tamb´em

e S

devem ser separados por, no m´aximo, k+1−|S

| caminhos disjuntos em G−S

Se existem mais de k + 1 − |S

| caminhos disjuntos entre S

e S

em G − S

, ent˜ao

existem mais de k + 1 caminhos disjuntos entre A e B em G e logo X n˜ao pode ser um

separador forte com no m´aximo k + 1 v´ertices. A Figura 4.5 facilita a compreens˜ao da

relac¸ ˜ao entre as partic¸ ˜oes.

A B

Figura 4.5. Construc¸˜ao de um S-separador forte de ordem no m´aximo k + 1.

Suponha ent˜ao que G admite um S-separador de ordem no m´aximo k + 1, e logo S

admite uma partic¸˜ao tal que existem no m´aximo k+1−|S

| caminhos disjuntos entre S

em G−S

. Tais caminhos podem ser encontrados, aplicando-se t´ecnicas de caminhos

alternados baseadas no Teorema de Menger, em tempo O(k|E|). Seja P = {v

, . . . , v

r ≤ k + 1 − |S

|, um conjunto contendo um v´ertice interno em cada caminho disjunto

encontrado entre S

e S

. Basta ver agora que X pode ent˜ao ser deﬁnido como P ∪ S

A como a uni˜ao das componentes de G − X que cont´em pelo menos um v´ertice em S

e B = V \ A \ X. Como para cada combinac¸˜ao de uma partic¸ ˜ao os caminhos disjuntos

devem ser avaliados, a complexidade total da rotina ´e O(k · 3

3k+1

· |E|). 

Como pelo Lema 3.17 tem-se E(G) < k|V (G)| para qualquer grafo G com largura

em ´arvore no m´aximo k, segue que O(|E(G)|) = O(|V (G)|), e logo a complexidade de

4.4. DEA em tempo linear

k-SEPARADO R ´e O(|V |). Vale notar que, embora k seja uma constante, contribui com um

grande fator exponencial que ﬁca escondido na notac¸ ˜ao assint´otica de complexidade.

N˜ao ´e dif´ıcil perceber que, para cada passo da recurs˜ao, a rotina ´e executada para

cada componente de G − X, ou seja, em l = O(|V |) sub-problemas disjuntos, e logo a

complexidade global de k-DEA REED ´e O(|V |

). Acrescentando a noc¸ ˜ao de S-separador

forte aproximado, Reed (1992) consegue dividir os sub-problemas de maneira que cada

um tenha tamanho no m´aximo (1 −) · |V |),  > 0, e logo pode-se concluir que a comple-

xidade ap´os a modiﬁcac¸˜ao torna-se O(|V | log |V |). O prec¸o deste ganho em desempenho

´e a obtenc¸˜ao de decomposic¸ ˜oes em ´arvore com largura no m´aximo 5k + 1, a partir de

separadores fortes de ordem no m´aximo 4k + 1.

4.4 DEA em tempo linear

Um dos principais resultados para decomposic¸ ˜oes em ´arvore ´e a obtenc¸˜ao de um algoritmo

linear para resoluc¸ ˜ao de k-LARGURAEM

ARVORE com k constante. Tal resultado pode ser

encontrado em (Bodlaender 1996), e resumido pelo seguinte teorema:

Teorema 4.4 (Bodlaender [1996]). Para todo k ∈ N, existe um algoritmo em tempo

linear que testa se um dado grafo G = (V, E) tem largura em

arvore no m

aximo k, e,

em caso positivo, retorna uma decomposic¸

ao em

arvore de G com largura em

arvore no

aximo k.

A id´eia principal do algoritmo ´e a partic¸

ao dos v´ertices em dois conjuntos: v´ertices

de baixo grau e v´ertices de alto grau. Pode ser mostrado que, para grafos com largura em

´arvore limitada por uma constante k, existem apenas “poucos” v´ertices de alto grau. Dois

casos s˜ao ent˜ao poss´ıveis:

1. Um n´umero “suﬁciente” de v´ertices de baixo grau ´e adjacente a um ou mais

v´ertices de baixo grau. Neste caso, pode ser mostrado que qualquer emparelha-

mento maximal em G cont´em Ω(n) arestas. Computa-se ent˜ao o grafo G



obtido

pela contrac¸˜ao de todas as arestas no emparelhamento maximal. Recursivamente,

pode-se computar uma decomposic¸ ˜ao em ´arvore de largura no m´aximo k de G



, ou

concluir que a largura em ´arvore de G



´e maior que k — e logo tamb´em a de G.

Desta decomposic¸˜ao em ´arvore, pode-se facilmente construir uma decomposic¸˜ao

em ´arvore de G com largura no m´aximo 2k + 1. Esta ´ultima decomposic¸˜ao ´e usada

para resolver o problema, usando o algoritmo de Bodlaender e Kloks (1996).

2. Um n´umero “pequeno” de v´ertice de baixo grau ´e adjacente a um ou mais v´ertices

de baixo grau. Pode ser mostrado que uma certa quantidade de arestas pode ser

adicionada a G sem tornar a sua largura em ´arvore maior que k, caso esta n˜ao

seja maior que k. Pode ser mostrado que G



, o grafo melhorado de G — G acres-

cido do novo conjunto de arestas — tem um n´umero suﬁciente de v´ertices que s˜ao

I-simpliciais: seus vizinhos formam uma clique no grafo melhorado, e algumas

outras condic¸ ˜oes s˜ao satisfeitas. Recursivamente, uma decomposic¸˜ao em ´arvore de

largura no m´aximo k ´e calculada de G



, obtida pela remoc¸ ˜ao de todos os v´ertices

I-simpliciais do grafo melhorado de G, ou pode-se concluir que a largura em ´arvore

4. Algoritmos de Decomposic¸

ao em

Arvore

de G



, e logo tamb´em de G, ´e maior que k. A partir de tal decomposic¸˜ao em ´arvore

de G



, pode-se facilmente construir uma decomposic¸˜ao em ´arvore de G com largura

no m´aximo k.

Alguns resultados auxiliares s˜ao necess´arios para compreens˜ao do algoritmo.

Deﬁnic¸

ao 24 (Decomposic¸˜ao em ´arvore suave). Uma decomposic¸˜ao em ´arvore D =

(X = {X

: i ∈ I}, T = (I, F )) de largura k ´e dita suave, se para todo i ∈ I :

| = k + 1, e para toda (i, j) ∈ F : |X

∩ X

| = k.

Bodlaender (1996) mostra que qualquer decomposic¸˜ao em ´arvore pode ser trans-

formada numa decomposic¸˜ao suave de mesma largura, aplicando o seguinte conjunto de

operac¸ ˜oes at´e que nenhuma seja mais poss´ıvel:

• Se para (i, j) ∈ F , X

⊆ X

, ent˜ao contraia a aresta (i, j) em T e tome como novo

n´o X



= X

;

• Se para (i, j) ∈ F , X

⊆ X

e |X

| < k + 1, ent˜ao escolha um v´ertice v ∈ X

\ X

e adicione v a X

;

• Se para (i, j) ∈ F , |X

| = |X

| = k + 1, e |X

\ X

| > 1, ent˜ao subdivida a aresta

(i, j) em T , e seja i



o novo n´o. Escolha agora um v´ertice v ∈ X

\ X

e um v´ertice

w ∈ X

\ X

, e fac¸a X



= X

\ {v} ∪ {w}.

Pelas propriedades de uma decomposic¸˜ao em ´arvore suave, pode-se estabelecer

uma relac¸ ˜ao direta entre o n´umero de v´ertices de um grafo, o n´umero de partes de uma

decomposic¸˜ao suave e a largura desta.

Lema 4.5. Se D = (X , T )

e uma decomposic¸

ao em

arvore suave de G = (V, E) com

largura k, ent

ao |I| = |V | − k.

Prova. Por induc¸˜ao em |I|. 

Seja c

uma constante denotando o limite superior da frac¸ ˜ao de v´ertices que s˜ao de

“alto” grau. Ent˜ao uma outra constante c

pode ser deﬁnida por:

+ 12k + 16

−

· k

(k + 1)

> 0

As deﬁnic¸ ˜oes de v´ertices de baixo e alto grau podem agora ser estabelecidas:

Deﬁnic¸

ao 25 (V´ertices de baixo e alto grau). Seja d = max(k

+ 4k +4, 2k/c

). Um

v´ertice v ´e dito de baixo grau se o grau de v ´e no m

aximo d, e ´e dito de alto grau se o grau

de v ´e maior que d.

Deﬁnic¸

ao 26 (V´ertice amig´avel). Um v´ertice v ´e dito amig

avel se ´e de baixo grau e

adjacente a pelo menos um outro v´ertice de baixo grau.

Primeira parte

A id´eia da primeira parte do algoritmo ´e realizar um emparelhamento maximal nas arestas,

contrai-las e ent˜ao aplicar um novo algoritmo de decomposic¸˜ao com base no novo grafo

obtido.

4.4. DEA em tempo linear

Inicialmente, deve-se garantir a condic¸˜ao de que se um n´umero suﬁciente de v´ertices

´e de baixo grau, uma boa decomposic¸˜ao pode ser obtida a partir do emparelhamento. O

primeiro resultado usa os v´ertices amig´aveis do grafo.

Lema 4.6. Se existem n

ertices amig

aveis em G = (V, E), ent

ao qualquer

emparelhamento maximal de G cont

em pelo menos n

/(2d) arestas.

Prova. Considere um emparelhamento maximal M. Qualquer v´ertice amig´avel v deve

ser uma extremidade de uma aresta em M, ou adjacente a um outro v´ertice amig´avel que ´e

extremidade de uma aresta em M. Para cada aresta e em M, pode-se associar no m´aximo

2d v´ertices amig´aveis que s˜ao extremidades de e ou adjacentes a um v´ertice amig´avel

de e. Se um v´ertice amig´avel n˜ao est´a associado a alguma aresta em M, ent˜ao M n˜ao ´e

maximal. Conseq¨uentemente |M| ≥ n

/(2d). 

A partir da contrac¸ ˜ao das arestas em M, pode-se obter um novo grafo, e, a partir

deste, proceder recursivamente na construc¸˜ao de uma decomposic¸˜ao em ´arvore. A relac¸ ˜ao

entre as duas decomposic¸ ˜oes — a do grafo original e do obtido pela contrac¸˜ao das ares-

tas no emparelhamento maximal — ´e estabelecida por uma func¸ ˜ao de correspondˆencia.

Formalmente, sejam M um emparelhamento maximal em G = (V, E) e G



= (V



, E



) o

grafo obtido pela contrac¸˜ao das arestas de M em G. Deﬁne-se ent˜ao f

: V → V



como

(v) = v se v n˜ao ´e uma extremidade de uma aresta em M, e seja f

(v) = f

(w)

o v´ertice resultante da contrac¸ ˜ao de (v, w) ∈ M. A decomposic¸˜ao em ´arvore de G pode

ent˜ao ser obtida a partir de G



Lema 4.7. Sejam M, G, G



, f

como acima. Se (W, T )

e uma decomposic¸

ao em

arvore

de G



com largura k, ent

ao (X , T ), onde X

= {v ∈ V : f

(v) ∈ W

e uma

decomposic¸

ao em

arvore de G com largura no m

aximo 2k + 1.

Lema 4.8. Sejam G e G



como deﬁnidos acima. A largura em

arvore de G



e no m

aximo

a largura em

arvore de G.

Prova. Basta observar que G



´e um menor de G, e logo, pela Propriedade 4, LA(G



) ≤

LA(G). 

Os Lemas 4.7 e 4.8 sugerem ent˜ao uma boa estrat´egia: encontrar, inicialmente, uma

decomposic¸˜ao em ´arvore D a partir da contrac¸ ˜ao das arestas de um emparelhamento ma-

ximal e, em seguida, uma nova decomposic¸˜ao D



a partir da func¸˜ao f

. Como a largura

de D



´e limitada — no m´aximo 2 · LA(D) + 1 — basta encontrar um algoritmo para en-

contrar uma nova decomposic¸ ˜ao D



a partir de D



, tendo esta largura no m´aximo LA(D).

Bodlaender e Kloks (1996) sugeriram tal algoritmo, encontrando o seguinte resultado:

Teorema 4.9. Para todo k, l, existe um algoritmo em tempo linear que, dados um grafo

G = (V, E) e uma decomposic¸

ao em

arvore (X , T ) de G com largura no m

aximo l,

determina se a largura em

arvore de G

e no m

aximo k, e, caso positivo, encontra uma

decomposic¸

ao em

arvore de G com largura no m

aximo k.

4. Algoritmos de Decomposic¸

ao em

Arvore

Segunda parte

Na segunda parte do algoritmo, um n´umero pequeno de v´ertices ´e de baixo grau; neste

caso, novos conceitos s˜ao necess´arios. Assim como na primeira parte um novo grafo ´e

obtido a partir do grafo original, tamb´em na segunda parte busca-se uma operac¸ ˜ao que

simpliﬁque a busca de uma decomposic¸˜ao em ´arvore limitada.

A id´eia da primeira parte ´e aproveitar o fato de que a maioria dos v´ertices s˜ao de

baixo grau e contrair arestas para obtenc¸ ˜ao de um novo grafo com largura em ´arvore

limitada, controlada. A segunda parte, no entanto, implementa uma abordagem de certa

forma contr´aria: se uma pequena parte dos v´ertices for de baixo grau, pode-se usar esta

caracter´ıstica para acrescentar arestas e manter a largura em ´arvore do grafo, enquanto a

busca de decomposic¸ ˜oes ´e facilitada. Considere ent˜ao o seguinte conceito:

Deﬁnic¸

ao 27 (Grafo melhorado). Dado um grafo G = (V, E), o grafo G



= (V, E



) ´e

dito melhorado de G, sendo obtido pela adic¸˜ao de arestas (v, w) a E para todos os pares

v, w ∈ V tais que v e w tem pelo menos k + 1 vizinhos em comum de baixo grau em G.

A relac¸ ˜ao entre G e seu grafo melhorado G



´e mostrada no seguinte lema:

Lema 4.10. Se a largura em

arvore de G

e no m

aximo k, ent

ao a largura em

arvore do

grafo melhorado de G

e tamb

em no m

aximo k. Al

em disso, qualquer decomposic¸

ao em

arvore de G com largura no m

aximo k

e tamb

em uma decomposic¸

ao em

arvore do grafo

melhorado com largura no m

aximo k, e vice-versa.

Prova. A prova ´e trivial, e segue diretamente da Propriedade 8. 

A partir do grafo melhorado de G pode-se acrescentar uma nova deﬁnic¸ ˜ao:

Deﬁnic¸

ao 28 (V´ertice I-simplicial). Um v´ertice de um grafo G ´e dito I-simplicial se ´e

simplicial no grafo melhorado de G, de baixo grau e n˜ao amig´avel em G.

Os lemas que se seguem mostram que, se G tem poucos v´ertices de alto grau e

poucos v´ertices amig´aveis, ent˜ao G tem muitos v´ertices I-simpliciais. Antes, no entanto,

um outro conceito se faz necess´ario:

Deﬁnic¸

ao 29 (V´ertice ´util). Um v´ertice v de um grafo G ´e dito

util com respeito a al-

guma decomposic¸˜ao em ´arvore (X , T ) se ´e de baixo grau, n˜ao amig´avel, e existe um n´o

i ∈ I tal que todos os viznhos de v pertencem a X

O pr´oximo resultado comp˜oe a base do algoritmo da segunda parte. Os le-

mas restantes procuram apenas estabelecer uma abordagem algor´ıtmica a partir da sua

interpretac¸ ˜ao.

Lema 4.11. Seja (X , T ) uma decomposic¸

ao em

arvore suave de G = (V, E) com

largura em

arvore k.

1. Para toda folha i de T , pode-se associar um v

ertice de baixo grau v ∈ X

tal que

este seja amig

avel ou

util com respeito a (X , T), e n

ao exista um j ∈ I, j = i, tal

que v ∈ X

2. Para cada caminho i

, i

, . . . , i

+3k+3

 em T com i

, . . . , i

+3k+2

os de grau 2

em T , pode-se associar pelo menos um v

ertice v ∈ X

∪ · · · ∪ X

+3k+2

que seja

4.4. DEA em tempo linear

amig

avel ou

util com respeito a (X , T ), e tal que v n

ao pertenc¸a a um conjunto X

com j ∈ I um n

o n

ao pertencente ao caminho.

Prova.

1. Seja j o vizinho da folha i em T . Seja v o ´unico v´ertice em X

\ X

, e logo v ´e

adjacente somente a v´ertices em X

. Dois casos podem ocorrer: ou todos os vizinhos

de v s˜ao de alto grau, onde neste caso v ´e ´util com respeito a (X , T ); ou um vizinho

de v ´e de baixo grau, e neste caso v ´e amig´avel.

2. Note que |X

∪ · · · ∪ X

+3k+3

| = k

+ 4k + 4 ≤ d. Conseq¨uentemente, todos

os v´ertices em X

∪ · · · ∪ X

+3k+2

\ (X

∪ X

+3k+3

) s˜ao de baixo grau. Supo-

nha que nenhum deles ´e amig´avel, isto ´e, eles s˜ao adjacentes somente a v´ertices

de alto grau em X

∪ X

+3k+3

. Suponha que X

cont´em r v´ertices de alto

grau, w

, . . . , w

. Claramente r ≤ |X

| = k + 1. Cada um destes w

pertencem

a conjuntos sucessivos X

, X

, . . . , X

. Suponha, sem perda de generalidade,

≤ i

≤ · · · ≤ i

. Se algum v´ertice v de baixo grau pertence a exata-

mente um conjunto X

, 1 ≤ j ≤ k

+ 3k + 2, ent˜ao este deve ser ´util com

respeito a (X , T ). Se algum v´ertice v de baixo grau pertence apenas aos conjun-

tos X

, . . . , X

j+1

(ou aos subconjuntos destes), ent˜ao todos os vizinhos de v

pertencem a X

j+1

, e logo v ´e ´util com respeito a (X , T ). Todos os v´ertices em

∪ · · · ∪ X

+3k+2

que n˜ao sejam de nenhum destes dois tipos devem pertencer a

pelo menos um dos conjuntos X

, X

, . . . , X

, X

+3k+3

. Estes s˜ao no total no

m´aximo (k + 1)(k + 3) = k

+ 4k + 3 v´ertices. Logo, pelo menos um v´ertice em

∪ · · · ∪ X

+3k+2

\ (X

∪ X

+3k+3

) deve ser ´util com respeito a (X , T ).



Deﬁnic¸

ao 30 (Colec¸ ˜ao folha-caminho). Uma colec¸

ao folha-caminho de uma ´arvore T

´e uma colec¸˜ao de folhas em T , mais uma colec¸ ˜ao de caminhos de comprimento k

+3k+3

em T , onde todos os n´os em um caminho que n˜ao sejam extremidades do caminho tˆem

grau 2 em T e n˜ao pertencem a nenhum outro caminho na colec¸ ˜ao. O tamanho da colec¸ ˜ao

´e o n´umero total de folhas mais o n´umero total de caminhos na colec¸ ˜ao.

Lema 4.12. Cada

arvore com r n

os cont

em uma colec¸

ao folha-caminho de tamanho no

ınimo r/(2k

+ 6k + 8).

Prova. Sejam r

o n´umero de n´os com grau no m´ınimo 3, r

o n´umero de folhas, e

o n´umero de n´os com grau 2. Claramente, r

< r

. Todos os n´os de grau 2 pertencem

a menos de r

+ r

componentes conectadas da ﬂoresta obtida pela remoc¸˜ao de todas

as folhas e todos os n´os com grau 3 ou maior da ´arvore. Cada componente cont´em no

m´aximo k

+ 3k + 3 n´os que n˜ao s˜ao parte de uma colec¸ ˜ao folha-caminho de tamanho

m´aximo. Logo, existem menos que (r

+ r

)(k

+ 3k + 3) n´os de grau 2 que n˜ao estejam

em algum caminho da colec¸ ˜ao. Conseq¨uentemente, existem no m´aximo

− (r

+ r

)(k

+ 3k + 3)

+ 3k + 4

4. Algoritmos de Decomposic¸

ao em

Arvore

caminhos numa colec¸ ˜ao folha-caminho de tamanho m´aximo. Segue que o tamanho

m´aximo de uma colec¸˜ao folha-caminho ´e no m´ınimo

max



− (r

+ r

)(k

+ 3k + 3)

+ 3k + 4

+ r



≥

+ 3k + 4



Corol

ario 4.13. Se (X , T )

e uma decomposic¸

ao em

arvore suave de G = (V, E) com

largura k, ent

ao G cont

em pelo menos |V |/(2k

+ 6k + 8) −1 v

ertices que s

ao amig

aveis

uteis com respeito a (X , T ).

Prova. T cont´em |V | − k n´os. Agora basta aplicar os dois ´ultimos lemas, 4.11 e 4.12.



Deﬁnic¸

ao 31 (Conjunto semi-importante e importante). Um conjunto Y ⊆ V de

v´ertices de alto grau ´e dito semi-importante com respeito a uma decomposic¸˜ao em ´arvore

(X , T ) de G = (V, E), se existe um i ∈ I com Y ⊆ X

. Um conjunto Y ´e dito impor-

tante se ele ´e semi-importante maximal com respeito a (X , T ), ou seja, n˜ao est´a contido

em nenhum conjunto semi-importante maior com respeito a (X , T ).

Lema 4.14. Seja (X , T ) uma decomposic¸

ao em

arvore de G = (V, E) com largura k. O

umero de conjuntos importantes diferentes com respeito a (X , T )

e no m

aximo o n

umero

de v

ertices de alto grau em G.

Prova. Seja L o conjunto de v´ertices de alto grau em G. ({X

∩ L : i ∈ I}, T ) ´e uma

decomposic¸˜ao em ´arvore de G[L]. Cada conjunto importante Y ´e um conjunto X

∩ L

que n˜ao est´a contido em outro conjunto X



∩ L. A partir da contrac¸ ˜ao repetitiva das

arestas (i, i



) em T com X

∩ L ⊇ X



∩ L, de modo que o novo n´o formado contenha

todos os v´ertices em X

, obt´em-se uma nova decomposic¸˜ao. Tal decomposic¸ ˜ao em ´arvore

resultante de G[L] cont´em os mesmos conjuntos maximais X

e ter´a no m´aximo |L| n´os.



Deﬁnic¸

ao 32 (Func¸ ˜ao UI). Uma func¸ ˜ao f que mapeia cada v´ertice ´util v (com respeito

a alguma decomposic¸˜ao em ´arvore (X , T )) a um conjunto importante Y (tamb´em com

respeito a (X , T )) com N

(v) ⊆ Y , ´e chamada func¸

ao UI para (X , T ). Por deﬁnic¸ ˜ao,

uma func¸˜ao UI sempre existe.

Lema 4.15. Seja f uma func¸

ao UI para uma decomposic¸

ao em

arvore suave (X , T )

de G = (V, E) com largura k. Seja Y um conjunto importante com respeito a (X , T ).

Ent

ao no m

aximo

(k + 1) v

ertices

uteis com respeito a (X , T ) em f

−1

(Y ) n

ao s

I-simpliciais.

Prova. Atribua, inicialmente, cada v´ertice ´util v que n˜ao seja I-simplicial a um par de

vizinhos de v que n˜ao sejam adjacentes no grafo melhorado de G. Pode-se ver que n˜ao se

pode atribuir mais de k v´ertices para cada par de v´ertices em G, porque, caso contr´ario,

estes teriam pelo menos k +1 vizinhos de baixo grau em comum, o que acrescentaria uma

4.4. DEA em tempo linear

aresta entre eles no grafo melhorado. Segue ent˜ao que o n´umero de v´ertices ´uteis e n˜ao

I-simpliciais v com f(v) = Y ´e no m´aximo

|Y |(|Y | + 1) ≤

(k + 1). 

Corol

ario 4.16. Se G = (V, E) tem largura em

arvore no m

aximo k, e cont

em n

ertices amig

aveis e n

ertices de alto grau, ent

ao existem pelo menos

|V |

+ 6k + 8

− 1 − n

−

(k + 1)n

ertices I-simpliciais em G.

Lema 4.17. Seja (X , T ) uma decomposic¸

ao em

arvore de largura no m

aximo k do grafo



obtido pela remoc¸

ao de todos os v

ertices I-simpliciais do grafo melhorado de G =

(V, E). Para todo v

ertice I-simplicial v, existe um i ∈ I com N

(v) ⊆ X

Prova. Basta ver que, por deﬁnic¸ ˜ao, v´ertices I-simpliciais n˜ao s˜ao adjacentes em G,

e que sua vizinhanc¸a forma uma clique no grafo melhorado de G. Logo, basta aplicar a

Propriedade 7 para concluir a prova. 

Algoritmo principal

O algoritmo apresentado por Bodlaender (1996) ´e recursivo, tendo como entrada um grafo

G e uma constante k e como sa´ıda uma decomposic¸˜ao em ´arvore de G com largura no

m´aximo k, se poss´ıvel.

A base da recurs˜ao, ou seja o resultado para grafos com no m´aximo um n´umero

constante de v´ertices, pode ser implementada a partir de qualquer outro algoritmo forc¸a

bruta, por exemplo. Caso G seja suﬁcientemente grande, o algoritmo principal pode ser

aplicado:

1. Veriﬁque se |E| ≤ k|V |−

k(k+1). Caso contr´ario, pelo Lema 3.17, G tem largura

em ´arvore maior que k: pare.

2. Conte o n´umero de v´ertices amig´aveis n

em G. Se existem pelo menos |V |/(4k

12k + 16) v´ertices amig´aveis, ent˜ao o algoritmo segue o primeiro caso:

(a) Encontre um emparelhamento maximal M em G.

(b) Obtenha o grafo G



pela contrac¸ ˜ao das arestas em M de G.



(d) Se G



tem largura em ´arvore maior que k, ent˜ao pare, j´a que, pelo Lema 4.8, a

largura em ´arvore de G deve tamb´em ser maior que k.

(e) Suponha que a chamada recursiva tenha retornado uma decomposic¸ ˜ao em

´arvore D



= (W, T ) de G



com largura em ´arvore k. Construa, com aux´ılio

do Lema 4.7, uma nova decomposic¸˜ao D

∗

= (X , T ) de G com largura no

m´aximo 2k + 1.

(f) Use o algoritmo proposto no Teorema 4.9 para encontrar uma nova decomposic¸˜ao

D a partir de D

∗

, k e l = LA(D

∗

) ≤ 2k + 1.

4. Algoritmos de Decomposic¸

ao em

Arvore

3. Neste passo, existem menos de |V |/(4k

+ 12k + 16) v´ertices amig´aveis, e logo

deve-se seguir o segundo caso:

(a) Encontre o grafo melhorado de G, G

∗

(b) Se existe um v´ertice I-simplicial de grau no m´ınimo k + 1 ent˜ao pare: G

∗

cont´em uma clique de tamanho k + 2, e logo, pelo Lema 4.10, a largura em

´arvore de G ´e tamb´em maior que k.



obtido pela remoc¸ ˜ao de todos os v´ertices I-simpliciais (em S) de G.

(d) Se |S| < c

|V |, ent˜ao pare, j´a que a largura em ´arvore de G ´e maior que k.

Pode-se chegar a esta conclus˜ao a partir da deﬁnic¸ ˜ao de c

e do Corol´ario 4.16,

onde, j´a que existem menos de |V |/(4k

+12k+16) v´ertices amig´aveis, deve-

se ter pelo menos |V |/(4k

+12k+16)−

(k+1)c

|V | v´ertices I-simpliciais

em G

∗

— supondo que a largura em ´arvore de G seja no m´aximo k.

(e) Como |S| ≥ c

|V |, aplique o algoritmo recursivamente a G



(f) Se a largura em ´arvore de G



´e maior que k, ent˜ao pare, j´a que, como G



´e um

subgrafo de G, LA(G) ≥ LA(G



) (Propriedade 2).

(g) Suponha que a chamada recursiva tenha retornado uma decomposic¸˜ao em

´arvore D



= (W, T



) de G



com largura em ´arvore k. Encontre uma nova

decomposic¸˜ao em ´arvore D = (X , T



) de G da seguinte forma:

i. Inicialmente, fac¸a D uma c´opia de D



, ou seja, acrescente a X todas as

partes em W, com T = T



ii. Para cada v´ertice v em S, encontre i

∈ I tal que N

(v) ⊆ X

. Pelo

Lema 4.17, i

sempre existe.

iii. Para cada i

, adicione um novo n´o j

a T adjacente a i

, e uma parte

= {v} ∪ N

(v) a X .

4. Retorne D, uma decomposic¸˜ao em ´arvore de largura no m´aximo k.

Teorema 4.18. O algoritmo proposto por Bodlaender (1996) tem complexidade de

tempo linear.

Prova. O tempo de execuc¸ ˜ao do algoritmo pode ser estimado da seguinte forma: como

um dos casos deve ser executado a partir da decis˜ao no passo 2, o algoritmo executa

recursivamente em um grafo G = (V, E) com (1 −1/(2d(4k

+ 12k + 16))) · |V | v´ertices

— primeiro caso, descrito ao longo do passo 2 — ou em um grafo com (1 − c

) · |V |

v´ertices. Logo, seja 0 ≤ c

< 1 uma constante:

= max



1 − c

, 1 −

2d · (4k

+ 12k + 16)



Como todos os passos n˜ao recursivos executam em tempo linear, tem-se que, se o

algoritmo toma tempo T (n) em um grafo com n v´ertices no pior caso, ent˜ao T (n) ≤

T (c

· n) + O(n), e logo, usando t´ecnicas convencionais de an´alise de complexidade,

conclui-se que T (n) = O(n). 

4.5. DEA usando reduc¸

4.5 DEA usando reduc¸

Enquanto que as abordagens apresentadas at´e agora baseiam-se em t´ecnicas “tradicionais”

de algoritmos em grafos — pesquisa de caminhos, separadores, busca em vizinhanc¸a e

adic¸ ˜ao de arestas, por exemplo — a t´ecnica de reduc¸

ao baseia-se fortemente em ´algebra

de grafos, como deﬁnida em (Arnborg et al. 1993), e em L´ogica Mon´adica de Segunda

Ordem, como em (Courcelle 1990). Uma revis˜ao dos conceitos b´asicos na Sec¸ ˜ao 2.8 ´e

recomendada para maior familiaridade com os novos conceitos a seguir introduzidos. A

primeira deﬁnic¸˜ao merece um destaque por se tratar da base da t´ecnica:

Deﬁnic¸

ao 33 (Regra de reduc¸ ˜ao). Uma regra de reduc¸

ao r ´e um par ordenado (H

, H

onde H

e H

s˜ao grafos l-terminais, l ≥ 0.

Um encaixe para uma regra de reduc¸ ˜ao r = (H

, H

) em um grafo G ´e um grafo l-

terminal G

isomorfo a H

e tal que existe um outro grafo l-terminal G

com G = G

⊕G

para algum l ≥ 0. Se G cont´em um encaixe G

para r, ent˜ao uma aplicac¸

ao de r em G

usando G

´e uma operac¸ ˜ao que mapeia G a um grafo G



tal que se G = G

⊕ G

, com G

isomorfo a H

, ent˜ao G



= G

⊕ G

, com G

isomorfo a H

. Diz-se tamb´em que G

foi

trocado por G

em G, obtendo-se G



A aplicac¸ ˜ao de uma regra de reduc¸ ˜ao pode ser simplesmente chamada de reduc¸

ao.

A aplicac¸˜ao de r em G usando G

´e tamb´em chamada de reduc¸ ˜ao correspondente ao

encaixe G

, sendo denotada por G

→



. De um modo geral, as reduc¸ ˜oes em um grafo s˜ao

executadas para algum encaixe, sem uma especiﬁcac¸ ˜ao deste, e logo denota-se a reduc¸ ˜ao

de G por r obtendo-se G



simplesmente por G

→ G



. Obviamente, grafos diferentes

podem ser obtidos a partir de G por reduc¸ ˜ao por r, dependendo dos encaixes escolhidos.

Se R ´e um conjunto {r

, . . . , r

} de regras de reduc¸ ˜ao, ent˜ao denota-se por G

→ G



reduc¸ ˜ao de G por alguma regra r ∈ R obtendo-se G



, ou seja, G

→ G



para algum r ∈ R.

Dado um conjunto de regras de reduc¸ ˜ao R, diz-se que G ´e redut

ıvel para R se e somente

se existe um encaixe G

para alguma regra r ∈ R em G; caso contr´ario, diz-se que G ´e

irredut

ıvel para R.

A Figura 4.6 (a) ilustra a aplicac¸ ˜ao das regras de reduc¸ ˜ao do conjunto R = {r, r



Normalmente representa-se graﬁcamente cada regra de reduc¸˜ao por seus grafos terminais

unidos por uma seta. Neste caso, se r = (H

, H

), diz-se que H

´e o lado esquerdo de r,

enquanto que H

´e o lado direito de r. Na Figura 4.6(b), G



´e obtido da reduc¸ ˜ao de G por

r, G

→ G



, enquanto G



´e uma reduc¸˜ao de G



por r



, e logo G

→ G



→ G



. Como ambas

as regras r e r



de R n˜ao podem mais ser aplicadas a G



, este ´e claramente irredut´ıvel

para R.

De modo a se obter uma caracterizac¸ ˜ao de uma propriedade de grafos por reduc¸ ˜ao,

deve-se levar em considerac¸˜ao as seguintes deﬁnic¸ ˜oes para conjuntos de regras de

reduc¸ ˜ao:

Deﬁnic¸

ao 34. Seja P uma propriedade de grafos e R um conjunto de regras de reduc¸˜ao.

• R ´e seguro para P se, sempre que G

→ G



, ent˜ao P (G) ⇔ P (G



4. Algoritmos de Decomposic¸

ao em

Arvore

(b)(a)







R = {r, r



}

Figura 4.6. Exemplo de aplicac¸˜ao de regras de reduc¸˜ao.

• R ´e completo para P se o conjunto I de grafos irredut´ıveis para R para os quais P

vale ´e ﬁnito.

• R ´e convergente se n˜ao existe uma seq¨uˆencia inﬁnita G

→ G

→ · · · .

• R ´e decrescente se, sempre que G

→ G



, ent˜ao G



cont´em menos v´ertices que G.

Deﬁnic¸

ao 35 (Sistema de reduc¸ ˜ao). Um sistema de reduc¸

ao para uma propriedade de

grafos P ´e um par (R, I), onde R ´e um conjunto ﬁnito de regras de reduc¸˜ao seguro,

completo e convergente para P , e I ´e o conjunto de grafos irredut´ıveis para R tal que

P (G) vale para todo G ∈ I, ou seja, I = {G : P (G) ∧ ¬∃G



: G

→ G



}. Diz-se ainda

que um sistema de reduc¸ ˜ao (R, I) para P ´e decrescente se R ´e decrescente.

O conceito de sistema de reduc¸ ˜ao decrescente sugere prontamente um algoritmo

para caracterizac¸ ˜ao de uma propriedade de grafos. Considere (R, I) um tal sistema, P

uma propriedade e G um grafo a ser avaliado com relac¸ ˜ao a P : aplique as regras em R

em G at´e que seja obtido um grafo G



irredut´ıvel; veriﬁque se G



pertence a I e ent˜ao

decida pela satisfac¸˜ao de P por G, ou seja, em caso aﬁrmativo, G



∈ I e logo G satisfaz

P , caso contr´ario, P n˜ao vale para G.

O primeiro problema desta abordagem est´a na deﬁnic¸ ˜ao do sistema de reduc¸ ˜ao,

que, de modo geral, n˜ao ´e de f´acil obtenc¸ ˜ao. Como exemplo, para uma caracterizac¸ ˜ao

dos grafos que s˜ao k-´arvore parciais, com 0 ≤ k ≤ 3 — e logo de largura em ´arvore

no m´aximo k — Arnborg et al. (1993) sugerem conjuntos (R

, I) seguros, completos,

convergentes e decrescentes contendo as regras de reduc¸ ˜ao mostradas na Figura 4.7. Nos

quatro sistemas, os conjuntos de grafos irredut´ıveis s˜ao iguais e cont´em somente o grafo

vazio, G

vazio

. Os conjuntos de regras de reduc¸˜ao s˜ao os seguintes: R

= {r

}, R

, r

}, R

= {r

, r

} e R

= {r

, r

4.5. DEA usando reduc¸

vazio

(Isolado)

(Folha)

(Triˆangulo)

(S´erie)

(Paralelo)

(Companheiro)

(Cubo)

Figura 4.7. Regras de reduc¸˜ao para conjuntos seguros, completos, convergentes e decrescentes para

propriedade de ser uma k-´arvore parcial, 0 ≤ k ≤ 3.

Como resultado mais importante, Arnborg et al. (1993) mostraram que, para cada

propriedade de grafos de ´ındice ﬁnito e para cada k inteiro, existe um sistema de reduc¸ ˜ao

seguro, completo e convergente para os grafos com largura em ´arvore no m´aximo k. Em

(de Fluiter e Bodlaender 1995) ´e encontrada uma lista de problemas relacionados `a pro-

priedades de ´ındice ﬁnito em grafos com largura em ´arvore limitada. Em (Arnborg et al.

1991) ´e mostrado que o problema de determinar se a largura em ´arvore de um grafo ´e no

m´aximo k, para k constante, refere-se a uma propriedade MS-deﬁn´ıvel, e logo de ´ındice

ﬁnito.

Supondo ent˜ao que um sistema de reduc¸ ˜ao seja conhecido para uma dada proprie-

dade, o problema agora est´a em encontrar um encaixe para as regras do sistema de reduc¸ ˜ao

no grafo G de entrada. Uma rotina forc¸a bruta pode fazer uma veriﬁcac¸˜ao para conjunto

de c v´ertices em G, onde c ´e o tamanho do maior grafo terminal nos lados esquerdos das

regras, tendo portanto complexidade em tempo O(n

), n = |V (G)|.

Usando o fato de que propriedades de grafos de ´ındice ﬁnito incluem todas as pro-

priedades que podem ser expressas em LMSO, Arnborg et al. (1993) apresentam um

algoritmo em tempo linear, mas de espac¸o polinomial O(n

) — p sendo o maior n´umero

de terminais dentre todos os lados esquerdos das regras — para decidir se uma dada pro-

priedade P vale para um grafo G com largura em ´arvore limitada. O algoritmo de Arnborg

et al. n˜ao depende da estrutura das regras de reduc¸ ˜ao do sistema, podendo ser aplicado

em qualquer conjunto de regras que seja ﬁnito, seguro, completo e decrescente (e logo,

convergente).

Uma maneira de tornar um algoritmo mais eﬁciente ´e encontrar um conjunto de

regras que tenha uma estrutura especial, de modo que o algoritmo possa tomar vantagem

de tal estrutura sob a forma de ganho de desempenho e espac¸o em mem´oria ao determinar

se alguma regra de reduc¸ ˜ao do sistema deve ser aplicada, e qual. Em (Bodlaender e Ha-

gerup 1995) ´e apresentado um algoritmo paralelo baseado nesta id´eia, usando um m´etodo

chamado busca limitada em listas de adjac

encia. de Fluiter e Bodlaender (1995) adap-

tam uma vers˜ao seq¨uencial deste algoritmo, estendendo os resultados em Arnborg et al.

(1993) de duas formas: encontrando um algoritmo construtivo para resolver o problema

4. Algoritmos de Decomposic¸

ao em

Arvore

de decis˜ao associado `a propriedade, e um m´etodo para resoluc¸˜ao de certos problemas de

otimizac¸˜ao em grafos com largura em ´arvore limitada. Al´em disso, ´e mostrado que uma

combinac¸˜ao destes resultados ´e ainda poss´ıvel, resultando portanto numa vers˜ao constru-

tiva de um algoritmo para resoluc¸˜ao de certos problemas de otimizac¸˜ao para grafos com

largura em ´arvore limitada.

A discuss˜ao destes ´ultimos algoritmos envolve conceitos mais t´ecnicos, tanto de

LMSO quanto de ´algebra de grafos, e n˜ao ser´a realizada aqui, dadas as limitac¸ ˜oes de

escopo e n´ıvel pretendido do texto. No entanto, a vers˜ao inicial de decis˜ao de uma propri-

edade ser´a abordada, sendo apresentado o algoritmo de reduc¸˜ao encontrado em (de Fluiter

1997). Mais conceitos s˜ao necess´arios:

Deﬁnic¸

ao 36 (Grafo terminal d-descobr´ıvel). Sejam d um inteiro positivo, G um grafo

dado, representado por listas de adjacˆencia, e G

um grafo l-terminal. Diz-se ent˜ao que

´e d-descobr

ıvel em G se

1. G

´e aberto e conexo, e o m´aximo grau de qualquer v´ertice de G

´e no m´aximo d,

ou seja, ∆(G

) ≤ d;

2. existe um grafo l-terminal G

tal que G = G

⊕ G

;

3. G

cont´em um v´ertice interno v tal que, para todos os v´ertices w ∈ V (G

), existe

uma trilha W em G

com W = u

, . . . , u

, com u

= v e u

= w, e, para cada i,

1 < i < s, na lista de adjacˆencia de u

em G, as arestas (u

i−1

, u

) e (u

, u

i+1

) tˆem

distˆancia no m´aximo d.

Um candidato a encaixe d-descobr´ıvel possui estrutura especial que lhe garante uma

vantagem algor´ıtmica:

Lema 4.19 (de Fluiter [1997]). Se um grafo terminal G

e d-descobr

ıvel em um grafo G

para algum d ≥ 1, ent

ao, para qualquer v

ertice interno de G

, todos os v

ertices e arestas

de G

podem ser encontrados a partir de v em complexidade de tempo que depende

apenas de d e do tamanho de G

, mas n

ao do tamanho do grafo G.

Prova. Sejam G um grafo, d um inteiro positivo, G

um grafo terminal d-descobr´ıvel

em G, e v um v´ertice interno qualquer de G

. Para provar o lema, basta mostrar que, para

qualquer outro v´ertice w de G

, pode-se encontrar uma trilha W satisfazendo a condic¸ ˜ao

3 da Deﬁnic¸˜ao 36 para G

e G e tal que o tamanho de W dependa apenas de d e G

, e

logo qualquer v´ertice de G

pode ser encontrado em tempo tamb´em dependente apenas

de d e G

Se W ´e uma trilha como acima, ´e sempre poss´ıvel encontrar uma trilha W



de-

rivada de W , e logo tamb´em entre v e w em G

, tal que qualquer aresta e = (x, y)

aparece no m´aximo duas vezes em W



. Suponha ent˜ao que exista uma aresta e = (x, y)

que aparece no m´ınimo trˆes vezes em W ; logo, como e aparece pelo menos duas ve-

zes em W no mesmo sentido, W cont´em uma sub-trilha W



da forma x, y, . . . , x, y

(ou y, x, . . . , y, x) e W



pode ser obtida pela remoc¸˜ao da sub-trilha y, . . . , x (ou

x, . . . , y) em W



de W . N˜ao ´e dif´ıcil perceber que W



= u



, . . . , u



 ´e tal que u



= v,



= w e, para cada i, 1 < i < p, as arestas (u



i−1

, u



) e (u



, u



i+1

) tˆem distˆancia no

m´aximo d na lista de adjacˆencia de G, e logo, W



tamb´em satisfaz a condic¸˜ao 3.

4.5. DEA usando reduc¸

Desta forma, sempre pode-se obter uma trilha W entre um v´ertice interno v e w em

tal que qualquer aresta em W aparec¸a no m´aximo duas vezes. O resultado do lema —

W poder ser encontrada em tempo dependente apenas de d e G

— segue agora do fato

de que G

´e aberto, e logo todo terminal ´e adjacente a um v´ertice interno. 

Considere agora a seguinte deﬁnic¸ ˜ao:

Deﬁnic¸

ao 37 (Sistema de reduc¸ ˜ao especial). Sejam P uma propriedade de grafos e

(R, I) um sistema de reduc¸ ˜ao decrescente para P . Seja n

max

o n´umero m´aximo de v´ertices

em qualquer lado esquerdo das regras em R. (R, I) ´e um sistema de reduc¸

ao especial para

P se existem inteiros positivos n

min

e d, n

min

≤ n

max

≤ d, tais que as seguintes condic¸ ˜oes

valem:

1. Para toda regra de reduc¸ ˜ao (H

, H

) ∈ R:

(a) se H

tem pelo menos um terminal, ent˜ao H

´e conexo e H

e H

s˜ao abertos;

(b) se H

´e um grafo zero-terminal, ent˜ao |V (H

)| < n

min

2. Para todos os grafos G tais que P (G) vale, e todas as representac¸ ˜oes de G em lista

de adjacˆencias:

(a) cada componente de G com pelo menos n

min

v´ertices tem um encaixe

d-descobr´ıvel;

(b) se todas as componentes de G tˆem menos que n

min

, ent˜ao ou G ∈ I ou G

cont´em um encaixe que ´e um grafo zero-terminal.

As condic¸ ˜oes 1(a) e 2(a) garantem que cada componente H de um grafo G, com

|V (H)| ≥ n

min

e P (G) valendo, cont´em pelo menos um encaixe d-descobr´ıvel para

uma regra de reduc¸˜ao, e este pode ser aplicado sem remoc¸˜ao de aresta m´ultiplas, j´a que

ambos os lados da regra s˜ao abertos. As condic¸ ˜oes 1(b) e 2(b), por sua vez, s˜ao somente

necess´arias para propriedades de grafos que n˜ao consideram o grafo de entrada como

conexo, e garantem que, se nenhuma outra regra de reduc¸ ˜ao ´e aplic´avel, ent˜ao encaixes

para regras com lado esquerdo contendo um grafo zero-terminal e desconexo podem ser

encontrados eﬁcientemente.

Com base na deﬁnic¸˜ao de sistema de reduc¸ ˜ao especial, pode-se projetar um algo-

ritmo em tempo e espac¸o lineares. O algoritmo consiste de duas fases, ilustradas nas

Figuras 4.8 e 4.9, respectivamente, cada uma tomando vantagem de cada condic¸˜ao do

sistema de reduc¸˜ao especial.

Na primeira fase, o algoritmo encontra encaixes d-descobr´ıveis (linha 6) e executa

as reduc¸ ˜oes correspondentes (linhas 8 a 8) at´e que o grafo de entrada G torne-se irredut´ıvel

com relac¸ ˜ao a encaixes d-descobr´ıveis, ou seja, com relac¸ ˜ao a regras de reduc¸ ˜ao com lados

esquerdos possuindo terminais. A irredutibilidade de G ´e veriﬁcada com base no conjunto

S de v´ertices de grau no m´aximo d, sendo este atualizado a partir das listas de adjacˆencia

de G, no lac¸o da linha 18. Vale notar que a func¸ ˜ao d-DESCOBR

IVEL , que tem como

objetivo encontrar um encaixe d-descobr´ıvel G

dentre as regras de R tal que v ´e interno

em G

, retorna r e tem complexidade de tempo estabelecida pelo Lema 4.19.

Na linha 23, G pode ser testado para pertinˆencia em I, e o algoritmo retorna ver-

dadeiro em caso positivo. Caso contr´ario, o algoritmo segue para a segunda fase, na

4. Algoritmos de Decomposic¸

ao em

Arvore

 Algoritmo RED UC¸

AO(G, R, I) — Fase 1

 Entrada: Um grafo G = (V, E) e um sistema de reduc¸ ˜ao especial (R, I)

para uma propriedade de grafos P e com parˆametros n

min

e d.

 Sa´ıda: Avaliac¸ ˜ao de P em G, P (G).

1. in´ıcio

2. n

max

← max

r∈R

{|V (H

)| : r = (H

, H

)}

3. S ← {v ∈ V : d(v) ≤ d}

4. enquanto S = ∅ fac¸a

5. selecione v : v ∈ S

6. r ← d-DE SC OB R

IV EL(v, G, R)

7. se r = ∅ ent

ao // Aplique r

8. selecione G

: G

⊆ G, v ∈ G

, G

≈ H

, r = (H

, H

)

9. selecione G

: G

≈ H

, r = (H

, H

)

10. // Remoc¸

ao de v

ertices internos e arestas de G

11. V ← V \ {u ∈ V (G

) : u ∈ Int(G

)}

12. E ← E \ E(G

)

13. S ← S \ {u ∈ V (G

) : u ∈ Int(G

)}

14. // Adic¸

ao de v

ertices internos e arestas de G

15. V ← V ∪ {u ∈ V (G

) : u ∈ Int(G

)}

16. E ← E ∪ E(G

)

17. S ← S ∪ {u ∈ V (G

) : d(u) ≤ d

18. para cada t ∈Term(G

) fac¸a

19. L ← LI STAADJ(t)

20. para cada (t, w) ∈ L : L mudou dentro da distˆancia d fac¸a

21. se d(w) ≤ d ent

ao S ← S ∪ {w}

22. S ← S \ {v}

23. se G ∈ I ent

ao retorna verdadeiro

Figura 4.8. Algoritmo para decis˜ao de uma propriedade de grafos P dado um sistema de reduc¸˜ao especial

para P , Fase 1.

Figura 4.9. O primeiro passo ´e veriﬁcar a condic¸˜ao 2(a) da Deﬁnic¸˜ao 37 para G, na li-

nha 25. Se a condic¸ ˜ao ´e satisfeita, ent˜ao novas regras de reduc¸ ˜ao s˜ao aplicadas a G. Ao

ﬁnal da segunda fase, G ´e realmente irredut´ıvel, j´a que todas as regras em R foram veri-

ﬁcadas nas duas fases, e, como R ´e completo para G, pode-se decidir pela satisfac¸˜ao de

P para G na linha 48.

Vale notar que o conjunto de regras de reduc¸ ˜ao aplic´aveis a G na segunda fase s˜ao

tais que todos os lados esquerdos destas s˜ao grafos zero-terminais (linha 26), j´a que as

outras regras j´a foram testadas na Fase 1. Para tanto, s˜ao constru´ıdas trˆes estruturas de

dados especiais, L

(linhas 29 a 31), i

(linha 33) e I

(linha 34).

A lista L

corresponde ao conjunto de grafos isomorfos `as componentes do lado

esquerdo de r, sem repetic¸ ˜oes. Posto de outra forma, L

corresponde ao sistema de

representantes distintos para as classes de equivalˆencia deﬁnidas por isomorﬁsmo nas

4.5. DEA usando reduc¸

 Algoritmo RED UC¸

AO(G, R, I) — Fase 2

 Entrada: Um grafo G = (V, E) e um sistema de reduc¸ ˜ao especial (R, I)

para uma propriedade de grafos P e com parˆametros n

min

e d.

 Sa´ıda: Avaliac¸˜ao de P em G, P (G).

24. S



← COM PO NENTES(G)

25. se ∃C ∈ S



: |V (C)| ≥ n

min

ent

ao retorna falso

26. R

← {r = (H

, H

) ∈ R : Term(H

) = ∅}

27. para cada r = (H

, H

) ∈ R

fac¸a

28. C ← COM PO NE NT ES(H

)

29. L

← ∅

30. para cada C ∈ C fac¸a

31. se  ∃C



∈ L

: C ≈ C



ent

ao L

← L

∪ {C}

32. para cada H ∈ L

fac¸a

33. i

(H) ← |{C ∈ C : C ≈ H}|

34. I

(H) ← ∅

35. enquanto S



= ∅ fac¸a

36. selecione C : C ∈ S



37. para cada r ∈ R

fac¸a

38. se ∃H ∈ L

: H ≈ C ent

ao I

(H) ← I

(H) ∪ {C}

39. se ∃r = (H

, H

) ∈ R

: ∀H



∈ L

: |I



)| ≥ i



) ent

ao // Aplique r

40. para cada H



∈ L

fac¸a

41. selecione L(H



) : L(H



) ⊆ I



), |L(H



)| = i



)

42. G ← G \

≈

L(H



)

43. para cada r



∈ R

fac¸a

44. I



) ← I



) \

≈

L(H



)

45. G ← G ∪ H

46. S



← S



∪ COM PO NENTES(H

)

47. S



← S



\ {C}

48. se G ∈ I ent

ao retorna verdadeiro sen

ao retorna falso

49. ﬁm

Figura 4.9. Algoritmo para decis˜ao de uma propriedade de grafos P dado um sistema de reduc¸˜ao especial

para P , Fase 2.

componentes do lado esquerdo de r. Ainda considerando isomorﬁsmo como uma relac¸ ˜ao

de equivalˆencia, pode-se deﬁnir uma extens˜ao ao operador de diferenc¸a entre conjuntos

para grafos, \

≈

: denota-se por G \

≈

H, G e H grafos desconexos, a retirada de G, para

cada componente C de H, de uma componente C



isomorfa `a C. O operador \

≈

´e utili-

zado nas linhas 42 e 44. Vale notar que ambos os operandos podem conter componentes

isomorfas, e que a operac¸˜ao pode ser aplicada tamb´em para conjuntos ou listas de grafos.

As listas i

e I

s˜ao relacionadas a cada elemento H em L

: i

(H) armazena o

n´umero de componentes isomorfas a H no lado esquerdo de r, enquanto que I

(H) tem

como objetivo guardar as componentes de G que s˜ao isomorfas a H, sendo inicialmente

vazia.

4. Algoritmos de Decomposic¸

ao em

Arvore

A complexidade de REDUC¸

AO, assim como a corretude, ´e deﬁnida pelo seguinte

teorema, cuja prova encontra-se em (de Fluiter 1997):

Teorema 4.20 (de Fluiter [1997]). Dados uma propriedade de grafos P e um sistema

de reduc¸

ao especial (R, I) para P , o algoritmo REDUC¸

AO reconhece corretamente gra-

fos para os quais P vale e usa complexidade de tempo e espac¸o O(|V (G)|), onde G

qualquer grafo dado como entrada.

4.6 Algoritmos para problemas em grafos com largura

arvore limitada

Pode-se demonstrar que uma decomposic¸˜ao em ´arvore de um grafo G = (V, E) pode ser

facilmente convertida — ou seja, em tempo linear — em uma decomposic¸˜ao em ´arvore

agrad

avel D = (X = {X

}

i∈I

, T = (I, F)) onde a ´arvore T ´e enraizada e bin´aria e os

n´os de T s˜ao de quatro tipos:

folha: n´os i do tipo folha s˜ao folhas em T e tais que |X

| = 1.

introduc¸

ao: n´os i de introduc¸˜ao tˆem um ﬁlho j e satisfazem X

= X

∪ {v}, para algum

v´ertice v ∈ V .

ıda: n´os i de sa´ıda tˆem um ﬁlho j e satisfazem X

= X

\ {v}, para algum v´ertice

v ∈ V .

junc¸

ao: n´os de junc¸˜ao i tˆem dois ﬁlhos j

e j

e tais que X

= X

Como Bodlaender (1997) observa, a considerac¸˜ao de decomposic¸ ˜oes em ´arvore

agradav´eis geralmente n˜ao implica em novas possibilidades algor´ıtmicas quando com-

parado com decomposic¸ ˜oes normais; no entanto, facilita enormemente o projeto de

algoritmos, por se tratar de uma ´arvore bin´aria. Al´em disso, pode-se esperar a obtenc¸˜ao

de melhores fatores constantes escondidos nas complexidades dos algoritmos.

Em (Bodlaender 1997) ´e apresentada uma t´ecnica para tratamento de problemas

em grafos com largura em ´arvore limitada, baseada em tabelas de caracterizac¸

oes de

soluc¸

oes parciais. Dada uma decomposic¸˜ao em ´arvore enraizada D = (X , T ) de um

grafo G, para cada n´o i de T calcula-se uma caracterizac¸

ao, numa ordem de baixo para

cima, ou seja, iniciando nas folhas e percorrendo os pais at´e atingir a raiz de T . Esta

estrat´egia foi inicialmente apresentada em (Arnborg e Proskurowski 1989), e consiste de

uma abordagem semelhante `a programac¸ ˜ao dinˆamica.

De um modo geral, um algoritmo baseado nesta t´ecnica possui a seguinte estrutura,

onde k ´e uma constante e limitante superior da largura em ´arvore do grafo de entrada

G = (V, E):

1. Encontre uma decomposic¸˜ao em ´arvore D de G de largura no m´aximo k.

2. Transforme D numa decomposic¸˜ao em ´arvore agrad´avel D



= (X = {X

}

i∈I

, T =

(I, F )) de largura no m´aximo k e onde r ´e a raiz de T .

4.6. Algoritmos para problemas em grafos com largura em

arvore limitada

3. Calcule para cada n´o i ∈ I uma certa tabela. Para a obtenc¸˜ao de cada tabela deve-se

usar somente as tabelas j´a calculadas para os ﬁlhos de i, o tipo de n´o de i — folha,

introduc¸˜ao, sa´ıda e junc¸ ˜ao — e a informac¸˜ao sobre G restrita a X

4. A soluc¸˜ao do problema encontra-se na tabela de r, a raiz de T .

Como Bodlaender (1997) observa, esta estrat´egia pode ainda ser usada para vers˜oes

construtivas do problema, onde uma soluc¸˜ao ´e constru´ıda na medida em que a ´arvore ´e

percorrida de baixo para cima, juntamente com as tabelas, ou uma outra fase ´e necess´aria

para construir a soluc¸˜ao a partir das tabelas j´a prontas.

Para construc¸ ˜ao das tabelas, suponha que se queira resolver um certo problema P,

onde se pode assumir que P ´e uma propriedade de grafos. O projeto do algoritmo segue

os seguintes passos:

1. Deﬁna a noc¸˜ao de soluc¸

ao. Para alguns problemas esta pode ser bem clara, como

no caso de MAX CONJUNTO INDEPENDENTE: um conjunto S de v´ertices n˜ao ad-

jacentes entre si em um grafo G tal que S tem cardinalidade m´axima dentre todos

os outros conjuntos independentes em G.

2. Deﬁna a noc¸ ˜ao de soluc¸

ao parcial. A id´eia de soluc¸˜ao parcial ´e intimamente relaci-

onada a de grafo terminal, ou seja, assim como uma soluc¸˜ao parcial deve contribuir

para a formac¸ ˜ao de uma soluc¸˜ao (geral), a operac¸ ˜ao de uni˜ao entre grafos terminais

deve construir o grafo de entrada G. Desta forma, uma soluc¸˜ao parcial corresponde

a uma soluc¸˜ao particular do problema quando restrita a um subgrafo terminal de G.

Como exemplo, uma soluc¸˜ao parcial para MAX CONJUNTO INDEPENDENTE seria

um conjunto independente m´aximo em H, um subgrafo terminal de G.

3. Deﬁna a noc¸˜ao de extens

ao de uma soluc¸

ao parcial. A extens˜ao deve descrever um

modo de como obter uma soluc¸˜ao a partir de soluc¸ ˜oes parciais. Para MAX CON-

JUNTO INDEPENDENTE, um conjunto S ´e uma soluc¸ ˜ao para G e uma extens˜ao

de um conjunto S



para um subgrafo terminal H de G se e somente se S



´e uma

restric¸˜ao de S em H.

4. Deﬁna a noc¸˜ao de caracter

ıstica de uma soluc¸

ao parcial. Como Bodlaender des-

creve, equivale ao que se deve saber sobre uma soluc¸˜ao parcial de modo a julgar a

sua capacidade de extender para uma soluc¸ ˜ao.

5. Um conjunto completo de caracter

ısticas para um grafo terminal H ´e o conjunto de

todas as caracter´ısticas das soluc¸ ˜oes parciais em H. O conjunto completo de carac-

ter´ısticas de um grafo G

para um n´o i de uma decomposic¸˜ao em ´arvore agrad´avel

´e tamb´em chamado conjunto completo para i.

Mostre agora, para cada um dos quatro tipos de n´os para i, o conjunto completo para

i pode ser calculado eﬁcientemente (em tempo polinomial ou constante), dados os

conjuntos completos para todos os ﬁlhos de i e assumindo que existem no m´aximo

k + 1 terminais em cada um dos grafos terminais envolvidos.

6. Mostre que o problema pode ser decidido eﬁcientemente dado um conjunto

completo para a raiz r da decomposic¸˜ao em ´arvore agrad´avel.

4. Algoritmos de Decomposic¸

ao em

Arvore

Bodlaender (1997) fornece ainda deﬁnic¸ ˜oes mais formais, denotando por sol

solp

, ex

as relac¸ ˜oes para os conceitos de soluc¸˜ao, soluc¸ ˜ao parcial, e extens˜ao, res-

pectivamente e por car

uma func¸ ˜ao correspondente ao conceito de caracter´ıstica. Desta

forma, sol

´e uma relac¸ ˜ao que tem como argumentos um grafo G e uma soluc¸˜ao s —

que pode ser representada como um vetor ou uma cadeia de caracteres, por exemplo —

de modo que, para todo grafo G, P(G) equivale a ∃s : sol

(G, s). De modo an´alogo,

solp

admite dois argumentos, um grafo terminal H e uma soluc¸˜ao parcial s



. A extens˜ao

vincula os dois conceitos anteriores, sendo uma relac¸ ˜ao com os quatro argumentos de

sol

e solp

: G um grafo, s uma soluc¸˜ao, H um grafo terminal e s



uma soluc¸˜ao parcial.

Uma extens˜ao deve satisfazer:

∀G, s, H, s



: ex

(G, s, H, s



) =⇒ ∃H



: G = H ⊕ H



∧ sol

(G, s) ∧ solp

(H, s



)

e tamb´em

∀G, s, H, s



: (sol

(G, s) ∧ (G = H ⊕ H



)) =⇒ ∃s



: solp

(H, s



) ∧ ex

(G, s, H, s



)

expressando que toda soluc¸˜ao admite uma soluc¸˜ao parcial em qualquer subgrafo terminal.

A func¸˜ao car

tem como argumentos H, um subgrafo terminal, e s uma soluc¸ ˜ao

parcial, deﬁnidos quando solp

(H, s) ´e verdadeiro. A caracter´ıstica car

deve satisfazer,

para todos os grafos terminais H, H



e H



, e todas as soluc¸ ˜oes parciais s e s



car

(H, s) = car



, s



) =⇒

(∃s



: ex

(H ⊕ H



, s



, H, s)) ⇔ (∃s



: ex



⊕ H



, s



, H



, s



))

O conjunto completo de caracter´ısticas de um grafo terminal H ´e deﬁnido como

comp

(H) = {car

(H, s) : solp

(H, s)}.

Como exemplo de aplicac¸ ˜ao mais not´oria, o algoritmo apresentado em (Bodlaender

e Kloks 1996) ´e baseado nesta estrutura, com especiﬁcac¸ ˜ao de soluc¸˜ao, soluc¸ ˜ao parcial,

extens˜ao, caracter´ıstica e conjunto completo de caracter´ısticas para, inicialmente, o pro-

blema de k-LARGURAEMCAMINHO, sendo os conceitos estendidos para o problema

de k-LARGURAEM

ARVORE. Os conjuntos completos de caracter´ısticas foram deﬁnidos

para n´os de uma decomposic¸˜ao em ´arvore agrad´avel de um grafo de entrada G. Em (Bo-

dlaender 1997) ´e apresentado um exemplo de aplicac¸˜ao para o problema de 3-partic¸ ˜ao do

conjunto de v´ertices de um grafo G.

Assim como na t´ecnica de reduc¸ ˜ao a diﬁculdade maior ´e a obtenc¸˜ao das regras

de reduc¸ ˜ao e de um sistema de reduc¸ ˜ao especial, aqui tamb´em a diﬁculdade est´a na

especiﬁcac¸ ˜ao de conceitos adequados para a aplicac¸˜ao da t´ecnica.

Cap´ıtulo 5

Conclus

oes e Recomendac¸

oes

A proposta deste texto ´e realizar uma pesquisa do estado da arte em decomposic¸ ˜oes em

´arvore, e em algoritmos para sua obtenc¸ ˜ao. Al´em disso, o texto prop˜oe-se a abordar tais

aspectos em tom introdut´orio, de modo a facilitar a sua familiarizac¸ ˜ao pelo leitor. De fato,

pretende-se que o texto sirva como fonte de referˆencia altamente recomendada, atuando

como ponto de partida para v´arios pesquisadores. A partir do que foi discutido princi-

palmente nos Cap´ıtulos 3 e 4, pode-se julgar que tais objetivos foram satisfatoriamente

alcanc¸ados.

Embora todo o texto tenha favorecido uma abordagem simples e eﬁciente — de

tal forma que o leitor possa assimilar mais rapidamente os conceitos e resultados — no

Cap´ıtulo 3, em particular, procurou-se contribuir com provas mais reﬁnadas, facilitadas,

sendo portanto de grande valia para iniciantes pelo seu car´ater did´atico. Optou-se por uma

abordagem gradativa, partindo de casos espec´ıﬁcos e culminando com resultados mais

profundos, no sentido em que permitem ao pesquisador perceber, em ˆambito mais geral,

as caracter´ısticas estruturais de grafos com largura em ´arvore limitada. Al´em de contribuir

com essa vis˜ao mais abrangente, as ´ultimas sec¸ ˜oes do Cap´ıtulo 3 retratam o estado da arte

em termos de resultados te´oricos para decomposic¸˜ao em ´arvore, n˜ao deixando de realc¸ar

os principais teoremas, suas relac¸ ˜oes e conseq¨uˆencias.

No Cap´ıtulo 4 foram considerados os aspectos mais pr´aticos, sendo apresentados

algoritmos eﬁcientes para obtenc¸˜ao de decomposic¸ ˜oes em ´arvore. Seguindo uma aborda-

gem semelhante a do Cap´ıtulo 3, os algoritmos s˜ao discutidos gradativamente, partindo

de casos particulares e prosseguindo para t´ecnicas mais reﬁnadas. Os algoritmos mais

importantes atualmente — retratando tamb´em o estado da arte em termos de t´ecnicas e re-

sultados — foram divididos em dois paradigmas: o construtivo e o redutivo. No primeiro,

t´ecnicas tradicionais de algoritmos em grafos s˜ao empregadas com base em recurs˜ao, en-

quanto que no segundo ´e usada uma t´ecnica de reduc¸˜ao, baseada em l´ogica de segunda

ordem e ´algebra de grafos. Embora os algoritmos tenham sido assim divididos de modo a

favorecer uma abordagem did´atica, eles n˜ao s˜ao de forma alguma independentes; de fato,

5. Conclus

oes e Recomendac¸

oes

´e at´e poss´ıvel estabelecer uma relac¸ ˜ao de eq¨uivalˆencia entre eles. Vale observar que tais

algoritmos foram desenvolvidos com base em resultados obtidos para uma vasta gama de

aplicac¸ ˜oes, sendo generalizados com base, principalmente, nestes dois paradigmas.

A maioria dos algoritmos conta com uma vers˜ao formalizada, apresentada numa

pseudo-linguagem de programac¸ ˜ao. A id´eia de tal representac¸ ˜ao visa facilitar uma

vis˜ao algor´ıtmica voltada para implementac¸˜ao. Assim como a vis˜ao algor´ıtmica de

decomposic¸˜ao em ´arvore veio enriquecer ainda mais a percepc¸ ˜ao dos conceitos e resul-

tados te´oricos — principalmente nos casos em que provas algor´ıtmicas s˜ao fornecidas

— um esforc¸o de implementac¸˜ao dos algoritmos aqui discutidos tem grande efeito es-

clarecedor e did´atico. De fato, um produto secund´ario deste trabalho de pesquisa foi o

desenvolvimento de um ambiente interativo para e com implementac¸˜ao dos principais al-

goritmos encontrados no texto, ou seja, al´em da implementac¸˜ao de rotinas e algoritmos,

foram disponibilizadas ferramentas para construc¸˜ao de decomposic¸ ˜oes em ´arvore.

Uma das principais recomendac¸ ˜oes para trabalhos futuros contempla, ent˜ao, o

prosseguimento do trabalho de implementac¸˜ao de modo a acrescentar mais ferramen-

tas, rotinas e algoritmos. Desta forma, este texto pretende ser tamb´em uma referˆencia

inicial para pesquisa de novos algoritmos. Outras recomendac¸ ˜oes podem sugerir ainda

o desenvolvimento de novas referˆencias para decomposic¸˜ao em ´arvore em l´ıngua

portuguesa.

Refer

encias Bibliogr

aﬁcas

ABRAHAMSON, K. R. E FELLOWS, M. R. (1993). “Finite automata, bounded

treewidth and wellquasiordering”. In: Graph Structure Theory, Contemporary

Mathematics, Volume 147, pp. 539–564. Providence, EUA: Am. Math. Soc.

ALON, N., SEYMOUR, P., E THOMAS, R. (1990). “A separator theorem for graphs

with an excluded minor and its applications”. In: Proceedings of the 22nd annual

ACM Symposium on Theory of Computing, pp. 293–299. ACM.

ARNBORG, S. (1985). “Efﬁcient algorithms for combinatorial problems on graphs

with bounded decomposability — a survey”. BIT (25): 2–23.

ARNBORG, S., CORNEIL, D. G., E PROSKUROWSKI, A. (1987). “Complexity of

ﬁnding embeddings in a k-tree”. SIAM J. Alg. Discrete Math. (8): 277–284.

ARNBORG, S., COURCELLE, B., PROSKUROWS KI, A., E SEESE, D. (1993). “An

algebraic theory of graph reduction”. J. Assoc. Comput. Mach. 40(5): 1134–1164.

ARNBORG, S., LAGERGREN, J., E SEESE, D. (1991). “Easy problems for

tree-decomposable graphs”. J. Algorithms (12): 308–340.

ARNBORG, S. E PROSKUROWSKI, A. (1986). “Characterization and recognition of

partial 3-trees”. SIAM J. Alg. Discrete Math. (7): 305–314.

ARNBORG, S. E PROSKUROWS KI, A. (1989). “Linear time algorithms for np-hard

problems restricted to partial k-trees”. Discrete Applied Math. (23): 11–24.

ARNBORG, S. E PROSKUROWS KI, A. (1990). “Canonical representation of partial 2-

and 3-trees”. In: Scandinavian Workshop on Algorithm Theory, pp. 310–319.

BERGE, C. (1973). Graph and Hypergraphs. Amsterdam, Holanda: North Holland.

BODLAENDER, H. L. (1986). Classes of Graphs with Bounded Treewidth. Relat´orio

t´ecnico, Department of Computer Science, Utrecht University, Utrecht, Holanda.

Refer

encias Bibliogr

aﬁcas

BODLAENDER, H. L. (1988). “Dynamic programming algorithms on graphs with

bounded tree-width”. In: Proceedings of the 15th International Colloquium on Au-

tomata, Languages and Programming, Volume 317 de Lecture Notes in Computer

Science, Berlin, Alemanha, pp. 105–119. Springer-Verlag.

BODLAENDER, H. L. (1993a). “Complexity of path-forming games”. Theoret.

Comput. Sci. (110): 215–245.

BODLAENDER, H. L. (1993b). “A linear time algorithm for ﬁnding tree-

decompositions of small treewidth”. In: Proceedings of the 25th annual ACM

Symposium on Theory of Computing, San Diego, California, EUA, pp. 226–234.

ACM Press.

BODLAENDER, H. L. (1993c). “A tourist guide through treewidth”. Acta Cybern. (11):

1–23.

BODLAENDER, H. L. (1994). “Improved self-reduction algorithms for graphs with

bounded treewidth”. Discrete Appl. Math. (54): 101–115.

BODLAENDER, H. L. (1996). “A linear time algorithm for ﬁnding tree-decompositions

of small treewidth”. SIAM Journal on Computing 25: 1305–1317.

BODLAENDER, H. L. (1997). “Treewidth: Algorithmic techniques and results”. In:

I. Privara e P. Ruzicka (Eds.), Proceedings 22nd International Symposium on

Mathematical Foundations of Computer Science, MFCS’97, Lecture Notes in

Computer Science, Volume 1295, Berlin, Alemanha, pp. 29–36. Springer Verlag.

BODLAENDER, H. L. (2000). Necessary edges in k-chordalizations of graphs.

BODLAENDER, H. L., GILBERT, J. R., HAFSTEINSS ON, H., E KLOKS, T. (1995a).

“Approximating treewidth, pathwidth, and minimum elimination tree height”. J.

Algorithms (18): 238–255.

BODLAENDER, H. L. E HAGERUP, T. (1995). “Parallel algorithms with optimal spee-

dup for bounded treewidth”. In: Proceedings of the 22nd International Colloquium

on Automata, Languages and Programming, Volume 944, Berlin, Alemanha, pp.

268–279. Springer Verlag.

BODLAENDER, H. L. E KLOKS, T. (1996). “Efﬁcient and constructive algorithms for

the pathwidth and treewidth of graphs”. J. Algorithms (21): 358–402.

BODLAENDER, H. L., KLOKS, T., E KRATSCH, D. (1995b). “Treewidth and

pathwidth of permutation graphs”. SIAM J. Discrete Math. (8): 606–616.

BODLAENDER, H. L. E M

OHRING, R. H. (1993). “The pathwidth and treewidth of

cographs”. SIAM J. Discrete Math. (6): 181–188.

BODLAENDER, H. L. E THILIKOS, D. M. (1999). “Graphs with branchwidth at most

three”. J. Algorithms (32): 167–194.

BONDY, J. A. E MURTY, U. S. R. (1976). Graph Theory with Applications. Londres,

Inglaterra: McMillan.

Refer

encias Bibliogr

aﬁcas

BORIE, R. B., PARKER, R. G., E TOVEY, C. A. (1992). “Automatic generation

of linear-time algorithms from predicate calculus descriptions of problems on

recursively constructed graph families”. Algorithmica (7): 555–582.

COURCELLE, B. (1990). “The Monadic Second-order Logic of graphs I: Recognizable

sets of ﬁnite graphs”. Information and Computation 85.

DE FLUITER, B. (1997). Algorithms for Graphs of Small Treewidth. Ph. D. thesis,

Department of Computer Science, Universiteit Utrecht, Utrecht, Holanda.

DE FLUITER, B. E BODLAENDER, H. L. (1995). Reduction Algorithms for

Graphs with Small Treewidth. Relat´orio T´ecnico UU-CS-1995-37, Department of

Computer Science, Universiteit Utrecht, Utrecht, Holanda.

DE FLUITER, B. E BODLAENDER, H. L. (1996). “Reduction algorithms for graphs

with small treewidth”. In: Proceedings of the 2nd Annual International Conference

on Computing and Combinatorics, COCOON’96, Volume 1090, pp. 199–208.

Springer Verlag, Lecture Notes in Computer Science.

DIESTEL, R. (2000). Graph Theory. New York, NY, EUA: Springer Verlag.

DIMITRIOU, T. E IMPAGLIAZZO, R. (1996). “Towards an analysis of local optimiza-

tion algorithms”. In: Proceedings of the 28th annual ACM Symposium on Theory

of Computing, Philadelphia, Pennsylvania, EUA, pp. 304–313. ACM Press.

DJIDJEV, H. E REIF, J. (1991). “An efﬁcient algorithm for the genus problem with ex-

plicit construction of forbidden subgraphs”. In: Proceedings of the 23rd annual

ACM Symposium on Theory of Computing, New Orleans, Louisiana, EUA, pp.

337–347. ACM Press.

ELLIS, J. A., SUDBOROUGH, I. H., E TURNER, J. (1994). “The vertex separation and

search number of a graph”. Inform. and Comput. (113): 50–79.

EVANS, J. R. E MINIEKA, E. (1992). Optimization Algorithms for Networks and

Graphs. E.U.A.: Marcel Dekker Inc.

FELLOWS, M. R. E LANGSTON, M. A. (1989). “On search decision and the efﬁciency

of polynomial-time algorithms (extended abstract)”. In: Proceedings of the 21st

annual ACM Symposium on Theory of Computing, Seattle, Washington, EUA, pp.

501–512. ACM Press.

FELLOWS, M. R. E LANGSTON, M. A. (1994). “On search, decision and the efﬁciency

of polynomial-time algorithms”. J. Comput. System. Sci. (49): 769–779.

FREDERICKSON, G. N. (1991). “Planar graph decomposition and all pairs shortest

paths”. Journal of the ACM 38(1): 162–204.

GAVOILLE, C., PELEG, D., P

ERENNES, S., E RAZ, R. (2001). “Distance labeling

in graphs”. In: Proceedings of the 12th annual ACM Symposium on Discrete

Algorithms, Washington, D.C., EUA, pp. 210–219. ACM Press.

GOLUMBIC, M. C. (1980). Algorithmic Graph Theory and Perfect Graphs. Nova

York, E.U.A.: Academic Press.

Refer

encias Bibliogr

aﬁcas

HABIB, M. E M

OHRING, R. H. (1994). “Treewidth of cocomparibility graphs and a

new order-theoretic parameter”. ORDER (1): 47–60.

KLOKS, T. (1993). Treewidth of Circle Graphs. Relat´orio t´ecnico, Department of

Computer Science, Utrecht University, Utrecht, Holanda.

KLOKS, T. (1994). “Treewidth — computations and approximations”. In: Lecture

Notes in Computer Science, Volume 842. Springer-Verlag.

KLOKS, T. E KRATSCH, D. (1994). “Finding all minimal separators of a graph”. In:

Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer

Science, Volume 775 de Lecture Notes in Computer Science, Berlin / Nova York,

pp. 759–768. Springer-Verlag.

KLOKS, T. E KRATSCH, D. (1995). “Treewidth of chordal bipartite graphs”. J.

Algorithms (19): 266–281.

KOBLER, D. E ROTICS, U. (2001). “Polynomial algorithms for partitioning problems

on graphs with ﬁxed clique-width (extended abstract)”. In: Proceedings of the 12th

annual ACM Symposium on Discrete Algorithms, Washington, D.C., EUA, pp.

468–490. ACM Press.

KOSTER, A. M., BODLAENDER, H. L., E VAN HOESEL, S. P. (2001). “Treewidth:

Computational experiments”. Electronic Notes in Discrete Mathematics 8.

LAGERGREN , J. (1996). “Efﬁcient parallel algorithms for graphs of bounded tree-

width”. J. Algorithms (20): 20–44.

LAGERGREN , J. E ARNBORG, S. (1991). “Finding minimal forbidden minors using

a ﬁnite congruence”. In: Proceedings of the 18th International Colloquium on Au-

tomata, Languages and Programming, Volume 510 de Lecture Notes in Computer

Science, Berlin / Nova York, pp. 533–543. Springer-Verlag.

MAHESHWARI, A. E ZEH, N. (2001). “I/o-efﬁcient algorithms for graphs of boun-

ded treewidth”. In: Proceedings of the 12th annual ACM Symposium on Discrete

Algorithms, Washington, D.C., EUA, pp. 89–90. ACM Press.

MATOUSEK, J. E THOMAS, R. (1991). “Algorithms ﬁnding tree-decompositions of

graphs”. J. Algorithms (12): 1–22.

MATOUSEK, J. E THOMAS, R. (1992). “On the complexity of ﬁnding iso- and other

morphisms for partial k-trees”. Discrete Mathematics (108): 343–364.

PAPADIMITRIOU, C. H. E STEIGLITZ, K. (1983). Combinatorial Optimization:

Algorithms and Complexity. New Jersey, E.U.A.: Prentice Hall, Englewood Cliffs.

PERKOVIC, L. E REED, B. (2000). “An improved algorithm for ﬁnding tree de-

compositions of small width”. International Journal of Foundations of Computer

Science 11(3): 365–371.

REED, B. A. (1992). “Finding approximate separators and computing tree width quic-

kly”. In: Proceedings of the 24th annual ACM Symposium on Theory of Computing,

Victoria, British Columbia, Canada, pp. 221–228. ACM Press.

Refer

encias Bibliogr

aﬁcas

REED, B. A. (1997). Surveys in Combinatorics, Volume 315, Cap´ıtulo Tree Width and

Tangles: A New Conectivity Measure and Some Applications, R. Bailey (ed.), pp.

87–162. Cambridge University Press.

ROBERTSON, N. E SEYMOUR, P. D. (1983). “Graph minors. I. Excluding a forest”. J.

Combin. Theory Ser. B. (35): 39–61.

ROBERTSON, N. E SEYMOUR, P. D. (1985). Surveys in Combinatorics, Cap´ıtulo

Graph Minors — A Survey, pp. 153–171. Cambridge, RU: Cambridge Univ. Press.

ROBERTSON, N. E SEYMOUR, P. D. (1986). “Graph minors. II. Algorithmic aspects

of tree-width”. J. Algorithms (7): 309–322.

ROBERTSON, N. E SEYMOUR, P. D. (1991). “Graph minors. X. Obstructions to tree-

decomposition”. J. Combin. Theory Ser. B. (52): 153–190.

ROBERTSON, N. E SEYMOUR, P. D. (1995). “Graph minors. XIII. The disjoint paths

problem”. J. Combin. Theory Ser. B. (63): 65–110.

SANDERS, D. P. (1996). “On linear recognition of tree-width at most four”. SIAM J.

Discrete Math. (9): 101–117.

WILSON, R. J. (1985). Introduction to Graph Theory. Nova York, E.U.A.: Longman

Scientiﬁc & Technical.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 