Teroria de grafos

Prévia do material em texto

Teoria dos Grafos
Material Teórico
Responsável pelo Conteúdo:
Prof. Dr. Cleber Silva Ferreira da Luz
Revisão Textual:
Prof.ª Me. Sandra Regina Fonseca Moreira
Conceitos Básicos e Aplicações de Grafos
• Introdução;
• História da Teoria dos Grafos;
• Aplicações da Teoria dos Grafos;
• Conclusões e Resumo da Unidade.
• Apresentar as defi nições básicas e aplicações de grafos.
OBJETIVO DE APRENDIZADO
Conceitos Básicos e 
Aplicações de Grafos
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:
Assim:
Organize seus estudos de maneira que passem a fazer parte 
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.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
Não se esqueça 
de se alimentar 
e de se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
Unidade Conceitos Básicos e Aplicações de Grafos
Introdução
Grafo é uma estrutura abstrata muito utilizada na resolução de diversos tipos 
problemas da matemática e da computação. O principal objetivo da teoria dos gra-
fos é estudar a relação entre objetos de um determinado conjunto (GOLDBARG; 
GOLDBARG, 2012). Um grafo G é representado por G(V, A), onde V é conjunto 
não vazio de objetos, denominados Vértices ou Nós, e A é um conjunto de pares 
não ordenados de V, chamados de Arestas, (CORMEN; LEISERSON; CHARLES; 
RIVEST; STEIN, 2002), Por exemplo. Considere um grafo G(4,6). Este grafo é for-
mado por 4 vértices e 6 arestas.
V = {v1, v2, v3, v4}
A = {a1, a2, a3, a4, a5, a6} onde, a1 =(v1, v2), a2 =(v2, v3), a3 =(v3, v4), a4 = (v1, v4), 
a5 =(v2, v4), a6 = (v4, v3)
Um grafo também pode ser representado graficamente. Nesta representação, 
os vértices são representados por círculos ou pontos. Os vértices são conectados 
por arestas, estas são representadas por linhas (FEOFILOFF; KOHAYAKAWA; 
WAKABAYASHI, 2004).
As Figuras 1 e 2 apresentam exemplos de grafos. A Figura 1 mostra a repre-
sentação gráfica do grafo G(4,6). Já a Figura 2 ilustra um grafo G(3,3), ou seja, um 
grafo com 3 vértices e 3 arestas.
a1
a4
a5
a3
a6
a2
V5
V2
V1
V4
Figura 1 – Exemplo de grafo 1
Fonte: Acervo do conteudista
8
9
a1 a3
a2
V3V2
V1
Figura 2 – Exemplo de grafo 2
Fonte: Acervo do conteudista
História da Teoria dos Grafos
A Teoria dos Grafos teve início em 1736 na cidade de Konigsberg, quando o ma-
temático suíço Leonhard Euler publicou um artigo sobre o problema das pontes de 
Konigsberg. Neste artigo, Euler solucionou o problema das setes pontes de Konigsberg 
através da criação de grafos. O problema das setes pontes de Konigsberg é formulado 
da seguinte maneira: a cidade de Konigsberg era cortada pelo rio Pregel, neste rio, 
havia duas ilhas e sete pontes, conforme ilustrado na Figura 3. O matemático Euler se 
questionou se era possível encontrar um caminho que passasse por cada ponte uma 
única vez só, e retornar ao ponto inicial [HOLANDA, 2011].
A
C
B
D
Figura 3 – Pontes de Konigsber
Fonte: Extraída de (HOLANDA, 2011)
Para resolver este problema, Euler criou um diagrama que representava a cidade 
de Konigsber. O diagrama foi proposto da seguinte forma: a cada ilha e margem, 
ele associou um ponto (vértice), e a cada ponte, uma ligação (aresta) (HOLANDA, 
201). O diagrama proposto por Euler é ilustrado na Figura 4.
9
Unidade Conceitos Básicos e Aplicações de Grafos
Figura 4 – Diagrama proposto por Euler
Fonte: Adaptado de HOLANDA, 2011
Analisando o diagrama proposto, Euler percebeu que para passar por todas as 
pontes uma única vez e voltar ao ponto inicial, seria necessário que os vértices ti-
vessem um número par de arestas. Dessa forma, era impossível realizar este trajeto, 
pois havia vértices com exatamente três arestas incidentes (HOLANDA, 2011). 
Aplicações da Teoria dos Grafos
Diversos problemas da computação e matemática são resolvidos utilizando gra-
fos. As próximas subseções apresentam alguns destes problemas.
Placas de Circuitos Eletrônicos
Para a indústria eletrônica, é fundamental criar placas de circuitos eletrônicos de 
boa qualidade. Uma placa de circuito eletrônico permite que correntes percorram 
por componentes eletrônicos. Este percurso é determinado por um complexo sis-
tema eletrônico que pode ser simplificado e representado por um grafo. O objetivo 
do sistema eletrônico é examinar o caminho da corrente elétrica entre alguns com-
ponentes da placa (GOLDBARG, M.; GOLDBARG, E, 2012).
Um sistema eletrônico pode ser facilmente representado por um grafo. Os compo-
nentes eletrônicos podem ser representados por vértices, e as suas conexões elétricas 
podem ser representadas por arestas que contêm setas para representar o sentido do 
caminho da corrente no circuito (GOLDBARG, M.; GOLDBARG, E, 2012).
10
11
 
Figura 5 – Modelagem de placa circuito eletrônico com grafos
Fonte: Acervo do conteudista
Mapa Rodoviário
Grafos também podem ser utilizados para representar mapas rodoviários. 
As cidades podem ser representadas por vértices, e as rodoviárias podem ser repre-
sentadas pelas arestas (GOLDBARG, M.; GOLDBARG, E, 2012).
Vamos utilizar uma “situação exemplo” para facilitar a compreensão: considere 
o estado de São Paulo, que por sinal, possui diversas cidades. Neste estado, é pos-
sível ir de uma cidade para outra através das rodovias. Agora, imagine a seguinte 
situação: você mora na cidade de Campinas e pretende curtir uma praia no litoral 
de São Paulo. Há diversos caminhos que você pode utilizar. Você pode pegar a ro-
dovia BR-50 que passa pelas cidades de Vinhedo e Jundiaí e depois pegar a rodovia 
BR-116 que passa pelas cidades de Cotia e São Paulo e chegar ao seu destino final.
Dada essa situação, as cidades do Estado de São Paulo podem ser representadas 
por vértices, e as rodovias, por arestas.
 
Figura 6 – Mapa Rodoviário representado através de grafos
Fonte: Getty Images e Acervo do conteudista
11
Unidade Conceitos Básicos e Aplicações de Grafos
Grafo de Visibilidade
Grafos podem ser utilizados no tratamento da representação de visibilidade 
(GOLDBARG, M.; GOLDBARG, E, 2012). Por exemplo, considere um robô que 
anda (se movimenta) para frente. Para que o robô se movimente sem nenhum 
problema, é necessário implementar um eficiente mecanismo de visibilidade. Dessa 
forma, o robô consegue visualizar o que pode ser um obstáculo em seu percurso, 
ou seja, identifica objetos que podem impedir a sua movimentação.
A visibilidade do robô pode ser representada facilmente por um grafo. Considere 
um grafo G(N, M) no qual os vértices representam posições de observações e as 
arestas(i, j) marcam se o vértice i enxerga o vértice j. Por exemplo, vamos supor 
que o robô encontra-se parado no ponto A (vértice A) e deseja se movimentar até 
o ponto B. Se o vértice A consegue enxergar o vértice B, o robô consegue realizar 
o seu percurso sem nenhum problema.
A Figura 7 mostra um cenário em que os pontos de observações são representa-
dos por pequenos círculos. Uma aresta desenhada por uma linha contínua que liga 
dois pontos implica que um ponto (vértice) enxerga o outro ponto. Já uma aresta 
com linha pontilhada ligando dois pontos implica que não exista visibilidade entre 
esses pontos.
B
D
C
F G
A
E
Figura 7 – Cenário de observação 
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
A Figura 8 apresenta uma situação em que o robô pode encontrar um obstáculo. 
O ponto B não enxerga o ponto C. Dessa forma, diretamente, o percurso de B até 
C não pode ser realizado.
12
13
B
A
D
C
Figura 8 – Ponto de obstáculos
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
A Figura 9 mostra a visibilidade do vértice A em relação aos outros vértices. Por 
exemplo, considere que o robô se encontra no vértice A. Dessa forma, é possível 
perceber quais pontos o robô consegue enxergar. Vale ressaltar que as arestas 
pontilhadas mostram que o robô não consegue enxergar aquele ponto, enquanto 
as arestas contínuas mostram que o robô consegue enxergar aquele ponto. Dessa 
forma, o robô conseguiria se mover diretamente para os pontos B, D, E e F, ao 
contrário dos pontos C e G.
B
D
C
F G
A
E
Figura 9 – Visibilidade do ponto A
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
A Figura 10 mostra como seria o grafo de visibilidade deste cenário. Em suma, 
um grafo de visibilidade mostra todos os vértices que se enxergam.
13
Unidade Conceitos Básicos e Aplicações de Grafos
B
D
C
F G
A
E
Figura 10 – Grafo de visibilidade
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
Grafo de Discos
Grafos também podem ser aplicados para os discos. Imagine n pontos distri-
buídos em um plano e uma unidade de distância r. É possível obter um grafo G 
considerando-se que os n pontos formam o conjunto N e que existe a aresta (i, j) 
se o ponto j está localizado dentro de um círculo de raio r traçado a partir de i, 
conforme ilustrado na Figura 12(1). A Figura 11(1) mostra o processo de criação do 
grafo, já a Figura 11(2) mostra os pontos distribuídos à distância r. A Figura 11(3) 
mostra o grafo de disco da Figura 11(2) e, por fim, a Figura 11(4) apresenta o grafo 
não direcionado obtido. Na aplicação de disco, é possível trabalhar com grafos di-
recionados ou grafos não direcionados (GOLDBARG, M.; GOLDBARG, E, 2012).
(2) Pontos distribuídos à distância r(1) Aresta
r
Figura 11 A – Construção de grafo de disco
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
14
15
(3) Grafo de disco da Figura (2) (4) Grafo não direcionado
Figura 11 B – Construção de grafo de disco
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
Grafo de Xadrez
Grafos podem ser aplicados até mesmo em jogos de xadrez. Um grafo de xa-
drez é um grafo que representa os movimentos válidos de determinada peça do 
jogo de xadrez. A Figura 12 (1) apresenta o grafo de movimentos válidos para o rei 
e o peão. Neste grafo, os movimentos das peças são representados pelas arestas, 
e as posições das peças nas casas do tabuleiro são representadas pelos vértices. 
No xadrez, o peão e o rei atacam apenas casas vizinhas em linhas e colunas. Des-
sa forma, o grafo que representa seus movimentos é também chamado de grafo 
grade. A Figura 12 (2) representa parte do grafo de movimento de uma torre. 
A torre pode percorrer linhas e colunas do tabuleiro. Uma torre pode se deslocar 
para qualquer casa na mesma linha ou coluna[4]. A Figura 12(2) exibe as possibili-
dades de arestas de uma linha do tabuleiro para a movimentação da torre.
(1) Grafo xadrez rei e pião (2) complemento para o grafo xadrez torre
Figura 12 – Grafo de xadrez
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
15
Unidade Conceitos Básicos e Aplicações de Grafos
Grafo de Estado
Um grafo também é útil para representar o espaço de estados de um sistema e 
mostrar como esses estados se relacionam. Habitualmente, o conjunto de vértices do 
grafo de estado está associado às configurações do sistema, que também são deno-
minadas de Estados. O estado de um sistema pode ser compreendido também como 
uma dada atribuição de valores para as suas variáveis livres. No grafo de estado, 
o conjunto de arestas indica as alternativas possíveis para executar uma transfor-
mação nas configurações do sistema. Tais configurações são representadas pelos 
vértices. Para exemplificar, imagine um grafo de estado em que uma aresta repre-
senta a possibilidade de movimentar uma peça no tabuleiro (ver o tópico anterior). 
Os tabuleiros, antes e depois da peça ser movimentada, representam possíveis esta-
dos do grafo ou seus vértices.
Uma transformação na configuração do sistema não obrigatoriamente determi-
na a alteração do estado do sistema. Grafo de estado também é útil para modelar 
um processo de decisão. Nesse caso, cada vértice do grafo representa o resultado 
de certa decisão, enquanto as arestas modelam a forma de transformação sofrida 
pela decisão anterior para transformá-la na decisão corrente (GOLDBARG, M.; 
GOLDBARG, E, 2012).
A Figura 13 ilustra um Grafo de estado e seus elementos.
1
4
2
3 5
- Transição
- Mudança de decisão
- Mudança de con
guração
- Decisão
- Con
guração
Estado 1
Estado 2
Figura 13 – Grafo de estado
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
16
17
Grafo de Estado para Solução de um Problema Lógico
Problema: O barqueiro João recebeu a missão de atravessar uma ovelha, um 
lobo e um pacote de alface de uma margem para outra do rio São Francisco 
(GOLDBARG, M.; GOLDBARG, E, 2012). Para realizar essa travessia, João irá 
utilizar a sua canoa que possui a capacidade de transportar somente duas 
pessoas. João só será pago após realizar a travessia da ovelha, do lobo e do 
pacote de alface, e se todos chegarem com segurança na outra margem. Todavia, 
caso o lobo permaneça em alguma margem sozinho com a ovelha, fatalmente ele 
irá devorá-la. Agora, se a ovelha permanecer sozinha com o pacote de alface, ela, 
com certeza, irá comê-lo. Infelizmente, nessa missão, não há ninguém que possa 
ajudar João. Como realizar a travessia de modo que a carga seja transportada 
com segurança?
Modelagem
Considere (J) como o rótulo para representar o João, (L) como rótulo para re-
presentar o lobo, (A) como rótulo para representar a alface e (O) para representar 
a ovelha.
A Figura 14 ilustra uma interpretação para este problema.
JLOA
LA
JO
JL
J
JL
J
JO
JO
LA
LA
LA
A
A
A L
L
O
O
A
Figura 14 – Modelagem do problema
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
Inicialmente todos estão na margam à esquerda. Após a travessia, todos deverão 
estar na margem à direita. Nesta modelagem, em nenhuma margem o lobo e a 
ovelha ficam sozinhos, ou a ovelha fica sozinha com o pacote de alface. Analisando 
essa modelagem, surge a pergunta: o grafo é relevante para modelar este problema? 
17
Unidade Conceitos Básicos e Aplicações de Grafos
A resposta é afirmativa. Vamos lá, considere um grafo de movimento, onde os vérti-
ces representam a população da margem inicial, e as arestas representam as viagens 
na canoa, conforme a Figura 16 exemplifica.
Margem inicial antes
do movimento
Margem inicial após
o movimento
Transporte na canoa
JLOA OA
JL
Figura 15 – Modelo do grafo
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
Depois de realizar esta formulação, é possível organizar um grafo de estado con-
forme mostrado na Figura 16.
JLOA
JA
LO
LA
OA
J
L
A
JLA
JLA
JLA
JOL
JOA
JA
JA
JO
JO JA
JLJL
JL
JL
O
O
JO
Retorno sem sentido
repete a viagem
Retorno sem sentido
repete a viagem
Figura 16 – Grafo de estado parcial do problema do barqueiro – margem inicial
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG,E, 2012
Quando a margem inicial ficar vazia, o problema será solucionado, ou seja, 
quando um vértice vazio for alcançado no grafo. O grafo não precisa explorar 
movimentos de violação das regras de segurança ou repetir operações. O grafo da 
Figura 16 pode ser reduzido ao grafo da Figura 17.
18
19
JLOA LA JLA
JA
JO
JOL
JL
JL
JO JOA JA
J
JOL JO
JO
O
L
A
O JA
JL
JLA A
JO
JOVolta
Volta
Volta
Volta
J
L
JJO
JL
Figura 17 – Grafo de movimento do problema do barqueiro – margem inicial
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
Grafo de Estado para a Solução do 8-Puzzle
O 8-puzzle é um jogo de quebra-cabeça bastante conhecido entre as pessoas. 
O jogo é composto por um tabuleiro com determinadas peças. Em cada peça há 
um número diferente escrito. O objetivo do jogo é alcançar uma determinada con-
figuração para os números do tabuleiro. Para isso, é possível movimentar os nú-
meros do tabuleiro deslizando as peças horizontalmente e verticalmente para uma 
posição vazia no tabuleiro (GOLDBARG, M.; GOLDBARG, E, 2012).
A Figura 18(1) apresenta um tabuleiro do 8-puzzle. A Figura 18(2) apresenta um 
exemplo de configuração desejada.
(1) Quadro Inicial (2) Quadro �nal desejado
1 2 3
6 4 5
8 7
1 2 3
8
6
4
7 5
Figura 18 – Confi guração do 8-Puzzle
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
19
Unidade Conceitos Básicos e Aplicações de Grafos
Para este jogo, o grafo de modelagem considera uma configuração do tabuleiro em 
cada vértice. Dessa forma, um vértice será uma configuração do tabuleiro. Já as arestas 
modelam os movimentos de deslizamento das peças. A Figura 19 exemplifica um grafo 
de modelagem com nove vértices. O início do jogo é representado pelo vértice 1.
1
1 2 3
6 4 5
8 7
1
5 6 7 8 9
4 3
1 2 3
6
4
5
8 7
1 2 3
6 4 5
78
1 2 3
6
4 5
8 7
1 2 3
6
4
5
8 7
1
2
3
6
4
5
8 7
1 2 3
6
4
5
8 7
1 2 3
6 4
58 7
1 2 3
6 4 5
8 7
Figura 19 – Grafo para modelar os movimentos do 8-Puzzle
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
Grafos para Modelar Jogos
Grafos também aparecem na modelagem de jogos. Habitualmente, um jogo é 
composto por personagens (agentes) que disputam recursos ou competem para 
alcançar um objetivo. Frequentemente, esses agentes tomam decisões. Grafos po-
dem ser úteis para representar as decisões que os agentes podem tomar, ou, até 
mesmo, mostrar os estados dos jogos.
Grafos são utilizados para modelar diversos jogos, entre eles, encontra-se o jogo 
da velha. No jogo da velha, grafos mapeiam todas as possíveis jogadas dos competi-
dores, onde os vértices representam as possíveis jogadas, e as arestas representam 
as ligações entre as jogadas.
Manejo Ecológico de Reservas Vegetais
A perversão da fauna e também da flora é muito importante para o equilíbrio 
do ecossistema. Habitualmente, os biólogos criam diversos modelos matemáticos 
20
21
para ajudar nas perversões ecológicas de reservas vegetais. Em contrapartida, para 
a sobrevivência do ser humano, em determinadas situações se faz necessária a utili-
zação de determinadas reservas vegetais. O maior desafio encontrado até hoje pelo 
ser humano é conciliar a preservação com a demanda de utilização das reservas 
(GOLDBARG, M.; GOLDBARG, E, 2012).
Na questão de preservação, grafos podem ser úteis para modelagem do ma-
nejo ecológico de reservas vegetais. Imagine que determinada área vegetal seja 
economicamente explorada para a extração de madeira de lei; considere também 
que as árvores sejam cortadas perto do fim do seu ciclo de vida natural. Leve em 
conta que as árvores removidas são substituídas por mudas de outra árvore que 
deve ser plantada no mesmo local da removida. Agora, observe a Figura 20. Esta 
figura exemplifica a planta de um lote de distribuição de espécies vegetais. Este 
lote é explorado economicamente. Nesta figura, os traços representam caminhos 
preexistentes (percurso para andar pela reservar), o quadrado vermelho é um pos-
to do IBAMA. 
Figura 20 – Distribuição das árvores no lote de exploração
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
Considere que duas remoções nunca podem ocorrer a menos de 500 metros 
de outra remoção, ou seja, deve haver um espaço mínimo de 500 metros entre 
uma remoção e a outra. A área para a remoção das árvores não pode ultrapassar 
2000 metros.
 A Figura 21 apresenta o modelo em grafo das restrições desse problema. Neste 
problema, caso duas á rvores estejam localizadas dentro do raio de 500 metros de 
afastamento mínimo, são ligadas por uma aresta.
21
Unidade Conceitos Básicos e Aplicações de Grafos
Figura 21 – Grafo de proximidade
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
A Figura 22 mostra uma solução viável para a exploração desse lote.
Figura 22 – Árvores escolhidas
Fonte: Adaptado de GOLDBARG, M.; GOLDBARG, E, 2012
Conclusões e Resumo da Unidade
Criados em 1736 pelo matemático suíço Euler, grafos podem ser compreendidos 
como estruturas abstratas cujo objetivo é demonstrar o relacionamento entre obje-
tos. Um grafo é composto por vértices (objetos) e arestas (ligação entre os objetos). 
Matematicamente, um grafo G é representado por G(V, A), onde V é conjunto não 
vazio de objetos denominados Vértices ou Nós, e A é um conjunto de pares não 
22
23
ordenados de V, chamados de arestas. Grafos também podem ser representados 
graficamente, onde os vértices são representados por círculos ou pontos, e as ares-
tas, por linhas contínuas.
Grafos são utilizados em diversas aplicações, dentre elas, estão: a fabricação de 
placas de circuitos eletrônicos, mapas rodoviários, mapas de visibilidade, mapas de 
disco, mapas de Xadrez, jogos, e também no manejo ecológico de reservas vege-
tais. Grafos aparecem até mesmo em redes sociais. Um grande exemplo disso é o 
Facebook. A ideia do Facebook é conectar pessoas. Dessa forma, as pessoas são 
encaradas como vértices e as ligações entre elas, são as arestas.
Como visto nesta unidade, grafos são de suma importância para a resolução de 
diversos problemas. Habitualmente, grafos são bem empregados em situações nas 
quais se deseja estudar o relacionamento entre objetos.
23
Unidade Conceitos Básicos e Aplicações de Grafos
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Livros
Teoria computacional de grafos, os algoritmos
SZWARCFITER, Jayme L. Teoria computacional de grafos, os algoritmos. São 
Paulo. Editora: Elsevier, 2018.
 Vídeos
Introdução à Teoria dos Grafos - Aula 1 - O que é um grafo?
Este vídeo conta a história da teoria dos grafos e exemplifica um grafo.
https://youtu.be/Frmwdter-vQ
Introdução à Teoria dos Grafos – Aula 2 – Alguns problemas simples
Este vídeo exemplifica alguns problemas solucionados com grafos.
https://youtu.be/fLNQfhpv-js
Teoria dos Grafos Aula 1
Este vídeo fala sobre a história da teoria dos grafos e sobre os conceitos básicos de 
grafos.
https://youtu.be/YCUKumiv_Ck
24
25
Referências
BOAVENTURA NETTO, Paulo Oswaldo. Grafos: teoria, modelos, algoritmos. 
2. ed. São Paulo: Edgard Blucher, 2001.
CORMEN, T. H.; LEISERSON, Charles E.; RIVEST, R.; STEIN, C. Algoritmos 
teoria e prática. 2. ed., Campus, 2002.
FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. – Uma Introdução 
Sucinta à Teoria dos Grafos, 2011, Disponível em: <https://bit.ly/2XrHdjR>. 
Acessado em: 24/11/2018.
FURTADO, A. L. – Teoria dos grafos algoritmos, Livros Técnicos e científicos. 
Rio de Janeiro: Editora S.A, 1973.
GOLDBARG, M.; GOLDBARG, E. Grafos conceitos, algoritmos e aplicações. 
São Paulo: Campus, 2012.
HOLANDA, Bruno – Teoria dos Grafos. – Relatório técnico. Disponível 
em: <https://bit.ly/2wzN7n9> Acessado em: 28/11/2018.
NETTO, P. O.; JURKIEWICZ, S. Grafos: Introdução e Prática. 2. ed. São Paulo: 
Blucher, 2017.
NICOLETTI, Maria do Carmo; HRUSCHKA JÚNIOR, Estevam Rafael. Fundamen-
tos 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. Rio de Janeiro: 
Interciência, 2013.
SZWARCFITER,J. L. Teoria computacional de grafos. 1. ed. São Paulo: 
Elsevier. (8 de março de 2018).
25
Teoria dos Grafos
Material Teórico
Responsável pelo Conteúdo:
Prof. Dr. Cleber Silva Ferreira da Luz 
Revisão Textual:
Prof.ª Me. Sandra Regina Fonseca Moreira
Conceitos e Propriedades de Grafos
• Introdução;
• Conceitos Básicos;
• Propriedades Fundamentais de Grafos.
• Apresentar os principais conceitos e propriedades da teoria dos grafos.
OBJETIVO DE APRENDIZADO
Conceitos e Propriedades de Grafos
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:
Assim:
Organize seus estudos de maneira que passem a fazer parte 
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.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
Não se esqueça 
de se alimentar 
e de se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Conceitos e Propriedades de Grafos
Introdução 
Proposto em 1736 pelo matemático suíço Leonhard Euler, grafos são essenciais 
para solucionar problemas de matemática. Como já visto anteriormente, um grafo 
é uma estrutura abstrata, cujo objetivo principal é estudar o relacionamento entre 
objetos (BOAVENTURA; Paulo, 2017). Um Grafo é composto por vértices (obje-
tos) e arestas (ligações entre os objetos). Matematicamente, um grafo G é dado por 
G(V,A), onde V é um conjunto não vazio de objetos, e A é um conjunto de arestas 
(CORMEN; LEISERSON; CHARLES; RIVEST; STEIN, 2002). A Figura 1 apresenta 
um grafo G(6,8).
Figura 1 – Exemplo de grafo
Fonte: Acervo do conteudista
A teoria dos grafos esta repleta de nomenclaturas, termos técnicos, propriedades 
e definições que são empregadas nos grafos. O objetivo desta unidade é apresentar 
os principais conceitos e propriedades presentes na teoria dos grafos, conforme 
veremos nas seções seguintes.
Conceitos Básicos
Vamos estudar um pouco sobre os conceitos básicos na teoria dos grafos. 
Um grafo é composto por vértices e arestas, certo? Os vértices são os objetos e 
as arestas são as ligações entre os objetos. Todavia, um grafo pode conter arestas 
paralelas. Observe as arestas a5 e a6 do grafo apresentado na Figura 2. Essas ares-
tas representam ligações diferentes entre vértices idênticos, com isso, são denomi-
nadas arestas paralelas (NICOLETTI; MARIA; HRUSCHKA; ESTEVAM, 2006). 
Agora, uma aresta pode ligar um vértice a ele mesmo. Observe a aresta a3 do 
grafo apresentado na Figura 2. Esta aresta liga o vértice V3 a ele mesmo, formando 
um laço. Aresta com essa característica é denominada de laço (FEOFILOFF, P.; 
KOHAYAKAWA, Y.; WAKABAYASHI, 2011). 
8
9
V2
V1 V4
V3
a5
a6
a4
a3
a2
a1
a7
Figura 2 – Arrestas paralelas e laços
Um grafo que não contém arestas paralelas e não contém arestas em forma de 
laços é denominado de grafo simples (BOAVENTURA; PAULO, 2017). 
Já um grafo que contém no mínimo um laço é chamado de pseudografo 
(GOLDBAR, M.; GOLDBARG, E, 2012). A Figura 3 ilustra um pseudografo.
a1
V1
V2 V3
Figura 3 – Pseudografo
Um pseudografo onde todos os vértices possuem um laço associado é deno-
minado como grafo reflexivo (SIMÕES; 2013). A Figura 4 ilustra um exemplo de 
grafo reflexivo.
a1
a3
a2
V1
V2 V3
Figura 4 – Grafo refl exivo
9
UNIDADE Conceitos e Propriedades de Grafos
Um grafo não direcional, que contém no mínimo duas arestas paralelas, é chama-
do de multigrafo (SZWARCFITER;2018). A Figura 5 ilustra um exemplo de multigrafo.
a1
a8
a7
a5
a6
a4
a3
a2
V1 V6
V5
V4
V3
V2
Figura 5 – Multigrafo
Um grafo direcionado, que possui no mínimo dois ou mais arcos de mesma 
direção ligando um mesmo par de vértices, é denominado multigrafo direcionado 
(FURTADO, 1973).
Já um grafo vazio é aquele que contém somente vértices (GOLDBAR, M.; 
GOLDBARG, E, 2012). A Figura 6 ilustra um exemplo de grafo vazio.
V1
V5
V4
V3V2
Figura 6 – Grafo vazio
Um grafo é denominado como trivial quando possui apenas um vértice. A Figura 7 
ilustra um exemplo de grafo trivial (GOLDBAR, M.; GOLDBARG, E, 2012). 
V1
Figura 7 – Grafo trivial
Um grafo é denominado como nulo quando não existem vértices (GOLDBAR, 
M.; GOLDBARG, E, 2012).
10
11
Já um grafo que contém apenas um vértice e n arestas é denominado de grafo 
Buquê (GOLDBAR, M.; GOLDBARG, E, 2012). A Figura 8 ilustra um grafo buquê.
V1
a3
a4
a5a1
a2
Figura 8 – Grafo Buquê
Um grafo pode ser generalizado para o caso em que a relação entre os vértices 
permite a consideração de mais de um par de nós ou vértices. “Quando um grafo 
possui uma ou mais arestas que correspondam a relações que envolvam mais de dois 
vértices, esse grafo é denominado hipergrafo” (GOLDBAR, M.; GOLDBARG, E, 
2012). A Figura 9 ilustra um hipergafo.
1 2
6
5
4
3
Figura 9 – Hipergrafo
Fonte: Adaptada de GOLDBAR, M.; GOLDBARG, E, 2012
Propriedades Fundamentais de Grafos
Grafos Rotulados
Um grafo pode possuir atribuições (informações) associadas tanto em suas ares-
tas como em seus vértices. Habitualmente, essas atribuições são descritas junto 
aos seus elementos. As anotações que permitem distinguir vértices e arestas são 
chamadas de rótulos (NETTO; JURKIEWICZ,2017). 
11
UNIDADE Conceitos e Propriedades de Grafos
Um grafo que possui atribuição em seus vértices ou arestas é denominado como 
grafo rotulado (NETTO; JURKIEWICZ,2017). Na Figura 10, o grafo 1 não é ro-
tulado, o grafo 2 possui rótulos nas arestas e o grafo 3 possui rótulos nos vértices. 
É importante ressaltar que os rótulos podem ser letras, números, palavras, ou até 
mesmo letras com números, ou palavras com números. Em palavras bem simples, 
rótulo é um nome dado aos vértices e arestas. 
1
2 3
a
a
e
e
d
dc c
b
b
Figura 10 – Exemplo de grafo rotulado 
Fonte: Adaptado de GOLDBAR, M.; GOLDBARG, E, 2012
Grafos Ponderados
Outro tipo de grafo muito comum é o grafo ponderado (BOAVENTURA; PAULO, 
2017). Um grafo é definido como ponderado se existem pesos associados as suas 
arestas ou vértices. A Figura 11 apresenta dois grafos, o grafo 1 e o grafo 2. O grafo 
1 possui pesos associados em suas arestas, já o grafo 2 possui pesos associados em 
seus vértices. 
1
1
98
15
3
3
4
5
7
7
7
12
65
2
2
2
Figura 11 – Exemplos de grafos ponderados
12
13
Um grafo pode possuir rótulos e pesos ao mesmo tempo. Observe a Figura 12. 
Esta figura apresenta dois grafos. O grafo 1 possui vértices rotulados e arestas com 
pesos. O grafo 2 possui seus vértices com rótulos e pesos ao mesmo tempo. 
Figura 12 – Exemplos de grafos ponderados
Grafos Orientados e Não Orientados
Como mencionadoanteriormente, o principal objetivo da teoria de grafos é es-
tudar a relação dos objetos, certo? Os objetos são representados pelos vértices, e as 
arestas representam a relação entre os objetos. Todavia, em determinadas circuns-
tâncias, pode ser importante analisar o sentido desta relação. Por exemplo, imagine 
um grafo no qual seus vértices representem pessoas, e uma aresta i-j existe se a 
pessoa i conhece a pessoa j; isto não implica que j conhece i. Neste caso, a aresta 
i-j é denominada arco, e é representada graficamente como uma flecha. A flecha 
determina o sentido da relação (BOAVENTURA; PAULO, 2017).
Quando em um grafo as direções das arestas são importantes, o grafo é definido 
como direcionado, orientado ou dígrafo (GOLDBAR, M.; GOLDBARG, E, 2012). A 
Figura 13 apresenta dois grafos. O grafo 1 é não direcionado, já o grafo 2 é direcionado. 
1 2
Figura 13 – Grafo não direcionado e grafo direcionado
Fonte: Adaptado de GOLDBAR, M.; GOLDBARG, E, 2012
13
UNIDADE Conceitos e Propriedades de Grafos
Um grafo também pode conter arestas e arcos ao mesmo tempo. Um grafo com 
esta característica é denominado de misto (GOLDBAR, M.; GOLDBARG, E, 2012). 
A Figura 14 ilustra um exemplo de grafo misto. 
Figura 14 – Grafo misto
Fonte: Adaptado de GOLDBAR, M.; GOLDBARG, E, 2012
Tamanho e Ordem de Grafos 
A quantidade de vértices de um grafo define a sua ordem – |N| (FEOFILOFF, P.; 
KOHAYAKAWA, Y.; WAKABAYASHI, 2011). Já o número de arestas que um grafo possui 
define o seu tamanho – |M| (FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, 
2011). O grafo 1 apresentado na Figura 15 é de ordem 6 e tamanho 9. Já o grafo 2 é de 
ordem 3 e tamanho 3. 
1 2
Figura 15 – Ordem e tamanho de grafos
14
15
Adjacência de Vértices
Outra propriedade muito importante na teoria dos grafos é a adjacência de 
vértices (SIMÕES; 2013). Um grafo é uma estrutura abstrata indicada para a re-
presentação topológica de formas de conexão. Há duas formas para entender vizi-
nhança entre vértices e arestas. A primeira é para o caso dos grafos direcionados 
e a outra para os não direcionados. 
Dois vértices i e j são vizinhos ou adjacentes quando existe uma aresta que 
liga i a j ou vice-versa. O conjunto de vértices vizinhos do vértice i é denominado 
Γ(i) ou N(i). 
Por exemplo, considere o grafo 1 apresentado na Figura 16. Queremos saber quais 
são os vértices adjacentes ao vértice 6. Para isso, basta olhar os vértices que estão co-
nectados ao vértice 6. O grafo 2 da Figura 16 mostra os vértices adjacentes ao vértice 6.
1 2
22
3
6 6
44 55
7 7
1 1
3
N(6)= {4,5,7}
Figura 16 – Adjacência de vértices
Sucessores e Antecessores
Quando o grafo é direcionado, em determinadas circunstâncias, pode ser im-
portante saber quais são os vértices sucessores e antecessores a um determina-
do vértice. Certo, mas como é possível descobrir os sucessores e antecessores a 
determinado vértice? Um vértice j é sucessor de i se existe pelo menos um arco 
ligando i a j. Os sucessores do vértice i são Γ+(i). No caso da ocorrência inver-
sa, diz-se que o vértice j é antecessor de i. Os antecessores do vértice i são Γ - (i) 
(GOLDBAR, M.; GOLDBARG, E, 2012). O grafo apresentado na Figura 17 ilustra 
exemplos de antecessores e sucessores. Neste grafo, o antecessor do vértice 6 é 
o vértice 1. Já os sucessores são os vértices 2 e 3.
15
UNIDADE Conceitos e Propriedades de Grafos
Figura 17 – Antecessor e sucessor de vértice
Adjacência de Arestas
Duas arestas ai e aj são adjacentes se estiverem conectadas ao mesmo vértice, 
ou seja, compartilham o mesmo vértice (SIMÕES; 2013). A Figura 18 apresenta um 
grafo que exemplifica o conceito de arestas adjacentes. Neste exemplo, são evidenciadas 
as arestas adjacentes ao vértice 3.
Figura 18 – Arestas adjacentes
Grau de Vértice 
Em determinadas circunstâncias, pode ser interessante, ou até mesmo necessário, cal-
cular o grau (ou valência) de um vértice de um determinado grafo (SZWARCFITER;2018). 
O grau de um vértice é calculado pelo número de arestas incidentes a ele. Dessa forma, o 
grau d(xi) de um vértice xi, em um grafo não direcionado é igual ao número das arestas 
incidentes no vértice. Caso o vértice contenha laços, é contado duas vezes. A Figura 19 
16
17
ilustra um exemplo para grafos não direcionados. Neste exemplo, é calculado o grau dos 
vértices 2 e 7. No vértice 7 há duas arestas incidindo a ele, dessa forma, o seu grau é 
d(x7) = 2. No vértice há apenas uma aresta incidindo a ele, com isso, o seu grau é d(x2) = 1.
Caso todos os vértices do grafo possuam grau finito, o grafo é denominado como 
localmente finito (GOLDBAR, M.; GOLDBARG, E, 2012). Quando o vértice possui 
grau zero, ele é denominado vértice isolado (GOLDBAR, M.; GOLDBARG, E, 2012).
d(x2)=1
d(x7)=2
1
8
4
2
7
6
5
3
Figura 19 – Exemplo de grau de vértice em grafo não direcionado
Fonte: Adaptado de GOLDBAR, M.; GOLDBARG, E, 2012
O grafo apresentado na Figura 19 exemplifica o calculo do grau para um grafo 
não direcionado. Todavia, e se o grafo for direcionado? Caso o grafo seja direciona-
do, o grau de um vértice xj é composto por um valor interno e um valor externo. 
O grau interno de um vértice xj de um grafo direcionado é igual ao número 
de arcos incidentes ao vértice (que apontam para o vértice). Já o grau externo de 
um vértice xj de um grafo direcionado é igual ao número de arcos emergentes 
ao vértice (que deixam o vértice considerado) (GOLDBAR, M.; GOLDBARG, E, 
2012) Habitualmente, os graus internos e externos de um grafo direcionado são 
representados por d-(xj) e d+(xj) respectivamente. 
O cálculo do grau interno e externo de um vértice xj em grafo direcionado é 
exemplificado na Figura 20. Neste exemplo, é calculado o grau interno e exter-
no dos vértices 2, 6 e 7. É possível observar que, o grau interno do vértice 2 é 
d-(x2) = 0, porque não há nenhuma aresta incidente a ele. Já o seu grau externo é 
d2(x2) = 1, pois há uma única aresta emergindo dele. O grau interno do vértice 6 
é dado por d-(x6) = -1 e o grau externo é dado por d+(x6) = +1. Para o vértice 5, 
o grau interno é d-(x5) = -2 e o grau externo é d+(x5) = +1.
17
UNIDADE Conceitos e Propriedades de Grafos
d-(x2)= 0
d+(x2)= +1
d-(x6)= -1
d+(x6)= +1
d-(x5)= -2
d+(x5)= +1
1
8
4
2
7
6
5
3
Figura 20 – Exemplo de grau de vértice em grafo não direcionado
Fonte: Adaptado de GOLDBAR, M.; GOLDBARG, E, 2012
Quando o grafo é direcionado, as parcelas do grau (grau externo e grau interno) 
do vértice que também podem ser denominadas como semigraus são denotadas 
com valores positivos e negativos. O valor final do grau do vértice é dado pela 
soma do valor absoluto do semigrau interior d-(xi) e exterior d
+(xi) (GOLDBAR, 
M.; GOLDBARG, E, 2012). Dessa forma, o valor final do grau do vértice é obtido 
pela expressão d(xi) = | d
+(xi) | + | d
-(xi)|.
Por exemplo, o cálculo do grau dos vértices 3 e 4 seria da seguinte maneira.
d(3) = | d+(3) | + | d-(3)| = | +3 | + | 0 | =3
d(4) = | d+(4) | + | d-(4)| = | 0 | + | -4 | = 4
Grafos Regulares
Um grafo é denotado como regular quando todos os seus vértices possuem o 
mesmo grau [4]. Um grafo regular com vértices de graus k é denominado de 
grafo regular-k. A Figura 21 apresenta o grafo 1 e o grafo 2. O grafo 1 é um grafo 
regular-2, porque todos os vértices desse grafo possuem 2 graus. Já o grafo 2 é 
um grafo regular-3, pois todos os vértices possuem 3 graus cada. 
Quando um grafo possui somente vértices, ele é denominado grafo regular-0.
18
19
Quando, em um grafo, cada par de vértices adjacentes tem o mesmo número i de 
vizinhos em comum, e cada par de vértices não adjacentes tem o mesmo número n 
de vizinhos em comum, o grafo é denotado como fortemente regular (GOLDBAR, 
M.; GOLDBARG, E, 2012). 
1 2
Figura 21 – Grafos regulares
Fonte: Adaptado de GOLDBAR, M.; GOLDBARG, E, 2012
Grafo Completo e Subgrafos
Um grafo completo é um grafo simples, onde todo vértice é adjacente a to-
dos os outros vértices (BOAVENTURA; PAULO, 2017) Habitualmente um grafocompleto de n vértices é denotado por Kn.
No começo do estudo da teoria de grafos, foi dito que grafos representam a 
relação entre objetos e que diversos problemas são modelados através de grafo. 
É possível afirmar que em certas situações seja necessário distinguir partes espe-
cíficas de um grafo para solucionar um problema, obtendo, assim, um subgrafo. 
Dado um grafo G = (N,M), um subgrafo Gs = (Ns,Ms) é obtido se Ns C N e Ms 
C M, e uma aresta (i,j) existir em Ms, somente se i,j existir em Ns. 
Um subgrafo pode ser classificado em subgrafo próprio ou parcial.
Um subgrafo próprio Gs = (Ns,Ms) é obtido de G = (N,M) se Ns C N e Ms C M, 
ou Ns C N e Ms C M, e uma aresta (i,j) existe em Ms, somente se i,j existir em Ns.
Já um subgrafo parcial Gs = (Ns,Ms) é obtido de G = (N,M) se Ns = N e Ms C M, 
e uma aresta (i,j) existe em Ms, somente se i,j existir em Ns.
Para ilustrar um subgrafo, considere o grafo apresentado na Figura 22. 
19
UNIDADE Conceitos e Propriedades de Grafos
Figura 22 – Grafo exemplo
Fonte: Adaptado de GOLDBAR, M.; GOLDBARG, E, 2012
A Figura 23 apresenta os subgrafos extraídos do grafo A. O grafo 1 é um sub-
grafo parcial de A, onde Ns = N e Ms = M. O grafo 2 é um subgrafo próprio de 
A, onde Ns C N e Ms C M. O grafo 3 é um subgrafo parcial próprio de A, onde 
Ns = N e Ms C M. Por fim, o grafo 4 é um subgrafo parcial de A, onde Ns = N e 
Ms C M (GOLDBAR, M.; GOLDBARG, E, 2012). 
1 2 3 4
Figura 23 – Exemplo de subgrafos
Fonte: Adaptado de GOLDBAR, M.; GOLDBARG, E, 2012
Grafos Bipartidos
Um grafo bipartido é um grafo cujos vértices podem ser divididos em dois 
conjuntos diferentes X e Y. A Figura 24 ilustra um grafo bipartido (GOLDBAR, M.; 
GOLDBARG, E, 2012).
20
21
Figura 24 – Exemplo de grafo bipartido
Importante!
A teoria dos grafos é um ramo da matemática que estuda o relacionamento entre os ob-
jetos. Um Grafo é composto por vértices (objetos) e arestas (ligações entre os objetos). 
Matematicamente, um grafo G é dado por G(V,A), onde V é um conjunto não vazio de 
objetos e A é um conjunto de arestas.
Grafos são essenciais para a resolução de diversos problemas matemáticos. A teoria dos 
grafos esta repleta de nomenclaturas, termos técnicos, propriedades e definições que 
são empregadas nos grafos.
Nesta unidade foram apresentados conceitos básicos sobre a teoria dos grafos, conforme 
resumimos a seguir: quando um par de vértices é ligado por mais de uma aresta, dize-
mos que as arestas são arestas paralelas. Um laço é uma aresta que liga o vértice a ele 
mesmo. Grafo simples é um grafo que não contém laço e nem arestas paralelas.
Quando um grafo contém no mínimo um laço, é chamado de pseudografo. Um pseu-
dografo onde todos os vértices possuem um laço associado é denominado como grafo 
reflexivo. Um grafo é denominado como nulo quando não existem vértices. Quando um 
grafo possui uma ou mais arestas que correspondam a relações que envolvam mais de 
dois vértices é denominado hipergrafo.
Também foram apresentadas propriedades fundamentais, como grafos rotulados. Um 
grafo rotulado é um grafo que contém rótulo (nome) nos vértices ou arestas. Um grafo 
ponderado é um grafo que contém pesos nas arestas ou nos vértices. Grafos orientados 
são grafos cujas arestas contêm direção. As arestas são chamadas de arcos. A quantidade 
de vértices de um grafo define a sua ordem - |N|. Já o número de arestas que um grafo 
possui define o seu tamanho - |M|. 
Um vértice x é adjacente a um vértice y se houver uma aresta que os ligue direto. Duas 
arestas ai e aj são adjacentes se estiverem conectadas ao mesmo vértice, ou seja, com-
partilhem o mesmo vértice. Grau de um vértice é o número das arestas incidentes no 
vértice. Um grafo é denotado como regular quando todos os seus vértices possuem o 
mesmo grau. Um grafo completo é um grafo simples, onde todo vértice é adjacente a 
todos os outros vértices. Um grafo bipartido é um grafo cujos vértices podem ser dividi-
dos em dois conjuntos diferentes X e Y.
Em Síntese
21
UNIDADE Conceitos e Propriedades de Grafos
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Vídeos
Estrutura de Dados – Aula 23 – Grafos - Conceitos básicos
https://youtu.be/MC0u4f334mI
Pesquisa Operacional II – Aula 25 – Introdução à Teoria dos Grafos
https://youtu.be/pbDHIMFGgLk
Estrutura de Dados – Aula 23 – Grafos - Conceitos Básicos
https://youtu.be/MC0u4f334mI
Introdução à Teoria dos Grafos – Aula 5 – Grau de um vértice e o problema das Pontes de Königsberg
https://youtu.be/125pPCIRjZ8
22
23
Referências
BOAVENTURA NETTO, Paulo Oswaldo. Grafos: teoria, modelos, algoritmos. 2. ed. 
São Paulo: Edgard Blucher, 2001. 
CORMEN, T. H.; LEISERSON, CHARLES E.; RIVEST, R.; STEIN, C. Algoritmos 
teoria e prática. 2. ed., Campus, 2002.
FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. Uma Introdução Su-
cinta à Teoria dos Grafos, 2011, Disponível em: <http://www.ime.usp.br/~pf/
teoriadosgrafos/>. Acessado em: 24/11/2018.
FURTADO, A. L. Teoria dos grafos algoritmos, Livros Técnicos e científicos. 
Rio de Janeiro: Editora S.A, 1973.
GOLDBARG, M.; GOLDBARG, E. Grafos conceitos, algoritmos e aplicações. 
São Paulo: Campus, 2012.
HOLANDA, B. Teoria dos Grafos. Relatório técnico. Disponível em: <https://
www.obm.org.br/content/uploads/2017/01/Nivel1_grafos_bruno.pdf>. Acesso em: 
28/11/2018.
NETTO, P. O.; JURKIEWICZ, S. Grafos: Introdução e Prática. 2. ed. São Paulo: 
Blucher, 2017.
NICOLETTI, M. do C.; HRUSCHKA JÚNIOR, Estevam Rafael. 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. Rio de Janeiro: 
Interciência, 2013.
SZWARCFITER, J. L. Teoria computacional de grafos. 1. ed. São Paulo: Else-
vier. (8 de março de 2018). 
23
Teoria dos Grafos
Material Teórico
Responsável pelo Conteúdo:
Prof. Dr. Cleber Silva Ferreira da Luz
Revisão Textual:
Prof. Me. Luciano Vieira Francisco
Planaridade e Conectividade
• Introdução;
• Conexidade;
• Grafos Finitos e Infinitos;
• Planaridade de Grafo;
• Coloração;
• Representações de Grafos.
• Conhecer todos os conceitos sobre conectividade em grafos, bem como os conceitos de 
grafos fi nitos e infi nitos e de coloração.
OBJETIVO DE APRENDIZADO
Planaridade e Conectividade
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: 
Assim:
Organize seus estudos de maneira que passem a fazer parte 
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.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
Não se esqueça 
de se alimentar 
e de se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contatocom seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Planaridade e Conectividade
Introdução
Nesta Unidade serão abordados alguns conceitos muito importantes na teoria 
dos grafos: conexidade de grafos, grafos finitos e grafos infinitos, planaridade de 
grafos e o teorema de Kuratowski, coloração de grafos e representações de grafos.
O primeiro conceito que estudaremos é conexidade. Este conceito visa o estudo 
da conexidade do grafo. A conexidade analisa se um grafo G é conexo ou não, isto 
é, se partindo de um vértice A é possível chegar ao vértice B ou não. Esta conexi-
dade é observada para todos os vértices do grafo G.
O segundo conceito que será abordado é o de grafos finitos e infinitos. Um gra-
fo é considerado finito quando possui o número finito de vértices e de arestas; caso 
contrário, será infinito.
O terceiro conceito a ser abordado é planaridade de grafos. Um grafo planar 
é aquele imerso em um plano no qual as suas arestas nunca se cruzam. Grafos 
planares são aplicados em:
• Linhas de produção em uma indústria;
• Linhas de transmissão de energia elétrica;
• Rodovias que conectam cidades;
• Circuitos integrados, entre outros.
Planaridade de grafo e o teorema de Kuratowski serão apresentados com mais 
detalhes na Seção 4.
Após estudar o conceito de planaridade de grafos, o próximo assunto que será 
abordado é a coloração de grafos. O problema da coloração é dos mais conheci-
dos na teoria dos grafos, e consiste em colorir um grafo G = (V, A) utilizando a me-
nor quantidade de cores possível. Todavia, colorir um grafo não é tão fácil assim, os 
vértices adjacentes devem possuir cores diferentes – este problema é apresentado 
com mais detalhes na Seção 5.
Por fim, o último assunto abordado nesta Unidade é representações de grafos. 
Existem duas formas de representar um grafo, por listas de adjacências e por 
matriz de adjacências – este assunto é explorado na Seção 6.
Conexidade
O conceito de conexidade analisa se um grafo é conexo ou não, ou seja, verifica 
se partindo do vértice A é possível chegar ao vértice B. Boa parte das aplicações 
modeladas por grafos necessita que um vértice esteja ligado ao outro, ou que de um 
vértice A exista um caminho para chegar ao vértice B.
8
9
Grafo Conexo
Um grafo G = (V, A) é dito conexo se existir um caminho entre qualquer par de 
vértices. Caso contrário, será desconexo. A Figura 1a exemplifica um grafo conexo, 
enquanto a Figura 1b exemplifica um grafo desconexo:
Figura 1 – Grafo conexo e desconexo
Fonte: Acervo do Conteudista
É importante observar que se todos os vértices de um grafo G com n vértices 
tem um grau maior ou igual a n-1
2
, então esse grafo é conexo. Agora, quando no 
grafo não existe nenhuma aresta, é dito totalmente desconexo.
Componente Conexa
Na teoria dos grafos, uma componente conexa de um grafo G = (V, A) é um sub-
grafo conexo maximal de G – para mais detalhes de subgrafos, veja a Unidade II.
O número de componentes conexas em G é denotado por c. Em palavras mais 
simples, um grafo G desconexo é formado por, pelo menos, dois subgrafos cone-
xos; neste caso, cada subgrafo conexo é denominado componente conexa de G.
A Figura 2 ilustra componentes conexas de um grafo G. Grafos conexos pos-
suem apenas uma componente conexa.
Figura 2 – Componente conexa
Fonte: Acervo do Conteudista
Uma componente conexa H = (NH, MH) de um grafo G = (N, M) é chamada de 
ímpar se |NF| for ímpar; caso |NF| for par, será chamada de par. A quantidade 
de componentes ímpares ou pares de um grafo G será denotado por q(G).
9
UNIDADE Planaridade e Conectividade
Conexidade em Arestas
A conexidade em arestas de um grafo conexo de G é denotada pelo menor 
número de arestas cuja remoção resulta na desconexão de G. A Figura 3b 
exemplifica a possibilidade de desconexão do grafo da Figura 3a. Neste exemplo, 
temos que l(G) = 2.
Figura 3 – Conexidade em arestas
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Conexidade em Vértices
Em um grafo G, a conectividade ou conexidade em vértices é o menor número 
de vértices cuja remoção resulta em um grafo desconexo ou em um grafo 
trivial. Este número é denotado por K(G). A conexidade em vértices é também 
chamada de conexidade de grafo. As figuras 4b e 4c exemplificam as remoções 
de vértices que resultam em um grafo desconexo. Neste exemplo, tem-se K(G) = 1.
Figura 4 – Conexidade em vértices
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
10
11
Grafo K-Conexo
Na teoria dos grafos, um grafo é denominado k-conexo quando para qualquer 
par de vértices de G existem, pelo menos, K caminhos diferentes entre os quais.
As figuras 5b, 5c e 5d ilustram três caminhos diferentes entre o mesmo par de vér-
tice do grafo da Figura 5a. Qualquer que seja o par de vértices do grafo, existirão 
três caminhos diferentes entre os quais; assim, k = 3 para o grafo da Figura 5a.
Figura 5 – Grafos k-conexo
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
A Figura 6 Ilustra um grafo 3-conexo (a), uma desconexão em vértices (b) e uma 
desconexão em arestas (c).
Figura 6 – Grafo conexo, grafo desconexo em vértice e grafo desconexo em arestas
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
11
UNIDADE Planaridade e Conectividade
Vértices Fortemente Conexos
Em um grafo G = (V, A) direcionado, é dito que dois vértices i e j estão forte-
mente conectados, se existe caminho direcionado de i para j e de j para i em G. 
Agora, dois vértices i e j estão fortemente conectados em um grafo G = (V, A) 
não direcionado, se existem dois caminhos distintos em arestas de i para j em G 
(GOLDBARG; GOLDBARG, 2012).
Vértices Fracamente Conexos
Em um grafo G = (V, A) direcionado, é dito que dois vértices i e j estão fraca-
mente conectados, se existe apenas um caminho direcionado de i para j ou de j 
para i em G (GOLDBARG; GOLDBARG, 2012).
Grafo Fracamente Conexo
Na teoria dos grafos, um grafo G = (V, A) direcionado é dito fracamente co-
nexo quando existe, pelo menos, um par de vértices i e j em G tal que o número 
de caminhos entre i e j seja menor que 1 (GOLDBARG; GOLDBARG, 2012). 
A Figura 7 ilustra dois grafos conexos. O grafo apresentado na Figura 7a é forte-
mente conexo, enquanto o grafo apresentado na Figura 7b é fracamente conexo. 
O grafo da Figura 7b é fracamente conexo porque do vértice 5 não é possível che-
gar a qualquer outro vértice.
Figura 7 – Exemplo de grafos fortemente conexo e fracamente conexo.
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Algoritmo Roy para Encontrar Componentes Conexas
O algoritmo Roy é simples e elegante. Esse algoritmo encontra componentes 
fortemente conexas de um grafo G direcionado através de relações de vizinhança. 
Identifica conjuntos de vértices que possuem sucessores e antecessores comuns. 
A seguir, o algoritmo Roy é apresentado:
12
13
1 - Ler G = (N,M)
2 - i ← 0
3 - V ← N
4 - Enquanto V ≠ ∅ Fazer
5 - Escolher e marcar um vértice qualquer v,v ∈ V, com (+) e (-)
6 - Enquanto for possível marcar com (+) um vértice w não marcado 
com (+) que tenha sucessor um vértice marcado com (+)
7 - Marcar w com (+)
8 - Fim_Enquanto
9 - Enquanto for possível marcar com (-) um vértice w não marcado 
com (-) que tenha como antecessor um vértice marcado com (-)
10 – Marcar w com (-)
11 – Fim_Enquanto
12 – i ← i + 1
13 – Si ← vértices que estão marcados com (+) e (-) simultaneamente 
14 – V ← V \ Si
15 – Desmarcar todos os vértices de v
16 – Fim_Enquanto
Grafos Finitos e Infinitos
Duas definições amplamente utilizadas na teoria dos grafos são as de grafo finito 
e grafo infinito. Um grafo é denominado finito quando possui um número finito de 
vértices e de arestas. Caso o grafo tenha um número infinito de vértices e arestas é 
denominado infinito. O grafo 1 da Figura 8 é finito, já o grafo 2 da mesma Figura é 
infinito, o elemento infinito do grafo 2 é representado por linhas pontilhadas.
Figura 8 – Grafo fi nito e infi nito
Fonte: Acervo do Conteudista
13UNIDADE Planaridade e Conectividade
Planaridade de Grafo
Segundo a literatura, a planaridade de grafos surgiu com Henry Dudeney em 
1913, quem formulou o famoso problema das três casas; neste problema é neces-
sário conectar três casas com três infraestruturas básicas – gás, água e energia –, 
conforme ilustrado na Figura 9. O problema se encontra em realizar estas conexões 
sem que se cruzem.
Figura 9 – Problema das três casas
Fonte: Adaptado de Getty Images
Matematicamente, tal problema pode ser formulado da seguinte maneira: dado 
um grafo K3,3 que é bipartido e completo, gostaríamos de saber se esse grafo pode 
ser desenhado no plano de tal forma que as suas arestas nunca se cruzem.
Depois de entender toda a contextualização da origem da planaridade de gra-
fos, podemos, finalmente, definir um grafo plano. Um grafo G é planar se admite 
uma representação no plano de modo que neste não exista cruzamento de arestas. 
A Figura 10 exemplifica dois grafos planares: 
Figura 10 – Exemplos de grafos planares
Fonte: Acervo do Conteudista
Um grafo planar divide o plano em várias regiões. Uma região é finita se a sua 
área é finita, caso contrário, a região será infinita. A Figura 11 exemplifica dois gra-
fos planos em regiões. O grafo da Figura 11a divide o plano em 4 regiões, enquan-
to o grafo da Figura 11b divide o plano em 10 regiões, sendo a região 10 infinita.
14
15
Figura 11 – Divisão de regiões em grafos planos
Fonte: Acervo do Conteudista
Teorema de Kuratowski
O teorema de Kuratowski diz que um grafo G = (V, A) é planar se e somente 
se G não contiver uma subdivisão K5 ou K3,3. Define uma caracterização de grafos 
planares em termos de um número essencialmente finito de subgrafos proibidos.
A Figura 12a ilustra uma representação do K5, enquanto a Figura 12b uma repre-
sentação do K3,3. Como é possível observar, estes grafos não podem ser planos, 
pois as suas arestas se cruzam.
Figura 12 – Representação do K5 e K3,3
Fonte: Acervo do Conteudista
Coloração
Segundo Goldbarg e Goldbarg (2012), colorir um grafo G = (V, A) é atribuir 
cores aos seus vértices de forma que os vértices adjacentes recebam cores distintas 
– tal procedimento é denominado coloração própria. Colorir um grafo é fácil, uma 
vez que se pode imaginar distribuir uma cor diferente para cada vértice. Todavia, o 
problema da coloração surge quando é necessário colorir o grafo G = (V, A) utili-
zando o menor número possível de cores.
É importante ressaltar que em uma coloração própria todos os vértices adja-
centes do grafo possuem cores diferentes. O menor número de cores que pode 
ser utilizado para coloração própria de um grafo recebe o nome de número cro-
mático. Este número é denotado por X(G).
15
UNIDADE Planaridade e Conectividade
A Figura 13b mostra a coloração do grafo apresentado na Figura 13a. Nesta 
coloração, cada cor diferente é codificada por um número sublinhado:
Figura 13 – Coloração de grafo
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Outro exemplo de coloração pode ser observado na Figura 14. A Figura 14b 
mostra a coloração do grafo apresentado na Figura 14a:
Figura 14 – Coloração de grafo
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Grau de Saturação
Na coloração de um grafo, grau de saturação de um vértice é o número de co-
res diferentes que são associadas aos vértices vizinhos a V. Por exemplo, observe o 
grafo apresentado na Figura 15, no qual os vértices são tingidos com quatro cores 
diferentes. Observemos o vértice v1: o grau de saturação deste vértice é 3, uma vez 
que os seus vizinhos estão coloridos com três cores diferentes (1, 2, 4); enquanto o 
vértice v2 também possui um grau de saturação 3, isto é, os seus três vizinhos são 
tingidos com três cores diferentes.
Figura 15 – Grau de saturação
Fonte: Goldbarg e Goldbarg, 2012
16
17
Coloração Harmoniosa
Na coloração de grafos, uma coloração é denotada harmoniosa quando cada par 
de cores aparece, no máximo, em um par de vértices adjacentes no grafo G.
Encontrar uma coloração harmoniosa em um grafo G é NP-Difícil – a Figura 16 
ilustra uma coloração harmoniosa.
Na coloração harmoniosa, às vezes é importante obter o número cromático 
harmonioso, o qual corresponde ao número mínimo de cores necessário a uma 
coloração harmoniosa em G.
Figura 16 – Coloração harmoniosa
Fonte: Goldbarg e Goldbarg, 2012
Coloração Exata
Uma coloração exata pode ser definida como uma coloração própria em que 
cada par de cores aparece exatamente uma vez em cada par de vértices ad-
jacentes em G – a Figura 17 ilustra uma coloração exata:
Figura 17 – Coloração exata
Fonte: Goldbarg e Goldbarg, 2012
Grafo Crítico, Vértice Crítico e Aresta Crítica
Na coloração, um grafo G é denominado crítico quando a remoção de qualquer 
vértice ou aresta acarreta o decréscimo de seu número cromático.
17
UNIDADE Planaridade e Conectividade
Um grafo G é denominado vértice crítico se X(G) > X(G - v), para qualquer que seja 
o vértice v ∈ G; ao passo que um G é denominado aresta crítica se X(G) > X(G - a) 
para qualquer que seja a aresta a ∈ G – observe a Figura 18:
Figura 18 – Grafo crítico
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
As Figuras 18b e 18e exemplificam as possibilidades de remoção de vértices 
e arestas do grafo apresentado na Figura 18a, confirmando a sua condição de 
grafo crítico.
Coloração Forte
Na coloração, dado um conjunto de partições diferentes – no qual os conjuntos 
não possuem vértices em comum – em vértices de G com cardinalidade k, uma 
coloração forte de G é uma coloração própria em que cada cor aparece exatamente 
uma vez em cada possível partição.
Coloração Fraca
Uma coloração fraca é aquela não própria de G em que cada vértice é adjacente 
a, pelo menos, um vértice de cor diferente.
18
19
Figura 19 – Coloração fraca
Fonte: Goldbarg e Goldbarg, 2012
Número Cromático Forte
Segundo (BOAVENTURA, 2012), o número cromático forte é o número míni-
mo de cores necessárias a uma coloração forte em G.
Coloração de Arestas
Uma coloração de arestas de G é uma atribuição de k cores a tais arestas de 
forma que duas arestas incidentes ao mesmo vértice recebam cores distintas.
Figura 20 – Coloração de arestas
Fonte: Goldbarg e Goldbarg, 2012
Representações de Grafos
Existem duas maneiras padronizadas para representar um grafo G(V,A):
• Listas de adjacências;
• Matriz de adjacência.
Habitualmente, a representação de lista de adjacência é mais utilizada, uma vez 
que fornece um modo compacto de representar grafos esparsos. Grafos esparsos 
são aqueles nos quais |A| é consideravelmente menor que |V|2. A representação 
19
UNIDADE Planaridade e Conectividade
de grafo na forma de matriz de adjacência é mais utilizada quando o grafo é 
denso, ou quando é necessário saber com rapidez se existe uma aresta conectan-
do dois vértices dados. Um grafo denso é aquele onde |A| está próximo de |V|2 
(CORMEN et al., 2002).
Representação de Grafo por Lista de Adjacência
Dado um grafo G = (V,A), a sua representação por lista de adjacência consiste 
em um arranjo adj. de |V| lista, uma para cada vértice em V. Para cada u ∈ V, 
a lista de adjacência Adj|u| possui um ponteiro para todos os vértices V tais que 
existe uma aresta (u,v) ∈ A. Isto é, Adj|u| consiste em todos os vértices adjacentes 
a u em G. Em geral, os vértices em cada lista de adjacências estão armazenados em 
uma ordem arbitrária (CORMEN et al., 2002). 
A Figura 21a apresenta um grafo G = (5,7), ao lado, a Figura 21b apresenta a 
representação deste grafo em forma de listas de adjacências:
Figura 21 – Exemplo de lista de adjacência
Fonte: Adaptado de Cormen e colaboradores, 2002
A representação de grafo na forma de lista de adjacência pode ser perfeitamente 
adaptada para grafos ponderados, isto é, grafos que possuem pesos associados 
em suas arestas. Habitualmente, os pesos são denotados por uma função peso w: 
E → R. Para facilitar, considere G = (V, A) como um grafo ponderado com função 
peso w. O peso w(u,v) da aresta (u,v) ∈ A está simplesmente armazenadocom o 
vértice v na lista de adjacência de (u). A representação de grafo na forma de lista 
de adjacência é bastante robusta nesse aspecto, podendo ser totalmente modificada 
para admitir muitas outras formas de grafos (CORMEN et al., 2002).
A Figura 22 apresenta um exemplo de representação de lista de adjacência para 
um grafo G = (6,8) orientado:
20
21
Figura 22 – Exemplo de lista de adjacência para grafos orientados
Fonte: Adaptado de Cormen e colaboradores, 2002
Em grafos orientados, a soma dos comprimentos de todas as listas de adjacên-
cias é |A|, porque uma aresta da forma (u,v) é representada fazendo-se v aparecer 
em Adj[u]. Já em grafos não orientados, a soma dos comprimentos de todas as 
listas de adjacências é 2|A|, porque se (u,v) é uma aresta não orientada, então u 
aparece na lista de adjacências de v e vice-versa (CORMEN et al., 2002).
Em questão de memória, a representação de grafo na forma de lista de adjacên-
cia exige θ (V+A).
A grande desvantagem da representação na forma de lista de adjacência é que 
não é possível determinar se uma dada aresta está presente no grafo quando se 
procura por v na lista de Adj.[u]. Para contornar essa desvantagem, podemos utili-
zar uma matriz de adjacência cuja representação é apresentada na próxima Seção.
Representação de Grafo por Matriz de Adjacência
A representação de um grafo G = (V, A) na forma de matriz de adjacência con-
siste em uma matriz |V| x |V| A = (aij) tal que:
( )
ij
1 se i, j A
a =
0 em caso contrário
∈  
 
  
Por exemplo, se o vértice 3 possui uma conexão com o vértice 4, isto é, se exis-
tir uma aresta que ligue o vértice 3 ao vértice 4, colocamos 1 no elemento a34 da 
matriz de adjacência.
21
UNIDADE Planaridade e Conectividade
A matriz de adjacência pode ser conceituada como uma matriz na qual os vérti-
ces são representados por linhas e colunas. Se houver uma ligação entre os vérti-
ces, é colocado 1 no seu respectivo elemento; caso não haja uma ligação entre os 
vértices, é colocado 0 em seu respectivo elemento. A Figura 23b ilustra uma matriz 
de adjacência para um grafo G = (5,7):
Figura 23 – Exemplo de matriz de adjacência
Fonte: Adaptado de Cormen e colaboradores, 2002
A matriz de adjacência também pode ser aplicada para grafos orientados. 
A Figura 24b ilustra uma matriz de adjacência de um grafo orientado:
Figura 24 – Exemplo de matriz de adjacência para grafos orientados
Fonte: Adaptado de Cormen e colaboradores, 2002
A representação de um grafo na forma de matriz de adjacência de um consome 
θ (V2) de memória do outro, independentemente da quantidade de arestas no grafo.
Observe a matriz de adjacência apresentada na Figura 24b. Veja a simetria ao 
longo da diagonal principal da matriz. Nesta simetria, a parte superior da diago-
nal principal é igual a parte inferior da diagonal principal. Quando essa simetria 
ocorre, é possível obter a matriz transposta. A transposta de uma matriz A = (aij) 
é definida como a matriz AT = )Tij(a dada por )
T
ij(a = aji. Partindo do princípio que 
em um grafo não orientado, (u,v) e (v,u) representa a mesma aresta, a matriz de 
adjacência A de um grafo não orientado é sua própria transposta: A = Ab. Vale 
ressaltar que dependendo da aplicação, compensa armazenar apenas as entradas 
contidas na diagonal e acima da diagonal da matriz de adjacência, possibilitando 
reduzir quase pela metade a memória necessária para armazenar o grafo.
22
23
Da mesma maneira que a lista de adjacência, a matriz de adjacência também 
pode ser usada no caso de grafos ponderados. Considere o seguinte exemplo, se 
G = (V, A) é um grafo ponderado com função peso de aresta w, o peso w(u,v) da 
aresta (u,v) ∈ A é simplesmente armazenado como a entrada na linha u e na colu-
na v da matriz de adjacência. Caso uma aresta não exista, pode ser armazenado o 
valor null ou 0, como sua entrada de matriz correspondente.
Embora a representação de grafo na forma de lista de adjacência seja assintoti-
camente tão eficiente quanto a representação de matriz adjacência, a simplicidade 
de uma matriz de adjacência pode ser preferível quando os grafos são consideravel-
mente pequenos. É interessante observar também que, se o grafo é não ponderado, 
existe uma vantagem adicional na questão de espaço de armazenamento, sendo 
favorável à representação de matriz de adjacência. A matriz de adjacência utiliza 
menos memória, pelo fato de armazenar apenas um bit (0 ou 1) por entrada.
Importante!
Nesta Unidade estudamos conceitos importantes sobre a teoria dos grafos. Conceitos 
como: conexidade de grafos, grafos finitos e infinitos, planaridade de grafos e o teorema 
de Kuratowski, coloração de grafos e representações de grafos.
O conceito de conexidade é amplamente aplicado na modelagem de problemas utilizan-
do grafos. Um grafo G = (V, A) é dito conexo se existir um caminho entre qualquer par de 
vértices; caso contrário, será desconexo.
Duas definições amplamente utilizadas na teoria dos grafos são as de grafo finito e gra-
fo infinito. Um grafo é denominado finito quando possui um número finito de vértices 
e de arestas. Caso tenha um número infinito de vértices e arestas é denominado infinito.
O conceito de planaridade de grafos permite definir se um grafo é planar ou não – um 
grafo planar é aquele imerso no plano e as suas arestas nunca se cruzam.
A coloração de um grafo consiste em colorir um grafo G = (V, A) utilizando a menor 
quantidade de cores possível. Todavia, um vértice A não pode ser colorido com a mesma 
cor do seu adjacente.
Habitualmente, grafos podem ser representados por duas formas padronizadas, listas 
de adjacências e matriz de adjacências. Tanto a lista de adjacência como a matriz de 
adjacência representam o conjunto de vértices e arestas de um grafo G.
Em Síntese
23
UNIDADE Planaridade e Conectividade
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Livros
Grafos: Teoria, Modelos, Algoritmos
AVENTURA NETTO, P. O. Grafos: teoria, modelos, algoritmos. 5. ed. São Paulo: 
Edgard Blucher, 2012.
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 JÚNIOR, E. R. Fundamentos da teoria dos grafos 
para computação. São Carlos, SP: Edufscar, 2006.
 Leitura
Matemática Discreta: Combinatória, Teoria dos Grafos e Algoritmos
CARDOSO, M.; SZYMANSKI, J.; ROSTAMI, M. Matemática discreta: combinatória, 
teoria dos grafos e algoritmos. [S.l.]: Escolar, 2009
https://bit.ly/2KON8LQ
24
25
Referências
BOAVENTURA NETTO, P. O. Grafos: teoria, modelos, algoritmos. 2. ed. São 
Paulo: Edgard 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. 2018. Disponível em: <http://www.ime.usp.br/~pf/
teoriadosgrafos>. Acesso em: 24 nov. 2018.
FURTADO, A. L. Teoria dos grafos algoritmos. Rio de Janeiro: Livros Técnicos 
e Científicos, 1973.
GOLDBARG, M.; GOLDBARG, E. Grafos – conceitos, algoritmos e aplicações. 
[S.l.]: Campus, 2012.
HOLANDA, B. Teoria dos grafos. 2011. Disponível em: <https://www.obm.org.
br/content/uploads/2017/01/Nivel1_grafos_bruno.pdf>. Acesso em: 28 nov. 2018.
NICOLETTI, A. M.; HRUSCHKA JÚNIOR, 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.
TEORIA dos grafos. [20--a]. Disponível em: <https://miltonborba.org/Algf/Gra-
fos.htm#Def_basicas>. Acesso em: 28 nov. 2018.
TEORIA dos grafos – aula 2. 20--b]. Disponível em: <http://www.riopomba.if-
sudestemg.edu.br/dcc/dcc/materiais/1469415723_Teoria%20dos%20Grafos%20-
-%20aula2.pdf>. Acesso em: 28 nov. 2018.
25
Teoria dosGrafos
Material Teórico
Responsável pelo Conteúdo:
Prof. Dr. Cleber Silva Ferreira da Luz
Revisão Textual:
Prof. Me. Luciano Vieira Francisco
Algoritmos de Busca em Grafos
• Introdução;
• Busca em Grafos.
• Conhecer todos os principais conceitos de busca em grafos.
OBJETIVO DE APRENDIZADO
Algoritmos de Busca em Grafos
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: 
Assim:
Organize seus estudos de maneira que passem a fazer parte 
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.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
Não se esqueça 
de se alimentar 
e de se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Algoritmos de Busca em Grafos
Introdução
Técnicas de busca em grafos são utilizadas em diversas modelagens utilizando 
grafos. Em inúmeros problemas há necessidade de visitar os vértices do grafo. 
Diferentes algoritmos de busca em grafos foram propostos ao longo dos anos, de 
modo que nesta Unidade estudaremos os principais algoritmos de busca em grafos, 
a saber; busca em profundidade e busca em largura.
O algoritmo de busca em profundidade realiza a procura em grafo G; começa no 
vértice raiz e explora tanto quanto possível cada um de seus ramos. Já o algoritmo 
de busca em largura também começa a procura por um vértice raiz e explora todos 
os seus vizinhos. Assim, começaremos a estudar um algoritmo genérico de busca. 
Busca em Grafos
Algoritmos de busca em grafos são utilizados para solucionar diversos proble-
mas. O seguinte Quadro apresenta um algoritmo para uma busca genérica:
Quadro 1
Ler G = (N, M)
Escolher e marcar um vértice i
Enquanto existir j Є N marcado com uma aresta (j, k) não explorado Fazer
 Escolher o vértice j e explorar a aresta (j, k)
 // condição variável em conformidade com o tipo de busca //
 Se k é não marcado então marcar k
Fim_do_Enquanto
Fonte: Acervo do conteudista
Um exemplo de aplicação que utiliza busca em grafos é dado no problema de 
encontrar a saída em um labirinto. Observe, na Figura 1a, um simples labirin-
to. O problema consiste em encontrar uma saída para o qual. É possível mode-
lar este problema com grafos e encontrar uma saída utilizando busca em grafo 
(GOLDBARG; GOLDBARG, 2012). 
Já a Figura 1b ilustra o começo do processo de modelagem. Primeiro, são colo-
cados círculos margeando todas as paredes do labirinto. Estes círculos representam 
vértices dos grafos e são pontos de mudanças de direção no caminho do labirinto. 
8
9
Entrada
Saída
Entrada
Saída
a) Labirinto b) Pontos de mudança de direção
Figura 1 – Transformação de um labirinto em um grafo
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Nesta modelagem, as arestas mostram a possibilidade de movimento no labirin-
to. A Figura 2a ilustra as arestas e os vértices representados dentro do labirinto; já 
a Figura 2b apresenta o grafo modelado no labirinto:
Entrada
Saída
Entrada
Saída
a) Grafo no labirinto b) Grafo do labirinto
Figura 2 – Grafo do labirinto
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Para encontrar a saída do labirinto é necessário percorrer os diversos caminhos 
possíveis. A forma mais simples de encontrar a saída do labirinto sem nunca percor-
rer mais de uma vez uma mesma parede consiste em rotular as arestas percorridas 
na busca, de modo a nunca transitar uma aresta anteriormente rotulada. A busca 
começa pela entrada do labirinto, isto é, pelo vértice que representa a entrada no 
labirinto, continuando até que o vértice que representa a saída seja alcançado.
As figuras 3a e 3b ilustram duas possíveis sequências de visita no grafo quando 
aplicado o algoritmo da busca genérica: o caminho exemplificado na Figura 3a 
consiste na visita ao vértice 1, caminhando depois pelas arestas (1,2), (2,3), (3,4), 
(4,5), (5,6), (6,7), (7,8), neste momento, o ciclo se fecha sobre o vértice 4 e pela 
aresta (8,4), continuando, são percorridas as arestas (4,9), (9,10), (10,11), (11, 12), 
9
UNIDADE Algoritmos de Busca em Grafos
(12,13) e, por fim, pela aresta (13,14). A Figura 3b apresenta uma busca mais efi-
ciente, inicialmente visitando o vértice 1 e percorrendo as arestas (1,2), (2,3), (3,4), 
(4,5), (5,6), (6,7), (7,8), chegando ao vértice 8, ou seja, à saída do labirinto.
a) Busca 1
14
1 12 2
3
34
49
11
10
12
13
5
5
8
8
6
6
7
7
b) Busca 2
Figura 3 – Busca no grafo do labirinto
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Diversos algoritmos são construídos com base no algoritmo genérico. Esses 
algoritmos variam o critério de avaliação dos vértices e das arestas. Assim, um 
algoritmo muito eficiente e elegante é conhecido como algoritmo de busca em 
profundidade – sobre o qual estudaremos na próxima seção.
Busca em Profundidade
A técnica de busca em profundidade tem se mostrado útil no desenvolvimento 
de algoritmos eficientes que resolvem problemas, tal como encontrar componentes 
fortemente conexos de um grafo (CORMEN et al., 2002).
O algoritmo conhecido como Busca em Profundidade (BP) é desenvolvido so-
bre um algoritmo genérico; todavia, a seleção de vértice é realizada sobre o vértice 
não marcado mais recentemente alcançado na busca – os passos que a BP realiza 
são apresentados a seguir:
Quadro 2
Procedimento BP(v)
marcar v
Enquanto existir w Є Γ(V) fazer
 Se w é não marcado
 explorar (v, w)
 marca w
 BP(w)
 Senão
 Se (v,w) não explorada
 explorar(v,w)
Fim_Enquanto
Fonte: Acervo do conteudista
10
11
Importante!
Note que esse procedimento é recursivo, considerando um grafo conexo e não direcional 
(GOLDBARG; GOLDBARG, 2012).
Importante!
Aplicando o procedimento de busca em 
profundidade em um grafo G a partir de um 
vértice v qualquer, os vértices marcados e as 
arestas exploradas em consequência da satis-
fação da condição do primeiro “se” compõem 
uma subárvore de G, denominada árvore de 
profundidade de G – as demais são denomi-
nadas arestas de retorno.
Analisaremos a busca em profundidade 
por meio de um exemplo; para isso, consi-
dere o grafo apresentado na Figura 4:
1
2
3
4
5
6 7
Figura 4 – Exemplo de grafo 
para a busca em profundidade
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Aplicaremos o algoritmo da busca em profundidade no grafo apresentado (Figu-
ra 4), partindo do vértice 1. As figuras 5a a 5f ilustram a aplicação do procedimento 
da busca em profundidade: 
1
1
2
2
3
1
2
3
a) Aresta (1, 2) b) Aresta (2, 3) c) Aresta (3, 1)
d) Aresta (3, 4) e) Aresta (4, 5) f) Aresta (5, 3)
1
2
3
1
2
3
4
4
5
4
5
1
2
3
Figura 5 – Buscaem profundidade
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
11
UNIDADE Algoritmos de Busca em Grafos
Considere que o grafo da Figura 4 está representado na forma de uma lista de 
adjacências, onde os vértices de cada lista encadeada estão ordenados. O inicial 
(Vértice 1) é a raiz da árvore de profundidade.
A busca começa no Vértice 1, logo após é verificado o Vértice 2. Como o Vér-
tice 2 é não marcado, então é realizada uma chamada recursiva do procedimento 
BP, passando esse vértice como parâmetro de entrada. Neste momento, a chama-
da do procedimento BP(1) fica interrompida, esperando a volta da chamada BP(2) 
para ser completada. Durante o processamento de BP(2) é verificado que no Vér-
tice 1 é marcado e que a aresta (1, 2) já foi explorada. Portanto, prossegue-se para 
o segundo vizinho do Vértice 2, o nó 3. Assim, a aresta (2, 3) é incluída na árvore, 
tal como exemplificado na Figura 5b e o procedimento BP(3) é, então, iniciado. A 
lista de adjacências do Vértice 3 é composta pelos vértices 1, 2, 4, 5, 6 e 7. A aresta 
(3, 1), ou (1, 3), é não explorada, entretanto, o Vértice 1 é marcado. A aresta (3, 1) 
não é incluída na árvore de profundidade, uma vez que é uma aresta de retorno, 
conforme ilustrado na Figura 5c – em que a aresta de retorno é representada por 
uma linha pontilhada. 
Já a aresta (3, 2) é explorada e a (3, 4) é incluída na árvore, conforme ilustrado 
na Figura 5d. Assim, uma chamada ao procedimento BP(4) e a aresta (4, 5) é inclu-
ída na árvore, condição ilustrada na Figura 5e.
O procedimento BP(5) é iniciado. O Vértice 3 é marcado, mas a aresta (3, 5) 
ainda não é explorada. Dessa forma, a aresta de retorno (5, 3) ou (3, 5) é explorada, 
conforme ilustrado na Figura 5f. A verificação do Vértice 5 termina e o procedi-
mento BP(5) é encerrado. No processamento do Vértice 4 também não existem 
outros adjacentes ao vértice, terminando, também, o procedimento BP(4).
Assim, retorna-se ao procedimento BP(3). A aresta (3, 5) já está explorada. 
Logo, o próximo vizinho do Vértice 3 a ser examinado é o Vértice 6. A aresta (3, 
6) é incluída na árvore e uma chamada para BP(6) é realizada. O Vértice 6 não tem 
outros vizinhos além do Vértice 3, o procedimento BP(6) é finalizado – isso também 
ocorre na verificação do Vértice 7. 
As figuras 6a e 6b ilustram as inclusões das arestas (3, 6) e (3, 7), respectivamen-
te, durante a verificação do Vértice 3; já a Figura 6c apresenta a árvore de profundi-
dade construída pelo algoritmo de busca de profundidade para o grafo apresentado 
na Figura 4, iniciando pelo Vértice 1. 
12
13
3
1
2
3
1
2
3
4
5
4
5
6 6
1
2
4
5
6
7 7
a) Aresta (3,6) b) Aresta (3,7) c) Árvore de profundidade
Figura 6 – Busca em profundidade em grafo não direcionado
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
No caso do grafo desconexo, o procedimento BP deve ser chamado novamente 
enquanto existir vértice não marcado no grafo. Dessa forma, em vez de uma árvore 
de profundidade, o algoritmo construirá uma floresta de profundidade.
O algoritmo de profundidade possui complexidade de O(n+m).
Algoritmo de Busca em Profundidade em Grafos Orientados 
Analisaremos o algoritmo de busca em profundidade em grafos orientados, sen-
do essencialmente o mesmo para grafos não orientados; contudo, uma diferença 
é que mesmo se o grafo for conexo, o algoritmo de busca pode gerar uma floresta 
de profundidade. Em grafos orientados, o algoritmo de busca é chamado enquanto 
ainda existir algum vértice não marcado. A seguir, veremos como a busca é realiza-
da para grafos orientados (GOLDBARG; GOLDBARG, 2012):
Quadro 3
Procedimento BP Dir
Ler G = (N, M)
Enquanto existir v Є N, v não marcado Fazer
 BP(v)
Fim_Equanto
Fonte: Acervo do conteudista
13
UNIDADE Algoritmos de Busca em Grafos
Em grafos orientados, as arestas são particionadas em quatro conjuntos, em vez 
de dois – como acontece nos grafos não orientados. O primeiro conjunto contém 
as arestas onde o vértice destino ainda não foi marcado. Tais arestas participam da 
árvore de profundidade que será construída pelo algoritmo. Considere o Vértice w 
e que o destino da aresta seja marcado, então, com uma das três situações a seguir, 
denotando o conjunto do qual a aresta participa:
1. Caso w seja descendente de v na floresta, então a aresta será denomi-
nada avanço;
2. Caso v seja descendente de w na floresta, então a aresta será denomi-
nada retorno;
3. Caso v não seja descendente de w e nem w seja descendente de v na flo-
resta, então a aresta será denominada cruzamento.
Aplicaremos o algoritmo de busca em profundidade em um grafo orientado; 
para isto, considere o grafo apresentado na Figura 7:
3
1 4
2
6
5
Figura 7 – Busca em profundidade em grafo direcionado (1)
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
As figuras 8a a 8f mostram a aplicação do algoritmo de busca em profundidade 
em um grafo orientado:
3
3
1 1
1
2
2
2
6
3
6
6
1
2
3
6
1
2
3
Arco de
retorno
Arco de
cruzamento
Arco de
avanço
1
2
4
a) Arco (1, 2) b) Arco (2, 3) c) Arco (3, 6)
d) Aresta (3, 4) e) Aresta (4, 5) f) Aresta (5, 3)
14
15
3
3
1 1
1
2
2
2
6
3
6
6
1
2
3
6
1
2
3
Arco de
retorno
Arco de
cruzamento
Arco de
avanço
1
2
4
a) Arco (1, 2) b) Arco (2, 3) c) Arco (3, 6)
d) Aresta (3, 4) e) Aresta (4, 5) f) Aresta (5, 3)
Figura 8 – Busca em profundidade em grafo direcionado (2)
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
Note que a busca começa pelo Vértice 1. Conforme ilustrado nas Figuras 8a a 
8c, o algoritmo procede incluindo os arcos (1, 2), (2, 3) e (3, 6), respectivamente.
Na verificação do Vértice 6 encontra-se o arco (6, 2). É verificado que o Vértice 
2 já é marcado e o Vértice 6 é o seu descendente na árvore. Dessa forma, o arco 
(6, 2) é classificado como de retorno, conforme ilustrado na Figura 8d. Os procedi-
mentos para os vértices 6, 3 e 2 são encerrados e a busca volta ao Vértice 1.
Agora, o arco (1, 3) é explorado. Devido ao fato de o Vértice 3 já estar na árvore 
e ser descendente de 1, então, o arco (1, 3) será reconhecido como de avanço, 
conforme ilustrado na Figura 8e. Assim, a chamada do procedimento de busca ao 
Vértice 1 se encerra, tendo construído uma primeira árvore – composta pelos arcos 
(1, 2), (2, 3) e (3, 6).
Todavia, os vértices 4 e 5 permanecem não marcados. Assim, uma nova chama-
da de procedimento de busca em profundidade é realizada ao Vértice 4. O primeiro 
arco explorado é o (4, 3). O Vértice 3 já está marcado. Como nem o Vértice 3 des-
cende de 4, como também 4 não descende de 3, então o arco (4, 3) é classificado 
como de cruzamento (GOLDBARG; GOLDBARG, 2012). 
Agora, os arcos (4, 5) e (5, 3) são considerados pela busca, procedimento ilustra-
do nas figuras 9a e 9b; já a Figura 9c apresenta a floresta de profundidade do grafo:
a) Arco (4, 5)
3
6
1
2
b) Arco (5,3)
4
5
3
6
1
2 4
5
3
6
1
2
c) Floresta de profundidade
Figura 9 – Busca em profundidade em grafo direcionado (3)
Fonte: Adaptada de Goldbarg e Goldbarg, 2012
15
UNIDADE Algoritmos de Busca em Grafos
A complexidade do algoritmo de busca em profundidade é de O(n+m). 
Busca em Largura
Busca em largura é outro algoritmo baseado no de busca genérico. Neste al-
goritmo de busca, a seleção do vértice é realizada sobre os vértices não marcados 
menos recentemente alcançados na busca. A seguir é apresentado o pseudocódigo 
da busca em largura (GOLDBARG; GOLDBARG, 2012). 
Quadro 4
Procedimento BL(G=(N,M))
definir uma fila Q vazia
escolher um vértice inicial v
marcar v
insere v em Q
Enquanto Q ≠ Ø Fazer
 v ← remove elemento de Q
 Para todo w Є Γ(v) Fazer
 Se w é não marcado
 explorar (v, w)
 insere w em Q
 marcar w
 Senão
 Se (v, w) não explorada
 explorar (v, w)
 Fim_Se
 Fim_para
Fim_enquanto
Fonte: Acervo do conteudista
Aplicaremos o algoritmo da busca em largura no grafo apresentado na Figura 10 e 
que é o mesmo grafo utilizado em exemplos anteriores. Consideraremos novamente 
que o grafo está representado através de umalista de adjacência cujos nós – de cada 
lista encadeada – estão ordenados. A busca é iniciada por meio do Vértice 1, enquan-
to que o vértice inicial é a raiz da árvore de profundidade.
16
17
1
2
3
4
5
6 7
Figura 10 – Busca em largura em grafo não direcionado (1)
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
A aplicação do algoritmo de busca em largura é ilustrada nas figuras 11a a 11h. 
Como a busca começa pelo Vértice 1, este é marcado e colocado em Q e logo em 
seguida removido de Q. O Vértice 1 possui como vértices adjacentes os de núme-
ros 2 e 3. O Vértice 2 não é marcado, assim, a aresta (1, 2) é incluída na árvore, 
o Vértice é marcado e incluído em Q, conforme ilustrado na Figura 11b; o mesmo 
ocorre com o Vértice 3, ilustrado na Figura 11c. O Vértice 2, na frente da fila Q, é 
removido e a aresta (2, 3) é explorada, assim como na Figura 11d. Já as figuras 11e 
a 11h ilustram as inclusões dos vértices 4, 5 e 7, respectivamente, na árvore de bus-
ca em largura e na fila Q. Depois que o Vértice 4 é removido da fila, a aresta (4, 5) 
é explorada, conforme ilustrado na Figura 11i. A execução do algoritmo continua 
e os vértices restantes são retidos da fila até que Q esteja vazia. 
3
1
1
2 3
1
2
1
2
4
3
1
2
4 5
3
1
2
4
5 6
3
1
2
4
1
2
5 6
7
3
Q = (1)
a) Inclusão de 1
Q = (2)
b) Aresta de (1, 2)
Q = (2, 3)
c) Aresta de (1, 3)
Q = (3)
d) Aresta de (2, 3)
Q = (4)
e) Aresta de (3, 4)
Q = (4,5)
f) Aresta de (3, 5)
4
55 6
7
3
1
2
Q = (4, 5, 6, 7)
h) Aresta de (3, 7)
Q = (4, 5, 6)
g) Aresta de (3, 6)
Q = (5, 6, 7)
i) Aresta de (4, 5)
17
UNIDADE Algoritmos de Busca em Grafos
3
1
1
2 3
1
2
1
2
4
3
1
2
4 5
3
1
2
4
5 6
3
1
2
4
1
2
5 6
7
3
Q = (1)
a) Inclusão de 1
Q = (2)
b) Aresta de (1, 2)
Q = (2, 3)
c) Aresta de (1, 3)
Q = (3)
d) Aresta de (2, 3)
Q = (4)
e) Aresta de (3, 4)
Q = (4,5)
f) Aresta de (3, 5)
4
55 6
7
3
1
2
Q = (4, 5, 6, 7)
h) Aresta de (3, 7)
Q = (4, 5, 6)
g) Aresta de (3, 6)
Q = (5, 6, 7)
i) Aresta de (4, 5)
Figura 11 – Busca em largura em grafo não direcionado
Fonte: Adaptada de Goldbarg e Goldbarg, 2012
A busca em largura possui complexidade de O(n+m)
Importante!
Algoritmos de busca em grafos são utilizados para solucionar diversos problemas mode-
lados por grafos.
Existem diversos algoritmos de busca em grafos, entre os quais o de busca em profundi-
dade e de busca em largura, sendo ambos simples e eficientes.
A busca em profundidade é um algoritmo que percorre os vértices do grafo com o ob-
jetivo de chegar a um determinado vértice. A principal característica desse algoritmo é 
percorrer todos os nós filhos de um nó pai.
A busca em largura também percorre os vértices do grafo, objetivando chegar a um 
vértice específico. Todavia, a técnica implementada na busca em largura é diferente da 
operada em profundidade, afinal, a busca em largura visita todos os vértices vizinhos. 
Em Síntese
18
19
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
CARDOSO, M.; SZYMANSKI, J.; ROSTAMI, M. Matemática discreta: combinatória, 
teoria dos grafos e algoritmos. [S.l.]: Escolar, 2009.
https://tinyurl.com/y6oek99n
19
UNIDADE Algoritmos de Busca em Grafos
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: <http://www.ime.usp.br/~pf/
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
Teoria dos Grafos
Material Teórico
Responsável pelo Conteúdo:
Prof. Dr. Cleber Silva Ferreira da Luz
Revisão Textual:
Prof. Me. Luciano Vieira Francisco
Caminhos em Grafos
• Introdução;
• Caminhos em Grafos.
• Conhecer todos os conceitos de caminhos em grafos, bem como os principais algoritmos 
para obter caminhos em grafos.
OBJETIVO DE APRENDIZADO
Caminhos em Grafos
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: 
Assim:
Organize seus estudos de maneira que passem a fazer parte 
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.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
Não se esqueça 
de se alimentar 
e de se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Caminhos em Grafos
Introdução
Nesta Unidade estudaremos o conceito de caminho, que é importante em gra-
fos. Dado um grafo G, podemos compreender caminho como uma sequência de 
vértices conectados por uma sequência de arestas. Esta conexão permite sair do 
vértice v e chegar a um vértice w.
O conceito de caminho é importante para resolver diversos problemas tidos como 
modelos por meio dos grafos – um dos quais é o problema para encontrar o menor 
caminho entre um vértice v e um vértice w. Este problema aparece em diversas apli-
cações, tais como encontrar uma rota com o menor caminho percorrido em uma 
cidade, encontrar um menor caminho para conectar um computador ao outro, 
entre outros. Serão abordados todos os aspectos que envolvem caminhos em grafos.
Caminhos em Grafos
Um caminho pode ser definido como uma sequência de vértices tal que para 
cada vértice da sequência há uma aresta para o próximo vértice da sequência 
(CORMEN et al., 2002). Formalmente, um caminho pode ser denotado como:
C(VE) = {< V1, V2... Vk,> | <Vi, Vi + 1>, ∈ E, 1 ≤ i < K}
Em diversas aplicações envolvendo grafos, muitas vezes é necessárioobter me-
nor caminho entre os vértices v e w. As próximas seções abordarão o problema 
para encontrar o menor caminho, dado um par de vértices em um grafo G.
Caminho Mais Curto em Grafos Não Ponderados
Segundo Goldbarg e Goldbarg (2012), o caminho mais curto entre dois vértices 
v e w de um grafo G não ponderado é aquele que acumula a menor quantidade de 
arestas entre v e w. Analisaremos um exemplo: A Figura 1a apresenta um grafo, 
de modo que obteremos um caminho entre os vértices v e w; a Figura 1b apresenta 
o menor caminho possível entre os vértices v e w.
Figura 1 – Caminho mais curto em grafos não ponderados
Fonte: adaptada de Goldbarg e Goldbarg (2012)
8
9
Caminho Mais Curto em Grafos Ponderados
Em grafos ponderados, o caminho mais curto entre dois vértices v e w de um grafo G 
é o caminho cuja soma dos pesos das arestas possui o menor valor possível entre to-
dos os caminhos entre v e w (GOLDBARG; GOLDBARG, 2012). A Figura 2b apresenta 
o menor caminho possível entre os vértices v e w do grafo apresentado na Figura 2a:
Figura 2 – Caminho mais curto em grafos ponderados
Fonte: adaptada de Goldbarg e Goldbarg (2012)
Caminho Mais Longo em Grafos
Dado um grafo G ponderado, o caminho mais longo que existe em G é o que 
acumula o maior valor possível entre todos os caminhos cabíveis entre v e w. Em 
um grafo não ponderado, o caminho mais longo é aquele que percorre o maior 
número de arestas entre v e w (GOLDBARG; GOLDBARG, 2012). Considerando 
o grafo não ponderado apresentado na Figura 1a, a Figura 3a ilustra o maior cami-
nho deste grafo; já a Figura 3b apresenta o maior caminho para o grafo ponderado:
Figura 3 – Caminho mais longo em grafos
Fonte: Adaptada de Goldbarg e Goldbarg (2012)
Caminho Mais Curto com Custo nos Vértices
Dado dois vértices v e w em um grafo G ponderado em vértices, o caminho mais 
curto entre v e w é aquele cuja soma dos pesos das arestas e dos vértices possui o 
menor valor possível entre os demais caminhos entre v e w (GOLDBARG; GOLD-
9
UNIDADE Caminhos em Grafos
BARG, 2012). Analisaremos um exemplo: a Figura 4a apresenta um grafo G ponde-
rado; já a Figura 4b apresenta o caminho mais curto entre v e w. No processamento 
para achar o caminho mais curto, sempre que um vértice é incluído no caminho, o 
custo de seu vértice é adicionado ao custo do caminho.
Figura 4 – Caminho mais curto com custos nos vértices
Fonte: Adaptada de Goldbarg e Goldbarg (2012)
Algoritmo de Dijkstra
Existem diversos algoritmos para achar o caminho mais curto entre dois vértices em um 
grafo. Em 1959, o cientista da computação Edsger Dijkstra propôs um algoritmo eficiente 
para obter o caminho mais curto em um grafo. A técnica utilizada por este algoritmo con-
siste em selecionar o vértice de menor potencial (CORMEN et al., 2002; GOLDBARG; 
GOLDBARG, 2012). Ademais, este algoritmo possui complexidade de o(n2).
Ler G = (N, M) e D = [dij], onde dij é o custo da aresta (i, j)
dt[1] ← 0
rot[1] ← ∞
Para i ← 2 ate n Faça
 dt[i] ← ∞
 rot[i] ← 0
A ← {N}
F ← ∅
Enquanto F ≠ N Faça
 r ← j ∈ A, tal que dt[j] é mínimo entre os elementos de A
 F ← F U {r}
 A ← A \ {r}
10
11
 V ← V \ F
 Para i ∈ V Faça
 p ← min{dt[i], (dt[r]+ dri)}
 Se p < dt[i]
 dt[i] ← p
 rot[i] ← r
 Fim_Se
 Fim_Para
 Fim_enquanto
O algoritmo de Dijkstra utiliza duas listas de vértices: a lista dos nós fechados (F) 
e a lista dos nós abertos (A). Um vértice está na lista F se o caminho mínimo da 
origem até aquele vértice já é conhecido, se não for, o vértice se encontra na lista A. 
O algoritmo possui dois vetores, um vetor denominado dt e outro denominado rot. 
Este algoritmo, o i-ésimo elemento do vetor dt guarda a distância calculada pelo al-
goritmo entre o vértice origem e o vértice i. Por sua vez, o i-ésimo elemento guarda 
o vértice anterior ao vértice i no caminho entre a origem e o vértice i, segundo a 
distância calculada (GOLDBARG; GOLDBARG, 2012).
No início é atribuído o valor zero para dt[1], que corresponde à distância do 
vértice 1 a esse mesmo, e atribuído o infinito para rot[1]. Para os demais vértices 
do grafo é atribuído infinito em dt e zero para o rot dos demais vértices. A lista de 
nós abertos (A) recebe N e a lista fechada permanece vazia. O algoritmo itera até 
que todos os vértices tenham sido incluídos na lista F. A cada iteração, o algoritmo 
escolhe e remove um vértice de A.
O vértice r escolhido é aquele que tiver o menor valor de dt[r]. Depois de esco-
lhido o vértice r, é incluído na lista F e todos os seus vizinhos que não estão em F 
são verificados. Estes vértices formam o conjunto V, descrito no algoritmo anterior. 
Para cada vértice i de V é verificado se a distância da origem até o qual é maior que 
a distância da origem até r mais o valor da aresta dri. Se sim, o caminho da origem 
até o vértice i passado pelo vértice r é menor do que o caminho anteriormente 
encontrado entre a origem e i. Neste caso, o valor dt[i] é atualizado com dt[r] + dri 
e rot[i] é atualizado com r, indicando que o vértice anterior a i no caminho entre a 
origem e i é o vértice r (GOLDBARG; GOLDBARG, 2012).
Em uma primeira impressão o algoritmo de Dijkstra pode parecer complexo; toda-
via, é simples e eficiente. Analisaremos um exemplo prático: considere o grafo apresen-
tado na Figura 5a; deseja-se obter o caminho mais curto entre os vértices a e j. A Figu-
ra 5b apresenta o grafo rotulado que caracteriza a iniciação da execução do algoritmo:
11
UNIDADE Caminhos em Grafos
Figura 5 – Rotulação do algoritmo de Dijkstra
Fonte: adaptada de Goldbarg e Goldbarg (2012)
Na Figura 5b é possível observar que para cada vértice w existe um rótulo com dois 
valores, sendo rot[w] o primeiro valor, e o segundo correspondendo ao valor do dt[w]. 
Na inicialização, os vértices do grafo, com exceção de a, recebem a primeira posição 
do rótulo rot[w] = 0, e valor ∞ para a segunda posição, representando que dt[w] ainda 
não foi calculado ou não existe. Dessa forma, o vértice a possui rot[0] = 0 e dt[0] = a.
O próximo passo é analisar os vértices adjacentes de a (Figura 6). Neste passo, os 
valores de dt e rot dos vértices b, c e d são revistos. É importante observar que estes 
vértices (b, c, d) são alcançados pelo vértice de origem (a). Os valores dos rótulos destes 
vértices são atualizados de modo a expressar a distância acumulada recém-calculada. 
Dessa forma, o caminho que chega até o vértice b recebe a marca de sua origem, rot[b] 
= a, e também o valor do dt[b] = 60, correspondendo à aresta (a, b). Os vértices c e d 
também são atualizados. Agora, tem-se: F = {a} e A = {b, c, d, e, f, g, h, i, e}.
Figura 6 – Verificação do vértice a
Fonte: adaptada de Goldbarg e Goldbarg (2012)
Na próxima iteração, um dos vértices de A é escolhido. A opção pelos vértices 
segue a forma gulosa do algoritmo de Dijkstra. Assim, o vértice a ser verificado em 
cada iteração é aquele que acumula o menor valor relativo à distância entre esse e 
o vértice de origem. Em nosso exemplo, o próximo vértice a ser verificado é o d. 
12
13
Os vértices adjacentes a d são b, c, e e f – e estão em A. Os rótulos dos vértices b 
e c não são alterados porque a inclusão do vértice d no caminho da origem a cada 
um dos quais não produz um caminho menor do que o anteriormente existente. 
Agora, os vértices e e f têm os seus rótulos alterados porque existem caminhos com 
os custos de 68 e 92, respectivamente – a Figura 7 ilustra a verificação do vértice d:
Figura 7 – Verifi cação do vértice d
Fonte: adaptada de Goldbarg e Goldbarg (2012)
No processamento do nosso grafo de exemplo, o próximo vértice a ser verifica-
do é o c. Este vértice acumula 54 em seu rótulo. Neste momento, o único vértice 
adjacente a c que está em A é o e. Pela verificação do vértice c, a rotulação de e 
não é alterada – a Figura 8 ilustra a verificação do vértice c:
Figura 8 – Verifi cação do vértice c
Fonte: adaptada de Goldbarg e Goldbarg (2012)
Na próxima iteração do algoritmo o vértice b é selecionado. O único vérticead-
jacente a b que não está em F é o vértice f. O rótulo de f é atualizado porque existe 
um caminho de a até f passando por b com valor menor – a verificação do vértice b 
é representada na Figura 9:
13
UNIDADE Caminhos em Grafos
Figura 9 – Verificação do vértice b
Fonte: adaptada de Goldbarg e Goldbarg (2012)
A verificação continua nos demais vértices. Agora pelo vértice e:
Figura 10 – Verificação do vértice “e”
Fonte: adaptada de Goldbarg e Goldbarg (2012)
Verificação do vértice f:
Figura 11 – Verificação do vértice f
Fonte: adaptada de Goldbarg e Goldbarg (2012)
14
15
Verificação do vértice g:
Figura 12 – Verifi cação do vértice g
Fonte: adaptada de Goldbarg e Goldbarg (2012)
Verificação do vértice h:
Figura 13 – Verifi cação do vértice h
Fonte: adaptada de Goldbarg e Goldbarg (2012)
Verificação do vértice j:
Figura 14 – Verifi cação do vértice j
Fonte: adaptada de Goldbarg e Goldbarg (2012)
15
UNIDADE Caminhos em Grafos
O caminho mais curto de a até j é apresentado na Figura 15:
Figura 15 – Caminho mais curto de a até j
Fonte: adaptada de Goldbarg e Goldbarg (2012)
Algoritmo de Ford-Moore-Bellman
Assim como o algoritmo de Dijkstra, o algoritmo de Ford-Moore-Bellman obtém 
o menor caminho entre dois vértices v e w em um grafo G. Contudo, diferentemen-
te do de Dijkstra, este algoritmo abre mão da possibilidade de fechar um vértice a 
cada iteração e se obriga a verificar todos os vértices até que melhorias não sejam 
mais possíveis. Utilizando essa estratégia, o algoritmo consegue calcular o caminho 
mais curto em grafos que contêm arestas negativas. A ideia principal desse algorit-
mo é que um caminho s para j com k + 1 arestas pode ser obtido de um caminho 
de s para j com k arestas. Em tal algoritmo, o critério de parada está baseado no 
fato de que, se em alguma iteração todos os rótulos dos vértices não foram altera-
dos, não há melhorias nas próximas iterações (GOLDBARG; GOLDBARG, 2012).
Ler G = (N, M) e D = [dij]
dt[1] ← 0
rot[1] ← 0
 Para i ← 2 até n Faça 
 dt[i] ← d1i
 Se ∃ (1, i) ∈ M
 rot[i] = 1
 senão 
 rot[i] ← 0
 dt[i] ← ∞
 Fim_Para
16
17
 Para k ← 1 até n-1 Faça
 altera ← ‘Falso’
 Para i ← 2 até n Faça
 V ← -- (1)
 Para j ∈ V Faça
 Se dt[i] > dt[j] + dji
 dt[i] ← dt[j] + dji 
 rot[i] ← j
 altera ← ‘Verdadeiro’
 Fim_se
 Fim_Para
 Fim_Para
 Fim_Para
Passeio em Grafos
Dado um grafo G, um passeio consiste de uma sequência finita alternada de 
vértices e arestas, que começa e termina por vértices tal que cada aresta é incidente 
ao vértice que a precede e ao que a sucede.
Grafos Hamiltonianos
De uma forma bem simples, podemos definir um grafo como hamiltoniano se 
neste existir um caminho que contém todos os vértices de G. Podemos compreen-
der, também, que um ciclo hamiltoniano é aquele que contém todos os vértices do 
grafo exatamente uma vez, com exceção dos vértices inicial e final – a Figura 16 
ilustra um grafo hamiltoniano:
 
Figura 16 – Grafo hamiltoniano
Fonte: elaborada pelo professor conteudista
17
UNIDADE Caminhos em Grafos
Na literatura existe um problema bem conhecido e que é modelado por grafos ha-
miltonianos, trata-se do problema do caixeiro viajante, no qual há um vendedor 
que necessita ir a diversas cidades; todavia, deseja achar um caminho que passará 
por todas essas localidades, mas que nunca passe duas vezes por uma mesma cidade.
Grafos Eulerianos
Um grafo é denominado euleriano se prover um ciclo que passe por todas as 
arestas de G sem repetição. Ou seja, um ciclo euleriano é aquele que passa por 
todas as arestas do grafo uma única vez. A Figura 17 ilustra um grafo euleriano, 
pois trata-se de um ciclo que passa por todas as arestas apenas uma vez (u1, u2, u3, 
u4, u5, u3, u1, u6, u2, u7, u3, u6, u7, u1):
Figura 17 – Grafo euleriano
Fonte: elaborada pelo professor conteudista
Importante!
Caminhos em grafo correspondem a um dos principais conceitos utilizados para modelar 
diversos problemas. Um caminho pode ser definido como uma sequência de vértices tal que 
para cada vértice da sequência há uma aresta para o próximo vértice da mesma sequência.
Diversos problemas que são modelados com grafos necessitam achar o caminho mais curto 
entre um par de vértices; de modo que o caminho mais curto entre dois vértices v e w de um 
grafo G não ponderado é aquele que acumula a menor quantidade de arestas entre v e w.
Existem diversos algoritmos para obter o caminho mais curto entre dois vértices em um 
grafo, por exemplo, os algoritmos de Dijkstra e de Ford-Moore-Bellman – ambos são 
eficientes e elegantes, provendo sempre o menor caminho entre um par de vértices.
Por fim, os grafos de tipo hamiltoniano e euleriano são aplicados na resolução de diver-
sos problemas, de modo que um grafo hamiltoniano é aquele que possui um caminho 
que contém todos os vértices de G; já um grafo euleriano contém um caminho que passa 
por todas as arestas, sem repetição.
Em Síntese
18
19
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 JÚNIOR, 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
CARDOSO, M.; SZYMANSKI, J.; ROSTAMI, M. Matemática discreta: combinatória, 
teoria dos grafos e algoritmos. [S.l.]: Escolar, 2009.
https://bit.ly/2KON8LQ
19
UNIDADE Caminhos em Grafos
Referências
BOAVENTURA NETTO, P. O. Grafos: teoria, modelos, algoritmos. 2. ed. São 
Paulo: Edgard 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. 2018. Disponível em: <http://www.ime.usp.br/~pf/
teoriadosgrafos>. Acesso em: 24 nov. 2018.
FURTADO, A. L. Teoria dos grafos algoritmos. Rio de Janeiro: Livros Técnicos 
e Científicos, 1973.
GOLDBARG, M.; GOLDBARG, E. Grafos – conceitos, algoritmos e aplicações. 
[S.l.]: Campus, 2012.
NICOLETTI, A. M.; HRUSCHKA JÚNIOR, 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
Teoria dos Grafos
Material Teórico
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.
• Conhecer todos os conceitos de árvores e topologia. 
OBJETIVO DE APRENDIZADO
Árvores e Ordenação Topológica
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: 
Assim:
Organize seus estudos de maneira que passem a fazer parte 
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 oconteú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.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
Não se esqueça 
de se alimentar 
e de se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
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
9
a) Árvore ponderada c) Estrelab) Árvore não ponderada
1 2
4
5
7 6
3
7
1
2
4
5
6
3
2
4
5
3
6
1
7
114
2
2
2
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
7
1 2
98
4 5 6
3
7
1 2
98
4 5 6
3
c) Árvore geradora
7
1 2
8 9
5 6
3
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
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
T1 T2 T3
T1 T2 T3
8
1 2
109
5 6
3
11
7
4
b) Florestas
8
1 2
109
5 6
3
11
4
c) Florestas
1 2
10
5 6
3
11
7
4
7
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)
7
1 2
10
56
8 9 4
3
c)
ee
7
1 2
10
56
8 9 4
3
b)
7
1 2
10
56
8 9 4
3
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
11
a) Grafo G
10 12
8 5
8 5
5
1
1
8
1
7
4
6
2
b) Árvore geradora mínima
5
5
1
11
7
4
6
2
c) Árvore geradora máxima
5
5
10
8
8
8
12
4
6
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
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 extremidadeem 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)
T = {1} ≠ N T = {1, 2} ≠ N
Aresta 1, 2
1 1
1
2
2
1
-2
3
3
4
b)
1 1
1
2
2
1
-2
3
3
4
1
2 4
53
6 1
2 4
53
6
c)
T = {1, 2, 3} ≠ N T = {1, 2, 3, 4} ≠ N
Aresta 2, 4Aresta 2, 3
1 1
1
2
2
1
-2
3
3
4
d)
1 1
1
2
2
1
-2
3
3
4
1
2 4
53
6 1
2 4
53
6
e)
T = {1, 2, 3, 4, 5} ≠ N
T = {1, 2, 3, 4, 5, 6} ≠ N
Aresta 4, 6
1 1
1
2
2
1
-2
3
3
4
f)
1 1
1
2
2
1
-2
3
3
4
1
2 4
53
6 1
2 4
53
6
Figura 6 – Evolução do algoritmo de Prim
Fonte: Adaptado de Goldbarg e Goldbarg, 2012
12
13
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 
algoritmo de Prim Colorido
1 3
1
2
2
22
-33
3
1
2 4
53
6
b) Vértice 1 é examinado Arestas (1, 2) 
e (1, 30) são coloridas de verde
1 3
1
2
2
22
-33
3
1
2 4
53
6
c) A menor aresta verda é colorida de 
azul e inserida na solução
1 3
1
2
2
22
-33
3
1
2 4
53
6
d) Vértice 2 é examinado e as Arestas 
(2, 4) e (2, 5) são pintadas de verde
1 3
1
2
2
22
-33
3
1
2 4
53
6
e) Aresta (1, 3) é colorida de vermelho 
e a Aresta (2, 3) é colorida de azul
1 3
1
2
2
22
-33
3
1
2 4
53
6
f) Vértice 3 é examinado. A aresta (3, 5) 
é colorida de verde e a aresta (2, 5) 
de vermelho
1 3
1
2
2
22
-33
3
1
2 4
53
6
g) Aresta (3, 5) é pintada de azul
1 3
1
2
2
22
-33
3
1
2 4
53
6
h) Vértice 5 é examinado e as arestas 
(5, 6) e (5, 4) são coloridas de verde
1 3
1
2
2
22
-33
3
1
2 4
53
6
i) A aresta (2, 4) é pintada de vermelho
1 3
1
2
2
22
-33
3
1
2 4
53
6
j) Dentre todas as verdes, a menor é (5, 4) Então 
ela é pintada de azul e incluída na solução
1 3
1
2
2
22
-33
3
1
2 4
53
6
l) O vértice 4 é examinado e a aresta (4, 6) 
é colorida de vermelho e a (5, 6) de azul, i = n –1 e �m
1 3
1
2
2
22
-33
3
1
2 4
53
6
13
UNIDADE Árvores e Ordenação Topológica
a) Grafo G exemplo para a aplicação do 
algoritmo de Prim Colorido
1 3
1
2
2
22
-33
3
1
2 4
53
6
b) Vértice 1 é examinado Arestas (1, 2) 
e (1, 30) são coloridas de verde
1 3
1
2
2
22
-33
3
1
2 4
53
6
c) A menor aresta verda é colorida de 
azul e inserida na solução
1 3
1
2
2
22
-33
3
1
2 4
53
6
d) Vértice 2 é examinado e as Arestas 
(2, 4) e (2, 5) são pintadas de verde
1 3
1
2
2
22
-33
3
1
2 4
53
6
e) Aresta (1, 3) é colorida de vermelho 
e a Aresta (2, 3) é colorida de azul
1 3
1
2
2
22
-33
3
1
2 4
53
6
f) Vértice 3 é examinado. A aresta (3, 5) 
é colorida de verde e a aresta (2, 5) 
de vermelho
1 3
1
2
2
22
-33
3
1
2 4
53
6
g) Aresta (3, 5) é pintada de azul
1 3
1
2
2
22
-33
3
1
2 4
53
6
h) Vértice 5 é examinado e as arestas 
(5, 6) e (5, 4) são coloridas de verde
1 3
1
2
2
22
-33
3
1
2 4
53
6
i) A aresta (2, 4) é pintada de vermelho
1 3
1
2
2
22
-33
3
1
2 4
53
6
j) Dentre todas as verdes, a menor é (5, 4) Então 
ela é pintada de azul e incluída na solução
1 3
1
2
2
22
-33
3
1
2 4
53
6
l) O vértice 4 é examinado e a aresta (4, 6) 
é colorida de vermelho e a (5, 6) de azul, i = n –1 e �m
1 3
1
2
2
22
-33
3
1
2 4
53
6
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
15
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. 
2 3
1
5 6 7
4
a) Grago G exemplo para o algoritmo Kruskal b) Ordenação das arestas de G em H
6
3 9
3 2 18 1
2 5
c) Inserção da Primeira aresta em T
1
Vetor H
h1 – (3, 6) = 1; h2 – (4, 7) = 1; h3 – (5, 6) = 2;
h4 – (2, 3) = 3; h5 – (2, 6) = 3; h6 – (6, 7) = 5;
h7 – (1, 3) = 6; h8 – (2, 5) = 8; h9 – (3, 4) = 9;
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
d) Inserção da Segunda aresta em T
1 1
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
g) Inserção da Quinta aresta em T
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
h) Inserção da Quinta aresta em T
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
i) Árvore geradora mínima
1
6
1
52
3
1 1
52
31
1 1
2
3
3
e) Inserção da Terceira aresta em T
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
f) Inserção da Quarta aresta em T
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4– (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
1 1
2
3
1 1
2
2 3
1
5 6 7
4
2 3
1
5 6 7
4 2 3
1
5 6 7
4
2 3
1
5 6 7
4
2 3
1
5 6 7
4
2 3
1
5 6 7
4
3
1
5 6 7
4
15
UNIDADE Árvores e Ordenação Topológica
2 3
1
5 6 7
4
a) Grago G exemplo para o algoritmo Kruskal b) Ordenação das arestas de G em H
6
3 9
3 2 18 1
2 5
c) Inserção da Primeira aresta em T
1
Vetor H
h1 – (3, 6) = 1; h2 – (4, 7) = 1; h3 – (5, 6) = 2;
h4 – (2, 3) = 3; h5 – (2, 6) = 3; h6 – (6, 7) = 5;
h7 – (1, 3) = 6; h8 – (2, 5) = 8; h9 – (3, 4) = 9;
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
d) Inserção da Segunda aresta em T
1 1
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
g) Inserção da Quinta aresta em T
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
h) Inserção da Quinta aresta em T
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
i) Árvore geradora mínima
1
6
1
52
3
1 1
52
31
1 1
2
3
3
e) Inserção da Terceira aresta em T
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
f) Inserção da Quarta aresta em T
Vetor H
h1 – (3, 6) = 1; 
h2 – (4, 7) = 1; 
h3 – (5, 6) = 2;
h4 – (2, 3) = 3; 
h5 – (2, 6) = 3; 
h6 – (6, 7) = 5;
h7 – (1, 3) = 6; 
h8 – (2, 5) = 8; 
h9 – (3, 4) = 9;
1 1
2
3
1 1
2
2 3
1
5 6 7
4
2 3
1
5 6 7
4 2 3
1
5 6 7
4
2 3
1
5 6 7
4
2 3
1
5 6 7
4
2 3
1
5 6 7
4
3
1
5 6 7
4
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
17
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.
12/15
6/7
11/16
13/14
9/10
17/18
2/5
3/4
1/8
Cuecas
Sapatos
Meias
Relógio
Calças
Cinto Gravata
Camisa
Paletó
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: 
17/18 11/16 12/15 13/14 9/10 1/8 6/7 2/5 3/4
CuecasMeias Calças Sapato Relógio Camisa Cinto Gravata Paletó
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
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. 
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. 
Em Síntese
18
19
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
http://bit.ly/2IvLc8r
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: <http://www.ime.usp.br/~pf/
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