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 – Busca