Teoria dos Grafos: Conceitos e Aplicações

Prévia do material em texto

Razer Anthom Nizer Rojas Montaño
TEORIA DOS GR
AFOS
Razer Anthom
 N
izer Rojas M
ontaño
Código Logístico
59398
Fundação Biblioteca Nacional
ISBN 978-85-387-6636-0
9 7 8 8 5 3 8 7 6 6 3 6 0
Teoria dos Grafos 
Razer Anthom Nizer Rojas Montaño
IESDE BRASIL
2020
© 2020 – IESDE BRASIL S/A. 
É proibida a reprodução, mesmo parcial, por qualquer processo, sem autorização por escrito do autor e do detentor dos 
direitos autorais.
Projeto de capa: IESDE BRASIL S/A. Imagem da capa: EnvatoElements
Todos os direitos reservados.
IESDE BRASIL S/A. 
Al. Dr. Carlos de Carvalho, 1.482. CEP: 80730-200 
Batel – Curitiba – PR 
0800 708 88 88 – www.iesde.com.br
CIP-BRASIL. CATALOGAÇÃO NA PUBLICAÇÃO 
SINDICATO NACIONAL DOS EDITORES DE LIVROS, RJ
M765t
Montaño, Razer Anthom Nizer Rojas
Teoria dos grafos / Razer Anthom Nizer Rojas Montaño. - 1. ed. - 
Curitiba [PR] : IESDE, 2020. 
126 p. : il.
Inclui bibliografia
ISBN 978-85-387-6636-0
1. Teoria dos grafos. 2. Algoritmos I. Título.
20-63940 CDD: 511.5
CDU: 519.17
Razer Anthom 
Nizer Rojas Montaño
Doutor em Ciência da Computação e mestre em 
Informática pela Universidade Federal do Paraná (UFPR), 
na área de inteligência computacional. Graduado 
bacharel em Informática pela mesma instituição. 
Atualmente, é professor do curso superior de 
Tecnologia em Análise e Desenvolvimento de Sistemas 
e coordenador acadêmico do Setor de Educação 
Profissional e Tecnológica da UFPR. Tem experiência 
nas áreas de análise, projeto e desenvolvimento de 
software (com ênfase na plataforma Java e aplicações 
corporativas), aprendizado de máquina (regressão, 
classificação, clusterização, regras de associação, 
linguagem R, avaliação de modelos), planejamento em 
inteligência artificial (com ênfase em lógica matemática, 
SAT, redes de Petri e raciocínio sobre ações) e aplicações 
em mensuração florestal.
Agora é possível acessar os vídeos do livro por 
meio de QR codes (códigos de barras) presentes 
no início de cada seção de capítulo.
Acesse os vídeos automaticamente, direcionando 
a câmera fotográ�ca de seu smartphone ou tablet 
para o QR code.
Em alguns dispositivos é necessário ter instalado 
um leitor de QR code, que pode ser adquirido 
gratuitamente em lojas de aplicativos.
Vídeos
em QR code!
SUMÁRIO
1 Introdução ao estudo dos grafos 9
1.1 História e teoria dos grafos 9
1.2 Noções e definições básicas 12
1.3 Tipos de grafos 14
1.4 Vizinhança e grau 17
1.5 Isomorfismo 21
1.6 Representação computacional 27
1.7 Aplicações dos grafos 29
2 Conectividade 34
2.1 Grafos conexos e componentes 34
2.2 Caminhos e circuitos 36
2.3 Subgrafos 40
2.4 Cortes 42
3 Caminho mínimo e árvores geradoras 51
3.1 Busca em grafos e árvore geradora 51
3.2 Árvore Geradora Mínima 62
3.3 Caminho Mínimo 65
4 Grafos eulerianos e hamiltonianos 74
4.1 Grafos eulerianos 74
4.2 Grafos hamiltonianos 84
5 Problemas em Grafos 97
5.1 Cliques e Conjuntos Estáveis 97
5.2 Cliques Máximas 101
5.3 Coberturas 104
5.4 Planaridade 106
5.5 Coloração 111
Gabarito 118
Agora é possível acessar os vídeos do livro por 
meio de QR codes (códigos de barras) presentes 
no início de cada seção de capítulo.
Acesse os vídeos automaticamente, direcionando 
a câmera fotográ�ca de seu smartphone ou tablet 
para o QR code.
Em alguns dispositivos é necessário ter instalado 
um leitor de QR code, que pode ser adquirido 
gratuitamente em lojas de aplicativos.
Vídeos
em QR code!
APRESENTAÇÃO
Vídeo A Teoria dos Grafos (TG) é uma área de estudo e pesquisa que 
possibilita a resolução de problemas de diversos setores, como logística, 
comunicações, tubulações, genética, química, entre outros. O objetivo da 
TG é a representação de problemas, como por exemplo, as estruturas 
matemáticas, chamadas de grafos, e a aplicação de soluções algorítmicas, 
sempre considerando aspectos computacionais de desempenho, em 
tempo de execução e armazenamento.
Na área de estudo dos grafos, pode-se abordar o assunto com viés 
teórico ou algorítmico. Na abordagem teórica, tem-se um peso maior nos 
aspectos matemáticos dos grafos, dos teoremas e das provas. Na abordagem 
algorítmica, estudam-se os problemas, as maneiras de resolução (eficientes 
ou não) e a implementação computacional dessas soluções.
Neste livro, buscou-se um equilíbrio entre a teoria, necessária para 
o entendimento matemático dos grafos, e os algoritmos, que levam em 
consideração sua composição computacional na solução de problemas. 
Os capítulos estão organizados de modo a apresentar os conceitos e 
problemas gradualmente. 
Inicia-se com os conceitos básicos necessários para equalizar o 
vocabulário e mostrar a estrutura matemática de um grafo, bem como sua 
história. Na sequência, conceitos mais avançados são expostos e alguns 
algoritmos são apresentados, além de teoremas pertinentes ao assunto. 
Em suma, essa obra traz informações básicas para a compreensão geral da 
Teoria dos Grafos em todas as áreas em que sua aplicação é possível.
Bons estudos!
Introdução ao estudo dos grafos 9
1
Introdução ao estudo dos grafos
Neste capítulo, será introduzido o estudo sobre a teoria dos grafos, o 
qual está organizado da seguinte maneira: na Seção 1.1 é apresentado o 
surgimento da teoria dos grafos, mostrando que a alavanca para o seu 
desenvolvimento foram problemas reais que os cientistas tiveram na épo-
ca. Na Seção 1.2 abordam-se as noções e definições básicas dos grafos, 
sua caracterização matemática e sua representação gráfica. Na Seção 1.3 
são mostrados os vários tipos de grafos e suas definições. Já os conceitos 
de vizinhança, grau e caminhos serão tratados na Seção 1.4. Na Seção 1.5 
exploram-se o conceito de isomorfismo em grafos e as suas caracterizações. 
Para executar algoritmos em grafos, também será necessário o estudo 
das representações computacionais, as quais estão descritas na Seção 
1.6. Por fim, na Seção 1.7 são abordadas algumas aplicações de grafos em 
problemas do mundo real.
1.1 História e teoria dos grafos
Vídeo Um grafo é uma estrutura que formaliza relações de interdependência exis-
tentes entre os elementos de um conjunto e que possui uma representação grá-
fica facilitadora do entendimento e desenvolvimento de alguns conceitos. Assim, 
os componentes de um grafo que representam os elementos de um conjunto em 
questão são diagramados como pontos e denominados como vértices ou nós. Para 
representar as relações entre os elementos do conjunto, traçam-se setas interli-
gando os vértices, as quais são denominadas arestas ou arcos.
Os grafos podem ser usados para resolver problemas em diversas áreas, por 
exemplo, na química, em que a estrutura de uma molécula pode ser represen-
tada por meio de um grafo; nas redes de rotas de transporte (estradas, logís-
tica etc.); nas redes de comunicações (rede de computadores local ou mesmo 
na internet); na distribuição de produtos e serviços, caso das tubulações de gás, 
água, petróleo etc.
De acordo com Szwarcfiter (2018), o estudo dos grafos surgiu com o proble-
ma das sete pontes de Königsberg. Em um artigo publicado por Leonhard Euler 
(1707–1783), em 1736, o autor discorreu sobre o assunto, apresentando uma so-
lução negativa, a qual originou a teoria dos grafos. Königsberg – que até 1945 foi 
território da Prússia – é uma cidade cortada pelo Rio Prególia, com duas grandes 
ilhas e sete pontes entre elas. A região foi bombardeada durante a Segunda Guerra 
Mundial e tomada pelos russos, quando foi renomeada para Kaliningrado. Durante 
10 Teoria dos Grafos
esse período, duas das sete pontes existentes foram destruídas. Observe a seguir o 
mapa das pontes em 1652 (as em vermelho foram destruídas).
Se
rg
ey
 M
er
ku
lo
v/
Sh
ut
te
rs
to
ck
Em 1736, Euler provou que não havia a possibilidade de passar por todas essas 
pontes sem repetir qualquer uma delas. Para comprovar essa tese, o estudioso 
desenhou o problema das pontes usando um diagrama como este:
v4
v1
v2
v3
Grafo do problema das sete pontesPor exemplo, seja o grafo G da Figura 23.
Figura 23
Grafo G
Fonte: Elaborada pelo autor.
v6
v5
v1
v2
v4
v3
Um corte de arestas é o conjunto c1 = {(v4, v6), (v3, v6), (v5, v6)}. A 
eliminação dessas arestas gera o grafo G’ da Figura 24.
Assim, consegue-se obter um corte de vértices a partir de c1 eli-
minando um subconjunto dos vértices cujas arestas em c1 incidem. 
Os vértices em c1 são v4, v3, v5, v6. Observe que eliminando v4, v3 
tem-se o grafo da Figura 25, desconexo, e que não há subconjunto 
de c2 = {v4, v3} que desconecte o grafo, sendo esse, portanto, um 
corte de vértices. Percebe-se também que o |c2| ≤ |c1|.
Posto isso, conclui-se que cv ≤ cA, a conectividade de vértices de 
um grafo qualquer é sempre menor ou igual à sua conectividade de 
arestas. Dado um grafo G não completo, cujo vértice v possui grau 
mínimo, é possível desconectar G removendo grau(v) arestas, que 
são as arestas que incidem em v. Por exemplo, uma vez que o grafo 
G da Figura 23 é um vértice de grau mínimo, ele é v1, sendo grau 
(v1) = 3. Assim, é possível desconectar o grafo G removendo todas 
as arestas incidentes a v1; nesse caso, são três arestas, a saber: (v1, 
v2), (v1, v3), (v1, v4).
Portanto, sendo v um vértice de grau mínimo, grau(v) ≥ cA ≥ cv. Se 
o grafo G for um grafo completo (G = Kn), então todos seus vértices 
possuem o mesmo grau n – 1 (pois estão conectados com todos os 
demais vértices) e, portanto, grau(v) = cA = cv = n – 1.
Figura 24
Grafo G’
Fonte: Elaborada pelo autor.
v6
v5
v1
v2
v4
v3
Figura 25
Grafo com vértices retirados
Fonte: Elaborada pelo autor.
v6
v5
v1
v2
Conectividade 45
Se um vértice de um grafo, ao ser removido, o desconecta, o vértice é chama-
do de articulação. Igualmente, se uma aresta do grafo, quando removida, desco-
necta o grafo, então essa aresta é chamada ponte. A Figura 26 mostra um grafo 
com articulações e uma ponte.
Figura 26
Grafo com ponte e articulações
Fonte: Elaborada pelo autor.
v6
v7v5v2
v8v1 v4v3
Articulações
Ponte
Dessa maneira, um grafo é biconexo em vértices se, e somente se, não possuir 
articulações. Isso acontece, pois, se o grafo possuir uma articulação, significa que 
o vértice, se removido, desconecta o grafo, portanto ele seria 1-conexo. Analoga-
mente, um grafo é biconexo em arestas se, e somente se, não possuir pontes, o 
raciocínio é o mesmo (SZWARCFITER, 2018).
Com o conceito de caminho, consegue-se dizer que em um grafo conexo G = (V, A), 
|V| > 2, as seguintes afirmações (SZWARCFITER, 2018):
1. Um vértice v ∈ V é articulação de G se, e somente se, existirem vértices v1, v2 ≠ 
v, tais que em todo caminho entre v1 e v2 em G, v está presente.
2. Uma aresta (v1, v2) ∈ A é ponte se, e somente se, (v1, v2) for o único caminho 
simples entre v1 e v2.
Tirando a prova
Observe, a seguir, as provas dessas afirmações.
Afirmação 1: um vértice v ∈ V é articulação de G se, e somente se, existirem 
vértices v1, v2 ≠ v, tais que em todo caminho entre v1 e v2, em G, v está presente.
Prova de ida →: assumimos que v é uma articulação, portanto, retirar v de G, 
pela definição de articulação, desconecta o grafo. Se o grafo G’ resultante da re-
moção de v é desconexo, então, é formado por, pelo menos, duas componentes 
conexas, dois vértices (v1 e v2) em componentes conexas diferentes. Então, como v 
é articulação, qualquer caminho entre v1 e v2 passa por v.
Prova de volta ← : assumimos dois vértices v1 e v2 de G, diferentes de v, tal que 
todo caminho entre v1 e v2 passa por v. Assim, se todo caminho entre v1 e v2 passa 
por v, significa que se o vértice v for removido do grafo G, então, v1 não é mais al-
cançável a partir de v2 (e vice-versa, assumindo G não dirigido), isto é, não há mais 
caminho entre dois vértices do grafo, o que caracteriza um grafo desconexo. Um 
vértice que quando removido desconecta o grafo, é a definição de articulação, por-
tanto, v é uma articulação G.
Sempre que se deve provar uma 
afirmação que contém se, e so-
mente se, a prova é formada por 
duas partes: a ida (→) e a volta 
(←). Por exemplo, queremos 
provar a afirmação: Chove se, e 
somente se, faz frio. A ida significa 
provar que se chove, então faz frio. 
Já a volta significa provar que se 
faz frio, então chove (GERSTING; 
IÓRIO, 2012).
Importante
46 Teoria dos Grafos
Afirmação 2: uma aresta (v1, v2) ∈ A é ponte se, e somente se, {v1, v2} for o único 
caminho simples entre v1 e v2.
Prova de ida → : assumimos a aresta (v1, v2) ∈ A é ponte do grafo G e, portanto, 
retirar essa aresta de G, pela definição de ponte, desconecta o grafo. Se o grafo G’ 
resultante da remoção de (v1, v2) é desconexo, então, v1 e v2 estão em componentes 
conexas distintas. Assim, a aresta (v1, v2) é o único caminho simples entre v1 e v2.
Prova de volta ← : assumimos que a aresta a (v1, v2) ∈ A é o único caminho 
simples entre v1 e v2. Como v1 e v2 são adjacentes (há uma aresta entre eles), ser o 
único caminho simples significa que não se tem arestas repetidas entre v1 e v2, nem 
outro caminho entre eles passando por outros vértices. Assim, remover a aresta 
(v1, v2) de G faz com que v1 não seja mais alcançável a partir de v2 (e vice-versa, as-
sumindo um grafo não dirigido), portanto, o grafo se torna desconexo. Uma aresta 
que quando removida do grafo o desconecta é a definição de ponte, portanto, (v1, 
v2), é ponte de G. 
Para um grafo G, definem-se componentes biconexas aos subgrafos maximais 
de G que sejam biconexos em vértices ou que sejam isomorfos a K2. As componen-
tes biconexas são também chamadas de blocos do grafo. Se um grafo G for bicone-
xo, ele só possui um bloco, que é o próprio G. A Figura 27 mostra todos os blocos 
do grafo da Figura 26 (FEOFILOFF, 2020).
Figura 27
Bloco do grafo
Fonte: Elaborada pelo autor.
v6
v5
v4
v4v3
v2
v1 v3 v6
v7
v8
Por essa definição, percebe-se que cada aresta de um grafo pertence a exatamente 
um bloco do grafo. Também percebe-se que um vértice é articulação do grafo se, e 
somente se, pertencer a mais de um bloco do grafo.
Na Figura 27 é possível perceber que cada aresta faz parte de somente um bloco 
do grafo e que os vértices v3, v4 e v6, que são articulações, são os únicos vértices que 
aparecem em mais de um bloco.
A caracterização de corte de vértices e de arestas é importante para a aplica-
ção de grafos na modelagem de alguns problemas reais. Veja como exemplo uma 
rede de computadores como a da Rede Nacional de Ensino e Pesquisa (RNP), or-
ganização responsável, entre outras coisas, pela manutenção da Rede Ipê – a rede 
acadêmica brasileira que interliga universidades. A rede é formada por Pontos de 
Presença (PoP) em cada uma das unidades da federação e esses pontos são conec-
tados por fibra ótica de alta velocidade (REDE..., 2020). Um dos problemas em que 
grafos são aplicáveis, apesar de nesse caso ser uma modelagem simples, é para 
Conectividade 47
verificar se há algum ponto em que essa rede pode ficar desconectada se algum 
link de internet deixar de funcionar.
Modelar essa rede como um grafo é simplesmente assumir que cada PoP é um vér-
tice do grafo e cada link de internet entre os PoPs é uma aresta. 
Figura 28
Mapa de tráfego da Rede Ipê
Fonte: RNP, 2020b.
Esta rede é mapeada pelo grafo da Figura 29.
Figura 29
Rede Ipê mapeada por um grafo
Fonte: Elaborada pelo autor com base em RNP, 2020b.
RO
AC
RS
SC
MT
MS
PR BA SE AL
AP
PE PB2
PB1
MARR
AM
PA
PI
SP RJ ES
GO
TO
DF MG CE RN
48 Teoria dos Grafos
Encontrar um link de rede que deixa algum estado desconectado é o mesmo 
que encontrar um corte de arestas no grafo que o torna desconexo. Esse grafo, 
em especial, é 1-conexo, pois se for retirada a aresta (PA, AP), o grafo se torna 
desconexo. Assim, se cair o link de internet entre os PoPs Pará e Amapá, o Amapá 
ficará desconectado do resto da rede. Com esse resultado, os engenheiros podem 
planejar expansões na rede, inclusive como um caminho alternativo entre PA e AP, 
para que haja redundância na rede.
Na Figura 28 percebe-se que o link entrePE e CE está em preto que, segundo 
a legenda, significa que não há tráfego entre esses dois pontos. Isso significa que 
qualquer comunicação entre MT e MS deve passar por outro caminho. Entre os 
possíveis caminhos estão: (MT, GO), (GO, DF), (DF, SP), (SP, PR), (PR, MS).
CONSIDERAÇÕES FINAIS
Este capítulo apresentou conceitos relativos à conectividade de grafos, como gra-
fos conexos e desconexos, as componentes conexas e suas caracterizações. Também 
foram mostrados os conceitos de caminhos e ciclos, que são de grande importância 
para a aplicação de grafos em problemas reais. Os conceitos de grafos hamiltonianos 
e eulerianos foram definidos sobre caminhos e ciclos, bem como em digrafos (grafos 
dirigidos ou orientados).
Ao final, foram expostas as definições de subgrafos, vértices de corte e arestas de 
corte. Em especial, os conceitos de pontes e articulações, que também são de grande 
importância no mapeamento de problemas reais para grafos. O problema de busca 
de pontes em grafos foi aplicado à Rede Ipê, para descobrir fraquezas na rede, em 
que a queda de um link de internet entre duas instituições pode deixar parte da rede 
desconectada.
ATIVIDADES
1. Dado o grafo a seguir, dê suas componentes conexas.
v1
v5
v3
v4
v2
v6
Conectividade 49
2. Dado o digrafo a seguir, encontre um caminho entre v3 e v4.
v2v1
v6
v3
v5
v4
3. Dado o grafo a seguir, encontre um ciclo euleriano.
v4
v2
v5
v1
v3
4. Dado o grafo semi-hamiltoniano a seguir, explique o que precisa ser feito para que 
se torne um grafo hamiltoniano?
v4
v2
v3v1
5. Dado o grafo a seguir, dê o subgrafo induzido contendo os vértices v1, v2 e v5.
v4
v2
v5
v1
v3
50 Teoria dos Grafos
6. Dado o grafo a seguir, apresente todas as suas componentes biconexas.
v4
v1
v3
v2
v5
v6
v7
v8
v8
REFERÊNCIAS
BOAVENTURA NETTO, P. O.; JURKIEWICZ, S. Grafos: introdução e prática. São Paulo: Blucher, 2009. 
FEOFILOFF, P. Instituto de Matemática e Estatística – USP, 2020. Algoritmos para grafos via Sedgewick. 
Disponível em: https://www.ime.usp.br/~pf/algoritmos_para_grafos/. Acesso em: 14 maio 2020.
FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. Uma introdução sucinta à Teoria dos Grafos. São 
Paulo: Instituto de Matemática e Estatística – USP, 2011. Disponível em: https://www.ime.usp.br/~pf/
teoriadosgrafos/. Acesso em: 14 maio 2020.
GERSTING, J. L.; IÓRIO, V. de M. Fundamentos matemáticos para a ciência da computação: um tratamento 
moderno de matemática discreta. 5. ed. Rio de Janeiro: LTC, 2012.
NICOLETTI, M. C; HRUSCHKA JUNIOR, E. R. Fundamentos da teoria dos grafos para computação. 3. ed. São 
Paulo: LTC, 2018.
RNP. Rede Nacional de ensino e pesquisa, 2020a. Página inicial. Disponível em: https://www.rnp.br. 
Acesso em: 14 maio 2020.
RNP. Panorama de Tráfego da Rede Ipê. Rede Nacional de ensino e pesquisa, 2020b. Disponível em: https://
www.rnp.br/sistema-rnp/ferramentas/panorama-de-trafego. Acesso em: 15 de abr. 2020.
SZWARCFITER, J. L. Teoria Computacional de Grafos. Rio de Janeiro: Elsevier, 2018.
Caminho mínimo e árvores geradoras 51
3
Caminho mínimo e 
árvores geradoras
Assumindo que problemas do mundo real podem ser mapeados 
para grafos, a resolução, às vezes, exige procedimentos que variam des-
de uma busca simples até o encontro de outros subgrafos com algumas 
características.
Nesse sentido serão apresentados na Seção 3.1 deste capítulo os al-
goritmos de busca em profundidade e largura dos grafos, indicando que 
esses conseguem encontrar as árvores geradoras dos grafos. Se os grafos 
possuem pesos, será explorado na Seção 3.2 o problema de encontrar 
a árvore geradora mínima, por meio dos algoritmos de Prim e Kruskal. 
Por fim, na Seção 3.3 será trabalhado o problema do caminho mínimo, isto 
é, encontrar o menor caminho entre dois vértices, que pode ser resolvido 
pelo algoritmo de Dijkstra.
3.1 Busca em grafos e árvore geradora
Vídeo Muitos problemas em grafos são resolvidos por procedimentos 
com base em algoritmos de busca ou suas adaptações, desde encon-
trar um caminho entre dois vértices até achar o emparelhamento 
máximo de um grafo.
Os procedimentos de busca em grafos se resumem em caminhar 
de maneira sistemática pelo grafo, considerando algumas condições 
para decidir se o problema foi resolvido. Em termos de busca, o ob-
jetivo é visitar todos os vértices e todas as arestas, evitando repetir a 
passagem nesses elementos. Essa questão é crucial na resolução de 
problemas, pois garante que não haja retrabalho, mas também exi-
ge a necessidade de recursos adicionais para marcar quando uma 
aresta ou um vértice já foi visitado. Assim, um vértice é dito marcado 
quando já foi visitado pelo procedimento de busca e, portanto, é dis-
tinto dos vértices não marcados.
O Algoritmo 1 1 apresenta um algoritmo básico de busca em 
grafos, que tem como entrada um grafo conexo com todos os seus 
vértices desmarcados. No primeiro passo, escolhe-se um vértice 
para ser o inicial, marcando-o. Já no segundo, elege-se um vértice 
Um algoritmo é uma 
sequência finita de passos 
usada para resolver algum 
problema. Os algoritmos 
são independentes de lin-
guagens de programação e 
podem ser codificados em 
qualquer plataforma. 
ZIVIANI, N. Projeto de Algoritmos 
Com Implementações em Pascal e C. 
Pioneira Thomson Learning. São Paulo: 
2a ed. 2004.
1
Um emparelhamento M, em um 
grafo não dirigido, é um conjunto de 
arestas em que todo vértice do grafo 
incide em, no máximo, um elemento 
de M (FEOFILOFF, 2020). Encontrar 
o emparelhamento máximo de 
um grafo pode ser útil para a 
determinação de rotas de veículos, a 
designação de tarefas etc.
Saiba mais
52 Teoria dos Grafos
marcado v1, que possua um vértice incidente v2, tal que a aresta (v1, v2) ∈ A e ain-
da não tenha sido selecionada. Em seguida, o vértice v2 é marcado, se ainda não 
estiver. Esse processo termina quando todas as arestas de G forem selecionadas.
Sempre que a aresta (v1, v2) é selecionada com base no vértice marcado v1, ela 
é dita explorada. Um vértice se denomina explorado quando todas as arestas in-
cidentes forem exploradas. Nesse processo, é possível que um vértice seja alcan-
çado várias vezes pelo procedimento de busca, então, este será chamado visitado. 
O mesmo conceito se aplica a arestas, caso precisem ser alcançadas várias vezes 
pelo procedimento.
Algoritmo 1
Busca em grafo
Dados: Grafo G = (V, A)
1 Desmarcar todos os vértices
2 Escolher o vértice inicial
3 Marcar o vértice inicial
4 ENQUANTO existir algum vértice v1 marcado e com aresta (v1, v2) não explorada FAÇA
5 Escolher o vértice v1
6 Explorar a aresta (v1, v2)
7 SE v2 não está marcado ENTÃO
8 Marcar v2
9 FIM SE
10 FIM ENQUANTO
Fonte: Adaptado de Szwarcfiter, 2018.
Percebe-se que no Algoritmo 1 há vários pontos de escolha que ficaram em 
aberto, a saber:
 • Qual vértice inicial escolher?
 • Qual vértice marcado v1 escolher?
 • Qual aresta incidente ao vértice marcado v1, (v1, v2), escolher?
A maneira com a qual essas escolhas são feitas determina o tipo de busca. O cri-
tério sobre qual vértice v1 marcado escolher indica se a busca é em profundidade 
ou em largura. Por exemplo, se o vértice selecionado for o último analisado, então, 
é uma busca em profundidade. Já se o vértice priorizar os vértices no mesmo nível 
(distância da raiz) antes de escolher os vértices do nível superior, então, é uma 
busca em largura.
A busca em profundidade (do inglês depth-first search – DPS) ocorre quando o 
próximo vértice marcado a ser escolhido for o mais recentemente alcançado pelo 
algoritmo de busca. Esse critério garante que a determinação do vértice seja única 
e sem ambiguidade.
Basicamente, ela pode ser implementada de duas formas: recursivamente ou 
pelo uso de uma pilha. O Algoritmo 2 mostra o pseudocódigo recursivo, em que 
Adj(v) é o conjunto de todos os vértices adjacentes a v.
Caminho mínimo e árvores geradoras 53
Algoritmo 2
Busca em profundidade recursiva
Dados: Grafo conexo G = (V, A)
1 PROCEDIMENTO Busca (v,pai)
2 Marcar v
3 PARA w ∊ Adj(v) FAÇA
4 SE w não está marcado ENTÃO
5 Visitar aresta de árvore (v, w)
6 Busca (w, v)
7 SENÃO
8 SE w ≠ pai ENTÃO
9 Visitar aresta de retorno (v, w)
10 FIM SE
11 FIM SE
12 FIM PARA
13 FIM PROCEDIMENTO
14 
15 Desmarcar todos os vértices de G
16 Escolher um vértice s
17 Busca (s, NULO)
Fonte: Adaptado de Szwarcfiter, 2018.
Convém ressaltar que visitar uma aresta significa efetuar uma operação espe-
cífica, por exemplo, adicionar em outro grafo. O procedimento Busca (v, pai) 
recebe como parâmetros o vértice a ser analisado e o vértice anterior da busca, o 
qual está sendo chamado de pai, para facilitar a compreensão.
O procedimento Busca executa algumas atividades, como:
 • Linha 2: marca o vértice recebido para garantir que ele não seja novamente 
escolhido.
 • Linha 3: o vértice que está sendo processado retorna todos os seus vértices 
adjacentes e, para cada um deles, é feita uma análise. 
 • Linhas 4, 5 e 6: se o vértice adjacente não está marcado, significa que ain-
da não foi processado, desse modo, visita a aresta e invoca recursivamen-
te o procedimento Busca, passando como parâmetros: o vértice adjacente 
encontrado e o próprio vértice que estava sendo processado como pai. Ao 
retornar dessa chamada recursiva, passa-se a processar o próximo vértice 
adjacente.
 • Linhas 7, 8 e 9: se o vértice adjacente está marcado, é necessário verificar se 
ele não é igual ao seu próprio pai. Se for, ignora-se, pois acabou de ser pro-
cessado. Se não for, visita-se a aresta, chamada de aresta de retorno.
Especialmente na linha 6, o procedimento Busca (w, v) é invocado recursi-
vamente para cada vértice w adjacente a v, dado pelo laço da linha 3. Isso significa 
que uma nova busca inicia, sendo o vértice w escolhido para ser o ponto inicial des-
sa busca. Quando há retorno de uma chamada recursiva, o processo é denomina-
do também de backtracking, isto é, o processo retorna para continuar o algoritmo 
com os próximos vértices adjacentes.
54 Teoria dos Grafos
No grafo da Figura 1, por exemplo, se fosse assumido o vértice v1 como pon-
to inicial, na linha 3 seriam retornados os vértices adjacentes {v2, v4, v5}. O proce-
dimento é invocado recursivamente usando v2. Ao retornar, isto é, ao executar o 
backtracking, ainda faltarão os vértices v4 e v5 para serem processados, os quais 
serão usados nas próximas interações do laço.
As arestas visitadas são classificadas de duas formas: arestas de árvore e 
arestas de retorno. As primeiras são as arestas encontradas na árvore da bus-
ca em profundidade. Uma aresta (v1, v2) é uma aresta de árvore se o vértice v2 foi 
alcançado pela primeira vez pela aresta (v1, v2). Já as segundas são arestas (v1, v2) 
que conectam o vértice v1 a um antecessor, nesse caso, v2, que já foi explorado.
O procedimento Busca, dentro de seu laço da linha 3, possui uma condicional 
para verificar qual tipo de aresta está tratando. Se forem consideradas somente as 
arestas de árvore (linha 5 do Algoritmo 2), por exemplo, para a construção de um 
outro grafo (nesse caso, um subgrafo), o grafo resultante claramente não teria ci-
clos, pois nesse trecho, o algoritmo nunca visita uma aresta adjacente a um vértice 
já marcado. Assim, é possível dizer que o algoritmo constrói uma árvore de busca 
em profundidade.
O vértice escolhido como sendo o primeiro a ser visitado, tam-
bém, é chamado de raiz da árvore de busca em profundidade. 
Para ilustrar e execução do Algoritmo 2, observe o grafo da Figura 1.
O algoritmo começa desmarcando todos os vértices e escolhe 
qualquer um destes para ser a raiz da busca. Aqui, será selecionado 
o vértice v1, mas poderia ser qualquer um, pois não há indicação no 
algoritmo. Ao ser chamado pela primeira vez, o procedimento é in-
vocado com Busca (v1, NULO), pois nesse momento não há ne-
nhum vértice anterior a v1 na busca, nesse momento.
Ao entrar no procedimento, o vértice v1 é marcado e todos os vér-
tices adjacentes são retornados, a saber: {v2, v4, v5}. Isso significa que 
dentro do laço haverá uma volta para um desses vértices. Na primeira 
volta, w = v2 e, como não está marcado, o processo entra no condicional 
da linha 4. A aresta (v1, v2) é visitada e o procedimento Busca é invoca-
do, de maneira recursiva como Busca (v2, v1). O grafo estará como 
na Figura 2, em que o vértice marcado é representado com fundo mais 
claro, a aresta de árvore visitada em tracejado e a aresta de retorno 
visitada com pontilhado.
Na chamada recursiva com Busca (v2, v1), o vértice analisado 
é o v2, portanto, ele é marcado e seus vértices adjacentes são retor-
nados: {v1, v3, v4}. O laço da linha 3 será executado para cada um 
desses vértices. Iniciando com v1, o condicional da linha 4 falha (pois 
já está marcado) e o da linha 8 também (pois v1 é o pai de v2, ou seja, 
foi passado como segundo parâmetro na chamada do procedimen-
to Busca). Desse modo, o laço retorna para obter o segundo vértice 
adjacente a v2, que é v3.
Figura 1
Grafo G
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
Figura 2
Grafo G – Busca em v1
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
Caminho mínimo e árvores geradoras 55
Como v3 não está marcado, o processo entra no condicional da 
linha 4, visitando a aresta de árvore (v2, v3) e chamando o procedi-
mento recursivamente como Busca (v3, v2) (Figura 3).
Na chamada recursiva com Busca (v3, v2), o vértice a ser ana-
lisado é o v3, portanto, ele é marcado e seus vértices adjacentes são 
retornados: {v2, v4}. O laço da linha 3 será executado para cada um 
desses vértices. Iniciando com v2, o condicional da linha 4 falha (pois 
já está marcado) e o da linha 8 também (pois v2 é o pai de v3, isto é, 
foi passado como segundo parâmetro na chamada do procedimen-
to Busca). Desse modo, o laço retorna para obter o segundo vértice 
adjacente a v3, que é v4.
Como v4 não está marcado, o processo entra no condicional da 
linha 4, visitando a aresta de árvore (v3, v4) e chamando o procedi-
mento recursivamente como Busca (v4, v3) (Figura 4).
Na chamada recursiva com Busca (v4, v3), o vértice analisado 
é o v4, portanto, ele é marcado e seus vértices adjacentes são retor-
nados: {v3, v2, v1, v5}. O laço da linha 3 será executado para cada um 
desses vértices. Iniciando com v3, o condicional da linha 4 falha (pois 
já está marcado) e o da linha 8 também (pois v3 é o pai de v4, isto é, 
foi passado como segundo parâmetro na chamada do procedimento 
Busca). Assim, o laço retorna para obter o segundo vértice adjacente 
a v4, que é v2.
Como v2 já está marcado, o processo entra no senão da linha 7 
(Algoritmo 2). Como v2 não é o pai de v4, o processo visita a aresta 
de retorno (v4, v2). Os condicionais terminam e o processo vai para 
a próxima volta do laço da linha 3 para tentar analisar o próximo 
vértice adjacente a v5.
Como v1 já está marcado, o processo entra no senão da linha 7. 
Como v1 não é o pai de v4, o processo visita a aresta de retorno (v4, v1). 
Os condicionais terminam e o processo vai para a próxima volta do 
laço da linha 3, analisando o próximo vértice adjacente a v4, que é v5.
Como v5 não está marcado, o processo entra no condicional da 
linha 4, visitando a aresta de árvore (v4, v5) e chamando o procedi-
mento recursivamente como Busca (v5, v4) (Figura 5).
Na chamada recursiva com Busca (v5, v4), o vértice analisado 
é o v5, portanto, ele é marcado e seus vértices adjacentes são retor-
nados: {v4, v1}. O laço da linha 3 será executado para cada um desses 
vértices. Iniciando com v4, o condicional da linha 4 falha (pois já está 
marcado) e o da linha 8 também (pois v4 é o pai de v5). Assim, o laço 
retorna para obter o segundo vértice adjacente a v5, que é v1.
Como v1 já está marcado, o processo entra no senão da linha 7. 
Como v1 não é o pai de v5, o processo visita a aresta de retorno (v5, v1). 
Os condicionais terminam e o processo vai para a próxima volta do 
laço da linha 3, analisando o próximo vértice adjacente a v4, que é v1.
Figura 3
GrafoG – Busca em v2
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
Figura 4
Grafo G – Busca em v3
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
Figura 5
Grafo G – Busca em v4
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
56 Teoria dos Grafos
Como não há mais vértices adjacentes a v5, o laço da linha 3 termina e a chama-
da recursiva também, retornando à última invocação de Busca (linha 6). Quando o 
procedimento analisa o vértice v4, o grafo fica como na Figura 6.
No retorno da última chamada recursiva, o procedimento estava 
analisando o vértice v4, cujos vértices adjacentes eram {v3, v2, v1 e v5} 
e já haviam sido analisados todos. Portanto, o laço da linha 3 termi-
na e essa chamada recursiva termina, retornando à última invoca-
ção de Busca (linha 6).
No retorno da última chamada recursiva, o procedimen-
to estava analisando o vértice v3 cujos vértices adjacentes eram 
{v2, v4} e já haviam sido todos analisados. Portanto, o laço da linha 
3 termina e a chamada recursiva também, retornando à última in-
vocação de Busca (linha 6), quando o procedimento estava anali-
sando o vértice v2.
No retorno da última chamada recursiva, o procedimento estava 
analisando o vértice v2 cujos vértices adjacentes eram {v1, v3, v4} e já 
haviam sido analisados os vértices v1 e v3. Portanto, o próximo vérti-
ce a ser analisado é o v4.
Como v4 já está marcado, o processo entra no senão da linha 7. Não sendo v4 
pai de v2, o processo visita novamente a aresta de retorno (v2, v4). Os condicionais 
terminam e o processo vai para a próxima volta do laço da linha 3.
Já que não há mais vértices adjacentes a v2, o laço da linha 3 termina e a chama-
da recursiva também, retornando à última invocação de Busca (linha 6), quando o 
procedimento estava analisando o vértice v1.
No retorno da última chamada recursiva, o procedimento estava analisando o 
vértice v1 cujos vértices adjacentes eram {v2, v4, v5} e já havia sido analisado o vértice 
v2. Portanto, o próximo vértice a ser verificado seria o v4.
Como v4 já está marcado, o processo entra no senão da linha 7. Como v4 não é 
o pai de v1, o processo visita novamente a aresta de retorno (v1, v4). Os condicionais 
terminam e o processo vai para a próxima volta do laço da linha 3. O próximo vér-
tice a ser analisado na lista de adjacentes é o v5.
Uma vez que v5 já está marcado, o processo entra no senão da 
linha 7. Como v5 não é o pai de v1, o processo visita novamente a 
aresta de retorno (v1, v5). Os condicionais terminam e o processo vai 
para a próxima volta do laço da linha 3.
Já que não há mais vértices adjacentes a v1, o laço da linha 3 ter-
mina e a chamada do procedimento Busca também, finalizando o 
processo de busca em profundidade.
Como resultado, a Figura 7 apresenta a árvore de busca em pro-
fundidade resultante da aplicação do algoritmo que contém o vérti-
ce v1 como raiz. Na composição foram usados somente os vértices 
visitados na linha 5 do algoritmo, que são os vértices de árvore.
Figura 6
Grafo G – Busca em v5
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
Figura 7
Árvore de busca em profundidade de G
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
Caminho mínimo e árvores geradoras 57
Um subgrafo de G é dito subgrafo gerador se possui todos os vértices de G. Se 
esse subgrafo for uma árvore, ele é denominado árvore geradora.
As arestas de árvore encontradas pela aplicação do Algoritmo 2, que podem ser 
vistas na Figura 7, foram: A’ = {(v1, v2), (v2, v3), (v3, v4), (v4, v5)}. Assim, o grafo T = (V, A’), 
resultante do processo de busca em profundidade, é uma árvore geradora do grafo 
G = (V, A).
Outro tipo de busca que pode ser efetuado é a busca em largura pelo gra-
fo. Ela é feita quando se escolhe o vértice incidente menos recentemente alcança-
do na busca. Para isso, assim que se obtém a lista de vértices adjacentes, deve-se 
enfileirá-los em uma estrutura de dados Fila. Toda vez que se escolhe um vértice, 
deve-se obtê-lo retirando-o da fila; toda vez que um vértice é marcado, deve-se en-
fileirá-lo. O Algoritmo 3 apresenta o pseudocódigo da busca em largura.
Algoritmo 3
Busca em largura
Dados: Grafo conexo G = (V, A)
1 PROCEDIMENTO Busca Largura(s)
2 Qprocessados na fila. Ao longo da execução do laço, novos 
vértices são inseridos e removidos.
Na primeira volta do laço, a variável v recebe o primeiro elemento da fila, no caso, 
v1. O laço da linha 7 varre todos os elementos adjacentes a v1, a saber, {v2, v4 e v5}, 
e, para cada volta do laço, um desses é analisado.
Inicia-se com v2, como não está marcado, e visita a aresta de árvore (v1, v2). 
Marca-se v2 e insere-se v2 em Q. O resultado pode ser visto na Figura 12.
Figura 12
Busca em largura – Vértice v2
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
V1 V2
Frente Trás
Fila Q
O mesmo processo dentro desse laço é feito para v4 e v5. Como nenhum desses 
está marcado, o procedimento sempre entra no condicional da linha 8. O resultado 
é apresentado na Figura 13.
Figura 13
Busca em largura – Vértices v4 e v5
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
V1 V2 V4 V5
Frente Trás
Fila Q
Ao término do laço da linha 7, a linha 18 é executada retirando-se da fila o vértice 
v, que, nesse caso, vale v1, sobrando para serem processados os vértices v2, v4 e v5.
Ao retornar à linha 5, o processo verifica que a fila não está vazia. Na linha 6, 
obtém-se o primeiro elemento da fila, no caso, v2. O laço da linha 7 varre todos os 
elementos adjacentes a v2, no caso {v1, v4, v3}, e, para cada volta do laço, um desses 
vértices é analisado.
Inicia-se com v1, como está marcado, e executa-se o caso contrário na linha 12. 
O condicional da linha 13 verifica se v1 está na fila; como não está, o condicional 
termina, retornando ao próximo vértice adjacente a v2.
O próximo vértice a ser analisado pelo laço da linha 7 é v4. Como já está mar-
cado, executa o caso da linha 12 e, no condicional da linha 13, encontra v4 ainda 
60 Teoria dos Grafos
na fila. Assim, visita-se a aresta de retorno (v2, v4) e termina-se essa volta do laço 
retornando ao próximo vértice adjacente a v2.
Em seguida, analisa-se v3. Como não está marcado, entra no condicional da li-
nha 8, visitando a aresta (v2, v3), marcando o vértice v3 e inserindo v3 na fila. Em 
seguida, finaliza o condicional e retorna ao laço da linha 7. Como v2 não tem mais 
vértices adjacentes, termina-se esse laço e executa-se a linha 18, retirando v2 da fila. 
O resultado pode ser visto na Figura 14.
Figura 14
Busca em largura – Término do processamento de v2
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
V4 V5 V3
Frente Trás
Fila Q
O laço da linha 5 reinicia. Na linha 6, o vértice v4 é atribuído a v e, na linha 7, 
inicia-se o laço sobre todos os elementos adjacentes a v4, a saber, {v3, v2, v1, v5}. 
Analisando o vértice v3, percebe-se que ele já está marcado, então, entra no caso 
contrário da linha 12. Como v3 está na fila, executa a linha 14, que visita a aresta de 
retorno (v4, v3). Ao final, retorna à próxima volta do laço da linha 7.
Analisando o vértice v2, percebe-se que ele já está marcado, então, entra no caso 
contrário da linha 12. Como v2 não está na fila, termina o condicional sem visitar a ares-
ta (pois ela já foi visitada). Ao final, retorna à próxima volta do laço da linha 7.
Também o vértice v1 já está marcado, assim, entra no caso contrário da linha 12. 
Como v1 não está na fila, termina o condicional sem visitar a aresta (pois ela já foi visi-
tada). Ao final, retorna à próxima volta do laço da linha 7.
Já o vértice v5, que também está marcado, entra no caso contrário da linha 
12. Como v5 está na fila, executa a linha 14, que visita a aresta de retorno (v4, v5). 
Ao final, retorna à próxima volta do laço da linha 7. Terminando o laço da linha 7, 
pois os vértices adjacentes de v4 acabaram, a execução do procedimento sai do laço 
e executa a linha 18, removendo v4 da fila. O resultado pode ser visto na Figura 15.
Figura 15
Busca em largura – Término do processamento de v4
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
V5 V3
Frente Trás
Fila Q
Caminho mínimo e árvores geradoras 61
O laço da linha 5 reinicia. Na linha 6, o vértice v5 é atribuído a v e, na linha 7, 
inicia-se o laço sobre todos os elementos adjacentes a v5, a saber, {v4, v1}.
Analisando o vértice v4, percebe-se que ele já está marcado, então, entra no caso 
contrário da linha 12. Como v4 não está na fila, termina o condicional sem visitar a 
aresta (pois ela já foi visitada). Ao final, retorna à próxima volta do laço da linha 7.
O vértice v1 também está marcado, assim, entra no caso contrário da linha 12. 
Como v1 não está na fila, termina o condicional sem visitar a aresta (pois ela já foi 
visitada). Ao final, retorna à próxima volta do laço da linha 7.
Terminando o laço da linha 7, pois os vértices adjacentes de v5 acabaram, sai do 
laço e executa a linha 18, removendo v5 da fila. O resultado pode ser visto na Figura 16.
Figura 16
Busca em largura – Término do processamento de v5
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
V3
Frente Trás
Fila Q
O laço da linha 5 reinicia. Na linha 6, o vértice v3 é atribuído a v e, na linha 7, 
inicia-se o laço sobre todos os elementos adjacentes a v3, a saber, {v4, v2}.
Analisando o vértice v4,, percebe-se que ele já está marcado, então, entra no caso 
contrário da linha 12. Como v4 não está na fila, termina o condicional sem visitar a 
aresta (pois ela já foi visitada). Ao final, retorna à próxima volta do laço da linha 7.
O vértice v2 também está marcado, assim, entra no caso contrário da linha 12. 
Como v2 não está na fila, termina o condicional sem visitar a aresta (pois ela já foi 
visitada). Ao final, retorna à próxima volta do laço da linha 7.
Terminando o laço da linha 7, pois os vértices adjacentes a v3 acabaram, sai 
do laço e executa a linha 18, removendo v3 da fila. O resultado pode ser visto na 
Figura 17.
Figura 17
Busca em largura – Término do processamento de v3
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
Frente Trás
Fila Q
62 Teoria dos Grafos
Já que a fila está vazia, o laço da linha 5 termina e a busca em largura é finaliza-
da. Como resultado, a Figura 18 apresenta a árvore de busca em largura resultante 
da aplicação do algoritmo, que contém o vértice v1 como raiz. Para a composição, 
são usadas somente as arestas visitadas na linha 9 do algoritmo, que são as arestas 
de árvore.
As arestas de árvore encontradas foram: A’ = {(v1, v2), (v1, v4), (v1, v5), 
(v2, v3)}. Assim, o grafo T = (V, A’), resultante do processo de busca em 
largura, também é uma árvore geradora do grafo G = (V, A).
Os procedimentos de busca apresentados foram aplicados 
a grafos não orientados e conexos. Percebe-se que todo grafo 
não orientado conexo tem, pelo menos, uma árvore geradora. 
Nos exemplos mostrados são conseguidas duas árvores gerado-
ras, mas, trocando a ordem de escolha dos vértices, facilmente 
chega-se a outras árvores.
Por suas características, uma árvore com n vértices possui exata-
mente n-1 arestas, portanto, a árvore geradora de um grafo conexo 
não orientado com n vértices tem exatamente n-1 arestas.
Figura 18
Árvore de busca em largura
Fonte: Elaborada pelo autor.
v5 v2
v4 v3
v1
3.2 Árvore Geradora Mínima
Vídeo Encontrar uma árvore geradora mínima é muito importante na teoria dos gra-
fos, pois vários problemas reais podem ser mapeados e solucionados por ela.
Por exemplo, para efetuar o projeto de uma rede de fibra ótica entre os nós, 
desconsiderando redundâncias, é preciso que todos os nós estejam conectados, e 
o objetivo é gastar o mínimo possível. Em um extremo, pode-se conectar todos os 
n nós com todos os outros, criando um grafo completo Kn. Se há um custo consi-
derável na ligação entre nós, este será em média multiplicado por n (n-1)
2
, que é o 
número de arestas que um grafo completo Kn possui.
Assim, dado um grafo conexo, um conjunto de arestas que o mantém – todos os 
vértices são alcançáveis – é uma árvore geradora. Se houver um custo associado, o 
objetivo é conseguir uma árvore geradora mínima.
Supondo que há a necessidade de asfaltar estradas entre cidades, com um dado 
conjunto de municípios e vias, o objetivo é asfaltar determinadosubconjunto para 
que todas as cidades sejam interligadas por vias asfaltadas e que o custo seja míni-
mo (BARROSO, 2014). Nesse caso, vários fatores devem ser analisados e considera-
dos para o custo de pavimentação de vias, como aspectos geológicos, de traçado, 
hidrológicos etc. Assim, para a modelagem do problema, assume-se que essas in-
formações já foram obtidas e que, para a análise matemática, tem-se um grafo no 
qual os vértices são as cidades, as arestas são as estradas que as conectam e cada 
aresta é ponderada com o custo de pavimentação.
Analisando esse grafo, conectar todas as cidades com estradas pavimentadas a 
um custo mínimo significa encontrar um conjunto de estradas a serem asfaltadas 
de tal forma que todas as cidades sejam alcançadas sem grandes valores, isto é, 
não havendo redundância (ciclos). Esse conjunto de arestas, juntamente com seus 
Uma formulação detalhada 
desse problema e das 
técnicas de resolução, 
como a aplicação de 
Árvores Geradoras 
Mínimas e Árvore de 
Steiner, pode ser vista no 
artigo Aplicação de grafos 
em um problema de rede.
BARROSO, M. M. de A. Abakós, v. 
2, n. 2, p. 48-78, 30 maio 2014. 
Disponível em: http://periodicos.
pucminas.br/index.php/abakos/arti-
cle/view/P.2316-9451.2014v2n2p48. 
Acesso em: 29 maio 2020.
Leitura
Caminho mínimo e árvores geradoras 63
vértices incidentes, será uma árvore (pois não possui ciclos) geradora, já que conta 
com todos os vértices do grafo original e é mínima, uma vez que o objetivo é encon-
trar o custo mínimo de pavimentação.
Assim, um dos problemas clássicos em grafos é encontrar uma árvore geradora 
mínima em um grafo não dirigido com custos (ou pesos) nas arestas. Para isso, 
faz-se necessário definir alguns conceitos.
Dado um grafo G não dirigido com custos, o custo de cada aresta 
pode ser positivo ou negativo e o custo de um subgrafo ou uma 
árvore de G é a soma dos custos de cada aresta.
Uma árvore geradora mínima de um grafo G, também conhecida 
como minimum spanning tree (MST), é uma árvore geradora de G com 
custo mínimo. Em outras palavras, é uma árvore geradora com custo 
menor dentre todas as possíveis árvores geradoras de G.
Convém ressaltar que, se todas as arestas tiverem o mesmo custo, 
então, qualquer árvore geradora é mínima, pois conta com o mesmo 
número de arestas, os mesmos custos em cada aresta e, portanto, o 
mesmo custo total. 
Observe o grafo da Figura 19. Claramente, ele conta com várias 
árvores geradores. 
Partindo de v1 como vértice raiz, a Figura 20 apresenta duas 
dessas árvores.
Figura 20
Árvores geradoras
Fonte: Elaborada pelo autor.
v2 v4
v3
v1
2
6
10
v2 v4
v3
v1
2
5
1
Ao calcular o custo da árvore geradora da esquerda, somando os custos das 
arestas, o valor total é 18. Já o valor total da árvore da direita é 8.
De acordo com Kruskal (1956) e Prim (1957), dois algoritmos são apresentados 
para encontrar a MST de um grafo: o algoritmo de Kruskal (concebido em 1956) e 
o algoritmo de Prim (concebido em 1957). Ambos são aplicados a grafos conexos 
ponderados, nos quais os pesos não são negativos.
Figura 19
Grafo ponderado
Fonte: Elaborada pelo autor.
v2 v4
v3
v1
2
6
1
10
5
64 Teoria dos Grafos
Os algoritmos que encontram uma MST são de busca gulosa, isto é, a cada passo 
selecionam a melhor aresta possível para compor a árvore. O Algoritmo 4 apresen-
ta o algoritmo de Prim para encontrar uma árvore geradora mínima (PRIM, 1957).
Algoritmo 4
Árvore Geradora Mínima – Algoritmo de Prim
Dados: Grafo conexo ponderado G = (V, A)
1 varesta gera um grafo acíclico.
A implementação mais eficiente 
conhecida tem complexidade 
O(|A| log |V|) e faz uso de 
otimizações na representação e 
verificação de conjuntos disjuntos. 
A estrutura chamada UNION-FIND, 
usando técnicas como union 
by rank e path compression 
(CP-ALGORITHMS, 2020), é capaz 
de melhorar o desempenho do 
algoritmo de Kruskal.
Saiba mais
3.3 Caminho Mínimo
Vídeo Percebe-se que os processos de busca em profundidade e largura apresentados 
caminham por todos os vértices do grafo, mas claramente é possível alterá-los para 
partir de um vértice v e chegar a outro vértice w. Assim, consegue-se encontrar uma 
sequência de vértices que determina um caminho de v a w.
O custo de um caminho em grafos ponderados, isto é, com pesos nas arestas, 
é dado pela soma dos pesos de todas as arestas que fazem parte do caminho. Em 
um grafo não ponderado, define-se como caminho mínimo entre o vértice v1 e v2 o 
caminho de menor tamanho, isto é, menor número de arestas entre v1 e v2.
Em razão da natureza do procedimento de busca em profundidade, não há 
como garantir que o caminho encontrado é o caminho mínimo. Para isso, em gra-
fos não ponderados, deve-se efetuar uma busca em largura pelo grafo.
66 Teoria dos Grafos
Para grafos ponderados, o caminho mínimo entre o vértice v1 e v2 é o caminho 
cuja soma dos pesos nas arestas possui o menor valor. Assim, em grafos pondera-
dos, o caminho mínimo pode não ser aquele que possui menor número de arestas.
O algoritmo de Dijkstra, publicado em 1959, rotula todos os vértices do grafo 
por meio de um vértice origem, indicando qual o menor caminho entre esse vértice 
e qualquer outro do grafo. Assim, ao final do algoritmo, consegue-se o caminho 
mínimo entre o vértice origem e qualquer outro vértice, bastando caminhar pela 
rotulação efetuada partindo do vértice destino.
Fonte: Adaptado de Goldbarg; Goldbarg, 2012.
Algoritmo 6
Caminho Mínimo em Grafo Ponderado – Algoritmo de Dijkstra
Dados: Grafo conexo ponderado G = (V, A), D = {dij}, em que dij é o peso da aresta entre o 
vértice i e j, um vértice inicial da busca s
1 PARA v ∈ V FAÇA
2 rot[v]e o processo retorna ao laço da linha 7. Como o conjunto 
V’ ainda não é vazio, mais uma volta desse laço é executada.
Na linha 8 é escolhido o elemento de V’ = {v2, v3, v4} que possui 
a menor distância dt, nesse caso, v4. Na linha 9, o vértice v4 é 
removido de V’, portanto, V’ = {v2, v3}. Já na linha 10 busca-se e 
varre-se todos os vértices adjacentes a v4, nesse caso, {v2, v3, v5}.
Para v2, verifica-se se dt[v4] (que é 5), acrescido do custo da 
aresta (v4, v2) (que é 5), é menor que dt[v2] (que é 10). Como não 
é menor, não faz qualquer atualização, e o grafo e as estruturas 
são mantidos da mesma forma. O laço, então, retorna para pro-
cessar o próximo adjacente a v4.
Para v3, checa-se se dt[v4] (que é 5), acrescido do custo da 
aresta (v4, v3) (que é 6), é menor que dt[v3] (que é 8). Como não 
é menor, não faz qualquer atualização, e o grafo e as estruturas 
Figura 24
Processamento 
de (v1, v3)
Fonte: Elaborada pelo autor.
v2 v4
v5v3
v1
8
5
1
3
6
10
2
V1 8
V1 10
0 0
0 ∞
0 ∞
Figura 25
Processamento 
de (v1, v5)
Fonte: Elaborada pelo autor.
v2 v4
v5v3
v1
8
5
1
3
6
10
2
V1 8
V1 10
0 0
V1 3
0 ∞
Figura 26
Processamento 
de (v5, v4)
Fonte: Elaborada pelo autor.
v2 v4
v5v3
v1
8
5
1
3
6
10
2
V1 8
V1 10
0 0
V1 3
V5 5
Caminho mínimo e árvores geradoras 69
são mantidos da mesma forma. O laço, desse modo, retorna para processar o 
próximo vértice adjacente a v4.
Para v5, verifica-se se dt[v4] (que é 5), acrescido do custo da aresta (v4, v5) (que é 
2), é menor que dt[v5] (que é 3). Como não é menor, não faz qualquer atualização, e 
o grafo e as estruturas são mantidos da mesma forma. O laço, então, retorna para 
processar o próximo vértice adjacente a v4.
Como não há mais vértices adjacentes a v4, o laço das linhas 10 a 15 termina e 
o processo retorna ao laço da linha 7. Como o conjunto V’ ainda não é vazio, mais 
uma volta desse laço é executada.
Na linha 8 é escolhido o elemento de V’ = {v2, v3} que possui a menor distância dt, 
nesse caso, v3. Na linha 9, o vértice v3 é removido de V’, portanto, V’ = {v2}. A linha 10 
busca e varre todos os vértices adjacentes a v3, nesse caso, {v1, v2, v4}.
Para v1, verifica-se se dt[v3] (que é 8), acrescido do custo da aresta (v3, v1) (que é 
8), é menor que dt[v1] (que é 0). Como não é menor, não se faz qualquer atualiza-
ção, e o grafo e as estruturas são mantidos da mesma forma. O laço, assim, retorna 
para processar o próximo vértice adjacente a v3.
Para v2, checa-se se dt[v3] (que é 8), acrescido do custo da aresta (v3, v2) (que é 1), 
é menor que dt[v2] (que é 10). Como é menor, a distância dt[v2] recebe 9 e o rótulo 
rt[v2] assume o vértice v3. O laço, desse modo, retorna para processar o próximo 
vértice adjacente a v3. O grafo e as estruturas ficam como na Figura 27.
Para v4, verifica-se se dt[v3] (que é 8), acrescido do custo da 
aresta (v3, v4) (que é 6), é menor que dt[v4] (que é 5). Como não 
é menor, não faz qualquer atualização, e o grafo e as estruturas 
são mantidos da mesma forma. O laço, então, retorna para pro-
cessar o próximo vértice adjacente a v3.
Como não há mais vértices adjacentes a v3, o laço das linhas 10 
a 15 termina e o processo retorna ao laço da linha 7. Como o con-
junto V’ ainda não é vazio, mais uma volta desse laço é executada.
Na linha 8, é escolhido o elemento de V’ = {v2} que possui a 
menor distância dt, nesse caso, v2, que é removido de V’, na linha 
9, portanto, V’ = Ø. Na linha 10 busca-se e varre-se todos os vérti-
ces adjacentes a v2, nesse caso, {v1, v3, v4}.
Para v1, checa-se se dt[v2] (que é 9), acrescido do custo da ares-
ta (v2, v1) (que é 10), é menor que dt[v1] (que é 0). Como não é 
menor, não é feita qualquer atualização, e o grafo e as estruturas 
são mantidos da mesma forma. O laço retorna para processar o 
próximo vértice adjacente a v2.
Para v3, verifica-se se dt[v2] (que é 9), acrescido do custo da aresta (v2, v3) (que é 
1), é menor que dt[v3] (que é 8). Como não é menor, não é feita qualquer atualiza-
ção, e o grafo e as estruturas são mantidos da mesma forma. O laço retorna para 
processar o próximo vértice adjacente a v2.
Para v4, checa-se se dt[v2] (que é 9), acrescido do custo da aresta (v2, v4) (que é 
5), é menor que dt[v4] (que é 5). Como não é menor, não é feita qualquer atualiza-
Figura 27
Processamento de (v3, v2)
Fonte: Elaborada pelo autor.
v2 v4
v5v3
v1
8
5
1
3
6
10
2
V1 8
V3 9
0 0
V1 3
V5 5
70 Teoria dos Grafos
ção, e o grafo e as estruturas são mantidos da mesma forma. O laço retorna para 
processar o próximo vértice adjacente a v2.
Como não há mais vértices adjacentes a v2, o laço das linhas 10 a 15 termina e o 
processo retorna ao laço da linha 7. Como o conjunto V’ é vazio, o procedimento e 
as estruturas de rótulos e distâncias ficam como na Figura 27.
Percebe-se que as distâncias mínimas entre v1 e cada um dos vértices são dadas 
de maneira direta pela estrutura dt. Já o caminho mínimo precisa ser calculado 
caminhando-se entre os rótulos, iniciando do vértice destino.
Por exemplo, para calcular o caminho mínimo entre v1 e v4, verifica-se o rótulo 
rot[v4], que possui v5. Isso indica que o caminho partindo de v1 passa por v5 para 
chegar em v4, isto é, a aresta (v5, v4) faz parte do caminho.
Analisando v5, percebe-se que seu rótulo rot[v5] possui v1. Significa que o cami-
nho passa por v1, isto é, a aresta (v1, v5) faz parte do caminho. Como se chegou em 
v1 (vértice origem), não há mais o que calcular, portanto, o caminho entre v1 e v4 é 
dado por: {(v1, v5), (v5, v4)}.
Efetuando-se todos os cálculos, as distâncias mínimas entre v1 e os demais vér-
tices do grafo, bem como os caminhos mínimos, são:
 • De v1 para v2 : distância 9, caminho {(v1, v3), (v3, v2)}
 • De v1 para v3 : distância 8, caminho {(v1, v3)}
 • De v1 para v4 : distância 5, caminho {(v1, v5), (v5, v4)}
 • De v1 para v5 : distância 3, caminho {(v1, v5)}
Assim, percebe-se que o algoritmo de Dijkstra varre o grafo todo desde de um 
vértice inicial e dá como resultado a distância e o caminho entre o vértice inicial es-
colhido e cada um dos vértices do grafo. Para encontrar o caminho entre um vértice 
qualquer e o vértice inicial, basta caminhar pelos rótulos em sequência.
Para digrafos (grafos direcionados), o algoritmo é o mesmo, bastando respeitar as 
orientações das arestas ao retornar a lista de vértices adjacentes, linha 10 do Algoritmo 6.
Uma melhoria no algoritmo de Dijkstra apresentado é na linha 10. Nesse pon-
to, o algoritmo retorna todos os vértices adjacentes a v, mas pode-se melhorá-lo 
para que sejam considerados somente vértices que ainda não foram analisados, 
isto é, aqueles pertencentes a V’
CONSIDERAÇÕES FINAIS
Muitos problemas em grafos, bem como problemas reais mapeados para grafos, 
são essencialmente resolvidos pela aplicação de algoritmos de busca ou adaptações. 
Assim, estes representam um papel importante no entendimento e nas aplicações da 
teoria de grafos.
Para grafos não ponderados, foi apresentado que a busca em largura é capaz de en-
contrar o caminho mínimo entre dois vértices, levando em consideração que o tamanho 
ou o custo de um caminho não ponderado é dado em número de arestas. Para grafos 
ponderados, o tamanho ou o custo de um caminho é gerado pela soma dos custos de 
suas arestas, assim, faz-se necessário o uso do algoritmo de Dijkstra, o qual calcula o 
Caminho mínimo e árvores geradoras 71
custo dos caminhos entre um vértice inicial e todos os demais vértices do grafo. Vale 
ressaltar que o algoritmo de Dijkstra exige a positividade dos custos das arestas.
Já no caso de grafos em que o custo das arestas pode ser negativo, deve-se aplicar 
o algoritmo de Bellman-Ford. E para encontrar o caminho mínimo entre todos os pa-
res de vértices de um grafo, utiliza-se o algoritmo de Floyd-Warshall.
Outro problema apresentado foi o de encontrar a árvore geradora mínima em 
grafos conexos e ponderados, também usada em vários problemas em grafos. Uma 
árvore geradora é umaárvore formada por todos os vértices do grafo, de modo que 
o custo da árvore é a soma dos custos individuais de suas arestas. Para tanto, foram 
apresentados os algoritmos clássicos de Prim e Kruskal.
ATIVIDADES
1. Considere o grafo a seguir.
Aplique o algoritmo de busca em profundidade, 
iniciando em v1. Dê a árvore de busca em 
profundidade resultante.
Restrição: para efeito de escolha de vértices 
a serem analisados, assuma que os vértices 
do grafo estão ordenados e que você sempre 
escolhe o qual tem índice menor. Por exemplo, 
se em um ponto de escolha há os vértices v6 e 
v3, você deve selecionar, primeiramente, o v3.
2. Observe o grafo a seguir.
Aplique o algoritmo de busca em largura, 
iniciando em v1. Dê a árvore de busca em lar-
gura resultante.
Restrição: para efeito de escolha dos 
vértices a serem analisados, assuma que os 
vértices do grafo estão ordenados e que você 
sempre escolhe o qual tem índice menor. Por 
exemplo, se em um ponto de escolha há os 
vértices v6 e v3, você deve selecionar, primei-
ramente, o v3.
v5 v3
v2
v1
v4
v6
v5 v3
v2
v1
v4
v6
72 Teoria dos Grafos
3. Dado o grafo a seguir, aplique o algoritmo de Prim, iniciando em v1, e encontre a 
árvore geradora mínima.
v5 v3
v2
v1
v4
v6
1
10
4
2
35
3 4
4. Dado o grafo a seguir, aplique o algoritmo de Kruskal, iniciando em v1, e encontre a 
árvore geradora mínima.
v5 v3
v2
v1
v4
v6
1
10
4
2
35
3 4
5. Dado o grafo a seguir, aplique o algoritmo de Dijkstra e encontre todos os rótulos 
e todas as distâncias, partindo do vértice v1.
v5 v3
v2
v1
v4
v6
1
10
4
2
35
3 4
Caminho mínimo e árvores geradoras 73
REFERÊNCIAS
BARROSO, M. M. de A. Aplicação de grafos em um problema de rede. Abakós, v. 2, n. 2, p. 48-78, 30 
maio 2014. Disponível em: http://periodicos.pucminas.br/index.php/abakos/article/view/P.2316-
9451.2014v2n2p48. Acesso em: 29 maio 2020.
FEOFILOFF, P. Algoritmos para Grafos via Sedgewick, 2020. Página inicial. Disponível em: https://www.ime.
usp.br/~pf/algoritmos_para_grafos/. Acesso em: 29 maio 2020.
FLOYD, R. W. Algorithm 97: Shortest path. Communications of the ACM, v. 5, n. 6, p. 345, jun. 1962. Disponível 
em: https://dl.acm.org/doi/10.1145/367766.368168. Acesso em: 29 maio 2020.
FREDMAN, M. L.; TARJAN, R. E. Fibonacci heaps and their uses in improved network optimisation 
algorithms. Journal of the ACM, v. 34, n. 3, p. 596-615, jul. 1987. Disponível em: https://dl.acm.org/
doi/10.1145/28869.28874. Acesso em: 29 maio 2020. 
GOLDBARG, M. C.; GOLDBARG, E. Grafos: conceitos, algoritmos e aplicações. 1. ed. Rio de Janeiro: Elsevier, 
2012.
JOHNSON, D. B. Priority queues with update and finding minimum spanning trees. Information Processing 
Letters, v. 4, n. 3, p. 53-57, dez. 1975. Disponível em: https://www.sciencedirect.com/science/article/abs/
pii/0020019075900010. Acesso: 29 maio 2020.
KRUSKAL, J. B. On the shortest spanning subtree of a graph and the traveling salesman problem. 
Proceedings of the American Mathematical Society, v. 7, n. 1, p. 48-50, fev. 1956. Disponível em: https://www.
jstor.org/stable/2033241?seq=1. Acesso em: 29 maio 2020. 
PRIM, R. C. Shortest connection networks and some generalizations. The Bell System Technical Journal, 
v. 36, n. 6, p. 1389-1401, nov. 1957. Disponível em: https://ieeexplore.ieee.org/document/6773228. Acesso 
em: 29 maio 2020. 
SZWARCFITER, J. L. Teoria Computacional de Grafos. Rio de Janeiro: Elsevier, 2018.
74 Teoria dos Grafos
4
Grafos eulerianos e hamiltonianos
Este capítulo trata de grafos que têm certas características específicas: 
os eulerianos e os hamiltonianos. São apresentados teoremas que carac-
terizam esses grafos, algumas aplicações e alguns algoritmos.
Para tanto, o estudo está organizado do seguinte modo: na Seção 4.1 
são abordados os conceitos que definem quando um grafo é euleriano, os 
teoremas que apresentam condições necessárias e suficientes, e os algo-
ritmos para a construção de um caminho euleriano. Já na Seção 4.2 estão 
descritas as condições para que um grafo seja hamiltoniano, bem como os 
teoremas que colocam as condições suficientes (mas não necessárias) e a 
discussão de algoritmos para encontrar um caminho hamiltoniano.
4.1 Grafos eulerianos 
Vídeo Os grafos eulerianos possuem esse nome graças a Leonhard Euler (1707–1783), 
que, em 1736, resolveu o famoso problema das sete pontes de Königsberg, dando 
origem à teoria dos grafos (SZWACFITER, 2018). O enigma se passa na cidade de 
Kaliningrado, que, à época, era conhecida como Königsberg. A cidade é cortada 
pelo Rio Prególia e possuía sete pontes (Figura 1), das quais duas foram destruídas 
por bombardeios na Segunda Guerra Mundial.
Figura 1
As pontes de Königsberg. 
As marcações em ver-
melho indicam as pontes 
destruídas na Segunda 
Guerra Mundial.
Se
rg
ey
 M
er
ku
lo
v/
Sh
ut
te
rs
to
ck
Figura 2
Grafo do problema das 7 
pontes de Königsberg
v1
v2
v3
v4
Fonte: Elaborada pelo autor.
Grafos eulerianos e hamiltonianos 75
4.1 Grafos eulerianos 
Vídeo Os grafos eulerianos possuem esse nome graças a Leonhard Euler (1707–1783), 
que, em 1736, resolveu o famoso problema das sete pontes de Königsberg, dando 
origem à teoria dos grafos (SZWACFITER, 2018). O enigma se passa na cidade de 
Kaliningrado, que, à época, era conhecida como Königsberg. A cidade é cortada 
pelo Rio Prególia e possuía sete pontes (Figura 1), das quais duas foram destruídas 
por bombardeios na Segunda Guerra Mundial.
Figura 1
As pontes de Königsberg. 
As marcações em ver-
melho indicam as pontes 
destruídas na Segunda 
Guerra Mundial.
Se
rg
ey
 M
er
ku
lo
v/
Sh
ut
te
rs
to
ck
Figura 2
Grafo do problema das 7 
pontes de Königsberg
v1
v2
v3
v4
Fonte: Elaborada pelo autor.
Na época, havia uma discussão se era possível atravessar todas as pontes, ini-
ciando e retornando na mesma margem, sem repetir qualquer uma delas. Em 1736, 
Euler provou que não era possível e, para isso, mapeou o problema com pontos e 
linhas ligando-os, conforme a Figura 2. Por esse diagrama, 
indicou as condições necessárias e suficientes para que fos-
se possível atravessar todas as pontes somente uma vez, 
iniciando e terminando na mesma margem, e destacou que 
as pontes de Königsberg não possuíam tais condições. As-
sim, surgiu a teoria dos grafos.
Como mencionado, ao longo desta seção serão apre-
sentadas as condições necessárias e suficientes para que 
um grafo seja euleriano, bem como a discussão dos teo-
remas e algoritmos envolvidos para a construção de ciclos 
eulerianos.
Dado um grafo não dirigido e conexo G = (V, A), um ca-
minho euleriano é um caminho que passa por todas as 
arestas do grafo somente uma vez. Ou seja, é uma sequên-
cia de vértices, v1, v2, ..., vk, tal que vi ∈ V e (vi, vi+1) ∈ A, para 
todo i, 1 ≤ i ≤ k, de modo que todas as arestas (vi, vi+1) do 
grafo estão presentes nesse caminho somente uma vez.
Considere o grafo G = (V, A) da Figura 3 e o mesmo grafo 
G com arestas rotuladas da Figura 4.
Figura 3
Grafo com caminho euleriano
v1
v2
v3
v4
v5
v6
v7
Fonte: Elaborada pelo autor.
76 Teoria dos Grafos
Figura 4
Grafo com arestas rotuladas e caminho euleriano
v1
v2
v3
v4
v5
v6
v7
a1
a2
a3
a4
a5
a6
a7
a8
Fonte: Elaborada pelo autor.
Na Figura 4, o grafo não dirigido G = (V, A) pode ser descrito por meio de seus 
componentes:
 • Vértices: V = {v1, v2, v3, v4, v5, v6, v7}
 • Arestas: A = {(v1, v2), (v2, v3), (v3, v4), (v4, v5), (v4, v2), (v4, v6), (v6, v7), (v7, v2)}
 • Arestas nomeadas:
a1 = (v1, v2)
a2 = (v7, v2)
a3 = (v4, v2)
a4 = (v4, v6)
a5 = (v6, v7)
a6 = (v4, v5)
a7 = (v3, v4)
a8 = (v2, v3)
Dado o caminho {v1, v2, v3, v4, v2, v7, v6, v4, v5}, é possível passar por todas as 
arestas somente uma vez na seguinte ordem: a1, a8, a7, a3, a2, a5, a4, a6. Portanto, 
diz-se que o grafo G possui um caminho euleriano. Se este for um ciclo, isto é, 
começar e terminar no mesmo vértice, é chamado de ciclo euleriano.
Considere o grafo G = (V, A) apresentado na Figura 5, contendo arestasrotuladas.
Grafos eulerianos e hamiltonianos 77
Figura 5
Grafo com arestas rotuladas e ciclo euleriano
v1 v2
v4v5
v3v6v7
a1
a2
a3
a4
a5
a10
a9
a6
a7
a8
Fonte: Elaborada pelo autor.
O grafo G (Figura 5) pode, também, ser descrito por meio de seus elementos:
 • Vértices: V = {v1, v2, v3, v4, v5, v6, v7}
 • Arestas: A = {(v1, v2), (v2, v3), (v3, v4), (v4, v5), (v4, v2), (v4, v6), (v6, v7), (v7, v2), (v1, v7), 
(v7, v5)}
 • Arestas nomeadas:
 • a1 = (v1, v2)
 • a2 = (v7, v2)
 • a3 = (v4, v2)
 • a4 = (v4, v6)
 • a5 = (v6, v7)
 • a6 = (v4, v5)
 • a7 = (v3, v4)
 • a8 = (v2, v3)
 • a9 = (v1, v7)
 • a10 = (v7, v5)
Dado o caminho {v7, v5, v4, v6, v7, v2, v4, v3, v8, v1, v7}, percebe-se que é possível 
passar por todas as arestas do grafo, somente uma vez, a saber: a10, a6, a4, a5, a2, a3, 
a7, a8, a1, a9. Portanto, trata-se de um caminho euleriano. Também vê-se que esse 
caminho é um ciclo e que, desse modo, o grafo contém um ciclo euleriano.
Denomina-se grafo euleriano um grafo que possui um ciclo euleriano. Assim, 
pode-se dizer que o grafo da Figura 5 é euleriano.
Se um grafo possui um caminho euleriano, mas não um ciclo euleriano, então, 
é dito semieuleriano. Para que um grafo semieuleriano se torne euleriano, deve-se 
inserir uma aresta entre o vértice de origem e o de término do caminho euleriano 
78 Teoria dos Grafos
(NICOLETTI; HRUSCHKA JUNIOR, 2018). O grafo da Figura 3, por exemplo, é um gra-
fo semieuleriano. Adicionando-se a aresta (v1, v5), consegue-se um grafo euleriano, 
pois resulta o seguinte ciclo: {v1, v2, v3, v4, v2, v7, v6, v4, v5, v1}, que é um ciclo euleriano. 
A Figura 6, por sua vez, apresenta o mesmo grafo com a aresta inserida (represen-
tada pela linha tracejada para facilitar a visualização).
Figura 6
Grafo semieuleriano com aresta inserida
v1
v2
v4
v5
v3
v6
v7
Fonte: Elaborada pelo autor.
Convém ressaltar que um grafo desconexo não pode ser euleriano, pois não há 
a possibilidade de se conseguir um ciclo euleriano, isto é, passando por todas as 
arestas, visto que parte do grafo está desconectada.
Observe a seguir dois teoremas importantes que caracterizam os grafos 
eulerianos.
Teorema 1
Seja o grafo G = (V, A), tal que o grau de todos os vértices é, pelo menos, dois, 
então, G contém um ciclo.
Prova: se o grafo G não for simples, ou seja, possuir laços (arestas incidindo no 
mesmo vértice) ou arestas paralelas (arestas distintas incidindo sobre os mesmos 
vértices), claramente G tem um ciclo, pois um laço é um ciclo de comprimento 1, e 
duas arestas paralelas formam um ciclo de tamanho 2.
Se o grafo G for simples, assume-se um vértice qualquer de G, v0, tomado como 
ponto de partida. Assim, como grau(v0) ≥ 2, consegue-se escolher uma aresta, a1, 
que incide em outro vértice diferente de v0 (caso fosse obrigatório voltar a v0, o gra-
fo não seria simples). Como grau(v1) deve ser maior ou igual a 2, seleciona-se outra 
aresta, a2, que incide em outro vértice diferente de v1, por exemplo, v2. O processo 
Grafos eulerianos e hamiltonianos 79
continua até que seja escolhida uma aresta ei, que incida nos vértices vi-1 e vi, de 
modo que vi-1 ≠ vi. Como G tem um número finito de vértices, eventualmente será 
necessário escolher uma aresta que incida sobre um vértice, chamado de vk, o qual 
já foi escolhido. Assim, se o vértice vk foi escolhido duas vezes, o caminho entre sua 
primeira escolha até a sua segunda escolha é um ciclo, pois os vértices pertencen-
tes são distintos: o caminho inicia em vk e termina em vk.
Já o Teorema 2 caracteriza os grafos eulerianos pelo grau de seus vértices. Esse 
teorema apresenta a condição necessária e suficiente para que um grafo seja eu-
leriano. A prova da ida foi dada por Euler (1736) e a da volta por Hierholzer (1873) 
(BOAVENTURA NETTO, 2003).
Teorema 2
Seja o grafo conexo G = (V, A). G é um grafo euleriano se, e somente se, o grau 
de todo vértice de G for par.
Prova de ida →: se o grafo G é euleriano, o grau de todo vértice de G é par.
Considere que o grafo G é euleriano, portanto, possui um ciclo que passa por 
todas as arestas de G somente uma vez. Caminhando pelo ciclo euleriano, ao pas-
sar por um vértice qualquer, deve-se ter duas arestas incidentes, uma para chegar 
ao vértice e outra para sair do vértice. Sendo assim, o grau de todo vértice do ciclo 
é par e o grau de todo vértice de G é par.
Prova de volta ←: se o grau de todo vértice de G é par, então, G é euleriano.
Essa demonstração será feita pela indução no número de arestas a = |A(G)|. 
Considere que o grau de todo vértice de G é par.
Base da indução: o teorema é verdade para o grafo com número de arestas 
igual a zero (a = 0), pois G é conexo, tem somente um vértice.
Passo indutivo: assuma que a > 1 (o grafo possui mais de uma aresta) e que 
o teorema é válido para todo grafo com número de arestas menor que a. Isto 
é, se o grafo possui vértices com grau par e menos do que a arestas, então, é 
euleriano.
Hipótese de indução: o teorema é válido para todo grafo com número de ares-
tas menor que a. Se um grafo possui menos que a arestas e o grau de todos os seus 
vértices é par, é euleriano.
Como G é conexo e o grau de seus vértices é par, estes devem possuir grau 
maior que 2. Como a quantidade de arestas de G é a > 1, o número de vértices 
de G, V(G) é maior ou igual a 2. Assim, pelo Teorema 1, o grafo possui um ciclo 
C = {v1, v2, ..., vk, v1}.
Considere G’ o grafo resultante da retirada das arestas participantes do ciclo C, 
ou seja, G’ = (V, A \ A(C)). Como cada vértice em C participa do ciclo com um vértice 
de entrada e outro de saída, a retirada das arestas pertencentes a C, para gerar 
80 Teoria dos Grafos
o grafo G’, remove graus dos vértices aos pares, mantendo a propriedade de que 
todos os vértices têm grau par.
Assim, as componentes conexas de G’ contêm somente vértices com grau par. 
Sejam G’1, G’2, ..., G’l as componentes conexas não triviais (que possuem mais de um 
vértice e mais de uma aresta) de G’, claramente |A(G’i)|de Königsberg
Euler descobriu que só seria possível passar por cada ponte uma única vez caso hou-
vesse nenhum ou dois pontos de onde saísse um número ímpar de caminhos. Assim, 
para que fosse possível chegar em um ponto e depois sair por uma aresta diferente, 
cada ponto deveria conter um número par de arestas (um para entrar, outro para sair). 
Os dois pontos com número ímpar de caminhos representam o início e o final do per-
curso, pois não precisam de uma aresta para entrar e uma para sair. Se não houvesse 
um número ímpar de caminhos, o percurso começaria e terminaria no mesmo ponto.
O autor, então, provou que para um grafo conexo ser euleriano, isto é, possuir 
um ciclo que passe por todas as arestas de um grafo somente uma vez, iniciando 
e terminando no mesmo vértice, todos os vértices precisam possuir um número 
par de arestas incidentes. O artigo de Euler foi considerado o primeiro resultado da 
teoria dos grafos, uma vez que continha o primeiro teorema provado dessa nova 
área, o qual determinou um método para solucionar problemas desse tipo.
Introdução ao estudo dos grafos 11
Outros problemas também foram resolvidos pela teoria dos grafos, como a colo-
ração de mapas. Determinar o mínimo de cores necessário para se colorir o desenho 
de um mapa era uma difícil missão, até que Francis Guthrie (1831–1899) conjecturou, 
em 1852, que era preciso, no mínimo, quatro cores. Mas apenas em 1976 essa hipó-
tese foi comprovada por Kenneth Appel (1932–2013) e Wolfgang Haken (1928–), com 
a ajuda de um IBM 360. A solução de Appel e Haken foi a construção de um programa 
que verificava todos os possíveis exemplos de mapas (1936 ao todo), sendo esse o 
primeiro teorema matemático provado com o auxílio de um computador, o que tam-
bém gerou controvérsia. A descoberta ficou conhecida como o teorema das quatro 
cores. A figura a seguir mostra o mapa do Brasil colorido com quatro cores, sendo os 
estados adjacentes coloridos com cores diferentes.
Filip Bjorkm
an/Shutterstock
Apesar de o artigo de Euler ser o primeiro resultado da teoria dos grafos, o ter-
mo foi utilizado pela primeira vez, com a conotação aqui apresentada, por James 
Joseph Sylvester (1814–1897) e Arthur Cayley (1821–1895). Em 1857, os estudiosos 
aplicaram os conceitos de grafos à química, enumerando isômeros de hidrocar-
bonetos, visto que toda molécula também pode ser representada por um diagra-
ma. O termo grafo apareceu nas palavras dos autores em um artigo publicado em 
1878, no primeiro volume do American Journal of Mathematics Pure and Applied, na 
revista Nature.
Em 1859, William Rowan Hamilton (1805–1865) elaborou um jogo chamado 
icosiano ou viagem à volta do mundo, inspirado pela prática de caixeiro-viajante. 
O objetivo era encontrar caminhos e circuitos no grafo dodecaédrico, satisfazendo 
determinadas condições, como achar um circuito que passasse uma única vez por 
cada vértice do grafo (conhecido como caminho hamiltoniano).
Em 1930, Kazimierz Kuratowski (1896–1980) encontrou uma condição 
necessária e suficiente para a planaridade de um grafo (desenhar um grafo com 
arestas que não se cruzam). Já o primeiro livro didático sobre grafos foi escrito por 
Dénes König (1884–1944) em 1936.
IBM 360 é um mainframe lan-
çado pela empresa International 
Business Machines Corporation 
(IBM) em 1964. Trata-se de um 
dos primeiros computadores 
fabricados com a utilização de 
circuitos integrados.
Saiba mais
caixeiro-viajante: representante 
de vendas; uma pessoa que vendia 
produtos em outras cidades e que, 
para isso, fazia muitas viagens.
Glossário
dodecaedro: sólido contendo 12 
faces, limitado por polígonos, com 
30 arestas e 20 vértices.
Glossário
12 Teoria dos Grafos
Em 1962, Lester Randolph Ford (1886–1967) e Delbert Ray Fulkerson (1924–
1976) desenvolveram a teoria dos fluxos em redes, um dos mais importantes resul-
tados da teoria dos grafos. Esse estudo é muito usado hoje em dia na distribuição 
de energia, na capacidade de redes de computadores, entre outras aplicabilidades, 
possibilitando o mapeamento e a análise dos fluxos em redes.
Atualmente, os grafos aparecem em várias áreas e modelam problemas di-
versos. O mapeamento de amigos em uma rede social é um exemplo disso, sen-
do os vértices as pessoas e as arestas a relação de amizade entre elas. A própria 
internet pode ser vista como um grafo, em que cada dispositivo conectado é um 
vértice e cada conexão, com ou sem fio, é uma aresta. Até mesmo aplicativos 
de mapas usam algoritmos de grafos para traçar uma rota entre dois pontos e 
calcular tempos de viagem. Redes de telefonia, saneamento básico, distribuição 
de energia, transporte público, todos esses serviços são exemplos da aplicação 
de grafos.
1.2 Noções e definições básicas
Vídeo Um grafo G é um par (V, A) em que V é um conjunto não vazio de vértices, tam-
bém representado por V (G), e A é um conjunto finito de arestas, também represen-
tado por A (G). Cada aresta é um par não ordenado (v, w) que pode ser denotado 
como vw ou wv, sendo v, w ∈ V. Uma aresta vw incide em v e w, sendo estes pontas 
da aresta (BOAVENTURA NETTO; JURKIEWICZ, 2009).
No geral, usa-se uma representação gráfica de um grafo para facilitar o entendi-
mento, por exemplo, o grafo G = (V, A):
V = {v1, v2, v3, v4, v5}
A = {(v1, v2), (v2, v3), (v2, v4), (v4, v5), (v2, v5), (v4, v4), (v1, v2)}
O grafo G pode ser visto da seguinte maneira:
v4
v5
v3
v2
v1
Figura 1
Grafo G
Fonte: Elaborada pelo autor.
Para facilitar o entendimento, pode-se nomear as arestas da seguinte forma:
V = {v1, v2, v3, v4, v5}
A = {a1, a2, a3, a4, a5, a6, a7}
Tal que: a1 = (v1, v2 ), a2 = (v2, v3 ), a3 = (v2, v4), a4 = (v4, v5), a5 = (v2, v5), a6 = (v4, v4), a7 = (v1, v2)
No filme Gênio Indomável, 
Will Hunting (Matt Damon) 
é faxineiro em uma univer-
sidade e possui um grande 
talento para a matemá-
tica. Em uma das cenas, 
o professor Lambeau 
(Stellan Skarsgård) deixa 
um problema de grafos 
no quadro como desafio 
para seus alunos de 
pós-graduação e Hunting o 
resolve, impressionando o 
professor e seus alunos.
Direção: Gus Van Sant Jr. Estados 
Unidos: Miramax, 1997. 
Filme
Introdução ao estudo dos grafos 13
Então, representa-se da seguinte maneira o que é chamado grafo rotulado:
Figura 2
Grafo com arestas nomeadas
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
a6
a4
a5
a2
a7
a1
a3
Se no grafo G todas as suas arestas (v, w) são tais que v ≠ w e não existem duas 
arestas diferentes que incidem nos mesmos vértices, diz-se que o grafo é simples. 
O grafo com arestas nomeadas (Figura 2) não é simples, pois tem duas arestas en-
tre os vértices v1 e v2, e o vértice v4 tem uma aresta com ele mesmo.
Se um grafo é simples e possui arestas entre todos os seus vértices é denomina-
do completo. Por exemplo, os grafos da Figura 3 são completos.
Figura 3
Grafos completos
v5v4
v1 v3
v2
v1 v2
v3v4
v1 v3
v2v2
v1
Fonte: Elaborada pelo autor.
Assim, o grafo G = (V, A) é completo se A = V2, em que V2 representa o conjunto 
de todos os pares não ordenados de elementos de V. Assim, G = (V, A) é completo 
se, e somente se, 
A
v, w ∈ V, v ≠ w, 
E
a ∈ A, a = (v, w) (Figura 4).
Figura 4
Grafo completo
Fonte: Elaborada pelo autor.
v4 v5
v3
v2
v1
14 Teoria dos Grafos
Os grafos completos são também denominados Kn, em que n é o número corres-
pondente à quantidade de vértices. Assim, na Figura 3, tem-se K1, K2, K3, K4, K5.
O complemento de um grafo G = (V, A) é o grafo G = (V, V2\A). Isto é, assumindo o 
grafo completo formado por todos os vértices V, o grafo complemento G é formado 
por todas as arestas resultantes da retirada das arestas A do grafo G.
Por exemplo, seja o grafo G = (V, A), como na figura a seguir (Figura 5), seu com-
plemento (Figura 6) é o grafo G = (V, V2\A).
Figura 5
Grafo g
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Figura 6
Complemento do grafo g
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Essas definições apresentadas servem de base para o estudo dos grafos. Por 
meioé verdade
2. ∀k P(r) é verdade para todo r, 1 ≤ r ≤ k → P(k+1)
A diferença recai sobre a proposição 2, que, no primeiro princípio, para provar P(k+1), assume-se 
somente P(k) como verdade; já no segundo princípio, para provar P(k+1), admite-se que todos os 
P(r), entre 1 e k, são verdadeiros.
Saiba mais
Para encontrar um ciclo euleriano em um grafo, são mostrados aqui dois algo-
ritmos: o de Hierholzer e o de Fleury. Ambos assumem que o grafo de entrada é 
euleriano e retornam o ciclo partindo de algum vértice.
Grafos eulerianos e hamiltonianos 81
O algoritmo de Hierholzer, de 1873, foi um dos primeiros a ser proposto, po-
dendo ser visto no Algoritmo 1 a seguir. Seu princípio básico de funcionamento é 
iniciar o processamento partindo-se de vértices. Assim que um vértice é escolhido, 
encontra-se um pequeno ciclo, com arestas aleatórias, o qual será agregado ao 
ciclo euleriano final. O ciclo formado por todos os pequenos ciclos adicionados é o 
resultado a ser retornado pelo algoritmo.
Fonte: Adaptado de Goldbarg e Goldbarg, 2012.
Algoritmo 1
Algoritmo de Hierholzer
Algoritmo: Constrói um Ciclo Euleriano
Dados: Grafo G = (V, A) euleriano
1 Escolha um vértice v qualquer de G
2 Faça G’= (V’, A’), tal que V’ = V e A’ = A
3 Faça C = {v}
4 ENQUANTO A’   FAÇA
5 Escolha v’  C, tal que grau(v’) > 0 em G’
6 C’são as esquinas do bairro. Se o grafo é euleriano, isto 
é, possui um ciclo que passa por todas as arestas ou ruas sem repetir nenhuma 
delas, a solução é simplesmente encontrar esse ciclo. Para detectar rapidamente 
se o grafo é euleriano, pode-se usar o Teorema 2, o qual demonstra que o grau 
de todos os vértices de um grafo euleriano é par. Podem ser aplicados, ainda, os 
algoritmos de Hierholzer ou Fleury. Aqui estão sendo desconsiderados os pesos 
das arestas, não gerando um grafo ponderado, para facilitar a compreensão.
Se o grafo não for euleriano, existirão arestas com grau ímpar. Convém ressaltar 
que o número de vértices de grau ímpar é par, conforme o Lema do Aperto de Mão.
Caso seja necessário repetir ruas, pode-se adicionar as que não fazem parte da 
área de cobertura para que o caminho mais curto seja encontrado.
Como pode ser observado, os grafos eulerianos possuem uma caracterização 
matemática clara, teoremas que apresentam as condições necessárias e suficien-
tes para determinar se um grafo é euleriano, bem como algoritmos definidos para 
encontrar um ciclo euleriano.
4.2 Grafos hamiltonianos
Vídeo
O Lema do Aperto de Mão 
(Handshaking Lemma) indica que 
a soma dos graus dos vértices, em 
um grafo não orientado, é duas 
vezes a quantidade de arestas. 
Como consequência, o número de 
vértices com grau ímpar é sempre 
par. Esse resultado foi provado 
por Euler no ano de 1736 (SILVA, 
2009).
Saiba mais
A origem dos grafos hamiltonianos se deu com o matemático britânico Thomas 
Pennington Kirkman (1806–1895), que em 1856 debruçou-se sobre problemas 
de enumeração combinatória em poliedros para buscar, mais especificamen-
te, condições para que ciclos sem repetição de arestas ou vértices fossem en-
contrados em poliedros. Antes mesmo de William Rowan Hamilton (1805-1865), 
Kirkman apresentou um exemplo de poliedro contendo um ciclo iniciado em um 
vértice, passando por todos os vértices sem repetição e retornando à origem 
(GOLDBARG; GOLDBARG, 2012).
 Em 1857, Hamilton propôs um jogo chamado Icosiano (ou viagem à volta do 
mundo) cujo objetivo era encontrar caminhos e ciclos em um dodecaedro (poliedro 
de 12 faces), conforme Figura 9.
Grafos eulerianos e hamiltonianos 85
Figura 9
Grafo de representação do jogo icosiano
Fonte: Elaborada pelo autor.
Uma solução para o jogo pode ser vista na Figura 10.
Figura 10
Solução para o jogo icosiano
Fonte: Elaborada pelo autor.
86 Teoria dos Grafos
O ciclo hamiltoniano de representação da solução do jogo pode ser visto na 
Figura 11.
Figura 11
Ciclo hamiltoniano para a 
solução do jogo icosiano
Fonte: Elaborada pelo autor.
Apesar de ter sido estudado em 1856, o problema de ciclos hamiltonianos foi 
amplamente difundido em 1934 por Hassler Whitney (1907–1989) e 
Karl Menger (1902–1985) com a publicação de um trabalho na Universidade de 
Princeton (FERNANDO et al., 2019).
Dado um grafo G = (V, A), em que o caminho contenha todos os 
vértices de G, sendo que cada um aparece somente uma vez, tem-
-se um caminho hamiltoniano. No grafo da Figura 12, o caminho 
{(v1, v2), (v2, v3), (v3, v4)} contém todos os vértices do grafo somente 
uma vez, portanto, é um caminho hamiltoniano.
Considere um ciclo sobre G contendo os seguintes vértices: 
v1, v2, v3, ..., vk, v1. Se o caminho v1, v2, v3, ..., vk for hamiltoniano, 
tem-se um ciclo hamiltoniano. Um grafo que contém um ciclo 
hamiltoniano é chamado de grafo hamiltoniano.
Ao se analisar o grafo da Figura 13 a seguir, percebe-se que 
o caminho (v2, v3), (v3, v5), (v5, v1), (v1, v4) passa por todos os vérti-
ces exatamente uma vez e que, portanto, trata-se de um cami-
nho hamiltoniano. No mesmo grafo, o caminho (v2, v3), (v3, v5), 
(v5, v1), (v1, v4), (v4, v2) é um ciclo (começa e termina em v2), sendo 
caracterizado, desse modo, como um ciclo hamiltoniano. Em ra-
zão disso, o grafo é hamiltoniano.
Figura 12
Grafo com caminho hamiltoniano
v1
v2
v4
v3
Fonte: Elaborada pelo autor.
Grafos eulerianos e hamiltonianos 87
Se um grafo contém um caminho hamiltoniano, mas não 
um ciclo hamiltoniano, é chamado de grafo semi-hamiltoniano. 
Percebe-se que para um grafo semi-hamiltoniano se tornar 
hamiltoniano, basta adicionar uma aresta entre o vértice iní-
cio e o vértice final do caminho.
Considere novamente o grafo da Figura 12, o qual contém 
o caminho hamiltoniano {(v1, v2), (v2, v3), (v3, v4)} e, portanto, é 
um grafo semi-hamiltoniano. Para que ele se torne hamilto-
niano, basta adicionar uma aresta entre o início e o final do 
caminho, no caso (v4, v1), como pode ser visto na Figura 14 cuja 
aresta inserida está tracejada para melhor visualização.
Como resultado dessa definição, consegue-se perceber 
que um grafo completo Kn, sendo n ≥ 3, é sempre hamilto-
niano. Isso ocorre porque, em um grafo completo, todos os n 
vértices possuem arestas incidentes em todos os demais n-1 
vértices. Assim, para todo vértice vi, 1 ≤ i ≤ n, existe o seguinte 
caminho C = {(v1, v2), (v2, v3), (v3, v4) … (vn-1, vn )}, o qual passa 
por todos os vértices {v1, …, vn} somente uma vez. Como todos 
vértices são adjacentes a todos os demais, o vértice vn tam-
bém é adjacente a v1, assim, o caminho C, adicionando a ares-
ta (vn, v1), é um ciclo que passa por todos os vértices, portanto, 
um ciclo hamiltoniano, e o grafo é hamiltoniano.
Para grafos hamiltonianos, não se tem uma condição ne-
cessária e suficiente conhecida (isto é, um teorema do tipo 
“se, e somente se”), como no caso dos grafos eulerianos. Basi-
camente, os teoremas apresentam condições suficientes para 
que o grafo seja considerado hamiltoniano, como pode ser 
observado a seguir, no Teorema de Ore (1960).
Figura 13
Grafo hamiltoniano
v1
v2
v4 v3
v5
Fonte: Elaborada pelo autor.
Figura 14
Grafo semi-hamiltoniano com aresta inserida
v1
v2
v3
v4
Fonte: Elaborada pelo autor.
Teorema 3
Teorema de Ore (1960)
O Teorema de Ore foi provado pelo matemático norueguês 
Øystein Ore (1899–1968) e estabelece que um grafo contendo uma quantidade su-
ficiente de arestas é hamiltoniano.
Considere o grafo simples G = (V, A), tal que |V| = n e n ≥ 3. Se para todo par de 
vértices não adjacentes de G, vi e vj for observado que grau(vi) + grau(vj) ≥ n, então, 
G é hamiltoniano.
A prova se dá por contradição, ou seja, assume-se que o grafo possui as con-
dições apresentadas, mas não é hamiltoniano. Encontrando-se uma contradição, 
prova-se que o grafo, necessariamente, é hamiltoniano.
88 Teoria dos Grafos
Seja o grafo G com as condições apresentadas, mas que não seja hamiltoniano, 
supõem-se que seja semi-hamiltoniano, isto é, possui um caminho hamiltoniano, e a 
adição de uma aresta entre o vértice inicial e final desse caminho o torna hamiltoniano. 
Se o grafo não for semi-hamiltoniano, pode-se adicionar arestas até que seja.
Convém ressaltar que a adição de arestas extras não contradiz a hipótese, pois 
são acrescentadas em vértices não adjacentes, os quais já atendem à condição de 
que a soma de seus graus é maior que n.
Assim, para tornar um grafo em hamiltoniano, basta adicionar a aresta (v, w), 
indicando que há um caminho passando por todos os vértices de G. Assumindo 
v = v1 e w = vn, o caminho é: C = {v, v2, v3, ..., vn-1, w}, conforme pode-se ver a seguir.
v1 v2 vi vn-1 vnvi-1
... ...
A hipótese apresentada – grau(v1) + grau(vn) ≥ n – indica que existe um con-
junto de pelo menos n-2 arestas que incidem em {v1, vn}. Isto é, a aresta (v1, vn) 
aumenta em 1 o grau de v1 e o grau de vn, indicando que, para que a soma de 
seus graus seja maior que n, n-2 arestas precisam incidir em v1 ou vn. Ademais, 
não é possível que todas as n-2 arestas incidam somente em v1 ou vn, pois seria 
necessário, no mínimo, um par de arestas paralelas, contradizendo a condição de 
que G é simples. Isso é facilmente verificável, pois assume-se todas as n-2 arestas 
incidentes somente em v1. Além da aresta que pertence ao caminho C (v1, v2), v2 
seria incidente a v1, em uma nova aresta, para que a condição fosse satisfeita, 
gerando arestas paralelas.A figura a seguir mostra essa composição contraditória de arestas. As arestas 
mais finas são as n-2 arestas. Percebe-se que a aresta fina (v1, v2) é paralela à aresta 
(v1, v2), a qual pertence ao caminho C, contradizendo a condição do teorema. Des-
considerando essa aresta, tem-se n-3 arestas, o que também contradiz a condição 
do teorema, pois, nesse caso, grau(v1) + grau(vn) não seria maior ou igual a n.
v1 v2 vi vn-1 vnvi-1
... ...
Grafos eulerianos e hamiltonianos 89
Assumindo as n-2 arestas incidentes em {v1, v2}, consegue-se apontar os vértices 
vi e vi-1, tal que vi é adjacente a v1, aresta (vi, v1), e vi-1 é adjacente a vn, aresta (vi-1, vn), 
conforme a figura a seguir.
v1 v2 vi vn-1 vnvi-1
... ...
Posto isso, consegue-se apontar o seguinte ciclo: {v1, v2, ..., vi-1, vn, vn-1, ..., vi+1, vi, v1}. Esse 
ciclo é hamiltoniano, portanto, o grafo G é hamiltoniano, contradizendo a suposição. 
Teorema 4
Teorema de Dirac (1952)
Outro teorema conhecido é o Teorema de Dirac, provado pelo matemático hún-
garo/britânico Gabriel Andrew Dirac (1925–1984). Ele também dá condições sufi-
cientes para que um grafo seja hamiltoniano com base no grau dos vértices.
Seja o grafo simples G = (V, A), tal que |V| = n e n ≥ 3, se o grau de todo vértice 
de G é maior ou igual a n/2, isto é, grau(v) ≥ n
2
, ∀v ∈ V, então, G é hamiltoniano.
Prova: se o grau de todos os vértices é maior que n/2, então, para todo par de 
vértices de G, adjacentes ou não, vale a regra:
grau(v) + grau(w) ≥ n
2
n
2
+
Sendo o mesmo que dizer:
grau(v) + grau(w) ≥ n
Assim, pelo Teorema de Ore (Teorema 3), G é hamiltoniano.
As definições de caminho, ciclo e grafo hamiltonianos se aplicam ainda a 
digrafos (grafos orientados). Em um digrafo, um caminho orientado é cha-
mado de caminho hamiltoniano se contiver todos os vértices do digrafo, sem 
repetição destes. Um ciclo orientado é dito ciclo hamiltoniano se for um ca-
minho hamiltoniano e se iniciar e terminar no mesmo vértice. Já um digrafo 
é dito hamiltoniano se contiver um ciclo orientado hamiltoniano. Se contiver 
um caminho orientado hamiltoniano, é chamado digrafo semi-hamiltoniano 
(NICOLETTI; HRUSCHKA JUNIOR, 2018).
90 Teoria dos Grafos
Algoritmos para encontrar um ciclo hamiltoniano são complicados. Para um 
grafo com n vértices, pode haver n! ciclos hamiltonianos. Ao se pensar em grafos 
completos, que são claramente hamiltonianos, Kn para n > 2, tem-se exatamente n! 
ciclos hamiltonianos, sendo, portanto, um limite superior da quantidade de ciclos 
possíveis.
Um algoritmo de força bruta, para encontrar um ciclo hamiltoniano em um gra-
fo, é inviável, pois, dado um grafo com n vértices, tem-se até n! sequências de vér-
tices que podem ser caminhos hamiltonianos e que devem ser 
enumeradas e testadas.
Isso ocorre em grafos completos, como o grafo completo K3, re-
presentado pela Figura 15. Observa-se que ele tem 6 ca-
minhos (3!), a saber:
 • {(v1, v2), (v2, v3), (v3, v1)}
 • {(v2, v3), (v3, v1), (v1, v2)}
 • {(v3, v1), (v1, v2), (v2, v3)}
 • {(v1, v3), (v3, v2), (v2, v1)}
 • {(v2, v1), (v1, v3), (v3, v2)}
 • {(v3, v2), (v2, v1), (v1, v3)}
Se for considerado o K4 (grafo completo com quatro 
vértices), apresentado na Figura 16, tem-se 24 cami-
nhos (4!), e assim por diante.
Convém ressaltar que quando o problema de en-
contrar ciclos hamiltonianos se inicia em um vértice 
específico, tem-se (n-1)! ciclos candidatos. Por exem-
plo, para enumerar todos os ciclos hamiltonianos em 
K4, da Figura 16, iniciando em v1 , tem-se (4-1)!, isto é 
3! ciclos.
v1 v3
v2
Figura 15
Grafo completo K3
Fonte: Elaborada pelo autor.
Figura 16
Grafo completo K4
v1
v2 v3
v4
Fonte: Elaborada pelo autor.
Essa quantidade de valores pode não parecer mui-
ta, mas considere um algoritmo ingênuo, que enume-
ra todas as possíveis combinações de ciclos em um grafo com n vértices, resultando 
em (n-1)! ciclos candidatos, e que testa se cada candidato é um ciclo hamiltoniano.
Considere, também, que para essa tarefa está disponível um computador com a ca-
pacidade de efetuar 12 trilhões de operações de ponto flutuante por segundo (12*1012), 
isto é, um computador com 12 teraflops 2 . Para varrer todos os possíveis ciclos de um 
grafo com 25 vértices, n = 25, a máquina é capaz de avaliar 
12*10
24
12
= 500 bilhões de 
ciclos candidatos por segundo. Como ele precisa calcular 24! possíveis ciclos, demorará 
24!
(500 bilhões)
 ≅ 39.348 anos, um tempo complemente inviável.
Para efeitos de comparação, essa 
capacidade de processamento é 
alcançada por alguns consoles de 
videogame, lançados em 2020, 
que possuem hardware dedicado 
ao processamento de vídeo.
2
Grafos eulerianos e hamiltonianos 91
Um dos problemas mais famosos envolvendo grafos hamiltonianos é o Problema 
do Caixeiro Viajante, do inglês Traveling Salesman Problem.
O dilema é enunciado como uma pessoa que precisa visitar várias cidades para 
efetuar as suas vendas. Conectando as cidades, tem-se estradas ou rodovias, aos 
pares, sendo que cada uma conta com uma distância (um peso). O objetivo é visitar 
todos os distritos somente uma vez, fazendo o percurso mais curto e retornando à 
cidade de origem.
Representar essa questão na teoria dos grafos é simples. Cada cidade é um vér-
tice e cada rodovia uma aresta ponderada com sua distância. Se houver estradas 
entre todas as cidades, o grafo é completo. Assumindo que o custo de um caminho/
ciclo é a soma dos pesos de suas arestas, a solução do problema é encontrar um 
ciclo hamiltoniano que tenha a menor despesa.
Por exemplo, considerando quatro cidades do estado de Santa Catarina: 
Joaçaba, Treze Tílias, Videira e Campos Novos, a representação em forma de grafo 
pode ser vista na Figura 17, indicando os vértices como cidades, as arestas como 
estradas e as distâncias como o peso de cada aresta.
Fonte: Elaborada pelo autor.
Figura 17
Cidades de Santa Catarina
v2
v1
v3
v4
34 km
38 km
64 km
66 km
78 km
45 km
Treze Tílias
Videira
 Joaçaba 
Campos Novos
92 Teoria dos Grafos
Constatando que o número de vértices é igual a 4, tem-se 6 possíveis ciclos, partin-
do de Joaçaba e retornando a Joaçaba, passando por todos os vértices somente uma 
vez, a saber:
 • Joaçaba → Campos Novos → Videira → Treze Tílias → Joaçaba : 183 km
 • Joaçaba → Campos Novos → Treze Tílias → Videira → Joaçaba : 221 km
 • Joaçaba → Videira → Campos Novos → Treze Tílias → Joaçaba : 246 km
 • Joaçaba → Videira → Treze Tílias → Campos Novos → Joaçaba : 221 km
 • Joaçaba → Treze Tílias → Videira → Campos Novos → Joaçaba : 183 km
 • Joaçaba → Treze Tílias → Campos Novos → Videira → Joaçaba : 246 km
Percebe-se que alguns ciclos são o inverso de outros. De todos eles, dois 
possuem a menor distância, e qualquer um deles é uma solução ao problema 
apresentado.
Para resolver o dilema, usa-se um método exato. A maneira mais comum é 
enumerar todas as combinações de vértices que formam um ciclo hamiltonia-
no e escolher a de menor custo. Sua complexidade é fatorial, significando que, 
para muitas cidades, o problema não termina em tempo hábil.
Outra saída é a aplicação de métodos heurísticos, que podem não resul-
tar exatamente o ciclo de menor custo, mas que chegam a uma boa solução, 
terminando o processo em tempo hábil. Os métodos heurísticos demandam 
técnicas aplicadas em inteligência artificial, como algoritmos genéticos, buscas 
heurísticas, entre outros (SOUZA, 2015).
Há também o método da busca gulosa, um algoritmo não exato, em que, 
dado um vértice de partida, é sempre escolhida a aresta de menor custo para 
atravessar. Esse processo é repetido sucessivamente até que todos os vértices 
tenham sido alcançados e que a única opção seja retornar ao vértice origem 
(LOPES, 2020).
Pelo algoritmo guloso (Figura 17), partindo de Joaçaba, a primeira escolha 
seria Treze Tílias, que possui a menor distância (38 km). De Treze Tílias, o 
algoritmo escolheria Videira (34 km). De Videira, a única opção seria Campos 
Novos, visto que não se pode voltar a Treze Tílias nemchegar a Joaçaba (final 
do ciclo). De Campos Novos, voltar a Joaçaba, resultando o seguinte caminho:
 • Joaçaba → Treze Tílias → Videira → Campos Novos → Joaçaba : 183 km
Coincidentemente é o caminho ideal.
Agora, em um segundo exemplo, considerando o grafo da Figura 18, o qual 
contém cinco vértices, percebe-se que trata-se de um grafo completo (todos 
os vértices são adjacentes a todos os demais) e que, portanto, possui (n-1)! 
ciclos hamiltonianos iniciando em v1, no caso, 24. Enumerando todos os ciclos 
Grafos eulerianos e hamiltonianos 93
hamiltonianos, é possível perceber que o menor custo é 676, com o seguinte 
caminho:
 • v1 → v4 → v2 → v3 → v5 → v1
Figura 18
Grafo com ciclos hamiltonianos
133
185
119
121
150
152
120
199
174
200
v2
v1
v3
v4
v5
Fonte: Adaptada de Lopes, 2020.
Aplicando o algoritmo guloso, partindo de v1, as escolhas feitas seriam de:
 • v1 para v3: custo 119
 • v3 para v5: custo 120
 • v5 para v4: custo 199
 • v4 para v2: custo 150
 • v2 para v1: custo 185
Resultando um custo total de 773, o que não é o menor custo, conforme calcu-
lado anteriormente (676).
Mesmo não sendo o melhor custo, o encontrado pelo método guloso é bem 
próximo do melhor custo. Isso deve ser levado em consideração, uma vez que o 
tempo para se chegar ao caminho pode ser bem maior pelo método exato.
Uma variação desse algoritmo é o método guloso com repetição, podendo ser 
implementado repetindo o algoritmo guloso, partindo de cada vértice, e, ao final, 
escolhendo o ciclo de menor caminho. No caso da Figura 18, seriam calculado cinco 
ciclos, cada um iniciando em um vértice diferente:
94 Teoria dos Grafos
 • v1 → v3 → v5 → v4 → v2 → v1: custo 773
 • v2 → v3 → v1 → v5 → v4 → v2: custo 722
 • v3 → v1 → v5 → v4 → v2 → v3: custo 722
 • v4 → v2 → v3 → v1 → v5 → v4: custo 722
 • v5 → v3 → v1 → v4 → v2 → v5: custo 741
Assim, o ciclo escolhido seria:
 • v2 → v3 → v1 → v5 → v4 → v2
Como é um ciclo, deslocando-o para que v1 seja o ponto de partida, tem-se:
 • v1 → v5 → v4 → v2 → v3 → v1
Não é o ciclo ideal, mas está mais perto, sendo, portanto, uma solução satisfató-
ria que pode ser calculada em tempo hábil.
A formulação de problemas com base em grafos hamiltonianos é ampla, con-
siderando a dificuldade computacional em se encontrar ciclos hamiltonianos, es-
pecialmente em grafos ponderados. Muitas pesquisas são feitas na área, tendo 
como objetivo a descoberta de novas técnicas para minimizar os efeitos da explo-
são combinatória.
CONSIDERAÇÕES FINAIS
Neste capítulo, estudou-se os grafos eulerianos e hamiltonianos. Foram mostrados 
teoremas que impõem as condições necessárias e suficientes para que um grafo seja 
euleriano, assim como os algoritmos de Hierholzer e Fleury, para encontrar um ciclo 
euleriano em um grafo euleriano.
Para os grafos hamiltonianos, foi apresentado que não há teoremas que impõem 
condições necessárias e suficientes, já que os teoremas de Dirac e Ore têm condições 
suficientes, apenas.
Quando o problema de busca pelo ciclo hamiltoniano envolve pesos e tem como 
objetivo um ciclo ótimo partindo de um determinado vértice, verificou-se que a explo-
são combinatória é da ordem de (n-1)!, sendo n o número de vértices do grafo. Perce-
be-se, portanto, que um método exato se torna inviável rapidamente, não terminando 
de executá-lo em tempo hábil.
Os métodos heurísticos que envolvem técnicas de inteligência artificial são os mais 
indicados. Eles não retornam a solução de menor custo, mas uma com um custo satis-
fatório e em tempo factível.
ATIVIDADES
1. Uma expedição para a exploração das luas de Saturno e Júpiter será lançada, 
passando por Calisto, Ganímedes, Io, Mimas e Titã. Após visitar essas luas, a nave 
deve retornar à Terra. O diagrama a seguir apresenta a duração da missão, em 
anos, estimada para a viagem entre cada par de luas. Qual seria o melhor caminho 
para tal expedição?
Grafos eulerianos e hamiltonianos 95
Para a resolução deste problema, utilize o algoritmo guloso.
0,8
5,1
4,7
5,7
Io Mimas
Titã
TerraGanímedes
Calisto
5,6
5,9
3,2
3,1
3,6
8,2
8,1
0,6
5,2
1,5
1,1
v2 v1
v3
v4 v5
v6
2. Resolva a Questão 1 pelo algoritmo guloso com repetição. Mostre todos os 
caminhos analisados, o tempo de cada caminho, e escolha que der o menor 
resultado, rearranjado para iniciar na Terra (se for o caso).
3. Dado o grafo a seguir, apresente um ciclo euleriano partindo de v1.
v1 v8
v2
v7v3
v4 v5 v6
4. Considerando o grafo simples G = (V, A), tal que |V| = 6 e ∀v ∈ V grau(v) = 3, prove 
que G é hamiltoniano.
96 Teoria dos Grafos
5. Seja o grafo simples G = (V, A), tal que |V| = 7, os seus vértices possuem os seguintes 
graus:
 • grau(v1) = 3
 • grau(v2) = 1
 • grau(v3) = 4
 • grau(v4) = 2
 • grau(v5) = 2
 • grau(v6) = 2
 • grau(v7) = 2
Esse grafo é euleriano? Justifique a sua resposta.
REFERÊNCIAS
BOAVENTURA NETTO, P. O. Grafos: teoria, modelos, algoritmos. 3. ed. São Paulo: Blucher, 2003.
FERNANDO, P. H. L. et al. O problema do caixeiro viajante aplicado na distribuição de peças/componentes do 
almoxarifado para a montagem de caminhões especiais em uma linha de produção na indústria automobilística. 
Sinergia (IFSP Online), São Paulo, v. 20, n. 1, p. 63-74, jan./mar. 2019. Disponível em: https://www.researchgate.
net/publication/332665441_O_PROBLEMA_DO_CAIXEIRO_VIAJANTE_APLICADO_NA_DISTRIBUICAO_DE_
PECASCOMPONENTES_DO_ALMOXARIFADO_PARA_A_MONTAGEM_DE_CAMINHOES_ESPECIAIS_EM_UMA_
LINHA_DE_PRODUCAO_NA_INDUSTRIA_AUTOMOBILISTICA/link/5cc259694585156cd7b18368/download. 
Acesso em: 6 jul. 2020.
GOLDBARG, M. C.; GOLDBARG, E. Grafos: conceitos, algoritmos e aplicações. Rio de Janeiro: Elsevier, 2012.
GOMES, M. J. N. et al. O problema do carteiro chinês, algoritmos exatos e um ambiente MVI para análise de 
suas instâncias: sistema XNÊS. Pesquisa Operacional, Rio de Janeiro, v. 29, n. 2, p. 323-363, jan./maio/ago. 2009. 
Disponível em: http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382009000200005&lng=en&
nrm=iso. Acesso em: 6 jul. 2020.
LOPES, S. A. Métodos Finitos em Matemática. Arquivo Escolar, 28 mar. 2011. Disponível em: http://
arquivoescolar.org/handle/arquivo-e/45. Acesso em: 6 jul. 2020.
NICOLETTI, M. C. do.; HRUSCHKA JUNIOR, E. R. Fundamentos da teoria dos grafos para computação. São Paulo: 
LTC, 2018.
SOUZA, M. M. Heurísticas para o problema do caixeiro viajante com seleção de hotéis. Viçosa, 2015. Dissertação 
(Mestrado em Ciência da Computação) – Universidade Federal de Viçosa. Disponível em: https://www.
locus.ufv.br/bitstream/handle/123456789/6650/texto%20completo.pdf?sequence=1&isAllowed=y. 
Acesso em: 6 jul. 2020.
SZWARCFITER, J. L. Teoria Computacional de Grafos. Rio de Janeiro: Elsevier, 2018.
Problemas em Grafos 97
5
Problemas em Grafos
O estudo de teoria de grafos é muito amplo e vários problemas surgem 
da análise destas estruturas matemáticas. Nesse sentido, serão abordados 
neste capítulo alguns problemas em grafos, como as cliques e os conjuntos 
estáveis, as cliques máximas, as coberturas, a planaridade e a coloração. Na 
seção 5.1 serão apresentados os conceitos de clique em grafos e seu com-
plementar, os conjuntos estáveis. Na seção 5.2 será desenvolvido o concei-
to de clique máxima, problema de solução difícil (NP-Completo). Em seguida, 
na seção 5.3, serão abordadas as coberturas de vértices e coberturas de 
arestas. O problema da planaridade de grafos também é estudado. Por fim, 
na seção 5.5, será exposto o problema da coloração em grafos.
5.1 Cliques e Conjuntos Estáveis
Vídeo Imagine uma empresa que, preocupada com a divulgação de seus produtos, 
mas com poucos recursos, decide investir em marketing digital em redes sociais. 
Levando em consideração um orçamento pequeno, o gerente de marketing quer 
divulgar para pessoas ou para empresas que possam ajudar na propagação para 
um conjunto bem conectado de contatos, o qual ele chamou de panelinha. Para 
otimizar seus gastos, o gerente não quer compartilhar sua divulgação com mais de 
umcontato de uma mesma panelinha.
A Figura 1 a seguir pode ser utilizada para esquematizar essa estratégia de mar-
keting. Com anúncios em apenas quatro dessas panelinhas, o gerente de marketing 
teoricamente conseguiria uma divulgação para 100 pessoas.
Figura 1
Panelinhas
Fonte: Elaborada pelo autor.
Panelinha 1
Empresa
Panelinha 2
Panelinha 3
Panelinha 4
98 Teoria dos Grafos
Modelando este problema para grafos, em que cada pessoa é um vértice e cada 
conexão uma aresta, percebe-se que grupos altamente conectados são subgrafos 
completos do grafo total, isto é, dentro de cada panelinha todas as pessoas estão 
conectadas entre si. Tomando cada panelinha como um grafo individual, diz-se que 
é um grafo completo.
Dado um grafo não orientado denotado por G = (V, A), uma clique é um subcon-
junto de vértices de G, em que todos os seus vértices são conectados dois a dois. 
Em outras palavras, uma clique V’ de G é tal que V’ ⊂ V e ∀v, w ∈ V’, assim como v ≠ 
w e (v, w) ∈ A.
Apesar de a definição indicar um subconjunto de vértices, muitos autores tam-
bém definem o termo clique como um subgrafo e, nesse caso, uma clique é um 
subgrafo completo de G. Outra maneira de indicar a clique é definindo-a como um 
subgrafo isomorfo a um grafo completo Kn.
Percebe-se que o conceito é parecido com o de grafos completos, podendo ser 
assim designado quando todos os seus vértices são conectados dois a dois. Os 
grafos completos possuem uma notação própria, a saber Kn, em que n é o número 
de vértices. Assim, a Figura 2 apresenta os grafos K2, K3, K4 e K5 respectivamente 
(lembrando que K1 é um grafo completo contendo somente um vértice).
v5v4
v1 v3
v2
v1 v2
v3v4
v1 v3
v2v2
v1
Fonte: Elaborada pelo autor.
Figura 2
Grafos Completos: K2, K3, K4 e K5
Assim, um grafo possui uma clique se possuir um subgrafo completo, por exem-
plo, o grafo G apresentado na Figura 3.
Nesse grafo podem-se observar as seguintes cliques:
 • {v1}
 • {v2}
 • {v3}
 • {v4}
 • {v5}
 • {v1, v2}
 • {v2, v3}
 • {v3, v4}
 • {v4, v5}
 • {v1, v5}
 • {v2, v4}
 • {v2, v3, v4}
Foi no trabalho de Luce e Perry 
(1949) que a palavra clique foi 
utilizada pela primeira vez para 
representar um subgrafo completo, 
denotando um grupo de pessoas 
que se conhecem em uma rede 
social. Essa palavra, portanto, foi 
usada para designar um grupo de 
pessoas, uma panelinha e não diz 
respeito ao ato de clicar.
Curiosidade
Fonte: Elaborada pelo autor.
v5
v2 v4
v3
v1
Figura 3
Grafo G contendo cliques
Problemas em Grafos 99
As cliques {v1, v5}, {v3, v4} e {v2, v3, v4} podem ser visualizadas de acordo com a 
Figura 4.
Figura 4
Grafo com algumas cliques destacadas
Fonte: Elaborada pelo autor.
v5
v2 v4
v3
v1
Isolando essas cliques como subgrafos induzidos de G, conforme a Figura 5, per-
cebe-se que cada uma delas é um subgrafo completo de G, sendo respectivamente 
K2, K2 e K3.
v4
v3
v2v4
v3
v5v1
Figura 5
Cliques de G separadas
Fonte: Elaborada pelo autor.
Define-se como tamanho de uma clique, ou sua cardinalidade, o 
número de vértices em cada; sendo C uma clique, |C| é a sua cardi-
nalidade. Para as cliques da Figura 5, seus tamanhos são dois, dois 
e três, respectivamente. Por exemplo, seja o grafo H da Figura 6, 
consegue-se observar duas cliques de tamanho três, a saber:
 • {v1, v5, v6}
 • {v2, v3, v4}
Seus subgrafos induzidos podem ser vistos na Figura 7.
Fonte: Elaborada pelo autor.
v2
v4
v3
v6
v5
v1
Figura 7
Cliques de tamanho 3 do Grafo H
Fonte: Elaborada pelo autor.
v6
v5
v2
v4
v3
v1
Figura 6
Grafo H
100 Teoria dos Grafos
Partindo do conceito de clique, chama-se conjunto independente de vértices, tam-
bém conhecido como conjunto estável de vértices, o conjunto de vértices totalmente 
desconexo, sem arestas entre eles. Isto é, um conjunto independente de vérti-
ces S de G é tal que S ⊂ V e ∀v, w ∈ S, para v ≠ w e (v, w) ∉ A.
Dado o grafo da Figura 8, é possível obter os seguintes conjuntos independen-
tes de vértices:
 • {v1, v4}
 • {v1, v3}
 • {v1, v5}
 • {v2, v4}
 • {v3, v5}
 • {v1, v3, v5}
Na Figura 9 consegue-se observar os conjuntos {v1, v4}, {v3, v5} e 
{v1, v3, v5}. Percebe-se que, para cada um desses conjuntos, não há 
arestas para qualquer par de vértices.
Define-se como tamanho de um conjunto independente de vértices 
o seu número de vértices. Para os conjuntos mostrados na Figura 8, 
os tamanhos são: dois, dois e três, respectivamente.
Um conjunto independente, ou estável de vértices, é máximo se 
tiver a maior cardinalidade entre todos os conjuntos estáveis do gra-
fo. Outro conceito é o número ou índice de estabilidade do grafo, dado 
pela cardinalidade de um conjunto estável máximo do grafo. Dado 
um grafo G, esse índice é denotado por α(G).
Assim, os conceitos de clique e conjunto independente de vérti-
ces são complementares. Enquanto no primeiro há uma aresta en-
tre todos os pares de vértices, no segundo não há. Isso significa que um conjunto 
vértices E é estável em um grafo G, se, e somente se, for uma clique no grafo com-
plementar de G. Seja o grafo J apresentado na Figura 9.
v5
v3
v1
v4
v1 v5
v3
Figura 9
Conjuntos independentes de vértices de G: {v1, v4}, {v3, v5} e {v1, v3, v5}
Fonte: Elaborada pelo autor.
O conjunto de vértices {v1, v3, v5} é um conjunto estável de vértices de J, pois, no 
grafo complementar exibido na Figura 10, {v1, v3, v5} é uma clique.
Fonte: Elaborada pelo autor.
v4
v5 v3
v1
v2
Figura 8
Grafo J
Problemas em Grafos 101
Um conceito correlato ao conjunto independente de vértices é o 
emparelhamento – matching, ou também acoplamento. Um empare-
lhamento de um grafo G é um conjunto de arestas que não compar-
tilham vértices.
A Figura 11 apresenta um grafo contendo um emparelhamento, 
sendo o conjunto de arestas {(v1, v2) e (v4, v5)}. Perceba que essas 
arestas não compartilham vértices.
Um emparelhamento máximo é aquele que contém o maior 
número de arestas possível. Encontrar um emparelhamento máxi-
mo pode ser feito em tempo polinomial e tem-se vários algoritmos 
eficientes desenvolvidos (SZWARCFITER; FIGUEIREDO, 1999).
As aplicações do estudo das cliques extrapolam a área da com-
putação e da matemática. Por exemplo, o trabalho de Rhodes et al. 
(2003), na área da química, mapeou o problema de similaridade de 
farmacóforos em um banco de dados como um problema de detec-
ção de cliques. Os farmacóforos são um conjunto de características 
que asseguram interações moleculares e esse estudo é importante 
para o desenvolvimento de moléculas bioativas (RHODES et al., 2003).
A aplicação de emparelhamentos também é ampla; um exemplo 
é o problema da atribuição de pessoal (SZWARCFITER; FIGUEIREDO, 
1999). Suponha uma possível contratação de candidatos a vagas em 
uma empresa, há n candidatos e m posições disponíveis. Cada can-
didato está qualificado a uma ou mais posições. O problema é des-
cobrir se há uma forma de alocar todos os candidatos de modo que 
cada um ocupe uma posição. Para uma resolução provável, é possí-
vel realizar o emparelhamento em grafos bipartidos.
Fonte: Elaborada pelo autor.
v5
v2 v4
v3
v1
Figura 11
Grafo com emparelhamento
Fonte: Elaborada pelo autor.
v4
v5 v3
v1
v2
Figura 10
Grafo complementar a J
5.2 Cliques Máximas
Vídeo Dando continuidade ao estudo das cliques, existem dois conceitos importantes 
na área de grafos que devem ser levados em consideração: a clique maximal e a 
clique máxima.
Uma clique maximal é um conjunto de vértices 
todos adjacentes entre si e que não está estritamen-
te contida em outra clique (GOLDBARG; GOLDBARG, 
2012). Isso significa que, tomada uma clique C de um 
grafo, se houver possibilidade de adicionar mais um 
vértice adjacente a todos os demais, formando um 
subgrafo completo e, portanto, outra clique C’, a cli-
que C não é maximal. Por exemplo, veja o grafo H da 
Figura 12.
v1 v5
v4
v3
v6
v2
Figura 12
Grafo H
Fonte: Elaborada pelo autor.
102 Teoria dos Grafos
Observe a clique C formada pelos vértices { v1, v2, v4 }, a qual podeser visualizada por arestas tracejadas na Figura 13 a seguir.
Se houver possibilidade de adicionar mais um vértice à clique C, 
de maneira que esse vértice seja adjacente a todos os elementos de 
C, então, C não é uma clique maximal. Analisando o grafo da Figura 
13, percebe-se que v3 e v6 não são adjacentes a todos os vértices de 
C, mas v5, sim. O vértice v5 é adjacente a v1, v2 e v4 , portanto, a clique 
C não é maximal, pois está contida em C’ = { v1, v2, v4, v5 }, conforme 
mostra a Figura 14.
Analisando os demais vértices, v3 não é adjacente a todos os vér-
tices em C’, assim como v6. Portanto, C’ é uma clique maximal do 
grafo H e pode ser visualizada na Figura 15.
Fonte: Elaborada pelo autor.
Figura 14
Clique C’ do Grafo H
v1 v5
v4
v3
v6
v2
Fonte: Elaborada pelo autor.
Figura 15
Clique Maximal C’ do Grafo H
v1 v5
v4v2
Fonte: Elaborada pelo autor.
Figura 13
Clique C no Grafo H
v1 v5
v4
v3
v6
v2
Convém ressaltar que podem haver mais cliques maximais em um grafo. A 
exemplo de H, a clique C’’= {v1, v2, v5, v6} também é maximal e pode ser observada 
na Figura 16.
Tomando novamente o grafo H de exemplo, a clique C’’’ = { v2, v3, v4 }, mostrada 
na Figura 17, também é maximal, apesar de possuir menos vértices que C’ e C’’. 
Isso porque uma clique é maximal se ela não está contida em outra clique e não há 
relação com outras cliques que podem ser encontradas no grafo.
Fonte: Elaborada pelo autor.
Figura 16
Clique maximal C’’ do Grafo H
v1 v5
v4
v6
Fonte: Elaborada pelo autor.
Figura 17
Clique Maximal C’’’ do Grafo H
v4
v3
v2
Problemas em Grafos 103
Há outro conceito básico em grafos, usado para denotar a maior clique que 
pode ser encontrada em um grafo, que é a clique máxima.
Uma clique máxima é uma clique de maior cardinalidade, isto é, a que possui 
o maior número de vértices entre todas as possíveis cliques do grafo (GOLDBARG; 
GOLDBARG, 2012).
Dado um grafo G = (V, A), o conjunto de todas as cliques de G é denotado por 
C(G). O tamanho da clique máxima, também chamado de número de clique, é dado 
por ω(G) = max { |C| | C ∈ C(G)}.
Observe o grafo I = (V, A), apresentado na Figura 18.
v1
v5
v4
v3
v6
v2
Figura 18
Grafo I
Fonte: Elaborada pelo autor.
A Figura 19 apresenta todas as cliques maximais de I. Não serão enumeradas 
todas as cliques, já que seria necessário acrescentar todos os pares de vértices 
adjacentes, pois são cliques de tamanho 2.
v1
v6
v1
v5
v4
v4
v3
v2
v1
v4
v2
Figura 19
Cliques Maximais de I
Fonte: Elaborada pelo autor.
Assim, o grafo I possui três cliques máximas, a saber:
 • { v1, v2, v4 }
 • { v2, v3, v4 }
 • { v1, v4, v5 }
Assim, ω(I) = 3
O Problema da Clique é um problema de decisão, em que, dados um grafo G e 
um número inteiro k, deve-se decidir se G tem uma clique de tamanho pelo menos k. 
Esse problema é da classe NP-completo e faz parte da clássica lista de Karp, conten-
do 21 problemas provados como NP-completos.
Em seu artigo, Richard Karp (apud 
MILLER; THATCHER; BOHLINGER, 
1972) demonstrou que 21 
problemas famosos da ciência da 
computação são NP-completos, 
usando como base a prova feita 
em 1971, por Stephen Cook, o 
qual constatou que o problema 
da Satisfatibilidade Booleana 
é NP-Completo. O trabalho de 
Karp impulsionou os estudos em 
complexidade computacional, 
principalmente se voltando ao 
grande problema não resolvido até 
hoje: P = NP?
Curiosidade
104 Teoria dos Grafos
Assim, uma solução exata para o problema da clique é exponencial. Pesqui-
sas atuais tentam diminuir sua ordem de complexidade pelo refinamento de 
algoritmos clássicos, como branch-and-bound, técnica baseada na enumeração de 
todas as possíveis cliques máximas, descartando aquelas que não satisfazem de-
terminados limites impostos pelo algoritmo (ZUGE, 2017).
5.3 Coberturas
Vídeo Suponha que há um projeto municipal para instalar câmeras de monitoramento 
de tráfego em ruas e avenidas de determinada cidade. Um dos objetivos é que os 
motoristas, ao trafegarem pelo município, sempre passem por uma câmera. En-
tretanto, como o orçamento é um problema em qualquer administração, deve-se 
gastar o mínimo possível, instalando o menor número de câmeras.
Modelando esse problema como um grafo, consegue-se representar as ruas 
pelas arestas e os cruzamentos pelos vértices. O objetivo é encontrar o menor nú-
mero de vértices, de modo que todas as arestas desse grafo estejam conectadas a 
um vértice desse conjunto. Assim, instalam-se as câmeras nesses cruzamentos.
Dado um grafo não orientado G = (V, A), um conjunto de 
vértices S é chamado de cobertura de vértices de G se toda 
aresta de G é incidente a pelo menos um vértice de S. Isto é, 
S ⊆ V, tal que se (v, w) ∈ A, então, ou v ∈ S, ou w ∈ S (ou 
ambos). Diz-se que S cobre as arestas de G (NICOLETTI; 
HRUSCHKA, 2018).
Observe o grafo da Figura 20: os conjuntos de vértices 
V’ = {v1, v3, v4, v5, v6} e V’’ = {v2, v4, v5} são coberturas de vértices.
Os dois conjuntos podem ser vistos na Figura 21, em 
que os vértices das coberturas V’ e V’’, respectivamente, 
estão representados normalmente e os vértices desconsi-
derados estão representados em branco. Percebe-se que 
todas as arestas possuem, pelo menos, uma ponta em um 
vértice da cobertura.
Fonte: Elaborada pelo autor.
Figura 21
Representação das coberturas de Vértices V’ e V’’, respectivamente
v1 v5
v4
v3
v6
v5
v4v2
Fonte: Elaborada pelo autor.
Figura 20
Grafo G
v1 v5
v4
v3
v6
v2
Problemas em Grafos 105
O número de cobertura de vértices de um grafo G é denotado τ(G) e é a car-
dinalidade da menor cobertura de vértices de G. Assim, no exemplo do grafo da Fi-
gura 20, o número de cobertura de vértices seria τ(G) = 3, pois não há um conjunto 
de menos de três vértices que cubra as arestas de G.
Um conceito análogo à cobertura de vértices é a cobertura de arestas. Dado um 
grafo G = (V, A), um conjunto C de arestas é chamado de cobertura de arestas, se 
todo vértice de G for extremidade de, pelo menos, uma aresta de C. Ou seja, C ⊆ A, 
tal que ∀v ∈ V e ∃w ∈ V e (v, w) ∈ C. Diz-se que C cobre os vértices de G.
Considerando o grafo G da Figura 20, os conjuntos de arestas A’ = { (v3, v5), (v2, v4), 
(v1, v4), (v5, v6) } e A’’ = { (v1, v4), (v2, v6), (v3, v5) } são coberturas de arestas. Esses dois 
conjuntos podem ser vistos na Figura 22, em que as arestas das coberturas A’ e A’’, 
respectivamente, estão representados normalmente e as arestas desconsideradas 
estão representadas em tracejado. Percebe-se que todos os vértices são atingidos 
por, no mínimo, uma aresta das coberturas.
Fonte: Elaborada pelo autor.
Figura 22
Representação das Coberturas e Arestas A’ e A’’, respectivamente.
v1 v5
v4v2
v3
v6
v1 v5
v4v2
v3
v6
O número de cobertura de arestas de um grafo G é denotado ξ(G), que é a cardi-
nalidade da menor cobertura de arestas de G. Assim, para o grafo da Figura 20, ξ(G) = 3, 
pois não há como cobrir todos os vértices do grafo com menos de três arestas.
O problema da cobertura de vértices mínima é um problema de otimização. 
Seu objetivo é encontrar uma cobertura de vértices com o menor número de vérti-
ces possível e sua formulação como um problema de decisão também é um dos 21 
problemas NP-Completos de Karp.
O problema da cobertura de arestas mínima é um problema de otimização e 
tem como objetivo encontrar uma cobertura de arestas com o menor número de 
arestas possível. Ao contrário do problema de cobertura de vértices mínima, esse é 
um problema polinomial, isto é, um problema tratável.
Para resolver o problema da cobertura de vértices mínima, não se pode usar um 
algoritmo fundado em força bruta (enumerando todas as possíveis coberturas e 
testá-las), pois já se sabe que o tempo de execução é exponencial em relação ao ta-
manho do grafo. Assim, algoritmos que retornam uma solução aproximada precisam 
ser empregados, não retornando a uma solução ótima, mas uma solução satisfatória.
Um problema de decisão, 
conforme o apresentado para a 
cobertura de vértices, é formuladocom um enunciado, para o qual se 
deseja uma resposta sim ou não. 
No caso, a versão do problema é 
a seguinte:
Dado o grafo G e um valor 
inteiro positivo k, G contém uma 
cobertura de vértices de tamanho, 
no máximo, k?
Formulado dessa forma, o proble-
ma faz parte dos 21 problemas 
NP-Completos de Karp.
Saiba mais
Segundo Gersting e Iório (2012), 
um problema é tratável quando 
há um algoritmo que o resolve 
em um tempo proporcional a 
um polinômio do tamanho de 
sua entrada. Esses problemas 
estão na classe de complexidade 
P, ou seja, os problemas que são 
resolvidos em máquinas de turing 
determinística, em tempo poli-
nomial, em relação ao tamanho 
da entrada.
Convém ressaltar que um polinômio 
pode conter qualquer expoente, por 
exemplo: n1560. Isso não deixa de 
torná-lo tratável, mas pode levar 
uma grande quantidade de tempo 
de processamento.
Já os intratáveis são aqueles cujos 
algoritmos são inerentemente 
ineficientes, com tempo expo-
nencial ao tamanho da entrada. 
Esses problemas são resolvidos 
por uma máquina de turing não 
determinística em tempo poli-
nomial, em relação ao tamanho 
da entrada, estando, portanto, na 
classe de complexidade NP.
Saiba mais
106 Teoria dos Grafos
Já o problema da cobertura de arestas mínima pode ser resolvido de uma ma-
neira ótima, encontrando um emparelhamento máximo, ou seja, um conjunto in-
dependente de arestas que não compartilham vértices e aplicando um algoritmo 
guloso para agregar todos os vértices.
5.4 Planaridade
Vídeo Um grafo é planar se sua representação gráfica em um plano pode ser feita 
sem que suas arestas se cruzem (SZWARCFITER, 2018).
Tome como exemplo o grafo apresentado na Figura 23. Apesar da sua represen-
tação na Figura 23 apresentar intersecção nas arestas (v2, v3) com (v1, v5) e, também, 
(v3, v4) com (v1, v5), o grafo G pode ser representado graficamente de outra forma, 
como mostra a Figura 24. Portanto, o grafo é planar.
Fonte: Elaborada pelo autor.
Figura 23
Grafo G com interseções em arestas
v1 v5
v4v2
v3
Fonte: Elaborada pelo autor.
Figura 24
Grafo G com interseções em arestas
v1 v5
v4v2
v3
Uma das motivações do estudo de planaridade de grafos veio do problema das 
três casas, enunciado pelo matemático inglês Henry Ernest Dudeney (1857-1930) 
em 1913 (SANTOS, 2017).
Nesse problema, três companhias de fornecimento de serviços públicos devem 
servir três casas distintas. Todas devem usar tubulações subterrâneas na mesma 
profundidade do solo, por questões de segurança. Representado como um gra-
fo, pode-se observar seis vértices e nove arestas. O problema é descobrir se há a 
possibilidade de suprir todos os serviços, sem que as linhas se cruzem.
A Figura 25 a seguir ilustra este problema.
Fonte: Elaborada pelo autor.
Figura 25
Problema das três casas
v4 v5 v6
v2 v3v1
Companhia 
Luz
Casa 1
Companhia 
Água
Casa 2
Companhia 
Telefone
Casa 3
Problemas em Grafos 107
Ao ser enunciado como um problema de grafos, percebe-se que o problema das 
três casas pode ser representado pelo grafo bipartido completo K3,3. Para respon-
der à questão, deve-se descobrir se o K3,3 permite uma representação gráfica em 
que suas arestas não se cruzam, isto é, se ele é planar.
No problema das três casas, em especial, não há uma forma de 
desenhar o grafo em um plano sem que as arestas se cruzem. Inclu-
sive, o K3,3 é uma referência para a planaridade, conforme será visto 
no teorema de Kuratowski mais adiante.
Em grafos planares, as arestas dividem o plano em regiões cha-
madas de faces. Seja o exemplo do grafo da Figura 26, nesse grafo 
tem-se quatro faces e a face de número quatro é chamada de face 
externa.
O Teorema a seguir apresenta a Fórmula de Euler que relaciona 
os vértices, arestas e faces em um grafo planar conexo.
Teorema 1
Fórmula de Euler (1750)
Seja um grafo conexo planar G e sejam: n o número de vértices, a o número de 
arestas e f o número de faces, tem-se n – a + f = 2.
Essa fórmula também pode ser apresentada como n + f = a + 2 e percebe-se, 
facilmente, sua igualdade (SZWARCFITER, 2018). Considerando o grafo da Figura 26, 
pode-se encontrar n = 4, f = 4 e a = 6, então, n + f = a + 2, assim, 4 – 6 + 4 = 2.
Pela fórmula de Euler, percebe-se que quanto maior for o número de arestas 
em um grafo, relativo ao número de vértices, mais difícil será a obtenção de uma 
representação plana do grafo. Isso é dado por meio do seguinte corolário, que de-
fine um limite máximo para o número de arestas.
Corolário 1: seja um grafo planar simples contendo n vértices, n ≥ 3, e a arestas, 
tem-se a ≤ 3n – 6.
Na prática, isso significa, por exemplo, que em um grafo planar com cinco vér-
tices há, no máximo, 9 arestas. Deve-se tomar cuidado, pois o Corolário 1 pode ser 
usado para demonstrar que um grafo não é planar, mas, se a condição for satisfei-
ta, não há garantia de que o grafo é planar.
Outro exemplo pode ser visto ao considerar o K3,3 (Figura 27), o qual possui 6 
vértices e 9 arestas. Aplicando-se a fórmula do Corolário 1, a condição é satisfeita, 
isto é, 9 ≤ 3*6 – 6, mas o grafo K3,3 não é planar.
Outro resultado importante advindo do Teorema 5.1 é o corolário a seguir.
Corolário 2: todo grafo planar simples contém um vértice cujo grau é no máxi-
mo cinco.
Esse resultado é muito importante, pois coloca um limite numérico em, pelo 
menos, um dos vértices do grafo planar.
v4
v3
v2
v1
2
3
4
1
Figura 26
Grafo planar e suas faces
Fonte: Elaborada pelo autor.
Lemas, Teoremas e Corolários são 
conceitos são correlatos:
• Lema: é uma afirmação que 
ajuda a provar um teorema. 
Basicamente, lema é um 
teorema anterior, que ajuda a 
provar outro teorema.
• Teorema: é uma proposição 
verdadeira, visto que possui 
uma prova
• Corolário: é uma afirmação, 
uma proposição ou outro teore-
ma, que pode ser estabelecido 
como consequência de um 
teorema já provado.
Saiba mais
108 Teoria dos Grafos
Outros resultados centrais para o estudo de grafos planares são as provas de 
que K5 e K3,3 não são planares (NICOLETTI; HRUSCHKA, 2018). A Figura 27 apresenta 
as formas mais comuns de representar graficamente K5 e K3,3.
Fonte: Elaborada pelo autor.
Figura 27
Representações de K5 e K3,3
v4 v5 v6
v2 v3v1
K3,3
K5
v4 v3
v2v5
v1
Percebe-se que o K3,3 atende ao Corolário 1, ou seja, a = 9, n = 6, portanto, 
9 ≤ 3*6 – 6, isto é 9 ≤ 12. Mesmo assim, K3,3 não é planar.
Fazem-se necessárias, também, algumas definições em grafos para o estudo de 
grafos planares. Em um grafo G = (V, A), dois vértices, v, w ∈ V, estão em série, se 
existe um vértice x ∈ V, tal que x ≠ v, x ≠ w, grau(x) = 2 e (v, x), (x, w) ∈ A. A Figura 28 
apresenta um grafo cujos vértices v2 e v4 estão em série. Perceba que o vértice v3 
possui grau 2 e é adjacente a v2 e v4, atendendo às condições impostas na definição.
Dado um grafo G = (V, A) e os dois vértices v, w ∈ V em série, uma redução de 
série é a eliminação do vértice x e a substituição das arestas (v, x) e (x, w) pela 
aresta (v, w). Assim, para o grafo da Figura 28, o grafo da Figura 29 (lado direito) foi 
obtido de uma redução de série, no caso, eliminando-se o vértice v3 e as arestas (v2, 
v3) e (v3, v4), ligando o v2 ao v4 pela aresta (v2, v4).
Fonte: Elaborada pelo autor.
Figura 29
Redução de série
v1 v5
v4v2 v3
v1 v5
v4v2
Dois grafos, G’ e G’’, são homeomorfos se podem ser obtidos a partir do mesmo 
grafo e de uma sequência de reduções de séries. Outra forma de definir que G’ e 
G’’ são homeomorfos é se eles podem ser reduzidos a grafos isomorfos por meio 
de reduções de séries.
A Figura 30 (do lado esquerdo) apresenta dois grafos homeomorfos, pois ao se 
aplicarem várias reduções de séries, obtém-se dois grafos isomorfos (do lado direito).
Fonte: Elaborada pelo autor.
Figura 28
Grafo com vértices em série
v1 v5
v4v2 v3
Problemas em Grafos 109
No primeiro grafo da Figura 30, foi reduzida a série (v1, v6), (v6, v7) e, em seguida, 
a (v1, v7), (v7, v5). No segundo grafo da Figura 30 foi reduzida a série (v1, v7), (v7, v2) 
seguidada (v1, v6), (v6, v5) e, por fim, a (v2, v3), (v3, v4).
v1 v5
v4v2
Fonte: Elaborada pelo autor.
Figura 30
Grafos homeomorfos
v1 v5
v4v2 v3
v6 v7
v1 v5
v4v2 v3
v6
v7
v1 v5
v4v2
Por meio dos grafos K5 e K3,3 e do conceito de homeomorfismo de grafos, o Teo-
rema de Kuratowski dá as condições necessárias e suficientes para indicar se um 
grafo é planar ou não (NICOLETTI; HRUSCHKA, 2018).
Teorema 2
Teorema Kuratowsk
Um grafo G é planar, se, e somente se, não tem um subgrafo homeomorfo a K5 
ou K3,3.
Observe o grafo não planar da Figura 31. Para mostrar que esse grafo não é 
planar, pode-se buscar por um subgrafo homeomorfo a K5 ou K3,3. Um subgrafo é 
obtido pela remoção de arestas e vértices. Para a propriedade de homeomorfismo, 
faz-se redução de série.
v1
v5
v4
v8
v9
v6v7
v2 v3
Figura 18
Grafo não planar
Fonte: Elaborada pelo autor.
110 Teoria dos Grafos
Para provar que esse grafo não é planar, a ideia é eliminar vértices e arestas 
para encontrar um subgrafo que seja homeomorfo a K5 ou K3,3. Ao encontrar esse 
subgrafo, efetuam-se reduções de série até encontrar um subgrafo que seja iso-
morfo a K5 ou K3,3.
A Figura 32 apresenta os passos efetuados até aqui. Primeiramente, serão elimi-
nadas as arestas (v4, v5) e (v2, v3). Esse subgrafo obtido é homeomorfo a K3,3 e, para 
ter certeza, efetuam-se as seguintes reduções de série: 1ª. redução (v1, v9) e (v9, v5), 
2ª. redução (v2, v8) e (v8, v5), e 3ª. redução (v3, v7), (v7, v6). Assim, pode-se perceber que 
o grafo obtido é isomorfo a K3,3.
Figura 32
Passos para provar que o grafo não é planar
v1
v5
v4
v8
v9
v6v7
v2 v3
Remoção 
de (V4, V5) e 
(V2, V3)
v1
v5
v8
v9
v6v7
v3
v4
v2
Redução de 
série (V1, V9) e 
(V9, V5)
v1
v5
v8
v9
v6v7
v3
v4
v2
v1
v5
v8
v6v7
v3
v4
v2
Redução de 
série (V2, V8) e 
(V8, V5)
v1
v5
v8
v6v7
v3
v4
v2
v1
v5
v6v7
v3
v4
v2
Fonte: Elaborada pelo autor.
Redução de 
série (V3, V7) e 
(V7 V6)
v1
v5
v6v7
v3
v4
v2
v1
v5
v6
v3
v4
v2
O primeiro algoritmo para teste de planaridade surgiu, em 1961, com Auslander 
e Parter (AUSLANDER; PARTER, 1961). O algoritmo posteriormente foi corrigido por 
Problemas em Grafos 111
Goldstein e, então, ficou conhecido como Algoritmo Auslander, Parter e Goldstein (Al-
goritmo APG) e possui complexidade cúbica (GOLDSTEIN, 1963).
O primeiro algoritmo com complexidade de tempo linear, para verificação de 
planaridade de grafos, é o Hopcroft e Tarjan (Algoritmo HT), fundamentado no al-
goritmo APG (HOPCROFT; TARJAN, 1974).
Outros algoritmos também foram desenvolvidos e são tópicos de pesquisa mais 
avançada na área.
5.5 Coloração
Vídeo Em grafos, uma coloração vértices é uma atribuição de rótulos aos vértices de 
grafos, tradicionalmente chamados de cores, de tal forma que não haja dois vérti-
ces adjacentes rotulados com a mesma cor (NICOLETTI; HRUSCHKA, 2018). Em teoria 
de grafos, também há os conceitos de coloração de arestas e coloração de faces, mas, 
aqui, será abordada apenas a coloração de vértices, sendo o ponto de partida para 
o estudo de coloração em grafos.
A Figura 33 apresenta um grafo com uma coloração aplicada. 
Uma coloração de vértices contendo k cores diferentes é chama-
da de k-coloração e, nesse caso, o grafo é k-colorível. No exemplo 
apresentado na figura tem-se três cores, portanto, trata-se de uma 
3-coloração para o grafo.
Claramente, percebe-se que em um grafo com n vértices, po-
de-se usar n cores, uma para cada vértice e, dessa forma, segu-
ramente, vértices adjacentes não possuirão a mesma cor. Assim, 
encontrar uma n-coloração em um grafo com n vértices, é trivial e 
não possui utilidade prática. Já encontrar uma coloração mínima, 
isto é, obtida com um número mínimo de cores, é um problema 
difícil e possui muitas aplicações práticas.
Em um grafo G, o número mínimo n de cores possíveis, tal que existe uma 
n-coloração em G, é chamado de índice cromático ou número cromático, denotado 
por χ(G). Assim, se χ(G) = n, então, G é n-cromático.
Se o grafo possui laços (vértices adjacentes a si mesmos), então, não há colora-
ção possível. Se existem arestas paralelas, ou seja, arestas que incidem nos mes-
mos vértices, diz-se que os vértices em questão são adjacentes e será considerada 
somente uma dessas arestas. Assim, consideram-se somente grafos simples.
Com base nisso, tem-se os seguintes teoremas e definições:
Teorema 3
Se um grafo G tem n vértices, então, χ(G) ≤ n.
Esse teorema é intuitivo. Se todos os n vértices de um grafo forem conecta-
dos a todos os demais, será necessário n cores para colori-lo. Caso contrário, há a 
possibilidade do número cromático ser menor que n. Então, n é um limite máximo 
para o número de cores necessárias para colorir qualquer grafo.
v1 v5
v4v2
v3
Figura 33
Grafo com uma coloração aplicada
Fonte: Elaborada pelo autor.
112 Teoria dos Grafos
Um grafo em que cada vértice é conectado a todos os demais é chamado de gra-
fo completo. Um grafo completo, com n vértices, é denotado por Kn e, assim, segue 
o próximo teorema.
Teorema 4
Seja o grafo Kn, então, χ(Kn) = n, para todo n ≥ 1.
Isto é facilmente observado em grafos completos. Como o exemplo do K5, na 
Figura 34, em que são cinco vértices e cada vértice é adjacente aos outros quatro 
vértices. Para o Kn, cada vértice é ligado aos outros n – 1 vértices. Assumindo v1, é 
necessária uma cor para colorir v1 e cores diferentes para cada vértice adjacente, 
ou seja, mais quatro cores. O mesmo raciocínio vale para Kn.
A Figura 35 apresenta uma coloração possível para o K5.
v4 v3
v2
v1
v5
Figura 34
Grafo K5
Fonte: Elaborada pelo autor.
v4 v3
v2
v1
v5
Figura 35
Grafo K5 colorido
Fonte: Elaborada pelo autor.
O Teorema 4 também relaciona os conceitos de coloração e cliques, isto é, 
subgrafos completos. Como são necessárias p cores para colorir os p vértices de 
uma clique, então, para um grafo G, seu número cromático é maior ou igual ao 
tamanho da sua maior clique. Pode-se dizer que, se um grafo G contém Kn como 
subgrafo, então, χ(G) ≥ n.
O próximo teorema apresenta o valor do número cromático para grafos 
bipartidos.
Teorema 5
Seja um grafo G não vazio, tem-se χ(G) = 2, ou seja, o grafo é bicolorível, se, e 
somente se, G for bipartido.
Esse teorema também é intuitivo, pois os grafos bipartidos são formados por 
dois conjuntos de vértices, sendo que os vértices pertencentes a cada um desses 
Problemas em Grafos 113
conjuntos não são adjacentes entre si. Desse modo, para cada conjunto, basta atri-
buir uma cor a todos seus vértices e, assim, o grafo total é bicolorível.
A Figura 36 mostra um grafo bipartido, visto que pode ser separado em dois 
conjuntos de vértices, {v1, v2} e {v3, v4, v5}, de modo que os vértices não são adja-
centes dentro dos conjuntos apresentados e as arestas existentes ligam vértices 
entre os conjuntos. Assim, cada um desses conjuntos recebe uma cor e a Figura 37 
apresenta uma coloração possível.
v2
v5v4
v1
v3
Figura 36
Grafo Bipartido
Fonte: Elaborada pelo autor.
Figura 37
Grafo Bipartido Colorido
Fonte: Elaborada pelo autor.
v4 v5v3
v2
v1
O conceito de coloração também é relacionado ao de conjunto independente de 
vértices. Um conjunto independente de vértices, ou um conjunto estável de vértices, 
de um grafo é o conjunto de vértices totalmente desconexos. Em outros termos, 
eles não são adjacentes entre si.
Essa propriedade pode ser observada no grafo da Figura 37, em que os conjun-
tos {v1, v2} e {v3, v4, v5} possuem vértices não adjacentes entre si e, portanto, são 
conjuntos estáveis de vértices.
A Figura 38 apresenta o grafo G.
v3
v5v4
v7
v6
v1v2
Figura 38
Grafo G
Fonte: Elaborada pelo autor.
Consegue-se obter três conjuntos independentes de vértices de G, que são 
disjuntos, por exemplo:
114 Teoria dos Grafos
 • {v5, v1, v7}
 • {v2, v3, v4}
 • {v6}
Assim, cada um desses conjuntos pode ser colorido com uma cor diferente, con-
forme mostra a Figura 39.
v3
v5v4
v7
v6
v1v2
Figura 39
Grafo G coloridoFonte: Elaborada pelo autor.
Seja uma k-coloração a um grafo G = (V, A) e sejam V1, V2, ..., Vk os subconjuntos 
disjuntos de V, induzidos pela k-coloração, então, cada Vi é um conjunto indepen-
dente de vértices de G. Assim, para determinar uma coloração mínima de G, pode-
-se particionar o conjunto V em um número mínimo de conjuntos independentes 
de vértices, sendo que cada um desses conjuntos receberá uma cor.
Considerando o grafo G = (V, A), o grau máximo de G, denotado por ∆(G), é o 
grau do vértice que possui o maior grau em G, isto é, ∆(G) = max{ grau(v) | v ∈ V }.
Pode-se observar que sempre é possível colorir um grafo G com ∆(G)+1 cores. Isso 
porque, se os vértices possuem grau no máximo ∆(G), usa-se uma cor para o próprio 
vértice e ∆(G) cores para os adjacentes. Mesmo para grafos completos, Kn possui ∆(G) 
= n – 1, o que significa que são necessárias n cores para colori-lo.
Assim, há um limite para o número cromático, em qualquer grafo, dado por 
χ(G) ≤ ∆(G)+1.
O próximo teorema foi enunciado pelo matemático inglês Rowland Leonard 
Brooks (1916-1993) em 1941, e dá uma relação do melhor que a apresentada ante-
riormente, entre o número cromático e o grau máximo de um grafo.
Teorema 6
Teorema de Brooks (1941)
Seja um grafo simples conexo G e seja ∆(G) ≥ 3. Se G não é um grafo completo (Kn) 
e não possui ciclos ímpares (com um número ímpar de vértices), então, χ(G) ≤ ∆(G).
O Teorema de Brooks é um resultado importante, pois dá um limite melhor para 
o número cromático χ(G) de um grafo, com ∆(G) como seu grau máximo. Em suma, 
Problemas em Grafos 115
dado um grafo G que atende algumas condições (∆(G) ≥ 3, não ser Kn, nem ter ciclos 
ímpares), o número cromático será sempre menor ou igual ao seu grau máximo.
Outro resultado importante da coloração de grafos é o Teorema das Quatro 
Cores, conjecturado por Francis Guthrie em 1952, provado pelo matemático 
estadunidense Kenneth Appel (1932-2013) e pelo matemático alemão Wolfgang 
Haken (1928-) em 1976. Este também foi o primeiro teorema matemático provado 
com o auxílio de um computador.
Teorema 7
Teorema das Quatro Cores, Appel e Haken
Todo grafo planar é 4-colorível.
Este teorema indica que qualquer grafo planar pode ser colorido com quatro co-
res. Mas decidir se um grafo planar é 3-colorível é um problema difícil (NP-Completo). 
Há várias aplicações para coloração em grafos; um exemplo é a aplicação de 
coloração em grafos para o controle de tráfego aéreo (BARNIER; BRISSET, 2004). O 
objetivo é evitar o congestionamento e o cruzamento entre voos que trafegam na 
mesma altura, modelando os cruzamentos dos voos. Cada voo é modelado como 
um vértice e cada cruzamento como uma aresta entre dois voos. Uma coloração, 
nesse grafo, determina a distribuição de diferentes alturas, isto é, cada cor uma 
altura que deve ser atribuída ao voo, garantindo a segurança nos cruzamentos.
CONSIDERAÇÕES FINAIS
Neste capítulo foram estudados outros problemas em grafos, os conceitos de cli-
que, conjunto estável de vértices e o problema da clique. Também foi abordado o 
conceito de cobertura, tanto de arestas quanto de vértices, bem como sua aplicação. 
A planaridade do grafo também foi explorada, expondo os teoremas que dão base ao 
estudo. Por fim, o problema da coloração de grafos foi apresentado, assim como seus 
teoremas e um exemplo de aplicação.
ATIVIDADES
1. Enumere todas as cliques com tamanho maior ou igual a 2 do grafo a seguir.
v1 v5
v4v2
v3
116 Teoria dos Grafos
2. Dê a clique máxima do grafo a seguir.
v7 v5
v1
v4
v2
v3
v6
3. Seja o grafo K3,3. desenhe o grafo e dê uma cobertura de arestas.
4. Considerando um grafo planar com oito vértices, qual o limite máximo de arestas 
que esse grafo contém?
5. Utilizando o Teorema de Kuratowski, prove que o grafo a seguir não é planar.
v7
v6v8
v1
v2v5
v3v4
6. Dado o grafo a seguir, encontre a uma coloração mínima e dê seu número 
cromático.
v7
v6
v8
v1
v2
v5
v3
v4
Problemas em Grafos 117
REFERÊNCIAS
AUSLANDER, L; PARTER, S. On imbeddings graphs in the plane, J. Math and Mech, v. 10, n. 3, p. 517-523, 
1961.
BARNIER, N.; BRISSET, P. Graph Coloring for Air Traffic Flow Management. Annals of Operation Research, n. 
130, p.163-178, 2004.
GOLDBARG, M. C.; GOLDBARG, E. Grafos: conceitos, algoritmos e aplicações. Rio de Janeiro: Elsevier, 2012.
GOLDSTEIN, A. An efficient and constructive algorithm for testing whether a graph can be embedded in a 
plane. Graph and Combinatorics Conference, Dept. Math., Princeton University, p. 16-18, 1963.
HOPCROFT, J; TARJAN, R. Efficient planarity testing. Journal of the Association for Computing Machinery, v. 21, 
n. 4, p. 549-568, 1974.
NICOLETTI, M. C.; HRUSCHKA Jr, E. R. Fundamentos da teoria dos grafos para computação. São Paulo: Editora 
LTC, 2018.
RHODES, N. et al. CLIP: similarity searching of 3D databases using clique detection. Journal of Chemical 
Information and Computer Sciences, v. 43, n. 2, p. 443–448, 2003.
SANTOS, E. L. S. Planaridade em grafos: o teorema de Kuratowski. São Cristóvão, 2017. Dissertação(Mestrado 
em Matemática) – Universidade Federal de Sergipe.
SZWARCFITER, J. L. Teoria Computacional de Grafos. Rio de Janeiro: Elsevier, 2018.
SZWARCFITER, J. L.; FIGUEIREDO, C. M. H. de F. Emparelhamento em Grafos: Algoritmos e Complexidade. 
Jornada de Atualização em Informática (JAI). Rio de Janeiro. 1999.
ZUGE, A. P. Algoritmos para o problema da clique máxima: análise e comparação experimental. Curitiba, 
2017. Tese (Doutorado em Ciência da Computação) – Universidade Federal do Paraná.
118 Teoria dos Grafos
GABARITO 
1 Introdução ao estudo dos grafos
1. Pelo teorema de Euler (1736), o teórico provou que para um grafo ser euleriano 
todos os seus vértices precisam ter grau par. Assim, uma solução possível é dada 
pela figura a seguir. As pontes (arestas) adicionadas estão tracejadas e são a8, a9 e a10.
a1
a2
a8
a4a7
a6
a9
a5v2
a3
a10
v1
v3
v4
E um possível ciclo euleriano, partindo de v1 é: a1, a2, a10, a3, a6, a5, a9, a7, a4, a8.
2. Uma representação geométrica possível é:
3
2
6
4
5
1
Gabarito 119
3. A matriz de adjacências é uma matriz contendo todos os vértices nas linhas e 
colunas. Coloca-se 1 se os vértices são adjacentes e 0 caso contrário. Assim, a 
matriz de adjacências é:
1 2 3 4 5 6
1 0 0 1 1 1 0
2 0 0 1 1 1 0
3 1 1 0 0 1 0
4 1 1 0 0 1 0
5 1 1 1 1 0 0
6 0 0 0 0 0 0
4. Sim, o grafo é bipartido, portanto, seus vértices podem ser separados em dois 
conjuntos: V1 = {1, 2, 4, 5} e V2= {3, 6}, tal que não existe aresta entre os vértices 
de V1, nem de V2, e toda aresta conecta um vértice de V1 com um vértice de V2. 
Colorindo diferentemente os dois conjuntos, tem-se o grafo a seguir.
32
4
5
1
6
5. O grau de um grafo é dado pela soma do grau de seus vértices, nesse caso: 5+2+2+2+2+1 
= 14. Como o grau de um grafo é o dobro do número de arestas, esse grafo possui sete 
arestas. Uma possível representação é dada pela figura a seguir:
v4
v5v6
v3v2
v1
2 Conectividade
1. As componentes conexas de um grafo são seus subgrafos maximais – que não 
estão contidos em outros grafos – conexos. Assim, no grafo apresentado tem-se 
duas componentes conexas:
120 Teoria dos Grafos
v4
v6
v5
v2
v1
v3
2. Sendo um digrafo, o caminho deve seguir as orientações das arestas. Portanto um 
caminho entre v3 e v4 é: (v3, v6), (v6, v2), (v2, v5), (v5, v4), representado na figura a seguir.
v1
v4
v5
v2
v6v3
3. Um ciclo euleriano é um caminho que inicia e termina no mesmo vértice que passa 
por todas as arestas do grafo somente uma vez. Assim, no grafo apresentado um 
ciclo euleriano é: (v1, v3), (v3, v5), (v5, v4), (v4, v2), (v2, v1), (v1, v5), (v5, v2), (v2, v3), (v3, v4), (v4, v1)
4. Um grafo semi-hamiltoniano é um grafo que possui um caminho hamiltoniano, 
mas não um ciclo hamiltoniano. Assim, basta adicionar uma aresta entre o término 
e a origem de um caminho hamiltoniano.
No caso do grafo apresentado, o caminho hamiltoniano é: (v1, v3), (v3, v4), (v4, v2).Desse modo, basta adicionar a aresta (v2, v1) e o grafo se torna hamiltoniano com o 
seguinte ciclo hamiltoniano: (v1, v3), (v3, v4), (v4, v2), (v2, v1).
O grafo fica:
v4
v2
v3v1
5. Um subgrafo induzido G’ sobre um grafo G é aquele em que, dados todos os 
vértices pertencentes a G’, todas as arestas em G sobre estes vértices também 
Gabarito 121
são arestas em G’. Assim, o subgrafo a seguir é um subgrafo induzido do grafo 
apresentado no enunciado da questão.
v5
v2
v1
6. As componentes biconexas, ou blocos de um grafo, são os subgrafos maximais 
biconexos em vértices – isto é, não possui articulações – ou isomorfos a K2. Assim, 
as componentes biconexas ou blocos do grafo apresentado são:
v8
v8
v7
v6
v2
v6
v2
v6
v7
v4
v1
v2
v3
3 Caminho mínimo e árvores geradoras 
1. A árvore de busca em profundidade resultante é:
v5 v3
v2
v1
v4
v6
2. A árvore de busca em largura resultante é:
v5 v3
v2
v1
v4
v6
122 Teoria dos Grafos
3. A árvore geradora mínima obtida pelo algoritmo de Prim é:
v5 v3
v2
v1
v4
v6
1
3
2
3
5
4. A árvore geradora mínima obtida pelo algoritmo de Kruskal é:
v5 v3
v2
v1
v4
v6
1
3
2
3
5
5. Para melhor entendimento, os rótulos e as distâncias estão assinalados no grafo 
a seguir.
v5 v3
v2
v1
v4
v6
1
3
10
2
2
4
3
5
V1 4
V1 3
V6 6V6 8
V5 9
0 0
4 Grafos eulerianos e hamiltonianos
1. Partindo da terra, as escolhas são:
 • Terra → Calisto: 3,1 anos
 • Calisto → Io: 0,8 anos
Gabarito 123
 • Io → Ganímedes: 1,1 anos
 • Ganímedes → Mimas: 5,7 anos
 • Mimas → Titan: 0,6 anos
 • Titan → Terra: 8,1 anos
Total de 19,4 anos de expedição.
2. A busca gulosa com repetição calcula um ciclo hamiltoniano iniciando de cada 
vértice e escolhe o menor. Os ciclos encontrados são:
 • Terra → Calisto → Io → Ganímedes → Mimas → Titã → Terra: 19,4 anos
 • Calisto → Io → Ganímedes → Terra → Titã → Mimas → Calisto: 19 anos
 • Io → Calisto → Ganímedes → Terra → Titã → Mimas → Io: 18,9 anos
 • Ganímedes → Io → Calisto → Terra → Titã → Mimas → Ganímedes: 19,4 anos
 • Mimas → Titã → Io → Calisto → Ganímedes → Terra → Mimas: 19,4 anos
 • Titã → Mimas → Io → Calisto → Ganímedes → Terra → Titã: 18,9 anos
Assim, escolhe-se um dos ciclos de 18,9 anos, por exemplo:
 • Io → Calisto → Ganímedes → Terra → Titã → Mimas → Io: 18,9 anos.
Rearranjado para iniciar na Terra:
Terra → Titã → Mimas → Io → Calisto → Ganímedes → Terra.
3. O caminho euleriano é dado pelas seguintes arestas:
(v1, v8), (v8, v2), (v2, v7), (v7, v5), (v5, v6), (v6, v7), (v7, v3), (v3, v5), (v5, v4), (v4, v3), (v3, v2), (v2, v1)
4. O Teorema de Ore afirma que se o grafo possui mais de 3 vértices e para todo par 
de vértices não adjacentes a soma de seus graus for maior ou igual ao número de 
vértices, então, o grafo é hamiltoniano.
Assim, se as condições do teorema forem satisfeitas, garante-se um grafo 
hamiltoniano.
O grafo G possui 6 vértices (que é maior ou igual a 3, conforme condição). Não é 
informado quais vértices são adjacentes, mas como todos têm grau igual a três, 
a soma dos graus de quaisquer pares de vértices é igual a 6. Para os vértices não 
adjacentes, a soma de seus graus também é 6, atendendo à outra condição do 
teorema.
Portanto, o grafo G é hamiltoniano. 
5. O grafo G não é euleriano. O Teorema de Euler atesta que o grafo ter grau par em 
todos os vértices é uma condição necessária e suficiente para ser euleriano.
O grafo G apresentado possui os vértices v1 e v2 com grau ímpar, portanto, não é 
euleriano. 
5 Problemas em Grafos
1. Uma clique é um subconjunto de vértices que induz o subgrafo completo do grafo 
original. No grafo apresentado tem-se 12 cliques, oito de tamanho 2 e quatro 
cliques de tamanho 3, a saber:
 • {v1, v2}
 • {v2, v4}
124 Teoria dos Grafos
 • {v4, v5}
 • {v1, v5}
 • {v1, v3}
 • {v2, v3}
 • {v3, v4}
 • {v3, v5}
 • {v1, v2, v3}
 • {v1, v3, v5}
 • {v2, v3, v4}
 • {v3, v4, v5}
2. A clique máxima nesse grafo é {v2, v7, v5, v4}, que induz a um subgrafo K4. Observe 
a seguir o grafo apresentado com as arestas adjacentes aos vértices da clique em 
tracejado.
v7 v5
v1
v4
v2
v3
v6
3. Grafo K3,3:
v4 v5 v6
v2 v3v1
Uma cobertura de arestas é: {(v1, v4), (v2, v5), (v3, v6)} e pode ser vista em tracejado a 
seguir.
v4 v5 v6
v2 v3v1
Gabarito 125
4. Pelo Corolário 5.2, um grafo planar tem seu número de arestas limitado pela 
seguinte fórmula: a ≤ 3n – 6. Assim, um grafo planar, contendo oito vértices, possui, 
no máximo, 18 arestas.
5. O Teorema de Kuratowski afirma que um grafo é planar, se, e somente se, não 
possuir um subgrafo homeomorfo a K5 ou K3,3.
Como se quer provar que o grafo não é planar, para conseguir um subgrafo pode-se 
remover arestas ou vértices até encontrar um grafo homeomorfo a K5 ou K3,3.
Para o grafo em questão, removem-se as arestas (v8, v6) e (v1, v7), obtendo-se o 
seguinte grafo:
v7
v6v8
v1
v2v5
v3v4
Esse grafo é homeomorfo a K5 e isso pode ser observado, pois, se forem removidas 
as séries 1) (v4, v8), (v8, v5); 2) (v4, v7), (v7, v3); e 3) (v2, v6) e (v6, v3), obtém-se exatamente 
o K5, como pode ser observado no grafo a seguir, provando que o grafo original 
não é planar.
v4 v3
v2v5
v1
6. O número cromático do grafo é 2, pois é possível usar, no mínimo, duas cores para 
colori-lo. A seguir tem-se o resultado da aplicação da coloração no grafo.
v7
v6
v8
v1
v2
v5
v3
v4
Razer Anthom Nizer Rojas Montaño
TEORIA DOS GRAFOS
Razer Anthom
 N
izer Rojas M
ontaño
Código Logístico
59398
Fundação Biblioteca Nacional
ISBN 978-85-387-6636-0
9 7 8 8 5 3 8 7 6 6 3 6 0delas, é possível elaborar problemas complexos de maneira correta, seguindo 
o formalismo matemático.
1.3 Tipos de grafos
Vídeo Os grafos podem ser classificados em diversos tipos, de acordo com algumas 
características específicas. Essas podem ser estruturais, sendo direcionamento das 
arestas, ou na composição dos seus elementos, por exemplo, possuindo somente 
um vértice e nenhuma aresta.
Relembrando a definição apresentada na Seção 1.2, um grafo simples não 
possui laços, isto é, arestas com pontas no mesmo vértice, nem arestas diferen-
tes que incidem nos mesmos vértices, ou paralelas (Figura 7). Um pseudografo 
é um grafo que contém laços; já um multigrafo é um grafo que contém arestas 
paralelas.
v4
v5
v3
Figura 7
Grafo simples
Fonte: Elaborada pelo autor.
v2
v1
O livro Uma Introdução 
Sucinta à Teoria dos Grafos 
é uma leitura complemen-
tar que reforça os concei-
tos básicos de grafos.
FEOFILOFF, P.; KOHAYAKAWA, Y.; 
WAKABAYASHI, Y. São Paulo: Edusp, 
2011.
Livro
Introdução ao estudo dos grafos 15
Ademais, estendendo a definição dos grafos, pode-se ter grafos com arestas 
direcionadas, em que uma aresta v, w conecta o vértice v a w e, portanto, é dife-
rente da aresta (w, v), que conecta o vértice w a v. Nesse caso, tem-se um grafo 
orientado ou digrafo. Este último é representado graficamente com as arestas 
contendo setas (Figura 8). Também, é possível que os grafos possuam valores 
(pesos) nas arestas, sendo chamados, nesse caso, de grafo ponderado ou valora-
do, podendo ou não ser direcionado (Figura 9).
Figura 9
Grafo ponderado ou valorado
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
3
1
1
5
8
20
10
Figura 8
Digrafo ou grafo direcionado
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Um grafo nulo é um grafo que possui um conjunto de vértices 
vazio, ou seja, G = (V, A), V = Ø. Já um grafo trivial possui apenas um 
vértice e nenhuma aresta.
Um grafo regular é um grafo em que todos os vértices possuem 
o mesmo número de arestas incidentes (Figura 10).
Outros exemplos de grafos regulares podem ser vistos na figura a 
seguir. É importante perceber, também, que qualquer grafo comple-
to é regular, como observado na Figura 2.
Figura 11
Grafos regulares
Fonte: Elaborada pelo autor.
Um grafo é conexo quando é possível estabelecer um caminho desde um vértice 
até qualquer outro vértice passando por arestas. Todos os grafos apresentados até 
agora são conexos, caso contrário, trata-se de um grafo desconexo. No exemplo a 
seguir, o vértice v3 faz parte do grafo, mas não tem aresta com nenhum outro vértice. 
Já na Figura 12-B, os vértices v3 e v5 possuem aresta entre si, mas não aresta com a 
outra parte do grafo, sendo, também, desconexo.
Figura 10
Grafo regular
Fonte: Elaborada pelo autor.
v4
v3
v2
v1
16 Teoria dos Grafos
Figura 12
Grafo desconexo
v4
v5
v3
v2
v1
Fonte: Elaborada pelo autor.
A – Exemplo de grafo com um vértice desconexo. B – Grafo com um subgrafo desconexo.
v4
v5
v3
v2
v1
Um grafo é dito acíclico se não possui ciclos, isto é, quando não é possível caminhar 
de um vértice a vértices adjacentes até retornar à origem. O grafo simples da Figura 7 é 
cíclico, visto que se pode caminhar de v2 até v4 por uma aresta, então de v4 a v5 por ou-
tra aresta e de v5 até v2. Caso contrário, é chamado de grafo acíclico, como na Figura 13.
v4
v5
Figura 13
Grafo acíclico
Fonte: Elaborada pelo autor.
v3
v2
v1
Chama-se árvore um grafo simples, acíclico e conexo. Simples significa que não 
pode ter laços nem arestas paralelas; acíclico indica que não é possível caminhar 
entre os vértices partindo de v e chegando novamente em v; e conexo determi-
na que todos os vértices precisam ser atingíveis por qualquer vértice. O grafo da 
Figura 13 também é uma árvore.
Se o grafo for simples, acíclico, mas não conexo, é chamado de floresta, isto é, 
uma união disjunta de árvores. A Figura 14 apresenta uma floresta formada por 
três árvores.
v4
v5
Figura 14
Grafo floresta
Fonte: Elaborada pelo autor.
v3
v7
v9
v6
v8
v2
v1
Introdução ao estudo dos grafos 17
Um grafo é chamado bipartido por ser separado em dois conjuntos de vérti-
ces, V1 e V2, de modo que não haja arestas entre elementos do mesmo conjunto 
e que toda aresta de G una um vértice de V1 a outro de V2. Por exemplo, o grafo 
da Figura 15 é bipartido, pois é possível separar seus vértices em dois conjuntos 
V1 = {v1, v2} e V2 = {v3, v4, v5} sem que haja arestas entre {v1, v2}, nem arestas entre 
{v3, v4, v5} e todas as arestas conectam vértices de V1 e V2, ou seja, 
A
 (v, w) ∈ A, v ∈ 
V1 e w ∈ V2. A Figura 16 apresenta os subconjuntos V1 e V2.
Figura 15
Grafo bipartido
Fonte: Elaborada pelo autor.
v4
v5
v2
v1
v3
Figura 16
Grafo bipartido com os subconjuntos
Fonte: Elaborada pelo autor.
v4
v1
v3
v5
v2
V1
V2
Um grafo bipartido completo é um grafo bipartido em que há arestas en-
tre todos os elementos de V1 e V2. Assumindo |V1| = m e |V2| = n, então, o 
grafo é denotado Km,n. Na Figura 17, pode-se observar alguns grafos bipartidos 
completos.
K1,3 K2,3 K3,3
Figura 17
Grafos bipartidos completos
Fonte: Elaborada pelo autor.
O artigo Algoritmos para Grafos em C via Sedgewick, de Paulo Feofiloff, apresenta uma vasta 
gama de materiais básicos e avançados sobre grafos, todos com base no volume Graph 
Algorithms, da terceira edição do livro Algorithms in C, de Robert Sedgewick, que é um clássico 
na ciência da computação.
Acesso em: 14 abr. 2020.
https://www.ime.usp.br/~pf/algoritmos_para_grafos/
Artigo
1.4 Vizinhança e grau
Vídeo Nesta seção serão apresentados alguns conceitos referentes à vizinhança e ao 
grau, que darão base para o estudo de problemas mais complexos.
O número de vértices de um grafo (G = (V, A)) é representado por |V|, sendo a 
quantidade de elementos de V (G) denominada ordem do grafo G. Já o número de 
18 Teoria dos Grafos
arestas de um grafo é representado por |A|, sendo a quantidade de elementos de 
A (G) denominada dimensão do grafo G.
Por exemplo, qual a ordem e a dimensão do grafo da figura a seguir?
Figura 18
Grafo G com arestas
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1 a3
a1
a5
a2
a4
Pode-se visualizar, na Figura 18, a ordem cinco (quantidade de vértices) e a di-
mensão cinco (quantidade de arestas).
Dados dois vértices v e w e a aresta a = vw que os conecta, diz-se que a aresta 
a incide em v e incide em w. Considerando o grafo da Figura 18, a aresta a1 incide 
sobre os vértices v2 e v5.
O par de vértices v e w é dito adjacente se conectado por uma aresta. Duas ares-
tas são adjacentes quando incidem em um mesmo vértice. Por exemplo, no grafo 
da Figura 18, os vértices v4 e v3 não são adjacentes, pois não possuem uma aresta 
que os conecta. As arestas a2 e a4 são adjacentes, pois incidem no mesmo vértice v2.
A vizinhança de um vértice é o conjunto de vértices adjacentes a v, denotado 
por vizinhos (v), sendo v não incluído nesse conjunto. A vizinhança fechada é o 
conjunto vizinhos [v] que é o conjunto vizinhos (v), incluindo-se v.
Analisando o grafo da Figura 18, é possível perceber que a vizinhança de v2 são 
os vértices adjacentes a v2, nesse caso, {v1, v3, v4, v5}. Já a vizinhança fechada de v2 é 
a sua vizinhança incluindo v2, ou seja, {v1, v2, v3, v4, v5}.
O grau de um vértice é o número de arestas incidentes em v, denotado por 
grau (v). Um vértice que possui grau zero é chamado isolado. No grafo da Figura 18 
não há nenhum vértice isolado (grau zero); já o grau do vértice v3 é um e o grau do 
vértice v4 é dois.
O grau de um grafo G é a soma dos graus de todos os seus vértices, denotado 
por d (G). Pode-se demonstrar facilmente com o seguinte teorema:
Seja G = (V, A) um grafo não orientado, então:
d (G) = ∑v∈V grau (v) = 2 * |A|
Para saber o grau de um grafo, deve-se somar o grau de todos os seus vértices, 
isto é, a quantidade de arestas incidentes em cada vértice. Como cada aresta incide 
sobre dois vértices, cada aresta é sempre considerada duas vezes. Assim, o grau do 
grafo é o dobrodo número de arestas.
O grau máximo de um grafo é o grau do vértice de maior grau em V (G), deno-
tado por ∆ (G). Já o grau mínimo de um grafo é o grau do vértice de menor grau em 
V (G), denotado por δ (G).
Introdução ao estudo dos grafos 19
O grau do grafo da Figura 18 é dez, pois é a soma dos graus de todos os vértices. 
Percebe-se que é, também, igual ao dobro do número de arestas. O seu grau má-
ximo é quatro, pois é o grau do vértice que contém o maior grau, que, nesse caso, 
é v2. Já o grau mínimo é um, pois v1 e v3 são os vértices com menor grau.
Uma sequência de vértices v1,...,vk, tal que (vi, vi+1) ∈ A, 1 ≤ igrafos conexos G e H são isomorfos entre si se, e somente se, 
seus grafos linha L (G) e L (H) são isomorfos. Para esse teorema, tem-se duas exce-
ções, a saber: K3 (grafo completo com três vértices) e K1,3 (grafo bipartido completo), 
pois não são isomorfos, mas seus grafos linha, L (K3) e L (K1,3), são.
Para entender esse teorema, deve-se primeiramente definir um grafo linha. O 
grafo linha de G, denotado por L (G) = (V’, A’), é o grafo em que seus vértices (V’) são 
as arestas de G, e existe aresta ab ∈ A’ em L (G) se a e b possuírem um vértice em 
comum em G.
Por exemplo, observe a figura a seguir.
Figura 23
Grafo G
v2
v1
v4
v3
a2
a3
a4
a1
Fonte: Elaborada pelo autor.
Para encontrar o grafo linha do grafo G, L (G), é preciso seguir os passos:
1. Encontrar os vértices de L (G); cada aresta de G é representada por um vértice 
em L (G), conforme a Figura 24.
Introdução ao estudo dos grafos 23
Figura 24
Vértices de L (G) que são as arestas de G
v2
v1
v4
v3
a2
a3
a1
a1
a3
a2
a4
a4
Fonte: Elaborada pelo autor.
2. Encontrar o primeiro vértice de L (G); como a3 e a2 possuem o vértice v3 em 
comum, adiciona-se uma aresta entre a3 e a2 em L (G), conforme a Figura 25.
Figura 25
Primeiro vértice de L (G)
v2
v1
v4
v3
a2
a3
a4
a1
a1
a3
a2
a4
Fonte: Elaborada pelo autor.
3. Encontrar o segundo vértice de L (G); como a4 e a3 possuem o vértice v2 em 
comum, adiciona-se uma aresta entre a4 e a3 em L (G), conforme a Figura 26.
Figura 26
Segundo vértice de L (G)
v2
v1
v4
v3
a2
a3
a4
a1
a1
a3
a2
a4
Fonte: Elaborada pelo autor.
24 Teoria dos Grafos
4. Encontrar o terceiro vértice de L (G); como a1 e a2 possuem o vértice v4 em 
comum, adiciona-se uma aresta entre a1 e a2 em L (G), conforme a Figura 27.
Figura 27
Terceiro vértice de L (G)
v2
v1
v4
v3
a2
a3
a4
a1
a1
a3
a2
a4
Fonte: Elaborada pelo autor.
5. Encontrar o quarto vértice de L (G); como a1 e a4 possuem o vértice v1 em 
comum, adiciona-se uma aresta entre a1 e a4 em L (G) a3, conforme a Figura 28.
Figura 28
Quarto e último vértice de L (G)
a3
a1
a4
a2
v2
v1
v4
v3
a2
a3
a4
a1
Fonte: Elaborada pelo autor.
6. Por fim, o grafo L (G) é o grafo representado pela Figura 29.
a3
a1
a4
a2
Figura 29
Grafo L(G)
Fonte: Elaborada pelo autor.
Desse modo, pelo Teorema de Whitney, dois grafos G e H são isomorfos se, e 
somente se, L (G) e L (H) são isomorfos. Usando o exemplo da Figura 22, tem-se os 
grafos linha de G1 e G2 representados na Figura 29.
Introdução ao estudo dos grafos 25
Seja V (L (G1)) e V (L (G2)) o conjunto de vértices de L (G1) e L (G2), respectivamente. 
Claramente, os grafos L (G1) e L (G2) são isomorfos, pois conseguem uma função 
f : V (L (G1)) → V (L (G2)), tal que:
f (a1) = e2
f (a2) = e4
f (a3) = e1
f (a4) = a3
Tal que:
(a1, a2) = (e2, e4)
(a2, a4) = (e4, e3)
(a3, a4) = (e1, e3)
(a1, a4) = (e2, e3)
(a3, a2) = (e1, e4)
Portanto, G1 e G2 são isomorfos.
Figura 30
Grafos L (G1) e L (G2)
a1
a3
a2
a4
L (G1)
v2
v3
v4
v1
a1
a2a4
a3
G1
L (G2)
e1
e3
e2
e4
e2
e3
e1
e4
a3
a4
a2
a1
G2Fonte: Elaborada pelo autor.
Os grafos G3 e G4 da Figura 31 possuem o mesmo número de vértices e o mes-
mo número de arestas, mas não são isomorfos.
26 Teoria dos Grafos
v1
a1
a3
a4
a2
v4
v2 v3
G3
b2
G4
b1 b3
b4
w1
w2 w4
w3
Figura 31
Grafos G3 e G4
Fonte: Elaborada pelo autor.
Ao representar seus grafos linha, obtém-se L (G3) e L (G4), conforme a Figura 32.
v1
a1
a3
a4
a2
v4
v2 v3
G3
a1
a3
a2
a4
L(G3)
Figura 32
Grafos linha L (G3) e L (G4)
L(G4)
b2
G4
b1 b3
b4
w1
w2 w4
w3
b1
b3
b2
b4
Fonte: Elaborada pelo autor.
Claramente, L (G3) e L (G4) não são isomorfos, pois não possuem o mesmo nú-
mero de arestas.
Uma solução algorítmica para isomorfismo é analisar cada uma das n! permu-
tações da função que define o isomorfismo (buscar todas as funções possíveis). O 
problema é que, no pior caso, esse algoritmo necessita de n! passos, sabidamente 
intratáveis. Hoje, não se conhece um algoritmo eficiente para o problema geral do 
isomorfismo em grafos.
Introdução ao estudo dos grafos 27
1.6 Representação computacional 
Vídeo Um grafo G = (V, A) é dito esparso se |A| é muito menor que |V|2. Se |A| está 
próximo de |V|2 é dito que o grafo é denso.
Tem-se basicamente três formas padrão de se representar computacionalmente 
um grafo: lista de adjacências, matriz de adjacências e matriz de incidências.
Na lista de adjacências armazena-se uma lista para cada vértice, e, em cada 
lista, referenciam-se os vértices que são adjacentes.
v3
v1
v4
v5
v2
v2
v1
v2
v2
v3
v5
v4
v4
v2
v2
v1
v3
v4
v5
v5
Fonte: Elaborada pelo autor.
Na Figura 33, o vértice v2 é representado por uma posição na lista. Esta possui 
uma lista de todos os vértices adjacentes a v2, no caso, v1, v3, v4 e v5.
Se o grafo for orientado (digrafo), a representação pode ser a mesma, como vis-
to na Figura 34. A diferença é que a vizinhança representada na lista é dada pelos 
vértices atingíveis por arestas de saída.
v3
v2
v1
v4
v5
v1
v2
v2
v4
v4
v3
v4
v5
v3
v5
v4
Figura 34
Lista de adjacências em grafo orientado
Fonte: Elaborada pelo autor.
Ao se analisar as listas de adjacências apresentadas, percebe-se que a soma dos 
comprimentos de todas as listas de adjacências para um grafo não orientado é o 
dobro do número de arestas, 2 * |A|, visto que cada aresta incide em dois vértices 
e que, portanto, precisa ser representada duas vezes. Já para o grafo orientado, 
essa soma é o número exato de arestas, isto é, |A|.
Na matriz de adjacências representa-se a estrutura do grafo G = (V, A) como 
uma matriz com dimensões |V| x |V|, em que cada posição aij é dada por:
Figura 33
Lista de 
adjacências
28 Teoria dos Grafos
1, se a aresta (i, j) ∈ A
0, caso contrárioaij=
Com essa representação, consultar se uma aresta faz parte do gráfico é feito em 
tempo constante.
v1 v2 v3 v4 v5
v1 0 1 0 0 0
v2 1 0 1 1 1
v3 0 1 0 0 0
v4 0 1 0 0 1
v5 0 1 0 1 0
v3
v1
v4
v5
v2
Figura 35
Matriz de adjacências
Fonte: Elaborada pelo autor.
Na Figura 35 tem-se a matriz de adjacências representada no grafo. A quantida-
de de memória necessária para compor a matriz tem limite assintótico restrito no 
quadrado do número de vértices, portanto, Θ (V2).
Como o grafo é não direcionado, percebe-se que a matriz é igual à sua trans-
posta, representando-se, portanto, somente os elementos abaixo da diagonal 
principal.
v3
v2
v1
v4
v5
Figura 36
Matriz de adjacências de um grafo orientado
Fonte: Elaborada pelo autor.
v1 v2 v3 v4 v5
v1 0 1 0 0 0
v2 0 0 1 1 0
v3 0 0 0 0 0
v4 0 0 0 1 1
v5 0 1 0 0 0
A Figura 36 apresenta a matriz de adjacências de um grafo orientado (digrafo). 
Percebe-se que, como as arestas são orientadas, a matriz não é igual à sua trans-
posta, pois uma aresta (v, w) não é a mesma que (w, v). Essa representação é ideal 
para grafos densos.
Outra forma matricial de representação de grafos é a matriz de incidências. 
Para o grafo G = (V, A), define-se como uma matriz com dimensões |V| x |A|, em 
que cada posição aij é dada por:
1, se a aresta j incide no vértice i 
0, caso contrárioaij=
Introdução ao estudo dos grafos 29
v3
v2
a6
a5
a4
a2
a3
a1
v4
v1 v5
Figura 37
Matriz de incidências
a1 a2 a3 a4 a5 a6
v1 0 0 0 0 0 1
v2 1 1 1 0 0 1
v3 0 0 1 0 0 0
v4 1 0 0 1 1 0
v5 0 1 0 1 0 0
Fonte: Elaborada pelo autor.
A Figura 37 mostra a matriz de incidências de um grafo. Cada coluna represen-
ta uma aresta e cada linha um vértice. As arestas contam com duas incidências, 
exceto a aresta a5, que é um laço. Para representar a matriz de incidências de um 
digrafo, pode-se optar pela seguinte definição:
1, se a aresta j incide no vértice i 
–1, se a aresta j sai do vértice i
0, caso contrário
aij=
Essa representação pode ser observada na Figura 38.
v4
v5
v3
v2
a6
a5
a4
a2
a3
a1
v1
Figura 38
Matriz de incidências em digrafo
Fonte: Elaborada pelo autor.
a1 a2 a3 a4 a5 a6
v1 0 0 0 0 0–1
v2 –1 1 –1 0 0 1
v3 0 0 1 0 0 0
v4 1 0 0 –1 1 0
v5 0 –1 0 1 0 0
1.7 Aplicações dos grafos
Vídeo Muitos problemas do mundo real, para serem resolvidos, são transformados 
em problemas de grafos. Essa comutação pode fornecer um ponto de vista diferen-
te sobre o problema, tornando-o mais simples e abrindo um leque de técnicas para 
a solução. Um exemplo disso foi o problema do caixeiro-viajante – ou TSP (Travelling 
Salesman Problem) –, no qual tentava-se resolver como esse profissional, que preci-
sava visitar várias cidades, poderia fazer isso para efetuar suas vendas. As cidades 
eram conectadas por estradas ou rodovias, sempre aos pares. Para maximizar seus 
30 Teoria dos Grafos
lucros, o caixeiro-viajante devia visitar todas as cidades somente uma vez e pela 
rota mais curta. Ou seja, ele precisava de um caminho ótimo passando por todas 
as cidades, sem repeti-las.
O TSP é um problema NP-Completo, isto é, faz parte da classe de problemas 
mais difíceis em NP, e NP é a classe de problemas que podem ser resolvidos em 
tempo polinomial, em uma Máquina de Turing Não Determinística. Atualmente, as 
soluções para os problemas NP-Completos levam um tempo exponencial em rela-
ção à entrada. Por exemplo, no caso do TSP, a solução mais simples é enumerar 
todas as rotas possíveis e escolher. No caso de n cidades, havendo estradas entre 
todas elas, deve-se efetuar (n – 1)! escolhas.
Suponha um computador que pode efetuar 1 trilhão de adições por segundo 
(1012), isto é, 1 teraflop. Para um problema com cinco cidades, n = 5, a máquina é capaz 
de avaliar 1012
4
= 250 bilhões de rotas por segundo. Como ele precisa calcular 4! rotas, 
demorará 4!/(250 bilhões) = 0,000000000096 segundos, um tempo insignificante.
Efetuando os mesmos cálculos para outras quantidades de cidades, tem-se o 
Quadro 1 a seguir.
Quadro 1
Tempo de execução da solução simples para o TSP.
n Rotas/segundo (n-1)! Tempo total
5 250.000.000.000 24 0,000000000096 s
10 110.000.000.000 362.880 0,00000329891 s
15 71.000.000.000 87.178.291.200 1,22786325633 s
20 53.000.000.000 1,216451 * 1017 26,56 dias
25 42.000.000.000 6,204484 * 1023 468.435,470 anos
100 10.000.000.000 9,332621 * 10155 2,9593 * 10138 anos
399 2.500.000.000 4,0121881 * 10863 5.089026 * 10846 anos
Fonte: Elaborado pelo autor.
Levando em consideração que se estima a idade do universo em 14 bilhões de 
anos, ou seja, 1,4 * 1010 anos, o tempo de cálculo de todas as rotas para um esta-
do do tamanho do Paraná, com 399 cidades, usando um computador que efetua 
1 trilhão de adições por segundo, é completamente inviável.
Assim, a solução de encontrar todas as rotas e verificar a melhor não pode ser 
aplicada. Quando mapeado para grafos, esse problema é enunciado como buscar 
um circuito hamiltoniano ótimo em um grafo valorado. Assim, resolver o problema 
de rotas é resolver um problema em grafos.
No artigo Algumas aplicações da teoria dos grafos, dos autores Pereira e Câmara, publicado 
em Famat em Revista, os conceitos básicos dessa teoria são revisitados e algumas aplicações 
são apresentadas, como é o caso do problema do caixeiro-viajante, enunciado sobre algumas 
cidades do estado de Minas Gerais. Também, são apresentados alguns algoritmos para sua 
solução.
Acesso em: 14 abr. 2020.
http://www.pucrs.br/ciencias/viali/graduacao/po_2/literatura/grafos/artigos/Famat_artigo_04.pdf
Artigo
Introdução ao estudo dos grafos 31
Outra problematização que pode ser mapeada para grafos é a robustez da ma-
lha elétrica para distribuição de energia. A malha elétrica é formada por torres e 
linhas de transmissão. Para saber quantas linhas no mínimo precisam falhar para 
que haja um apagão, isto é, para que parte do sistema fique desconectado, pode-se 
mapear as torres como vértices e as linhas de transmissão como arestas. Assim, o 
problema do apagão se transforma em descobrir o corte mínimo em um grafo, ou 
seja, o conjunto de arestas que, quando retiradas do grafo, interrompe o fluxo de 
um vértice a outro (Figura 39).
t2
t1
t4
t5
t3
t6
t7
t8
t9
Figura 39
Malha elétrica
Fonte: Elaborada pelo autor.
A Figura 39 apresenta um exemplo de torres e linhas de transmis-
são. Partindo de t1 até t9, por exemplo, quantas arestas no mínimo 
precisam ser retiradas para que t9 sofra um apagão?
O problema de alocação de professores e disciplinas também 
pode ser representado como um grafo. Sejam n professores e m 
disciplinas, assumindo que cada professor pode ministrar algumas 
disciplinas, mas que só poderá ofertar uma disciplina no semestre, é 
possível que todas as disciplinas sejam ofertadas simultaneamente? 
Qual o maior número de disciplinas que pode ser ofertado?
A Figura 40 mostra a representação do problema de alocação de 
professores e disciplinas. Pode-se observar que esse é um grafo bi-
partido e que, portanto, definições e algoritmos referentes a esse 
tipo de grafo são úteis para a solução do problema.
Outro problema interessante é o famoso lema do aperto de 
mão, que é consequência do teorema do grau dos grafos, apresen-
tado na Seção 1.4. Informalmente, em qualquer festa contendo um 
grupo de pessoas, sendo que algumas se cumprimentam (apertam 
as mãos), o número de pessoas que apertam um número ímpar de 
mãos sempre é par.
Seja o problema mapeado como um grafo, em que os vértices são 
pessoas e uma aresta indica que uma pessoa aperta a mão de outra, 
P1
P2
P3
P4
P5
d1
d2
d3
d4
d5
Professores Disciplinas
Figura 40
Professores X disciplinas
Fonte: Elaborada pelo autor.
32 Teoria dos Grafos
a quantidade de vezes que uma pessoa aperta a mão de outra é o grau do vértice. 
Suponha que esse grafo tenha um número ímpar de vértices de grau ímpar. Assim, 
a soma desses graus é ímpar. Sabendo-se que a soma dos graus dos vértices de 
grau par sempre é par, então, a soma dos graus de todos os vértices, nesse caso, 
é ímpar. Isso contradiz o teorema que indica que a soma dos graus dos vértices de 
um grafo é o dobro do número de arestas, logo, um número par. Portanto, o núme-
ro de vértices de grau ímpar deve obrigatoriamente ser par.
CONSIDERAÇÕES FINAIS
Este capítulo apresentou a história dos grafos, mostrando a sua origem, que é mais 
antiga do que os computadores conhecidos hoje em dia. Mesmo sendo uma teoria 
ancestral, os grafos até hoje são usados para mapear problemas do mundo a serem 
resolvidos com algoritmos computacionais.
Também foi possível observar os vários conceitos complexos necessários para o 
estudo dos grafos. Convém ressaltar que essa teoria, por se tratar de um ramo da 
matemática, com aplicações em várias áreas, é defina por uma notação formal a ser 
absorvida. Esse formalismo é necessário para que o desenvolvimento de conceitos 
avançados e algoritmos possa ser feito de maneira correta.
ATIVIDADES
1. Observe o problema das pontes de Königsberg, conforme a figura a seguir.
Se
rg
ey
 M
er
ku
lo
v/
Sh
ut
te
rs
to
ck
Esse problema é mapeado pelo seguinte grafo:
v4
v1
v2
v3
Introdução ao estudo dos grafos 33
Sabendo que não é possível partir de qualquer ponto e passar por todas as pontes 
somente uma vez, retornando ao ponto de partida, uma vez que o grafo resultante 
não é euleriano, construa mais algumas pontes de modo que o grafo torne-se euleria-
no e seja possível passar por cada aresta somente uma vez, partindo e chegando no 
mesmo ponto.
2. Construa a representação geométrica do grafo G = (V, A), tal que:
V = {1, 2, 3, 4, 5, 6}
A = {(1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,5), (4,5)}
3. Construa a matriz de adjacências do grafo da Questão 2.
4. Verifique se o seguinte grafo é bipartido. Dê os dois conjuntos de vértices 
característicos.
32
4
5
1
6
5. Desenhe um possível grafo que contenha vértices de grau 5, 2, 2, 2, 2, 1. Quantas 
arestas esse grafo possui?
REFERÊNCIAS
BOAVENTURA NETTO, P. O.; JURKIEWICZ, S. Grafos: introdução e prática. São Paulo: Blucher, 2009.
EULER, L. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum 
Petropolitanae,v. 8, p. 128-140, 1736.
RODRIGUES, E. J. Um Algoritmo para o Problema do Isomorfismo de Grafos. São Paulo, 2014. Dissertação 
(Mestrado em Ciência da Computação) – Universidade Federal do ABC. Disponível em: http://biblioteca.
ufabc.edu.br/index.php?codigo_sophia=75394 Acesso em: 14 abr. 2020.
SZWARCFITER, J. L. Teoria Computacional de Grafos. Rio de Janeiro: Elsevier, 2018.
34 Teoria dos Grafos
Conectividade
2
A conectividade em grafos é um aspecto muito importante no estudo da 
teoria de grafos, pois muitos problemas podem ser mapeados e analisados 
através de uma sequência de arestas. Para isso, deve-se conceituar grafos co-
nexos e desconexos, bem quanto suas componentes conexas. Para caminhar 
em um grafo, tanto orientado como não orientado, faz-se necessária a aplicação 
de conceitos, como caminhos e circuitos. E destes conceitos surgem os grafos 
eulerianos e hamiltonianos. Quando se trabalha com componentes conexas de 
grafos também se faz necessário o estudo de subgrafos e suas denominações.
Assim, neste capítulo será apresentada, na Seção 2.1, a teoria sobre grafos 
conexos e desconexos, bem como a definição de componentes conexas e suas 
implicações. Na Seção 2.2 são apresentadas noções sobre caminhos e circuitos, 
bem como a formalização de grafos conexos e componentes conexas. Também 
são apresentados formalmente os conceitos de grafos eulerianos e hamiltonia-
nos. Na Seção 2.3 são mostrados os subgrafos e seus usos. Os conceitos de vér-
tice de corte, arestas de corte e suas aplicações são apresentados na Seção 2.4.
2.1 Grafos conexos e componentes
Vídeo Um grafo conexo é aquele em que é possível estabelecer um caminho desde um 
vértice a outro, passando pelas arestas; caso um grafo não atenda esta condição, é 
chamado grafo desconexo (BOAVENTURA NETTO). Por exemplo, na Figura 1, o vértice 
v3 faz parte do grafo, mas não tem aresta com nenhum outro vértice e, na Figura 2, os 
vértices v3 e v5 possuem aresta entre si, mas não possuem aresta com a outra parte 
do grafo, caracterizando, portanto, dois grafos desconexos.
v4
v5
v3
v2
v1
Figura 1
Grafo desconexo com aresta desconexa
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Figura 2
Grafo desconexo com duas componentes conexas
Fonte: Elaborada pelo autor.
Conectividade 35
Denominam-se componentes conexas do grafo G todos os subgrafos maximais 
conexos de G, isto é, subgrafos conexos que não estão estritamente contidos em 
outros subgrafos conexos. Por exemplo, o grafo G (Figura 3) possui três compo-
nentes conexas, G’, G’’, G’’’, a saber:
G’ = (V’, A’)
 • V’ = {v1, v2, v3}
 • A’ = {(v1, v2), (v2, v3), (v3, v4)}
G’’ = (V’’, A’’)
 • V’’ = {v4, v5, v6, v7}
 • A’’ = {(v4, v5), (v5, v6), (v6, v4), (v7, v6)}
G’’’ = (V’’’, A’’’)
 • V’’’ = {v8}
 • A’’’ = {}
v4
v5
v6
v7
v8
v3
v2
v1
Figura 3
Grafo G com três componen-
tes conexas
Fonte: Elaborada pelo autor.
Para ser uma componente conexa, o subgrafo deve ser maximal, ou seja, não 
deve estar contido em outro subgrafo. No exemplo da Figura 3, o subgrafo formado 
pelos vértices v5 e v6, juntamente com a aresta (v5, v6), não é uma componente cone-
xa, pois está contido no subgrafo G’’.
Um grafo é chamado totalmente desconexo se todos os seus vértices pos-
suem grau zero, como na Figura 4.
v3v2v1
Figura 4
Grafo Totalmente Desconexo
Fonte: Elaborada pelo autor.
Os conceitos de conectividade, como componentes conexas, são importantes 
para o entendimento de assuntos como caminhos e circuitos, cortes, árvores e ou-
tros. Em muitos problemas mapeados para grafos, a conectividade é discutida e 
calculada, o que torna esses conceitos imprescindíveis.
Um subconjunto X’ de um con-
junto X é dito maximal em relação 
a alguma propriedade, se X não 
for subconjunto de nenhum outro 
subconjunto de X que possua 
aquela propriedade. Cuidado para 
não confundir maximal com 
máximo. Maximal diz respeito 
à pertinência e máximo, à cardi-
nalidade (número de elementos) 
(GOLDBARG; GOLDBARG, 2012).
No caso aqui, uma componente 
conexa é um subgrafo maximal, 
G’, isto é, um subgrafo para o qual 
não existe outro subgrafo H’, tal 
que G’ está contido em H’.
Saiba mais
36 Teoria dos Grafos
2.2 Caminhos e circuitos
Vídeo O conceito de caminho é muito usado em vários problemas mapeados para grafos. 
Um desses problemas é descobrir se existe um caminho entre um vértice e outro; se 
existe um conjunto de arestas que, quando visitadas em sequência, levam do ponto 
origem ao ponto destino.
Segundo Szwarcfiter (2018), um caminho ou passeio em um grafo G = (V, A) é 
uma sequência de vértices v1,...,vk, tal que vi ∈ V, (vi, vi+1) ∈ A, 1 ≤ iNesse caso, um caminho ou passeio em um digrafo D = (V, A) é uma 
sequência de vértices v1,..., vk tal que (vi, vi+1) ∈ A, 1 ≤ ipercebe-se que o grau de entrada de v2 é o seu grau de saída 
mais um. O grau de saída de v1 é o seu grau de entrada mais um. Todos os 
demais vértices possuem grau de entrada igual ao grau de saída. Assim, esse 
digrafo possui um caminho euleriano que inicia exatamente em v1 e termina 
em v2. O caminho euleriano nesse dígrafo é: (v1, v5), (v5, v3), (v3, v4), (v4, v5), (v5, 
v2), (v2, v6), (v6, v4), (v4, v2), (v2, v3), (v3, v1), (v1, v2).
Figura 12
Digrafo com caminho euleriano
v2
v1
v6
v3
v5
v4
Fonte: Elaborada pelo autor.
2.3 Subgrafos
Vídeo De maneira coloquial, um subgrafo de um grafo G é uma parte dele, ou seja, é 
um grafo contendo uma parte dos vértices e das arestas de G. Quais e quantos 
vértices e arestas do grafo G definem o tipo de subgrafo se torna. Define-se um 
grafo H como um subgrafo de G, como sendo um grafo em que todo vértice de H 
também é vértice de G e toda aresta de H também é aresta de G (FEOFILOFF; KOHA-
YAKAWA; WAKABAYASHI, 2011). Por exemplo, o grafo G, na Figura 13.
Ao analisar o grafo da Figura 14, percebe-se que todo vértice de H 
está em G e que toda aresta de H também está em G. Portanto, o 
grafo H é um subgrafo de G.
Segundo Feofiloff, Kohayakawa e Wakabayashi (2011), um grafo H 
é um subgrafo próprio de G, se H for subgrafo e diferente de G. Um 
grafo H é um subgrafo gerador de G, se tiver todos os vértices de G. 
O grafo H da Figura 14 não é um sub-
grafo gerador de G, pois tem vértices 
em G que não estão em H. Do mes-
mo modo, como H é diferente de G, 
diz-se que H é um subgrafo próprio de G.
O subgrafo H é um subgrafo induzido de G se 
todo arco de G, que tem ambas as pontas em H, 
também for um arco de H, isto é, se H possuir to-
Figura 13
Grafo G
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Figura 14
Subgrafo de G
Fonte: Elaborada pelo autor.
v4
v3
v2
v1
Conectividade 41
das as arestas que aparecem em G sobre os mesmos vértices. A 
Figura 15 apresenta um grafo induzido de G. Todas as arestas de 
G que possuem as duas pontas em arestas do subgrafo aparecem 
no grafo induzido.
Um grafo H é um grafo parcial de G, se H for um subgrafo de 
G e se possuir o mesmo conjunto de vértices que G. Na Figura 
16 percebe-se que o grafo possui todos os vértices do grafo G da 
Figura 13, portanto, esse é um grafo parcial de G.
Pode-se definir também G’ como um supergrafo de G, se G for 
subgrafo de G’.
Os conceitos de subgrafos também são aplicáveis a digrafos, 
levando-se em consideração que as arestas são dirigidas. Seja G = 
(V, A) um grafo. Dois subgrafos de G, G’ = (V’, A’) e G’’ = (V’’, A’’) são 
chamados aresta-disjuntos se não possuírem arestas em comum, 
ou seja, A’∩ A’’ = ∅. Da mesma maneira, são chamados de vérti-
ces-disjuntos se não possuírem vértices em comum, ou seja, V’ ∩ 
V’’ = Ø.
Por exemplo, dado o grafo G da Figura 13, a Figura 17 apresen-
ta dois subgrafos aresta-disjuntos de G e a Figura 18 apresenta 
dois subgrafos vértice-disjuntos de G.
Figura 16
Grafo parcial de G
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Figura 17
Subgrafos de G aresta-disjuntos
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
v4
v5
v3
v2
v1
Figura 18
Subgrafos de G vértice-disjuntos
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Figura 15
Subgrafo induzido de G
Fonte: Elaborada pelo autor.
v4
v5
v2
v1
42 Teoria dos Grafos
2.4 Cortes
Vídeo Seja G = (V, A) um grafo conexo. Denomina-se vértices de corte ou corte de vérti-
ces de G o subconjunto minimal de vértices V’ ⊂ V, cuja remoção de G torna o grafo 
desconexo ou trivial (apenas um vértice sem qualquer aresta). O grafo G – V’ é des-
conexo ou trivial. Qualquer subconjunto próprio de V’, a saber, V’’ ⊂ V’, se retirado de 
G, isto é G – V’’, torna o grafo conexo e não trivial (SZWARCFITER, 2018).
Um corte de arestas pode ser definido da seguinte maneira: seja G = (V, A) um 
grafo conexo, um corte de arestas é um subconjunto A’ ⊂ A, cuja remoção de G tor-
na o grafo desconexo, ou seja, G – A’ é um grafo desconexo. Assim, para qualquer 
subconjunto próprio de A’, a saber, A’’ ⊂ A’, o grafo G – A’’ é conexo.
O termo conectividade de vértices (cv de G) denota a cardinalidade do menor 
corte de vértices de G. Já conectividade de arestas (cA de G) denota a cardinalidade 
do menor corte de arestas de G. Assim, cV é o menor número de vértices que, 
quando removidos de G, torna-o desconexo ou trivial. Se G é um grafo descone-
xo, então cV = cA = 0.
Considerando o grafo G mostrado na Figura 19.
Figura 19
Grafo G
Fonte: Elaborada pelo autor.
v6v1
v7v3
v8
v5v2
v4
Observe que um corte de vértices de G pode ser c1 = {v4}, pois o grafo G’ (Figura 
20) com os vértices V’ = V – {v4} é desconexo. Perceba também que o conjunto c1 = 
{v4} é minimal, pois não há qualquer subconjunto de c1 que, quando retirados os 
vértices em G, torne o grafo desconexo.
Figura 20
Grafo G’
Fonte: Elaborada pelo autor.
v6
v7
v8
v5
v1
v3
v2
Um subconjunto X’ de um conjun-
to X é dito minimal, em relação a 
alguma propriedade, se X não for 
superconjunto de nenhum outro 
subconjunto de X que possua 
aquela propriedade. Cuidado 
para não confundir minimal com 
mínimo. Minimal diz respeito à 
pertinência e mínimo à cardina-
lidade (número de elementos) 
(GOLDBARG; GOLDBARG, 2012).
Saiba mais
É conveniente observar que um 
grafo completo K
n
, n > 1, não 
possui subconjunto próprio de 
vértices V’ ⊂ V cuja remoção de K
n
 
o desconecte, embora a remoção 
de n – 1 vértices torne o grafo 
trivial.
Importante
Conectividade 43
Já, para o mesmo grafo G, um corte de arestas pode ser c2 = {(v2, v4), (v3, v4)}, pois 
retirando essas arestas, é obtido o grafo G’’ (Figura 21), que é desconexo. Perceba 
que o conjunto c2 = {(v2, v4), (v3, v4)}, é minimal, pois não há qualquer subconjunto de 
c2 que, quando retiradas as arestas em G, torne o grafo desconexo.
Figura 21
Grafo G’’
Fonte: Elaborada pelo autor.
v6
v7
v8
v5
v1
v3
v2
v4
Para o conjunto c3 = {(v2, v4), (v3, v4), (v4, v6)}, quando essas arestas são retiradas 
de G, é gerado o grafo G’’’ (Figura 22), que é desconexo. Mas c3 não é um corte de 
arestas, pois não é um conjunto minimal, isto é, existe um subconjunto próprio 
de c3, que no caso é o c2, que também desconecta o grafo quando as arestas são 
retiradas de G.
Figura 22
Grafo G’’’
Fonte: Elaborada pelo autor.
v6
v7
v8
v5
v1
v3
v2
v4
Para determinar a conectividade de vértices cv, obtém-se o corte de vértices de 
menor cardinalidade (número de elementos), ou seja, o menor número de vértices 
que, quando removidos, desconecta o grafo. Para o grafo G da Figura 19, os menores 
cortes de vértices são os conjuntos c1 = {v4} e c2 = {v6}, portanto, a conectividade de 
vértices de G é cv = 1.
Para determinar a conectividade de arestas cA, obtém-se o corte de arestas de 
menor cardinalidade (número de elementos); o menor número de arestas que, 
quando removidas, desconecta o grafo. Para o grafo G da Figura 19, o menor 
corte de arestas é o conjunto c3 = {(v6, v8)}, portanto, a conectividade de arestas 
de G é cA = 1.
Um subconjunto X’ de um 
conjunto X é dito próprio se X’ 
é subconjunto de X, mas não é 
igual a X. Em outras palavras, 
existe pelo menos um elemento 
de X que não está no seu 
subconjunto X’.
Atenção
44 Teoria dos Grafos
Segundo Szwarcfiter (2018), um grafo G é k-conexo em vértices se a sua conec-
tividade de vértices for cv ≥ k. Da mesma maneira, um grafo G é k-conexo em ares-
tas quando a sua conectividade de arestas for cA ≥ k. O valor k é importante, pois 
se um grafo é k-conexo em vértices (arestas), não existe corte de vértices (arestas) 
menor que k. O grafo G da Figura 19 é 1-conexo em vértices e 1-conexo em arestas. 
Quando um grafo é 2-conexo também é chamado biconexo.
Para um grafo G = (V, A) e um corte de arestas de G, A’ ⊆ A, sempre é possível 
encontrar um corte de vértices V’ de tamanho |V’| ≤ |A’|. Para isso, escolhe-se para 
fazer parte de V’ um subconjunto de vértices tal que, para toda aresta a ∈ A’, A inci-
de neste vértice.