Teoria dos Grafos

Material Teórico
Árvores e Ordenação Topológica

Responsável pelo Conteúdo:

Prof. Dr. Cleber Silva Ferreira da Luz

Revisão Textual:
Prof. Me. Luciano Vieira Francisco
 Árvores e Ordenação Topológica

• Introdução;
• Árvore;
• Ordenação Topológica e Algoritmos de Fluxo de Rede;
• Fluxo em Redes.

OBJETIVO DE APRENDIZADO
• Conhecer todos os conceitos de árvores e topologia.
 Orientações de estudo
Para que o conteúdo desta Disciplina seja bem
aproveitado e haja maior aplicabilidade na sua
formação acadêmica e atuação profissional, siga
algumas recomendações básicas:
Conserve seu
material e local de
estudos sempre
organizados.
Aproveite as
Procure manter indicações
contato com seus de Material
colegas e tutores Complementar.
para trocar ideias!
Determine um Isso amplia a
horário fixo aprendizagem.
para estudar.

Mantenha o foco!
Evite se distrair com
as redes sociais.

Seja original!
Nunca plagie
trabalhos.

Não se esqueça
de se alimentar
Assim: e de se manter
Organize seus estudos de maneira que passem a fazer parte hidratado.
da sua rotina. Por exemplo, você poderá determinar um dia e
horário fixos como seu “momento do estudo”;

Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma

alimentação saudável pode proporcionar melhor aproveitamento do estudo;

No material de cada Unidade, há leituras indicadas e, entre elas, artigos científicos, livros, vídeos
e sites para aprofundar os conhecimentos adquiridos ao longo da Unidade. Além disso, você tam-
bém encontrará sugestões de conteúdo extra no item Material Complementar, que ampliarão sua
interpretação e auxiliarão no pleno entendimento dos temas abordados;

Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de discus-
são, pois irão auxiliar a verificar o quanto você absorveu de conhecimento, além de propiciar o
contato com seus colegas e tutores, o que se apresenta como rico espaço de troca de ideias e de
aprendizagem.
UNIDADE Árvores e Ordenação Topológica

Introdução
Nesta Unidade estudaremos conceitos importantes sobre grafos, árvore, orde-
nação topológica e fluxo em redes. Tais conceitos são de suma importância no
estudo de grafos, além de aplicáveis em diversos problemas. Por exemplo, em pro-
jeto de circuitos eletrônicos frequentemente é necessário tornar os pinos de vários
componentes eletricamente equivalentes, juntando a fiação de todos. Nessa mode-
lagem, para interconectar um conjunto de n pinos, podemos utilizar um arranjo de
n-1 fios, cada qual conectado a dois pinos. Assim, de todos os arranjos possíveis,
aquele que utiliza a quantidade mínima de fios é normalmente o mais desejável.
Este problema é facilmente modelado com árvores – veremos mais detalhes.

Ordenação topológica será o segundo assunto estudado nesta Unidade. Pode-

mos dizer que uma ordenação topológica de um grafo pode ser vista como uma
ordenação de seus vértices ao longo de uma linha horizontal, de tal forma que
todas as arestas orientadas sigam da esquerda para a direita. Ordenação topoló-
gica somente é aplicada a grafos orientados e acíclicos. Na teoria de grafos, os
acíclicos orientados são empregados em muitas aplicações para indicar a prece-
dência entre eventos.

De uma maneira bem simples, fluxo em rede envolve a complexidade de fazer

circular determinado produto através dos vértices e das arestas de uma rede. Ha-
bitualmente, os problemas de fluxos são associados às várias situações reais de
distribuição de água, eletricidade, produtos industriais, movimentação de veículos,
entre outros.

Árvore
De uma maneira bem simples, podemos definir uma árvore como um grafo
conexo e acíclico. Todavia, essa conceituação é bem sucinta. Uma definição mais
completa e tradicional pode se dada a seguir:

Uma árvore é um grafo conexo T em que existe um e somente um caminho

entre qualquer par de vértices de T. Quando árvores são mencionadas, preci-
samos definir também subárvores. Uma subárvore pode ser definida como um
subgrafo conexo e acíclico.

Outra definição importante também é a de grafo estrela: dado um grafo G com

n vértices, um grafo é denominado estrela quando G é uma árvore que possui um
vértice de grau n-1 e os demais vértices com grau 1.

Na teoria dos grafos, árvores são estruturas que podem ser utilizadas para mo-
delar diversos problemas, estes que podem ser encontrados em diversas áreas,
desde a computação, até a comunicação. A Figura 1 apresenta alguns exemplos
de árvores:

8
a) Árvore ponderada b) Árvore não ponderada c) Estrela
7 2 1 2 2
4 1 1
1 3
1 2 3 3
4
4 7 4 6
2 7 6
2
6
5 5 5

Figura 1 – Exemplos de árvores

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Propriedades das Árvores

A estrutura em árvore possui algumas propriedades básicas:
• Todo grafo G conexo possui, pelo menos, uma subárvore que contém todos
os seus vértices;
• Toda árvore é um grafo planar;
• Toda árvore finita com n > 1 possui, pelo menos, dois vértices terminais.

Árvore Geradora
Uma árvore geradora de um grafo G é um subgrafo gerador conexo e acícli-
co. Assim, todo grafo conexo possui, pelo menos, uma árvore geradora. Vale
lembrar que um grafo acíclico é aquele que não possui círculos, ou seja, as suas
arestas não formam círculos. A Figura 2 apresenta exemplos de árvores geradas
de um grafo:

a) Exemplo de grafo b) Árvore geradora c) Árvore geradora

1 2 3 1 2 3 1 2 3

4 5 6 4 5 6 5 6

7 8 9 7 8 9 7 8 9

Figura 2 – Exemplo de árvore geradora

Fonte: adaptado de Goldbarg e Goldbarg, 2012

Floresta
Na teoria dos grafos, floresta é um conjunto de árvores sem vértices em
comum. Uma floresta geradora contém todos os vértices de G. Podemos dizer
que uma floresta geradora é um subgrafo que generaliza o conceito de árvore
geradora. Assim, na floresta geradora cada componente conexo é uma árvore e

9
9
UNIDADE Árvores e Ordenação Topológica

cada vértice do grafo original está em alguma árvore. De maneira simples, uma
floresta geradora em G é um subgrafo acíclico e gerador – a Figura 3 exemplifica
florestas de um grafo:

a) Exemplo de grafo b) Florestas c) Florestas

1 2 3 4 1 2 3 4 1 2 3 4
T1 T2 T3
T1 T2 T3

5 6 7 5 6 7 5 6 7

8 9 10 11 8 9 10 11 10 11

Figura 3 – Florestas
Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Aresta Elo
Na teoria de grafos, um conceito importante é o de aresta elo. Para entendê-lo
considere um grafo G = (N, M) e T (N, MT), uma árvore geradora de G, uma aresta
e ∈ M|MT, denominando-se elo de G em relação a T.

É importante observar que a adição de um elo em uma árvore produz um único

ciclo no grafo resultante – a Figura 4b apresenta uma aresta que produz um ciclo
na árvore:

a) 10 b) 10 c) 10

1 2 3 1 2 3 1 2 3
e
e

8 9 4 8 9 4 8 9 4

7 6 5 7 6 5 7 6 5

Figura 4 – Ciclo fundamental produzido por aresta elo

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Árvore Geradora Mínima e Árvore Geradora Máxima

Na teoria de grafos, uma árvore geradora mínima (TMIN) é a árvore geradora
de menor custo entre todas as possíveis em G. O custo de uma árvore geradora T
de um grafo ponderado G é dado pelo somatório dos custos das arestas de T.

Já uma árvore geradora máxima é de maior custo em G. As figuras 5b e 5c

apresentam as árvores geradoras mínima e máxima, respectivamente, do grafo
apresentado na Figura 5a:

10
a) Grafo G b) Árvore geradora mínima c) Árvore geradora máxima

5 5 5
10 12 10 12

8 7 1 6 7 1 6 8 6
8 5 5 8

4
1 4 1 2 1 4 1 2
8 5 8 5

Figura 5 – Árvore geradora mínima e máxima

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Outros dois conceitos importantes são árvore geradora de grau mínimo e árvore
geradora mínima com mínimo grau. Começaremos por árvore geradora de grau
mínimo, tratando-se de uma árvore geradora desenvolvida em um grafo não pon-
derado e possuindo o menor grau máximo possível. Agora, árvore geradora mí-
nima com mínimo grau é uma árvore geradora mínima de um grafo ponderado a
qual possui o menor grau máximo possível (GOLDBARG; GOLDBARG, 2012).

A seguir serão apresentados dois algoritmos clássicos para se obter a árvore

geradora mínima de um grafo.

Algoritmo de Prim
O algoritmo de Prim é eficiente e elegante. Foi proposto por Robert C. Prim, em
1957. A ideia central desse algoritmo é incluir, de forma gulosa, um a um, os vértices
da árvore. São sempre considerados os conjuntos TMIN, T, e V, onde TMIN ⊆ M, T ⊆
N, V ⊆ N. Eis a descrição do algoritmo de Prim (GOLDBARG; GOLDBARG, 2012):

Quadro 1

Ler G = (N, M) e D = [dij] a matriz de pesos de G

Escolha qualquer vértice i ∈ N
T←{i}
V ← N \ {i}
TMIN ← ∅
Enquanto T ≠ N Faça
Encontrar a aresta (j, k) ∈ M tal que j ∈ T, K ∈ V e djk é mínimo.
T ← T U {K}
V ← V / {K}
TMIN ← TMIN U (j,k)
Fim_enquanto
Escrever TMIN{o conjunto das arestas da árvore geradora mínima}

11
11
UNIDADE Árvores e Ordenação Topológica

O algoritmo de Prim parte de qualquer vértice de G. A cada passo, acrescenta a

menor aresta incidente no conjunto de vértices que já foi selecionado e que possui
uma extremidade em vértices fora desse conjunto. A Figura 6 exemplifica o funcio-
namento do algoritmo de Prim para o grafo apresentado na Figura 6a. A Figura 6e
demonstra a árvore final.

Ademais, na Figura 6 é importante observar que a cada passo do algoritmo um

novo vértice é acrescentado à árvore em formação através da aresta “mais barata”
incidente no conjunto do vértice já examinado. Por exemplo, no passo 3 apresenta-
do na Figura 6c, as arestas examinadas são (2,4), (2,5), (3,4) e (3,5); o conjunto já
examinado é representado pela nuvem pontilhada vermelha.
a) b) Aresta 1, 2
1 1
2 4 2 4
1 3 1 1 3 1
4 4
1 1 -2 6 1 1 -2 6

3 2 3 2
3 5 3 5
2 2
T = {1} ≠ N T = {1, 2} ≠ N

c) Aresta 2, 3 d) Aresta 2, 4
1 1
2 4 2 4
1 3 1 1 3 1
4 4
1 1 -2 6 1 1 -2 6

3 2 3 2
3 5 3 5
2 2
T = {1, 2, 3} ≠ N T = {1, 2, 3, 4} ≠ N

e) Aresta 4, 6 f)
1 1
2 4 2 4
1 3 1 1 3 1
4 4
1 1 -2 6 1 1 -2 6

3 2 3 2
3 5 3 5
2 2
T = {1, 2, 3, 4, 5, 6} ≠ N
T = {1, 2, 3, 4, 5} ≠ N
Figura 6 – Evolução do algoritmo de Prim
Fonte: Adaptado de Goldbarg e Goldbarg, 2012

12
 Algoritmo de Prim Colorido
O algoritmo de Prim obtém a árvore geradora mínima. Todavia, caso haja um
controle das arestas que são examinadas, esse algoritmo ficará mais eficiente. Essa
versão do algoritmo de Prim é chamada de Prim colorido, vejamos (GOLDBARG;
GOLDBARG, 2012).

Quadro 2

Ler G = (N, M) e D = [dij] a matriz de pesos G

Escolha qualquer vértice j ∈ N
I←0
Definir T = (NT, MT); NT ← {j}; MT ← ∅
Colorir com verde as arestas incidentes do vértice j
Enquanto i < n-1 Faça
Selecionar a aresta verde (j,k) j ∈ NT, tal que djk é mínima e colori-la de Azul
MT ← MT U (j, k); NT ← NT U {k}
Para cada aresta (k, z), z ∉ NT Fazer
Se não existir aresta verde incidente em z, colorir(k, z) como verde
Senão
Se existir aresta verde (w, z) tal que dwz > dkz colorir (w,z) com
vermelho e (k, z) com verde
Fim_Para
i←i+1
Fim_enquanto
Escrever Ti {a árvore geradora mínima}

Semelhante ao algoritmo clássico de Prim, o algoritmo de Prim colorido escolhe

aleatoriamente o vértice inicial da árvore geradora. O algoritmo de Prim colorido
possui complexidade de o(n2).
Observemos um exemplo: a Figura 7 apresenta o desenvolvimento do algoritmo
de Prim colorido. No grafo da Figura 7a o vértice escolhido foi o 1, apresentando
o grafo G, onde será obtida a árvore gerada mínima; já a Figura 7a (l) ilustra o de-
senvolvimento do algoritmo de Prim colorido em um passo a passo:
a) Grafo G exemplo para a aplicação do b) Vértice 1 é examinado Arestas (1, 2) c) A menor aresta verda é colorida de
algoritmo de Prim Colorido e (1, 30) são coloridas de verde azul e inserida na solução
22 22 22
2 4 2 4 2 4
1 3 1 3 1 3

1 1 -3 6 1 1 -3 6 1 1 -3 6
3 3 3

3 2 3 2 3 2
3 5 3 5 3 5
2 2 2

d) Vértice 2 é examinado e as Arestas e) Aresta (1, 3) é colorida de vermelho f) Vértice 3 é examinado. A aresta (3, 5)
(2, 4) e (2, 5) são pintadas de verde e a Aresta (2, 3) é colorida de azul é colorida de verde e a aresta (2, 5)
de vermelho
22 22 22
13
2 4 2 4 2 4 13
1 3 1 3 1 3
UNIDADE Árvores
1
e1 Ordenação
3 -3
Topológica
6 1 1 3 -3 6 1 1 3 -3 6

3 2 3 2 3 2
3 5 3 5 3 5
2 2 2

d) Vértice 2 é examinado e as Arestas e) Aresta (1, 3) é colorida de vermelho f) Vértice 3 é examinado. A aresta (3, 5)
(2, 4) e (2, 5) são pintadas de verde e a Aresta (2, 3) é colorida de azul é colorida de verde e a aresta (2, 5)
de vermelho
22 22 22
2 4 2 4 2 4
1 3 1 3 1 3

1 1 -3 6 1 1 -3 6 1 1 -3 6
3 3 3

3 2 3 2 3 2
3 5 3 5 3 5
2 2 2

g) Aresta (3, 5) é pintada de azul h) Vértice 5 é examinado e as arestas i) A aresta (2, 4) é pintada de vermelho
(5, 6) e (5, 4) são coloridas de verde
22 22 22
2 4 2 4 2 4
1 3 1 3 1 3

1 1 -3 6 1 1 -3 6 1 1 -3 6
3 3 3

3 2 3 2 3 2
3 5 3 5 3 5
2 2 2

j) Dentre todas as verdes, a menor é (5, 4) Então l) O vértice 4 é examinado e a aresta (4, 6)
ela é pintada de azul e incluída na solução é colorida de vermelho e a (5, 6) de azul, i = n –1 e fim
22 22
2 4 2 4
1 3 1 3

1 1 -3 6 1 1 -3 6
3 3

3 2 3 2
3 5 3 5
2 2

Figura 7 – Desenvolvimento do algoritmo de Prim colorido

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Note que a Figura 7l apresenta a árvore geradora mínima, pintada de azul.

Algoritmo de Kruskal
Além do algoritmo de Prim, diversos outros foram formulados para obter a ár-
vore geradora mínima, entre os quais encontra-se o algoritmo de Kruskal, proposto
por Joseph B. Kruskal, em 1956.

A ideia central desse algoritmo é voltada à formação da árvore por meio da

inclusão de arestas – e não de vértices, como em Prim. Assim, a “árvore” que
se forma é, de fato, uma floresta. A seguir é apresentado o algoritmo de Kruskal
(GOLDBARG; GOLDBARG, 2012).

14
 Quadro 3

Ler G = (N, M) D = [dij] a matriz de pesos de G

Ordene as arestas em ordem não crescente de pesos dij no vetor.
H = [hi], i = 1, 2, ..., m
T ← h1
i←2
Enquanto |T| < n Faça
Se T U hi é um grafo acíclico então
T ← T U hi
i←i+1
Fim_Enquanto
Escrever T {arestas da árvore geradora mínima}

Nesse algoritmo, H representa o vetor das arestas ordenadas e hj é um elemento

de H; a árvore em formação é representada por T.

As figuras 8a a 8h exemplificam o algoritmo de Kruskal, valendo observar que

na Figura 8g a inclusão da aresta (2,6) é recusada porque leva à formação de um
ciclo em T.

A próxima aresta H (6,7) é, então, examinada e incluída na Figura 8h – a próxi-

ma etapa do algoritmo Kruskal incluiria a aresta (3,1), concluindo o procedimento.

1
6
3 9
2 3 4 Vetor H
8 3
1
2 1 h1 – (3, 6) = 1; h2 – (4, 7) = 1; h3 – (5, 6) = 2;
h4 – (2, 3) = 3; h5 – (2, 6) = 3; h6 – (6, 7) = 5;
2 5
5 6 7 h7 – (1, 3) = 6; h8 – (2, 5) = 8; h9 – (3, 4) = 9;
a) Grago G exemplo para o algoritmo Kruskal b) Ordenação das arestas de G em H

1 Vetor H 1 Vetor H
h1 – (3, 6) = 1; h1 – (3, 6) = 1;
h2 – (4, 7) = 1; h2 – (4, 7) = 1;
h3 – (5, 6) = 2; h3 – (5, 6) = 2;
2 3 4 h4 – (2, 3) = 3; 2 3 4 h4 – (2, 3) = 3;
h5 – (2, 6) = 3; h5 – (2, 6) = 3;
1 h6 – (6, 7) = 5; 1 1 h6 – (6, 7) = 5;
h7 – (1, 3) = 6; h7 – (1, 3) = 6;
h8 – (2, 5) = 8; h8 – (2, 5) = 8;
5 6 7 h9 – (3, 4) = 9; 5 6 7 h9 – (3, 4) = 9;

c) Inserção da Primeira aresta em T d) Inserção da Segunda aresta em T

1 Vetor H 1 Vetor H
h1 – (3, 6) = 1; h1 – (3, 6) = 1;
h2 – (4, 7) = 1; h2 – (4, 7) = 1;
h3 – (5, 6) = 2; h3 – (5, 6) = 2;
2 3 4 h4 – (2, 3) = 3; 2 3 3 4 h4 – (2, 3) = 3;
h5 – (2, 6) = 3; h5 – (2, 6) = 3;
1 1 h6 – (6, 7) = 5; 1 1 h6 – (6, 7) = 5;
h7 – (1, 3) = 6; h7 – (1, 3) = 6;
2 h8 – (2, 5) = 8; 2 h8 – (2, 5) = 8; 15
5 6 7 h9 – (3, 4) = 9; 5 6 7 h9 – (3, 4) = 9; 15
 2 3 4 h4 – (2, 3) = 3; 2 3 4 h4 – (2, 3) = 3;
h5 – (2, 6) = 3; h5 – (2, 6) = 3;
UNIDADE Árvores e Ordenação1 Topológica h6 – (6, 7) = 5; 1 1 h6 – (6, 7) = 5;
h7 – (1, 3) = 6; h7 – (1, 3) = 6;
h8 – (2, 5) = 8; h8 – (2, 5) = 8;
5 6 7 h9 – (3, 4) = 9; 5 6 7 h9 – (3, 4) = 9;

c) Inserção da Primeira aresta em T d) Inserção da Segunda aresta em T

1 Vetor H 1 Vetor H
h1 – (3, 6) = 1; h1 – (3, 6) = 1;
h2 – (4, 7) = 1; h2 – (4, 7) = 1;
h3 – (5, 6) = 2; h3 – (5, 6) = 2;
2 3 4 h4 – (2, 3) = 3; 2 3 3 4 h4 – (2, 3) = 3;
h5 – (2, 6) = 3; h5 – (2, 6) = 3;
1 1 h6 – (6, 7) = 5; 1 1 h6 – (6, 7) = 5;
h7 – (1, 3) = 6; h7 – (1, 3) = 6;
2 h8 – (2, 5) = 8; 2 h8 – (2, 5) = 8;
5 6 7 h9 – (3, 4) = 9; 5 6 7 h9 – (3, 4) = 9;

e) Inserção da Terceira aresta em T f) Inserção da Quarta aresta em T

1 Vetor H 1 Vetor H
h1 – (3, 6) = 1; h1 – (3, 6) = 1;
h2 – (4, 7) = 1; h2 – (4, 7) = 1;
h3 – (5, 6) = 2; h3 – (5, 6) = 2;
1 3 3 4 h4 – (2, 3) = 3; 2 3 3 4 h4 – (2, 3) = 3;
h5 – (2, 6) = 3; h5 – (2, 6) = 3;
3 1 1 h6 – (6, 7) = 5; 1 1 h6 – (6, 7) = 5;
h7 – (1, 3) = 6; h7 – (1, 3) = 6;
2 h8 – (2, 5) = 8; 2 5 h8 – (2, 5) = 8;
5 6 7 h9 – (3, 4) = 9; 5 6 7 h9 – (3, 4) = 9;

g) Inserção da Quinta aresta em T h) Inserção da Quinta aresta em T

1
6

2 3 3 4

1 1

2 5
5 6 7

i) Árvore geradora mínima

Figura 8 – Desenvolvimento do algoritmo de Kruskal

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Ordenação Topológica e
Algoritmos de Fluxo de Rede
Segundo Cormen e colaboradores (2002), ordenação topológica é uma ordena-
ção linear de todos os seus vértices, tal que se G contém uma aresta (u, v), então u
aparece antes de v na ordenação. Para isso, o grafo deve ser acíclico e orientado.
Caso o grafo não seja acíclico, então não é possível nenhuma ordenação linear.

Podemos dizer que uma ordenação topológica de um grafo pode ser vista como
uma ordenação de seus vértices ao longo de uma linha horizontal, de tal forma que
todas as arestas orientadas sigam da esquerda para a direita.

Na teoria de grafos, grafos acíclicos orientados são empregados em diversas

aplicações para indicar a precedência entre eventos. A Figura 9 mostra um exemplo
que surge quando o hipotético professor João se veste pela manhã: deve trajar certas

16
peças de roupas antes de outras – por exemplo, meias antes de sapatos –; já outros itens
podem ser colocados em qualquer ordem. Assim, no grafo apresentado na Figura 9
uma aresta (u, v) indica que a peça de roupa u deve ser vestida antes da peça v.

Meias 17/18
11/16 Cuecas Relógio 9/10
Sapatos 13/14
12/15 Calças
Camisa 1/8
6/7 Cinto Gravata 2/5
Paletó 3/4
Figura 9 – Grafo do exemplo
Fonte: Adapatado de Cormen e colaboradores, 2002

Portanto, uma ordenação topológica desse grafo fornece uma ordem ao proces-
so de se vestir (CORMEN et al., 2002).

A Figura 10 apresenta o grafo topologicamente organizado como uma ordena-

ção de vértice ao longo de uma linha horizontal, tal que todas as arestas orientadas
sigam da esquerda para a direita:

Meias Cuecas Calças Sapato Relógio Camisa Cinto Gravata Paletó

17/18 11/16 12/15 13/14 9/10 1/8 6/7 2/5 3/4

Figura 10 – Ordenação topológica

Fonte: Adaptado de Cormen e colaboradores, 2002

Fluxo em Redes
Segundo Goldbarg e Goldbarg (2012), os problemas de fluxo abordam a comple-
xidade de fazer circular determinado produto através dos vértices e das arestas de
uma rede. Assim, esse tipo de problema associa aos componentes de um grafo já
conhecido um novo elemento denominado fluxo. Habitualmente, os problemas de
fluxo são associados às diversas situações reais de distribuição de água, eletricidade,
produtos industriais, movimentação de veículos, entre outros fatores.

Em fluxo de redes, a distribuição dos produtos não é realizada obrigatoriamente

de um ponto de produção a um ponto de demanda, assim, é possível que existam
pontos intermediários, tais como depósitos ou centros de concentração e distribui-
ção. Todavia, no trajeto do objeto pela rede pode haver algumas restrições, tais
como de capacidade de tráfego, de custos etc.

17
17
UNIDADE Árvores e Ordenação Topológica

Em fluxo de rede, sempre é procurado manter o maior fluxo possível, mesmo

havendo restrições – de custo ou capacidade, por exemplo –, isso é conhecido
como o problema do fluxo máximo. Na literatura foram propostos diversos algo-
ritmos a esse tipo de problema, tais como Dantzig, Ford & Fulkerson, Edmonds &
Karp, entre outros.

Em Síntese Importante!

Nesta Unidade estudamos conceitos importantes sobre grafos, tais como árvore, orde-
nação topológica e fluxo em redes. Esses conceitos são de suma importância no es-
tudo de grafos, sendo aplicados em diversos problemas. De uma maneira bem simples,
podemos definir árvore como um grafo conexo e acíclico.
Ordenação topológica foi o segundo assunto estudado nesta oportunidade, de modo
que podemos dizer que uma ordenação topológica de um grafo pode ser vista como uma
ordenação de seus vértices ao longo de uma linha horizontal, de tal forma que todas as
arestas orientadas sigam da esquerda para a direita. Ademais, fluxo em rede envolve a
complexidade de fazer circular determinado produto através dos vértices e das arestas
de uma rede.
Por sua vez, árvore geradora de um grafo G é um subgrafo gerador conexo e acíclico.
Logo, na teoria de grafos uma árvore geradora mínima (TMIN) é a árvore geradora de me-
nor custo entre todas as possíveis em G. Existem dois algoritmos clássicos para se obter a
árvore geradora mínima, os algoritmos de Kruskal e de Prim.

18
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:

Livros
Introdução à teoria dos grafos
CLÁUDIO, L. L. Introdução à teoria dos grafos. [S.l.]: Impar, 2016.
Fundamentos da teoria dos grafos para computação
NICOLETTI, A. M.; HRUSCHKA JR, E. R. Fundamentos da teoria dos grafos para
computação. São Carlos, SP: Edufscar, 2006.
Grafos e redes: teoria e algoritmos básicos
SIMÕES, J. M. S. Grafos e redes: teoria e algoritmos básicos. [S.l.]: Interciência, 2013.

Leitura
Matemática discreta: combinatória, teoria dos grafos e algoritmos
[Link]

19
19
UNIDADE Árvores e Ordenação Topológica

Referências
BOAVENTURA NETTO, P. O. Grafos: teoria, modelos, algoritmos. 2. ed. São
Paulo: Blucher, 2001.

______.; JURKIEWICZ, S. Grafos: introdução e prática. 2. ed. [S.l.]: Blucher, 2017.

CORMEN, T. et al. Algoritmos – teoria e prática. 2. ed. [S.l.]: Campus, 2002.

FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. Uma introdução su-

cinta à teoria dos grafos. 2011. Disponível em: <[Link]
teoriadosgrafos>. Acesso em: 24 nov. 2018.

FURTADO, A. L. Teoria dos grafos algoritmos. Rio de Janeiro: LTC, 1973.

GOLDBARG, M.; GOLDBARG, E. Grafos – conceitos, algoritmos e aplicações.

[S.l.]: Campus, 2012.

NICOLETTI, A. M.; HRUSCHKA JR, E. R. Fundamentos da teoria dos grafos

para computação. São Carlos, SP: Edufscar, 2006.

SIMÕES, J. M. S. Grafos e redes: teoria e algoritmos básicos. [S.l.]: Interciência, 2013.

SZWARCFITER, J. L. Teoria computacional de grafos. [S.l.]: Elsevier, 2018.

20