Livro - Teoria dos Grafos

Prévia do material em texto

Razer Anthom Nizer Rojas Montaño
TEORIA DOS GR
AFOS
Razer Anthom
 N
izer Rojas M
ontaño
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.
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.
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
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, Eulerprovou 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 pontes 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
v3v4v1 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 grafoG = (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 delas, é 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
v2v1
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 
https://www.ime.usp.br/~pf/algoritmos_para_grafos/
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 dobro do 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 ≤ i < k, é denominada 
caminho ou passeio, quando v1 atinge ou alcança vk. Diz-se, ainda, que vk é atingível 
ou alcançável. Um caminho de k vértices é formado por k – 1 arestas, e o valor k – 1 
revela o tamanho do caminho. Um ciclo é um caminho que começa e termina no 
mesmo vértice.
Quando um caminho passa por todos os vértices do grafo, sem repetição, é 
chamado de caminho hamiltoniano. Este, se for um ciclo, então, é denominado de 
ciclo hamiltoniano, e o grafo que contém um ciclo hamiltoniano é conhecido como 
grafo hamiltoniano.
Já quando um caminho passa por todas as arestas do grafo, sem repetição, é 
chamado de caminho euleriano. Este, se for um ciclo, então, é denominado de ciclo 
euleriano, e grafo que contém um ciclo euleriano é conhecido como grafo euleriano.
No grafo da Figura 18, v1 é alcançável por meio de v5, pois consegue um caminho 
partindo de v5 e chegando a v1, por exemplo, v5, v4, v2 e v1. O tamanho desse caminho 
é três, que é o número de arestas presentes.
A distância entre dois vértices, denotada por d (v, w), é o comprimento do 
menor caminho entre v e w. A excentricidade de um vértice de um grafo é o valor 
máximo da distância entre v e w para todo vértice w ∈ V. Define-se como centro de 
G o subconjunto dos vértices de excentricidade mínima.
Assim, a distância entre os vértices v1 e v5, no grafo da Figura 18, denotada por 
d (v1, v5), é dois, pois, apesar de haver dois caminhos entre v1 e v5 – a saber, (v1, v2, v4, 
v5) e (v1, v3, v5) – o de menor comprimento é o último, que é dois.
Os grafos direcionados (digrafo), conforme apresentado anteriormente, são 
aqueles em que as arestas são direcionadas, ou seja, são pares ordenados de 
vértices. Então, sendo G um grafo direcionado, a aresta (v, w) possui uma única 
direção de v para w.
Define-se, também, o grau de saída de um vértice como sen-
do o número de arestas que saem de v, e o grau de entrada de 
um vértice como sendo o número de arestas que chegam em v.
Se um vértice no grafo G possui grau de entrada nulo, então, 
é chamado de fonte. Se possui grau de saída nulo, é chamado de 
sumidouro.
O grafo da Figura 19 é um digrafo. O vértice v2 possui grau de 
saída dois e grau de entrada três; o vértice v3 é uma fonte, pois 
não possui arestas de entrada; e o vértice v5 é um sumidouro, 
pois não possui arestas de saída.
Os conceitos de caminho e alcançabilidade de vértices tam-
bém se aplicam aos digrafos, sempre levando em consideração 
as direções das arestas. Se um vértice alcançar todos os vértices, 
então, v é chamado de raiz do digrafo.
Figura 19
Digrafo
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
3
1
1
5
8
20
10
20 Teoria dos Grafos
Analisando-se o grafo da Figura 19, o vértice v1 é alcançável por meio de v3, pois 
há o caminho (v3, v2, v1). Já o vértice v4 não é alcançável por v3, pois não há caminho 
partindo de v3 que chega em v4, seguindo as orientações das arestas. Pelas particu-
laridades desse grafo, nenhum de seus vértices consegue alcançar todos os outros, 
portanto, não há raiz.
Seja G um digrafo, o grafo obtido pela retirada de todas as direções das arestas 
de G é um multigrafo não direcionado, conhecido como grafo subjacente de G.
O grafo subjacente do grafo da Figura 19 é o grafo da Figura 20.
v4
v5
v3
v2
v1
Figura 20
 Grafo subjacente
Fonte: Elaborada pelo autor.
3
1
1
5
8
20
10
Conforme apresentado anteriormente, uma árvore é um grafo sem ciclos 
(acíclico) e conexo (todas as arestas são alcançáveis). Se algum vértice possuir grau 
menor ou igual a um é chamado de folha, caso contrário, com grau maior que um, 
é denominado de vértice interior.
Percebe-se que toda árvore com n vértices possui exatamente n – 1 arestas. 
Assim, um grafo T é uma árvore se, e somente se, existir um único caminho entre 
cada par de vértices de T.
Uma árvore T = (V, A) é dita enraizada quando algum vértice v ∈ V é escolhido, 
portanto, chamado de raiz da árvore. Uma árvore não enraizada é conhecida como 
árvore livre.
Seja a árvore T = (V, A) enraizada, de raiz r, sendo dois vértices v, w ∈ V. Se v per-
tence ao caminho entre r e w, então, v é chamado ancestral de w, e w é descendente 
de v. Se v ≠ w, v é ancestral próprio de w, e w é descendente próprio de v. Se (v, w) 
é uma aresta de T e v é ancestral de w, então, v é pai de w, e w é filho de v. Dois 
vértices que possuem o mesmo pai são chamados de irmãos. Assim, a raiz de uma 
árvore não possui pai, e todo vértice que não é raiz tem exatamente um pai. 
Um vértice folha não possui filhos. O nível de um vértice v, denotado por nível (v), 
é o número de vértices do caminho entre a raiz e v. Assim, se r é raiz de uma árvore 
T, nível (r) = 1. Se dois vértices são irmãos, então, possuem o mesmo nível. A altura 
da árvore T é o valor máximo de nível (v) para todo vértice v ∈ T.
Introdução ao estudo dos grafos 21
O grafo da Figura 21 é uma árvore, pois é um grafo ací-
clico e conexo. Os vértices v3, v7, v6 e v8 possuem grau ≤ 1, 
portanto, são vértices folha. Já os vértices v1, v2, v4 e v5 são 
vértices interiores. Como essa árvore possui oito vértices, 
ela também conta com exatamente sete arestas.
Pode-se escolher o vértice v2 para ser a raiz dessa árvore, 
chamando-a, portanto, de árvore de enraizada. Assim, diz-se 
que v4 é ancestral de v8, pois está no caminho entre a raiz (v2) e 
v8. O vértice v8 também é conhecido como descendente de v4.
Já o vértice v4 é pai dos vértices v5 e v6, pois existem ares-
tas (v4, v5) e (v4, v6), sendo v4 ancestral de v5 e de v6. Os vérti-
ces v5 e v6, portanto, são filhos de v4. Já os vértices v6 e v5, por 
possuírem o mesmo pai, são irmãos.
O valor de nível (v2), por ser a raiz, é um. O nível (v6) é 
três, pois tem-se três arestas entre a raiz (v2) e v6. A altura da árvore da Figura 21 é 
três, pois dentro todos os vértices v8 têm valor de nível (v8) = 4.
v4
v6
v5
v3
v2
v1
v7
Figura 21
Árvore
Fonte: Elaborada pelo autor.
v8
1.5 Isomorfismo
Vídeo Como foi visto, é comum referir-se a um grafo por meio de sua representação 
gráfica ou geométrica. Dessa forma, dois grafos são isomorfos entre si se suas re-
presentações geométricas se referem ao mesmo grafo. De outra forma, dois grafos 
são isomorfos entre si se existe correspondência entre seus vértices e suas arestas, 
preservando as adjacências entre os vértices.
Assim, dados dois grafos G1 = (V1, A1) e G2 = (V2, A2), tal que |V1| = |V2| = n, 
ambos são isomorfos se existe uma função unívoca (com somente uma correspon-
dência) f : V1 → V2, tal que (v, w) ∈ A1 se, e somente se, (f (v), f (w)) ∈ A2 para todo 
v, w ∈ V11 (RODRIGUES, 2014).
Figura 22
Grafos isomorfos entre si
v3
v2
v1
v4
G1
a4
a3
a2
a1
G2
Fonte: Elaborada pelo autor.
22 Teoria dos Grafos
Na Figura 22, os dois grafos G1 = (V1, A1) e G2 = (V2, A2) são isomorfos entre si, pois:
V1 = {v1, v2, v3, v4}
A1 = {(v2, v3), (v1, v2), (v4, v2), (v1, v4)}
V2 = {a1, a2, a3, a4}
A2 = {(a1, a4), (a1, a2), (a1, a3), (a3, a2)}
|V1| = |V2| = 4
f : V1 → V2 tal que:
 • f (v1) = a3
 • f (v2) = a1
 • f (v3) = a4
 • f (v4) = a2
Assim como as arestas sãopreservadas da seguinte forma:
(v2, v3) = (a1, a4)
(v1, v2) = (a1, a3)
(v4, v2) = (a1, a2)
(v1, v4) = (a3, a2)
Uma das maneiras de se caracterizar o isomorfismo entre grafos é usando o 
Teorema de Whitney, que se baseia no conceito de grafos linha e é formulado da 
seguinte forma: dois grafos 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 incideno 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 10
12
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
http://www.pucrs.br/ciencias/viali/graduacao/po_2/literatura/grafos/artigos/Famat_artigo_04.pdf
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érticescaracterí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 ≤ i < k. Esse caminho 
é formado pelas seguintes arestas: (v1, v2), (v2, v3), (v3, v4),...(vk-1, vk).
v3
v2v1
v4
v6
v5
Figura 5
Grafo G
Fonte: Elaborada pelo autor.
Por exemplo, o grafo G da Figura 5 possui, pelo menos, um caminho entre v4 e 
v6, formado pelas arestas (v4, v2), (v2, v5), (v5, v6). Perceba que, a partir da segunda, 
cada aresta é adjacente à anterior.
Um trajeto é definido como um caminho sem arestas repetidas. Um caminho 
simples é um caminho que não possui vértices repetidos. O caminho entre v4 e v6 
formado pelas arestas (v4, v2), (v2, v5), (v5, v6) sobre o grafo G (Figura 5) é um trajeto, 
pois não repete arestas. Também é um caminho simples, pois não repete vértices. 
Já o caminho formado pelas arestas (v4, v1), (v1, v2), (v2, v4), (v4, v6) não é um caminho 
simples, pois repete o vértice v4. E o caminho formado pelas arestas (v4, v2), (v2, v1), 
(v1, v4), (v4, v2), (v2, v5), (v5, v6) não é um trajeto, pois repete a aresta (v4, v2) (ou (v2, v4), 
já que é um grafo não dirigido).
O primeiro vértice v1 que faz parte do caminho é chamado origem, e seu último 
vértice vk é conhecido como término. Assim, diz-se que esse caminho vai de v1 a vk. 
No exemplo apresentado anteriormente, o vértice v4 é a origem do caminho e v6 o 
seu término.
Com a definição de caminho, é possível formular que um grafo é conexo quan-
do existe caminho entre cada par de vértices e, caso contrário, é desconexo. O ta-
manho de um caminho é dado pelo número de arestas que fazem parte dele. Se 
o caminho é formado por k vértices, então possui pelo menos k – 1 arestas e o valor 
k – 1 é o tamanho do caminho. Se o caminho é simples (sem vértices repetidos) en-
tão seu comprimento é exatamente k – 1. Assim, a distância entre dois vértices 
pode ser medida pelo tamanho do menor caminho entre eles (FEOFILOFF, 2020). 
No exemplo aplicado ao grafo G (Figura 5), o caminho simples (v4, v2), (v2, v5), (v5, v6) 
é formado por quatro vértices e tem tamanho três.
Conectividade 37
É definido como ciclo um caminho v1,..., vk, vk+1, de tal forma que v1 = vk+1 e k ≥ 
3. Isto é, um ciclo é um caminho que começa e termina no mesmo vértice, desde 
que contenha mais de dois vértices envolvidos. Um ciclo simples ou elementar é 
um ciclo v1,..., vk, vk+1 em que o caminho v1,..., vk é simples, não possui vértices re-
petidos, exceto o primeiro e último, o que determina ser um ciclo. Se não houver 
ambiguidade, os termos caminho e ciclo são usados denotando caminho simples 
e ciclo simples, respectivamente. Se o ciclo possuir tamanho três, então é chama-
do triângulo.
Para o grafo G, da Figura 5, o caminho simples (v4, v2), (v2, v5), (v5, v6), (v6, v4) é um 
ciclo, pois seu início e término são pelo mesmo vértice (v4), e é simples, pois não 
repete vértices. Nesse mesmo grafo, o ciclo (v4, v2), (v2, v1), (v1, v4) é um triângulo, 
pois possui tamanho três.
Se um ciclo puder ser obtido de outro pela permutação circular dos seus vérti-
ces, então esses ciclos são considerados idênticos. O grafoG (Figura 5) representa 
dois ciclos: (v4, v2), (v2, v1), (v1, v4) e (v2, v1), (v1, v4), (v4, v2). Perceba que ambos os 
ciclos possuem as mesmas arestas e só mudam em relação a sua origem e tér-
mino. Assim, um é permutação circular do outro, fazendo com que sejam ciclos 
idênticos.
Todos os conceitos apresentados também são aplicados a digrafos (grafos 
orientados). Nesse 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 ≤ i < k. Esse caminho é formado 
pelas seguintes arestas orientadas: (v1, v2), (v2, v3), (v3, v4),…(vk– 1, vk). Convém ressal-
tar que, por ser um grafo orientado, a aresta (vi, vi+1) indica que o vértice vi+1 é adja-
cente ao vértice vi, mas a recíproca não é necessariamente verdadeira.
Por exemplo, na Figura 6, o digrafo D tem um caminho formado pelas seguin-
tes arestas: (v5, v3), (v3, v1), (v1, v2), (v2, v5). Já a seguinte sequência de arestas: (v3, 
v1), (v1, v4), (v4, v5), (v5, v3) não é um caminho, pois a aresta (v1, v4) não existe, a 
aresta existente é (v4, v1), a ordem importa.
Figura 6
Digrafo D com caminho
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
38 Teoria dos Grafos
Seja o digrafo D = (V, A), se para qualquer par de vértices vi, vj houver caminho 
orientado partindo de vi a vj, e se houver caminho orientado partindo de vj a vi, o 
digrafo é chamado fortemente conexo. Informalmente, qualquer vértice é acessível a 
partir de qualquer outro e essa propriedade pode ser observada no grafo da Figura 
7. Perceba que para qualquer par de vértices vi e vj, há um caminho partindo de vi e 
chegando em vj, e um caminho partindo de vj e chegando em vi.
Se para o digrafo D = (V, A) e qualquer par de vértices vi, vj, houver caminho 
orientado partindo de vi a vj, mas não houver caminho orientado partindo de vj a vi, 
então o digrafo é chamado unilateralmente conexo. Se o digrafo não for fortemente 
conexo, mas tiver seu grafo subjacente – resultante da retirada das orientações das 
arestas – conexo, então é dito fracamente conexo. O digrafo da Figura 6 não é forte-
mente conexo, mas seu grafo subjacente (Figura 8) é conexo. Portanto, o digrafo da 
Figura 6 é fracamente conexo.
Um caminho em um grafo G que contém todos os vértices de G 
somente uma vez é chamado de caminho hamiltoniano. Seja um ci-
clo v1,..., vk, vk+1 em um grafo G, se o caminho v1,..., vk for hamiltonia-
no, então o ciclo v1,..., vk, vk+1 é denominado ciclo hamiltoniano. Um 
grafo que contém um ciclo hamiltoniano é um grafo hamiltoniano. 
Se um grafo contiver um caminho hamiltoniano, mas não um ciclo 
hamiltoniano, é um grafo semi-hamiltoniano. Na prática, um grafo 
semi-hamiltoniano se torna hamiltoniano ao acrescentar uma ares-
ta entre a origem e o término do caminho hamiltoniano.
As definições de caminho, ciclo e grafo hamiltoniano também se 
aplicam a digrafos (grafos orientados). Um caminho orientado em 
um digrafo é um caminho hamiltoniano, se contiver todos os vérti-
ces do digrafo sem repetição de vértices. Agora, se for um caminho 
hamiltoniano e iniciar e terminar no mesmo vértice, um ciclo orien-
tado em um digrafo é um ciclo hamiltoniano. Já um digrafo é hamiltoniano se con-
tiver um ciclo orientado hamiltoniano. Se um digrafo contiver um caminho orientado 
hamiltoniano, o digrafo é semi-hamiltoniano (NICOLETTI; HRUSCHKA JUNIOR, 
2018).
Como resultado dessa definição, é possível perceber que um grafo completo Kn, 
sendo n ≥ 3, é sempre hamiltoniano. Isso ocorre porque em um grafo completo to-
dos os n vértices possuem arestas incidentes a todos os demais n – 1 
vértices. Assim, para todo vértice vi, 1 ≤ i ≤ n, existe o seguinte cami-
nho C = {(v1, v2), (v2, v3), (v3, v4)..., (vn–1, vn)}, que passa por todos os vér-
tices {v1,..., vn} somente uma vez. Como todos vértices são adjacentes 
aos demais, o vértice vn também é adjacente a v1, assim o caminho 
C adicionando-se a aresta (vn, v1) é um ciclo que passa por todos os 
vértices, portanto, é um ciclo hamiltoniano e o grafo é hamiltoniano.
Ao se analisar o grafo da Figura 9, percebe-se que o caminho 
(v2, v3), (v3, v5), (v5, v1), (v1, v4) passa por todos os vértices, exata-
mente uma vez, portanto, é um caminho hamiltoniano. No mes-
mo grafo, o caminho (v2, v3), (v3, v5), (v5, v1), (v1, v4), (v4, v2) é um ciclo 
Figura 7
Digrafo fortemente conexo
Fonte: Elaborada pelo autor.
v1
v3
v2
Figura 8
Grafo Subjacente de D
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Figura 9
Grafo hamiltoniano
Fonte: Elaborada pelo autor.
v4
v5
v3
v2
v1
Conectividade 39
(começa e termina em v2), caracterizando-o, portanto, como um ciclo hamiltonia-
no e, por conta disso, o grafo é hamiltoniano.
Se um caminho em um grafo G contém todas as arestas do grafo somente uma 
vez, é chamado de caminho euleriano. Se esse caminho for um ciclo, então é co-
nhecido como ciclo euleriano. Um grafo que contém um ciclo euleriano é um grafo 
euleriano. Um grafo é semieuleriano se possuir um caminho euleriano, mas não 
um ciclo euleriano. Na prática, um grafo semieuleriano se torna euleriano bastando 
inserir uma aresta entre a origem e o término do caminho euleriano (NICOLETTI; 
HRUSCHKA JUNIOR, 2018).
Conforme já apresentado, um grafo não orientado é um grafo euleriano se, e 
somente se, todos os seus vértices possuem grau (número de arestas incidentes) 
par. Um grafo é semieuleriano se possuir dois vértices com grau ímpar e todos os 
demais com grau par.
Observando o grafo da Figura 10, percebe-se que há um caminho passando pelos 
seguintes vértices na sequência (v1, v2, v3, v4, v5, v6, v1, v4, v2, v5, v1) que passa por todas 
as arestas, somente uma vez, sendo, portanto, um caminho euleriano. Como esse 
caminho começa em v1 e termina em v1, é um ciclo euleriano e, consequentemente, 
o grafo é euleriano.
Os conceitos também se aplicam a digrafos, isto é, se um caminho orientado em 
um digrafo D contém todas as arestas do grafo somente uma vez, então é um ca-
minho euleriano. Se esse caminho for um ciclo orientado, então é conhecido como 
ciclo euleriano. Um digrafo que contém um ciclo euleriano é chamado de digrafo 
euleriano.
Para verificar se um digrafo é euleriano há uma condição necessária e suficien-
te. Um digrafo D = (V, A) é euleriano se, e somente se, for unilateralmente conexo e 
se para todo vértice vi ∈ V, o grau de entrada de vi – denotado como grau
+(vi) ou o 
número de vértices que chegam em vi– for igual ao grau de saída de vi – denotado 
como grau– (vi) ou o número de vértices que saem de vi.
Por exemplo, o digrafo da Figura 11 é euleriano, pois é unilateralmente conexo 
– para cada par de vértices há um caminho orientado entre eles, em algum sentido 
– e para cada vértice, o número de vértices que entram (grau de entrada) é igual ao 
número de vértices que saem (grau de saída).
No digrafo da Figura 11, um ciclo euleriano é: (v6, v4), (v4, v2), (v2,, v3), (v3, v4), (v4, v5), 
(v5, v3), (v3, v1), (v1, v5), (v5, v2), (v2, v6).
Um teorema similar existe para verificar se o digrafo possui um caminho eule-
riano (não um ciclo). Um digrafo D = (V, A) possui um circuito euleriano se, e somen-
te se, for unilateralmente conexo e se possuir as seguintes condições:
1. Dois de seus vértices vi e vj são tais que:
 • o grau de entrada de vi é igual ao seu grau de saída mais um, isto é, grau
+(vi) 
= 1 + grau–(vi);
 • o grau de saída de vj é igual ao seu grau de entrada mais um, isto é, grau
–
(vj) = 1 + grau
+(vj).
2. Para todos os demais vértices, seus graus de entrada e saída são iguais, isto 
é, 
A
v ∈ V, grau–(v) = grau+(v).
Figura 10
Grafo euleriano
Fonte: Elaborada pelo autor.
v4
v6
v3
v2
v5v1 a7
a9
a10
a1 a4
a8
a6
a2
a5
a3
Figura 11
Digrafo Euleriano
v2
v1
v6
v3
v5
v4
Fonte: Elaborada pelo autor.
40 Teoria dos Grafos
Com essas condições, o caminho euleriano se inicia em vj (o vértice com mais 
arestas de saída do que de entradas) e termina em vi (o vértice com mais arestas de 
entrada do que de saídas).
Como exemplo, pode-seanalisar o digrafo da Figura 12, que é unilateralmente 
conexo. Os graus dos seus vértices são:
 • vértice v1: grau
+(v1) = 1 e grau
–(v1) = 2
 • vértice v2: grau
+(v2) = 3 e grau
–(v1) = 2
 • vértice v3: grau
+(v3) = 2 e grau
–(v1) = 2
 • vértice v4: grau
+(v4) = 2 e grau
–(v1) = 2
 • vértice v5: grau
+(v5) = 2 e grau
–(v1) = 2
 • vértice v6: grau
+(v6) = 1 e grau
–(v1) = 1
Claramente percebe-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) 
menorque 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. Por 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,