Teoria_Grafos_Material

Prévia do material em texto

Professores: 
Marcelo Bruno Gomes Pedroza 
Glauber Marcio Silveira Pereira 
Erica Boizan Batista 
Introdução à Teoria dos Grafos 
Unidade 1. Elementos da Teoria dos Grafos. 
TÓPICOS 
Representação de grafos 
Tipos de grafos 
Árvores 
Noções sobre grafos 
Grafos hamiltonianos 
 
Grafos Eulerianos 
 
História da teoria dos grafos 
No século XIII, um enigma agitou a pequena Königsberg, cidade da antiga Prússia 
e atual Kaliningrado (Rússia). Ela era cortada pelo Rio Pregel, que dividia a cidade 
e formava duas grandes ilhas que, juntas, formavam um complexo unido por sete 
pontes. Seis delas interligavam duas ilhas às margens do Rio Pregel e uma fazia a 
ligação entre as duas ilhas, conforme exposto na figura abaixo. 
Fonte: Universo Racionalista. https://universoracionalista.org/wp-
content/uploads/2016/03/untitled-infographic_block_1.jpg. Acesso em: 18 abr. 2021. 
Figura 1. Mapa da cidade. 
https://universoracionalista.org/wp-content/uploads/2016/03/untitled-infographic_block_1.jpg
https://universoracionalista.org/wp-content/uploads/2016/03/untitled-infographic_block_1.jpg
https://universoracionalista.org/wp-content/uploads/2016/03/untitled-infographic_block_1.jpg
https://universoracionalista.org/wp-content/uploads/2016/03/untitled-infographic_block_1.jpg
https://universoracionalista.org/wp-content/uploads/2016/03/untitled-infographic_block_1.jpg
No problema, discutia-se a possibilidade de atravessar todas as pontes 
uma única vez e retornar ao ponto de partida. Em 1736, Leonhard 
Euler (ver foto abaixo) apresentou uma solução para o problema. Euler 
propôs transformar as partes de terra da cidade em pontos e as pontes 
que os unia em retas, criando assim, o primeiro grafo da história. 
Fonte: Wikipedia 
https://pt.wikipedia.org/wiki/Ficheiro:Leonhard_Euler.jpg 
Acesso em 11 mai. 2021. 
Figura 2. Leonhard Euler. 
História da teoria dos grafos 
https://pt.wikipedia.org/wiki/Ficheiro:Leonhard_Euler.jpg
Graças aos estudos de Euler os grafos são amplamente utilizados 
hoje em dia em diversas áreas. Vemos nas figuras abaixo exemplos 
de grafos, a esquerda um mapa de um metrô e a direita uma 
molécula. 
Fonte: https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-
metro_13153632.htm. Acesso em: 18 mai. 2021. 
Fonte: https://pixabay.com/pt/vectors/cafeína-molécula-
estrutura-química-148821/ 
 Acesso em: 18 mai. 2021. 
História da teoria dos grafos 
Figura 3. Exemplo de grafo. 
Figura 4. Exemplo de grafo. 
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://br.freepik.com/vetores-gratis/metro-ilustracao-do-mapa-do-metro_13153632.htm
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
https://pixabay.com/pt/vectors/cafeína-molécula-estrutura-química-148821/
Nas próximas unidades apresentaremos alguns exemplos 
de problemas solucionados usando teoria dos grafos, 
incluindo o problema das sete pontes de Euler. 
 
No entanto, para isso precisamos primeiro abordar as 
principais definições e propriedades da teoria dos grafos. 
História da teoria dos grafos 
Definição 1 (Grafo): Grafo é uma 
estrutura matemática composta de 
vértices (ou nós) e arestas (ou 
traços) representados por G(𝑉, 𝐴), 
onde 𝑉 é o conjunto não vazio de 
vértices e 𝐴 o conjunto de arestas 
que são pares não ordenados de 
𝑉 . 
 
Graficamente, um grafo pode ser 
representado com pontos 
correspondendo aos nós unidos 
por traços associados às arestas. 
Um exemplo com 𝑉 = { 𝑣1, 𝑣2, 𝑣3} e 
𝐴 = { 𝑒1, 𝑒2, 𝑒3}, pode ser visto na 
figura ao lado. 
Noções sobre grafos 
Fonte: Autoria própria. 
Figura 5. Exemplo de grafo. 
Noções sobre grafos 
 
Definição 2 (Vértices adjacentes): Dados dois vértices de um grafo, dizemos 
que eles são adjacentes (ou vizinhos) se existir uma aresta comum entre eles. 
Na Figura abaixo, tem-se que 𝑣1 e 𝑣2 são exemplos de vértices adjacentes uma 
vez que existe uma aresta, 𝑒2, comum entre eles. 
Fonte: Autoria própria. 
Figura 6. Exemplo de grafo. 
Noções sobre grafos 
Definição 3 (Arestas adjacentes): 
Dadas duas arestas de um grafo, 
dizemos que elas são adjacentes se 
tiverem ao menos um vértice em 
comum. 
 
Na Figura abaixo, temos que as 
arestas que 𝑒2 e 𝑒3 são exemplos de 
arestas adjacentes, uma vez que 
elas tem o vértice que 𝑣2 em comum. 
 
Fonte: Autoria própria. 
Figura 7. Exemplo de grafo. 
Noções sobre grafos 
 
Definição 4 (Laços): Um laço é uma aresta que liga um vértice a ele mesmo. 
Na Figura abaixo, temos que a aresta que 𝑒1 é um exemplo de laço. 
Fonte: Autoria própria. 
Figura 8. Exemplo de grafo. 
Noções sobre grafos 
Definição 5 (Vértices incidentes): 
Dados dois vértices de um grafo, 
dizemos que eles são incidentes em 
uma aresta se eles são extremos 
dela. 
 
Na Figura ao lado, 𝑣2 e 𝑣3 são 
vértices incidentes da aresta 𝑒3 (ou 
𝑒4). 
 
Fonte: Autoria própria. 
Figura 9. Exemplo de grafo. 
Noções sobre grafos 
 
Definição 6 (Arestas incidentes): Arestas incidentes são arestas que partem de 
um vértice. 
Na Figura abaixo, 𝑒2, 𝑒3 e 𝑒4 são exemplos de arestas incidentes ao vértice 𝑣2. 
Fonte: Autoria própria. 
Figura 10. Exemplo de grafo. 
Definição 7 (Arestas paralelas): 
Quando dois vértices de um grafo 
𝐺 têm mais de uma aresta 
ligando-os, dizemos que essas 
arestas são paralelas. 
 
 
Na Figura ao lado, temos que 𝑒3 e 
𝑒4 são exemplos de arestas 
paralelas. 
 
Noções sobre grafos 
Fonte: Autoria própria. 
Figura 11. Exemplo de grafo. 
Noções sobre grafos 
 
Definição 8 (Grau de um vértice): O grau de um vértice é o número de arestas 
que incidem nesse vértice. 
Usaremos a notação 𝑔(𝑣) para indicar o grau do vértice 𝑣. Um laço conta duas 
vezes para o grau de um vértice. Na Figura abaixo, temos que 𝑔(𝑣1) = 3 , 
𝑔(𝑣2) = 3, 𝑔(𝑣3) = 2, e 𝑔(𝑣4) = 0. 
Fonte: Autoria própria. 
Figura 12. Exemplo de grafo. 
Definição 9 (Vértices isolados): 
Vértice isolado é todo vértice de 
grau zero. 
 
 
Na Figura ao lado, o vértice 𝑣4 é 
um exemplo de vértice isolado. 
 
Noções sobre grafos 
Fonte: Autoria própria. 
Figura 13. Exemplo de grafo. 
Noções sobre grafos 
 
Definição 10 (Grau de um grafo): O grau de um grafo𝐺(𝑉, 𝐴), é o máximo entre 
os graus de seus vértices, ou seja, 𝑔 𝐺 = max 𝑔(𝑣1 , … , 𝑔(𝑣𝑘)}. 
Na Figura abaixo, o grau do grafo é 𝑔 𝐺 = max 𝑔(𝑣1 , 𝑔(𝑣2), 𝑔(𝑣3), 𝑔(𝑣4)} =
max{ 3, 3, 2, 0 } = 3. 
Fonte: Autoria própria. 
Figura 14. Exemplo de grafo. 
Noções sobre grafos 
 Definição 11 (Passeio entre vértices): Em um grafo, um passeio entre os 
vértices 𝑣𝑖 e 𝑣𝑗 é uma sequência alternada de vértices e arestas iniciando em 𝑣𝑖 e 
terminando em 𝑣𝑗. 
O passeio entre vértices não é único. Tanto arestas quanto vértices podem ou 
não ser distintos. Se os vértices de origem e destino forem o mesmo, então o 
passeio é chamado de passeio fechado. Na Figura abaixo, temos 
{𝑣1, 𝑒1, 𝑣1, 𝑒2, 𝑣2, 𝑒4, 𝑣4, 𝑒6, 𝑣3, 𝑒3, 𝑣2, 𝑒5, 𝑣5, 𝑒9, 𝑣6, 𝑒8, 𝑣4, 𝑒7, 𝑣5, 𝑒10, 𝑣6} é um exemplo 
de passeio entre os vértices 𝑣1 e 𝑣6. 
Fonte: Autoria própria. 
Figura 15. Exemplo de grafo. 
Noções sobre grafos 
Definição 12 (Caminhos): Um 
caminho é uma sequência em que 
tanto as arestas quanto os vértices 
são distintos. 
 
Na Figura ao lado, temos 
{𝑣1, 𝑒2, 𝑣2, 𝑒3, 𝑣3, 𝑒6, 𝑣4, 𝑒7, 𝑣5, 𝑒9, 𝑣6} é 
um exemplo de caminho entre os 
vértices 𝑣1 e 𝑣6. 
 Fonte: Autoria própria. 
Figura 16. Exemplo de grafo. 
Noções sobre grafos 
 Definição 13 (Ciclos ou circuitos): Ciclo é um caminho em que o vértice de 
origem e o de destino são o mesmo. 
Na Figura abaixo, temos {𝑣1, 𝑒2, 𝑣2, 𝑒3, 𝑣3, 𝑒6, 𝑣4, 𝑒7, 𝑣5, 𝑒9, 𝑣6, 𝑒11, 𝑣1} é um exemplo 
de ciclo. 
Fonte: Autoria própria. 
Figura 17. Exemplo de grafo. 
Representação de grafos 
Seja 𝐺(𝑉, 𝐴) um grafo com 𝑛 vértices e 𝑚 arestas. Duas 
representações clássicas são: 
 
1- Matriz de adjacência; 
2- Matriz de incidência. 
Representação de grafos 
Definição 14 (Matriz de adjacência): A matriz de adjacência é uma matriz 
simétrica de ordem 𝑛, 𝐴 = 𝑎𝑖𝑗 𝑛×𝑛
 que acumula o relacionamento entre os 
vértices do grafo. Cada entrada 𝑎𝑖𝑗 é igual a: 
𝑎𝑖𝑗
= 
0, se 𝑣𝑖 não adjacente a 𝑣𝑗; 
𝑝, quantidade de arestas incidentes tanto em 𝑣𝑖 quanto em 𝑣𝑗 (com 𝑖 ≠ 𝑗);
𝑞,e a quantidade de laços incidentes em 𝑣𝑖 = 𝑣𝑗 . 
 
 
Representação de grafos 
Segue a tabela que representa a relação entre os vértices do grafo da figura 
abaixo e sua matriz de adjacência: 
1 1 0
1 0 1
0 1 0
0 0
1 1
1 0
1
0
0
0 1 1
0 1 0
0 1
1 0
1
2
1 0 0 1 2 0
 
𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 𝑣6 
𝑣1 1 1 0 0 0 1 
𝑣2 1 0 1 1 1 0 
𝑣3 0 1 0 1 0 0 
𝑣4 0 1 1 0 1 1 
𝑣5 0 1 0 1 0 2 
𝑣6 1 0 0 1 2 0 
Fonte: Autoria própria. 
Figura 18. Exemplo de grafo, tabela e matriz. 
Representação de grafos 
Definição 15 (Matriz de incidência): A matriz de incidência, 𝐵 = 𝑏𝑖𝑗 𝑛×𝑚
, é 
aquela, na qual as linhas estão associadas aos vértices e as colunas às 
arestas. Cada entrada 𝑏𝑖𝑗 relaciona o vértice 𝑣𝑖 à aresta 𝑒𝑗 assumindo os 
seguinte valores: 
𝑏𝑖𝑗 = 
0; se 𝑒𝑗 não é incidente em 𝑣𝑖; 
1; se 𝑒𝑗 é ou não um laços; e 𝑣𝑖 é uma das suas extremidades.
 
 
Representação de grafos 
Segue a tabela que representa a relação entre os vértices e as arestas do grafo 
da figura abaixo: 
𝑒1 𝑒2 𝑒3 𝑒4 𝑒5 𝑒6 
𝑣1 1 1 0 0 0 0 
𝑣2 0 1 1 1 1 0 
𝑣3 0 0 1 0 0 1 
𝑣4 0 0 0 1 0 1 
𝑣5 0 0 0 0 1 0 
𝑣6 0 0 0 0 0 0 
𝑒7 𝑒8 𝑒9 𝑒10 𝑒11 
0 0 0 0 1 
0 0 0 0 0 
0 0 0 0 0 
1 1 0 0 0 
1 0 1 1 0 
0 1 1 1 1 
Fonte: Autoria própria. 
Figura 19. Exemplo de grafo e tabela. 
Representação de grafos 
Segue a tabela e a matriz de incidência do grafo da figura anterior: 
1 1 0
0 1 1
0 0 1
0 0
1 1
0 0
0 0 0 0 0 1
0 0 0 0 0 0
1 0 0 0 0 0
0 0 0
0 0 0
1 0
0 1
1 1 1 0 0 0
0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 1 1
 
𝑒1 𝑒2 𝑒3 𝑒4 𝑒5 𝑒6 
𝑣1 1 1 0 0 0 0 
𝑣2 0 1 1 1 1 0 
𝑣3 0 0 1 0 0 1 
𝑣4 0 0 0 1 0 1 
𝑣5 0 0 0 0 1 0 
𝑣6 0 0 0 0 0 0 
𝑒7 𝑒8 𝑒9 𝑒10 𝑒11 
0 0 0 0 1 
0 0 0 0 0 
0 0 0 0 0 
1 1 0 0 0 
1 0 1 1 0 
0 1 1 1 1 
Fonte: Autoria própria. 
Figura 20. Exemplo de tabela e matriz. 
Tipos de grafos 
 
Definição 16 (Grafo trivial): É um grafo com um único vértice e não tem arestas. 
Na Figura abaixo segue um grafo trivial: 
Fonte: Autoria própria. 
Figura 21. Exemplo de grafo trivial. 
Tipos de grafos 
 
Definição 17 (Grafo simples). Um grafo é dito simples se ele não possui laços e 
nem arestas paralelas. 
Na Figura abaixo segue um grafo simples: 
Fonte: Autoria própria. 
Figura 22. Exemplo de grafo simples. 
Tipos de grafos 
 
Definição 18 (Grafo completo): Um grafo é completo se ele for um grafo simples 
onde todos os vértices conectam-se uns aos outros. 
Na Figura abaixo segue um grafo completo: 
Fonte: Autoria própria. 
Figura 23. Exemplo de grafo completo. 
Tipos de grafos 
 
Definição 19 (Grafo regular): Um grafo é regular quando todos os seus vértices 
possuem o mesmo grau. 
Na Figura abaixo segue um grafo regular: 
Fonte: Autoria própria. 
Figura 24. Exemplo de grafo regular. 
Tipos de grafos 
 
Definição 20 (Subgrafo): Subgrafo é um grafo construído de tal forma que seus 
vértices e suas arestas estão contidos em outro grafo. 
Abaixo o grafo da Figura a direita é um subgrafo do grafo da Figura a esquerda: 
Fonte: Autoria própria. 
Figura 25. Exemplo de grafo. 
Fonte: Autoria própria. 
Figura 26. Exemplo de subgrafo. 
Tipos de grafos 
 
Definição 21 (Grafo bipartido): Um grafo é dito bipartido quando seu conjunto 
de vértices 𝑉 puder ser particionado em dois subconjuntos 𝑉1 e 𝑉2, tais que toda 
aresta de 𝐺(𝑉, 𝐴) une um vértice de 𝑉1 a outro de 𝑉2. 
Na Figura abaixo segue um grafo bipartido: 
Fonte: Autoria própria. 
Figura 27. Exemplo de grafo bipartido. 
Tipos de grafos 
 
Definição 22 (Grafo conexo): Grafo conexo é um grafo onde existe um ou mais 
caminhos que nos levam a qualquer vértice do grafo independente de qual seja o 
vértice de partida. 
Na Figura abaixo segue um grafo conexo: 
Fonte: Autoria própria. 
Figura 28. Exemplo de grafo conexo. 
Tipos de grafos 
 
Definição 23 (Grafo desconexo). É um grafo onde existe pelo menos um vértice 
que não pode ser conectado a outro por um caminho. 
Na Figura abaixo segue um grafo desconexo: 
Fonte: Autoria própria. 
Figura 29. Exemplo de grafo desconexo. 
Tipos de grafos 
 
Definição 24 (Grafo direcionado ou Dígrafo): Grafo direcionado é um grafo que 
contém um direcionamento quanto ao sentido das arestas. 
Grafos direcionados são usados para problemas com fluxo único. Por exemplo 
avenidas com direção única para os veículos. Na Figura abaixo segue um grafo 
direcionado: 
Fonte: Autoria própria. 
Figura 30. Exemplo de grafo direcionado ou dígrafo. 
Tipos de grafos 
 
Definição 25 (Grafo não direcionado): Grafo não direcionado é um grafo onde 
não existe nenhuma orientação quanto ao sentido da aresta. 
São grafos onde o fluxo em todas as arestas podem seguir nas duas direções. 
Na Figura abaixo segue um grafo não direcionado: 
Fonte: Autoria própria. 
Figura 31. Exemplo de grafo não direcionado. 
Tipos de grafos 
 
Alguns autores definem também grafos mistos, com arestas não direcionadas 
e direcionadas. Note que toda aresta não direcionada pode ser substituída por 
duas arestas direcionadas nas duas direções possíveis. Segue nas figuras 
abaixo um exemplo, tendo à esquerda um grafo misto e à direita um grafo 
direcionado, que podem ser aplicado para o mesmo problema. 
Fonte: Autoria própria. 
Figura 32. Exemplo de grafos mistos. 
Tipos de grafos 
 
Definição 26 (Grafo rotulado): Um grafo é dito ser rotulado em vértices (ou 
arestas) quando a cada vértice (ou aresta) estiver associado um rótulo. 
Na Figura abaixo segue um grafo rotulado: 
Fonte: Autoria própria. 
Figura 33. Exemplo de grafo rotulado. 
Tipos de grafos 
 
Definição 27 (Grafo valorado): Um grafo é ditoser valorado quando existe uma 
ou mais funções (peso) relacionando vértices e/ou arestas a um valor escalar. 
Estes valores podem representar distância gasta de um vértice para outro. 
Existem grafos não valorados, por exemplo uma casa e cada vértice um cômodo 
da casa. Na Figura abaixo segue um grafo valorado: 
Fonte: Autoria própria. 
Figura 34. Exemplo de grafo valorado. 
Tipos de grafos 
 
Definição 28 (grau de entrada e a saída): Considere um grafo direcionado 𝐺, 
definimos o grau de saída de um vértice 𝑣, denotado 𝑑−(𝑣), como o número de 
arcos que têm origem em 𝑣 , e o grau de entrada, 𝑑+ 𝑣 , como o número de arcos 
que têm seu destino em 𝑣. 
Na Figura abaixo segue um grafo direcionado com 𝑑− 𝑣1 = 3, 𝑑
− 𝑣2 = 0 , 
𝑑− 𝑣3 = 2 , 𝑑
− 𝑣4 = 0 , 𝑑
− 𝑣5 = 1 e 𝑑
+ 𝑣1 = 0, 𝑑
+ 𝑣2 = 2 , 𝑑
+ 𝑣3 = 0 , 
𝑑+ 𝑣4 = 3, 𝑑
+ 𝑣5 = 1. 
Fonte: Autoria própria. 
Figura 35. Exemplo de grafo – grau de entrada e a saída. 
Definição 29: Um grafo 𝐺(𝑉,𝐴) é denominado árvore se ele for conexo, 
não contiver qualquer ciclo como subgrafo e a remoção de qualquer 
uma de suas arestas o torna desconexo. 
 
 
Adição Árvores 
 
 
Seja 𝐺(𝑉,𝐴) uma árvore que possui 𝑛 vértices, então 𝐺(𝑉,𝐴) possui 
(𝑛 − 1) arestas. Na Figura abaixo segue um exemplo de árvore com 
7 vértices e 6 arestas. 
 
Fonte: Autoria própria. 
Figura 36. Exemplo de grafo árvore. 
Definição 30 (Árvore geradora): Árvore geradora é uma árvore que 
interliga direta ou indiretamente todos os vértices do grafo. 
 
Adição Árvores 
 
 
Abaixo o grafo da Figura à direita é uma árvore geradora do grafo da 
Figura à esquerda: 
Fonte: Autoria própria. 
Figura 37. Exemplo de grafo árvore geradora. 
Definição 31 (Árvore geradora mínima): Uma árvore gerada mínima 
de um grafo com pesos nas arestas (grafo valorado) é qualquer árvore 
geradora que tenha peso mínimo. 
Adição Árvores 
 
 
Abaixo o grafo da Figura à direita é uma árvore geradora mínima do 
grafo da Figura à esquerda: 
Fonte: Autoria própria. 
Figura 38. Exemplo de grafo árvore geradora mínima. 
Grafos eulerianos 
 
Definição 32 (Ciclo euleriano): Chamamos de ciclo euleriano um ciclo em 
𝐺(𝑉, 𝐴) que passe por todas as arestas desse grafo uma única vez. 
Na Figura abaixo, temos que {𝑒1, 𝑒2, 𝑒3, 𝑒4, 𝑒5, 𝑒6, 𝑒7, 𝑒8, 𝑒9, 𝑒10} é um exemplo de 
ciclo euleriano. 
Fonte: Autoria própria. 
Figura 39. Exemplo de grafo ciclo euleriano. 
Grafos eulerianos 
 
Definição 33 (Grafo euleriano): Grafo euleriano é um grafo que contém um 
ciclo euleriano. 
Lema 1: Se 𝐺(𝑉, 𝐴) é um grafo euleriano, então todo vértice de 𝐺(𝑉, 𝐴) possui 
grau par. 
Lema 2: Seja 𝐺(𝑉, 𝐴) um grafo conexo. Se o grau de cada vértice é pelo 
menos dois, então 𝐺(𝑉, 𝐴) contém um ciclo. 
Lema 3: Seja 𝐺(𝑉, 𝐴) um grafo conexo. Se todo vértice de 𝐺(𝑉, 𝐴) possui grau 
par, então 𝐺(𝑉, 𝐴) é euleriano. 
Para as demonstrações das propriedades, pode ser visto em Vulcani (2015). 
Grafos eulerianos 
 
Teorema 1 (Teorema de Euler): Um grafo conexo 𝐺(𝑉,𝐴) é euleriano se, e 
somente se, o grau de todos os vértices de 𝐺(𝑉,𝐴) é par. 
Corolário: Um grafo conexo 𝐺(𝑉,𝐴) possui caminho euleriano se, e 
somente se, 𝐺(𝑉,𝐴) tem exatamente zero ou dois vértices de grau ímpar. 
Teorema 2 (Teorema de Euler para grafo direcionado): Um grafo 
direcionado conexo 𝐺(𝑉,𝐴) é euleriano se, e somente se, todos seus vértices 
têm valores de grau de entrada e saída iguais, ou seja, se para todo vértice 
𝑣 de 𝐺(𝑉,𝐴) vale que 𝑑+ 𝑣 = 𝑑−(𝑣). 
 
Grafos hamiltonianos 
 
Definição 34 (Grafo hamiltoniano): Grafo hamiltoniano é um grafo que contém 
um ciclo que passa por todos os seus vértices, sendo que cada vértice só 
aparece uma única vez no ciclo. 
A Figura abaixo é um exemplo de um grafo hamiltoniano: 
Fonte: Autoria própria. 
Figura 40. Exemplo de grafo hamiltoniano. 
Grafos hamiltonianos 
 
Definição 35 (Ciclo hamiltoniano). Chamamos de ciclo hamiltoniano um ciclo 
em 𝐺(𝑉,𝐴) que contenha todos os seus vértices, sendo que cada vértice só 
aparece uma vez no ciclo, com exceção do vértice de início. 
Na Figura abaixo, temos que {𝑣1, 𝑒1, 𝑣2, 𝑒3, 𝑣5, 𝑒5, 𝑣3, 𝑒6, 𝑣4, 𝑒7, 𝑣1} é um exemplo de 
ciclo hamiltoniano. 
Fonte: Autoria própria. 
Figura 41. Exemplo de grafo ciclo hamiltoniano. 
Elementos da teoria dos grafos 
Resumo da apresentação 
 
Nesta apresentação abordamos a definição 
de grafo, seus diversos tipos e algumas das 
principais propriedades de teoria dos grafos. 
 
CRÉDITOS 
Autor 
Autores 
Marcelo Bruno Gomes Pedroza 
Graduado em Matemática 
Especialista em Matemática e Física 
 Mestre em Matemática 
 
Glauber Marcio Silveria Pereira 
Graduado em Matemática 
Mestre em Bioestatística 
Doutor em Estatística 
 
Erica Boizan Batista 
Graduada em Matemática 
Mestre em Matemática 
Doutora em Matemática 
REFERÊNCIAS 
BOAVENTURA, E. de O.; URIBE, E. B. O. Estudo sobre grafos e algumas aplicações. Colloquium Exactarum, v. 08, n. Especial, p. 26–33, jul–dez 
2016. 
 
BOAVENTURA NETTO, P. O. Grafos: Teoria, Modelos, Algoritmos. 3. ed. Rio de Janeiro: Edgard Blücher, 2003. 
 
CARVALHO, D. A. de; MALDONADO, M. O problema do carteiro chinês: Modelagem e métodos de solução. Procedding Series of the Brazilian 
Society of Computational and Applied Mathematics, v. 6, n. 2, p. 010162–1–010162–2, 2018. 
 
FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. Uma Introdução Sucinta à Teoria dos Grafos. 1. ed. São Paulo: USP/SBM, 2011. 
 
PEDROSA, M. B. G. Uma introdução à Teoria de Grafos Utilizando Problemas do Cotidiano (dissertação PROFMAT) – Universidade Federal do 
Cariri – UFCA, Juazeiro do Norte, Ceará, 2020. 
 
PEREIRA, G. M. R.; CÂMARA, M. A. da. Algumas aplicações da teoria dos grafos. FAMAT em Revista Controle & Automação, v. 11, p. 67–80, Oct 
2008. 
 
OLIVEIRA, G. F.; O problema do carteiro chinês (trabalho de conclusão de curso) – Universidade de São Paulo – USP, São Paulo, São Paulo, 2020. 
 
SILVA, A. A.; Uma abordagem heurística para o problema do carteiro chinês capacitado na coleta de lixo urbano (dissertação) – Universidade 
Federal de Pernambuco – UFPE, Recife, Pernambuco, 2020. 
 
VULCANI, R. de L. M. Grafos Eulerianos e Aplicações. Dissertação (Ph.D. dissertation) — Universidade Estadual de Campinas, Instituto de 
Matemática, Estatística e Computação Científica, Campinas, São Paulo, 2015. 
 
 
 
O material Introdução à Teoria dos Grafos - Unidade 1: Elementos da Teoria dos Grafos de Marcelo Bruno Gomes Pedroza, 
Glauber Márcio Silveira Pereira e Erica Boizan Batista está licenciado com uma Licença Creative Commons Atribuição-
NãoComercial 4.0 Internacional. 
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
28/10/2022 10:56 Grafos: Transcrição do vídeo da Unidade 2
https://cursos.poca.ufscar.br/mod/page/view.php?id=4209 1/4
Introdução à Teoria dos Grafos
Página inicial Meus cursos Grafos Transcrição do vídeo da Unidade 2
Transcrição do vídeo da Unidade 2
Transcrição do vídeo
Unidade 2 - Problemas Clássicos
Sejam bem-vindos à Unidade 2 do curso de Introdução à Teoria dos Grafos.
Nesta unidade veremos alguns problemas clássicos onde foi aplicado recursos de Teoria dos Grafos. Abordaremos quatro problemas
clássicos cujos títulos são:
- O problema das Sete Pontes de Königsberg 
- O problema do Carteiro Chinês 
- O problema das Quatro Cores 
- O problema do Caixeiro Viajante
Nesta unidade iremos apenas apresentar e comentar a relação desses problemas com a Teoria de Grafos, não necessariamente
mostrando suas soluções.
Este é o mapa da cidade chamada Königsberg, quefica na Alemanha. Esta cidade possui sete pontes, que aqui estão destacadas em
verde.
O problema das Sete Pontes de Königsberg consiste em encontrar uma forma de uma pessoa atravessar todas as pontes da cidade
uma única vez e retornar ao ponto de partida. Por vários anos esse problema não teve solução até que em 1736, Leonhard Euler
solucionou esse enigma. Euler propôs representar as partes de terra da cidade por pontos ( que ele chamou de vértices) e as pontes
que os uniam por linhas (que chamou de arestas). Observe como é feita a correspondência entre os vértices do grafo e as partes de
terra. Por outro lado, aqui vemos como as arestas se correspondem com cada uma das pontes.
Assim vemos que com esse grafo podemos representar bem o problema das sete pontes. Mas ainda fica a pergunta: É possível passar
pelas sete arestas uma única vez e retornar ao vértice inicial? Vamos fazer aqui uma tentativa de encontrar um caminho que solucione
esse problema.
Podemos começar pelo v1.
Então precisamos escolher entre as arestas e1, e2 e e7.
Escolhemos e1, e chegamos em v2.
Agora precisamos escolher entre e2, e3, e4 e e6.
Note que não podemos escolher e1 porque já passamos por essa aresta.
Escolhemos e3, e chegamos em v3.
Agora escolhemos e5, e chegamos em v4.
Depois escolhemos e7, e chegamos a v1.
Como já passamos por e1 só podemos escolher e2, e chegamos a v2.
Note que agora só podemos escolher entre e4 e e6, mas não importa a escolha que fizermos vamos falhar, pois não chegaremos a v1
e não passaremos por todas as arestas.
Portanto essa nossa tentativa não foi bem sucedida. 
Experimente pausar o vídeo e tentar você também encontrar um caminho que possa resolver o problema.
Esse problema inspirou Euler a provar seu famoso resultado, o conhecido Teorema de Euler, que diz:

https://cursos.poca.ufscar.br/
https://cursos.poca.ufscar.br/course/view.php?id=100&section=0
https://cursos.poca.ufscar.br/mod/page/view.php?id=4209
28/10/2022 10:56 Grafos: Transcrição do vídeo da Unidade 2
https://cursos.poca.ufscar.br/mod/page/view.php?id=4209 2/4
“Um grafo conexo G é euleriano se, e somente se, o grau de todos os vértices de G é par”.
Note que no nosso grafo os vértices v1, v3 e v4 tem grau três, enquanto que v2 tem grau 5. Então, de acordo com o Teorema de
Euler o caso das sete pontes não tem solução, pois todos os vértices do grafo têm grau ímpar.
Efeito sonoro 
Problema do Carteiro Chinês foi proposto por um matemático chinês chamado Meigu Guan em 1962.
O problema é o seguinte: Um carteiro tem que cobrir sua rota e depois retornar ao Posto de Correio. Qual é a menor rota que o
carteiro deve percorrer para cumprir seu trabalho?
Olhando esse problema sob a ótica da teoria dos grafos podemos interpretar as ruas de uma cidade como sendo as arestas de um
grafo e as intersecções entre as ruas seriam seus vértices.
Para que um caminho seja uma solução desse problema é necessário passar por todas as arestas pelo menos uma vez. Mas diferente
do problema anterior, o problema do Carteiro Chinês também é um problema de otimização, pois deve-se determinar o menor
caminho que satisfaça essa condição.
No exemplo abaixo temos um grafo cujos vértices têm todos grau par, e portanto é um grafo Eureliano. Logo, o caminho que serve de
solução para o problema é um ciclo Eureliano.
No entanto, para grafos não-Eurelianos o problema se torna mais complexo, porque é necessário considerar todas as distâncias entre
os cruzamentos das ruas. Essas distâncias aparecem como pesos nas arestas do grafo.
Esse problema se torna ainda mais complicado se considerarmos um grafo orientado, como seria o caso se o carteiro estivesse usando
um veículo e precisasse então levar em consideração as regras de trânsito.
Efeito sonoro
Vejamos agora o Problema do Caixeiro Viajante.
Neste problema consideramos um caixeiro viajante que quer visitar um número finito de cidades.
Conhecendo o custo de viagem entre elas, como podemos determinar a trajetória mais barata de modo que ele possa visitar todas as
cidades uma única vez e retornar à cidade inicial?
Este problema pode ser traduzido por um grafo, onde os vértices representam as cidades e as arestas representam o custo da viagem
de uma cidade a outra.
Vejamos como fica o grafo para esse problema.
Começamos com 4 cidades.
Denotamos por c(1,2) o custo para viajar da cidade 1 para a cidade 2;
por c(2,3) o custo para viajar da cidade 2 para cidade 3, e assim por diante.
Se aumentarmos uma cidade no problema, perceba que o grafo se torna mais complexo.
À medida que aumentamos o número de cidades o problema vai se complicando e o nosso viajante terá muito mais trabalho para
determinar sua rota. O primeiro registro do Problema do Caixeiro Viajante, é encontrado em um livro publicado na Alemanha em
1832.Em 1979 Nicos Christofides sugeriu um algoritmo aproximado para o problema do caixeiro viajante que possuiu o melhor fator
de aproximação por 30 anos.
Até que, em junho de 2020, uma aproximação melhor foi desenvolvida por Karlin, Klein e Gharan.
O Problema das Quatro Cores tem como objetivo determinar o número mínimo de cores necessárias para colorir um mapa de forma
que locais com fronteira comum recebam cores diferentes.
A história desse problema teve início em 1852, quando Francis Guthrie, tentava colorir os vários distritos do mapa da Inglaterra de tal
modo que dois distritos vizinhos não tivessem a mesma cor.
Perceba que esse problema pode ser traduzido para a linguagem de grafos se representarmos as regiões do mapa por vértices e as
fronteiras por arestas.
No exemplo podemos ver que a região em vermelho faz fronteira com as outras três regiões, consequentemente o vértice vermelho
está ligado aos três outros vértices. Por outro lado, a região amarela não faz fronteira com a região verde e por isso não há uma
aresta ligando o vértice amarelo ao vértice verde.
Após ter refletido sobre o problema, Guthrie afirmou que qualquer mapa poderia ser colorido com apenas quatro cores, mas não
provou.

28/10/2022 10:56 Grafos: Transcrição do vídeo da Unidade 2
https://cursos.poca.ufscar.br/mod/page/view.php?id=4209 3/4
É preciso esclarecer que quando várias regiões se encontram em um único ponto, não são consideradas vizinhas para a formulação
deste teorema. Assim, na figura a seguir, cada região tem fronteira com apenas duas outras, mesmo que todas elas se toquem em um
ponto no centro da figura.
Essa pergunta então foi compartilhada com outros matemáticos, que tentaram provar o resultado.
Em 1879 Alfred Bray Kempe publicou uma demonstração completa do Teorema das Quatro Cores no American Journal of Mathematics;
Mas, em 1890, Percy John Heawood, provou que a demonstração de Kempe tinha um erro.
Heawood, infelizmente, não conseguiu provar o Teorema das Quatro Cores, mas enunciou e demonstrou o Teorema das Cinco Cores
que diz que não são necessárias mais do que cinco cores para colorir um mapa plano onde territórios de fronteira comum têm cores
diferentes. Em 1976, Kenneth Appel e Wolfgang Haken apresentaram uma demonstração do Teorema das Quatro Cores. No entanto, a
demonstração incluía mais de mil horas de uso de computadores de alta velocidade, e portanto era muito longa para ser conferida
manualmente.
Hoje em dia a validade da demonstração é aceita pela comunidade matemática, mas continua sendo alvo de polêmica.
A questão de construir uma demonstração que não necessite do auxílio de computadores continua em aberto!
Vejamos um exemplo de mapa que precisa de pelo menos quatro cores para ser colorido.
Aqui temos o mapa da América do Sul. Vamos primeiro colorir o Brasil de verde.
Como a Argentina faz fronteira com o Brasil não podemos colorir ela de verde, logo vamos pintá-la de amarelo.
Agora, como a Bolívia faz fronteira com o Brasil e com a Argentina, não podemos colorir ela de verde nem de amarelo, por isso vamos
usar a cor vermelha.
Note que o Paraguai faz fronteira com o Brasil, a Argentina e a Bolívia, portanto precisaremos de uma quarta cor para colorir oParaguai. No caso usaremos azul.
Na Figura vemos o mapa do Brasil colorido com exatamente quatro cores.
Uma observação importante é que não existe uma solução única para esse problema, ou seja, se usarmos pelo menos quatro cores é
possível encontrar várias configurações diferentes para a coloração do mapa.
Agora convidamos você a fazer a sua própria solução do problema acessando o link que está na descrição do vídeo.
Nessa apresentação abordamos alguns dos problemas clássicos da Teoria dos Grafos
Participaram da produção dessa aula os professores Marcelo Bruno Gomes Pedroza, Glauber Marcio Silveira Pereira e Erica Boizan
Batista.
Agradecemos por você ter acompanhado o curso até aqui e gostaríamos de saber a sua opinião.
Para isso aguardamos o seu comentário no fórum do curso.
Até mais!
Última atualização: quarta-feira, 14 jul 2021, 16:42

Manter contato
Secretaria Geral de Educação a Distância
 http://www.sead.ufscar.br
 contato@poca.ufscar.br
 Resumo de retenção de dados
 Obter o aplicativo para dispositivos móveis
http://www.sead.ufscar.br/
mailto:contato@poca.ufscar.br
https://cursos.poca.ufscar.br/admin/tool/dataprivacy/summary.php
https://download.moodle.org/mobile?version=2021051708&lang=pt_br&iosappid=633359593&androidappid=com.moodle.moodlemobile
28/10/2022 10:56 Grafos: Transcrição do vídeo da Unidade 2
https://cursos.poca.ufscar.br/mod/page/view.php?id=4209 4/4
ORGULHOSAMENTE FEITO COM 
Feito com  por conecti.me

https://moodle.org/
http://conecti.me/
Professores: 
Marcelo Bruno Gomes Pedroza 
Glauber Marcio Silveira Pereira 
Erica Boizan Batista 
Introdução à Teoria dos Grafos 
Unidade 3. Algoritmos. 
TÓPICOS 
Algoritmo de Kruskal 
Algoritmo de Fleury 
Algoritmo dos Mínimos Sucessivos 
O que é um algoritmo? 
 
 
Um algoritmo é como chamamos as ordens do 
programador em sequência para obter a solução para 
um determinado problema. 
 
É parecido com uma receita, siga as ordens na 
sequência para ter o resultado esperado. 
Algoritmo dos Mínimos Sucessivos 
 
 
O Algoritmo dos Mínimos Sucessivos foi desenvolvido 
com o intuito de resolver o Problema do Caixeiro Viajante 
(PEDROZA, 2020), que vimos na unidade anterior, em 
que escolhe-se a cidade mais próxima sempre que o 
caixeiro se desloque até que todas as cidades sejam 
visitadas. 
Algoritmo dos Mínimos Sucessivos 
 
 Seja 𝐺(𝑉,𝐴) um grafo hamiltoniano com 𝑛 vértices que contém 𝑘 ciclos 
hamiltonianos. 
 
- Dentre todos os vértices, escolha um aleatoriamente para ser o 
ponto de partida; 
- Selecione outro vértice que seja adjacente ao anterior e que a aresta 
que os una seja a de menor peso. Caso haja dois ou mais vértices, 
cujas arestas tenham o mesmo peso, escolhe-se um deles 
aleatoriamente; 
- Deve-se passar por todos os vértices sem repetir nenhum deles. 
Salvo o primeiro vértice, que após todos terem sido visitados, 
voltamos ao ponto de partida; 
- Repetir sucessivamente até formar um ciclo hamiltoniano. 
Algoritmo dos Mínimos Sucessivos 
 
 
A aplicação desse passo a passo será a mesma 
quantidade que o número de vértices, pois todos os 
vértices terão que ser ponto de partida para um ciclo 
hamiltoniano. 
 
A solução será o ciclo que apresentar o menor peso. 
Algoritmo dos Mínimos Sucessivos 
 
 Vamos demonstrar o funcionamento do Algoritmo dos mínimos 
sucessivos para encontrar o ciclo de menor peso do grafo ilustrado na 
figura abaixo, cujos pesos das respectivas arestas estão indicados. 
Fonte: Autoria própria. 
Figura 1. Exemplo de Grafo. 
Algoritmo dos Mínimos Sucessivos 
 
 Escolhendo o vértice 𝑣1 , como vértice de partida. Em seguida, 
escolhemos o vértice adjacente ao vértice 𝑣1, cuja aresta que os una 
seja a de menor peso. Note que 𝑣2 e 𝑣3 são vértices adjacentes a 𝑣1, 
cujas arestas 𝑒1 = 4 e 𝑒1 = 4 têm o mesmo peso, logo podemos 
escolher um deles aleatoriamente. 
Figura 2. Exemplo de Grafo. 
Fonte: Autoria própria. 
Algoritmo dos Mínimos Sucessivos 
 
 
Escolhemos a aresta 𝑒1 = 4 que leva ao vértice 𝑣2 . Escolhendo 
novamente a aresta de menor peso, nesse caso 𝑒6 = 2, chegamos à 
𝑣4. De 𝑣4 podemos ir para o vértice 𝑣3 ou 𝑣5, como devemos seguir 
pela de menor peso, nessa caso 𝑒9 = 13, chegamos ao vértice 𝑣3. 
Fonte: Autoria própria. 
Figura 3. Exemplo de Grafo. 
Algoritmo dos Mínimos Sucessivos 
 
 
De 𝑣3 só podemos seguir para o vértice 𝑣5, pela aresta 𝑒8 = 8. Agora 
que passamos por todos os vértices devemos retornar ao vértice de 
partida, 𝑣1, usando para isso a aresta 𝑒2 = 9. Desse modo, formamos 
o ciclo ilustrado na figura abaixo. Ou seja, {𝑣1, 𝑣2, 𝑣4, 𝑣3, 𝑣5, 𝑣1} . 
Somando os pesos das arestas do ciclo formado temos: 4 + 2 + 13 +
8 + 9 = 36. 
Figura 4 . Exemplo de Grafo 
Fonte: Autoria própria. 
Algoritmo dos Mínimos Sucessivos 
 
 Usaremos como agora 𝑣2 como nosso vértice de partida. Escolhendo a aresta 
de menor peso, que em nosso grafo é aresta 𝑒6 = 2, chegamos em 𝑣4. De 𝑣4 
percorremos por 𝑒3 = 6, chegando em 𝑣1. De 𝑣1 para 𝑣3 usando 𝑒4 = 4. De 𝑣3 
seguimos por 𝑒8 = 8 para 𝑣5. Como passamos por todos os vértices, devemos 
retornar a 𝑣2 usando a aresta de menor peso que é 𝑒5 = 10. Desse modo, 
formamos o ciclo ilustrado na figura abaixo: 
Figura 5. Exemplo de Grafo. 
Fonte: Autoria própria. 
Algoritmo dos Mínimos Sucessivos 
 
 Ou seja, {𝑣2, 𝑣4, 𝑣1, 𝑣3, 𝑣5, 𝑣2}. Somando os pesos das arestas do ciclo 
formado temos: 2 + 6 + 4 + 8 + 10 = 30. 
Tomando 𝑣3 como vértice de partida e aplicando os passos do 
algoritmo, temos o ciclo ilustrado na figura abaixo: 
Fonte: Autoria própria. 
Figura 6. Exemplo de Grafo. 
Algoritmo dos Mínimos Sucessivos 
 
 Ou seja, {𝑣2, 𝑣4, 𝑣1, 𝑣3, 𝑣5, 𝑣2}. Somando os pesos das arestas do ciclo 
formado temos: 2 + 6 + 4 + 8 + 10 = 30. 
Tomando 𝑣3 como vértice de partida e aplicando os passos do 
algoritmo, temos o ciclo ilustrado na figura abaixo: 
Fonte: Autoria própria. 
Figura 7. Exemplo de Grafo. 
Algoritmo dos Mínimos Sucessivos 
 
 Ou seja, {𝑣3, 𝑣1, 𝑣2, 𝑣4, 𝑣5, 𝑣3}. Somando os pesos das arestas do ciclo 
formado temos: 4 + 4 + 2 + 17 + 8 = 35. 
Tomando 𝑣4 como vértice de partida e aplicando os passos do 
algoritmo, temos o ciclo ilustrado na figura abaixo: 
Fonte: Autoria própria. 
Figura 8. Exemplo de Grafo. 
Algoritmo dos Mínimos Sucessivos 
 
 Ou seja, {𝑣4, 𝑣2, 𝑣1, 𝑣3, 𝑣5, 𝑣4}. Somando os pesos das arestas do ciclo 
formado temos: 2 + 4 + 4 + 8 + 17 = 35. 
Tomando 𝑣4 como vértice de partida e aplicando os passos do 
algoritmo, temos o ciclo ilustrado na figura abaixo: 
Fonte: Autoria própria. 
Figura 9. Exemplo de Grafo. 
Algoritmo dos Mínimos Sucessivos 
 
 
Ou seja, {𝑣5, 𝑣3, 𝑣1, 𝑣2, 𝑣4, 𝑣5}. Somando os pesos das arestas do 
ciclo formado temos: 8 + 4 + 4 + 2 + 17 = 35. 
 
Note que os ciclos formados com início em 𝑣3, 𝑣4 e 𝑣5 representa 
o mesmo percurso, apenas com início diferente. 
 
Isso pode ser confirmado quando observamos as somas dos 
pesos de cada um desses ciclos e quando observamos nas 
figuras apresentadas. Como solução, escolhemos o ciclo de 
menor peso, ou seja, o ciclo , {𝑣2, 𝑣4, 𝑣1, 𝑣3, 𝑣5, 𝑣2}. 
Algoritmo de Kruskal 
O Algoritmo de Kruskal foi proposto em 1956 pelo matemático 
Joseph Bernard Kruskal Junior (1928 à 2010). Esse algoritmo 
busca uma árvore geradora mínima para um grafo conexo com 
pesos. 
 
Ou seja, ele encontra um subconjunto das arestas que formam 
uma árvore que inclui todos os vértices do grafo, onde o peso total 
(dado pela soma dos pesos das arestas da árvore) é o mínimo 
possível. 
Algoritmo de Kruskal 
O Algoritmo de Kruskal executado em um grafo 𝐺(𝑉,𝐴) com 𝑛 
vértices e cujas as arestas são ponderadas, funcionará da 
seguinte forma: 
 
- Seja 𝑒𝑖 uma aresta de 𝐴 de menor peso. Se ei não criar ciclo em 
𝐺(𝑉,𝐴), 
então é adicionada a Árvore Geradora Mínima de 𝐺(𝑉,𝐴). Caso 
contrário, é 
descartada de 𝐴; 
 
- O processo é repetido até que 𝐴 seja vazio.Algoritmo de Kruskal 
Em outras palavras, o algoritmo construirá a Árvore Geradora 
Mínima de 𝐺(𝑉,𝐴) em que a primeira aresta a ser adicionada será 
aquela de menor peso. 
 
Feito isso, a próxima aresta a ser adicionada será novamente a de 
menor peso e que conecte quaisquer dois vértices ainda não 
conectados por nenhum caminho em 𝐺(𝑉,𝐴). 
 
Este processo será repetido até que as (𝑛 − 1) arestas da árvore 
sejam construídas. 
 
Algoritmo de Kruskal 
Vamos demonstrar o funcionamento do Algoritmo de Kruskal para 
encontrar a Árvore Geradora Mínima do grafo ilustrado na figura abaixo, 
cujos pesos das respectivas arestas estão indicados. 
Fonte: Autoria própria. 
Figura 10. Exemplo de Grafo. 
Algoritmo de Kruskal 
Escolhemos a aresta de menor peso, que nesse caso é 𝑒1 = 2. Assim, ela 
será incluída na árvore, conforme mostra a figura abaixo: 
Fonte: Autoria própria. 
Figura 11. Exemplo de Grafo. 
Algoritmo de Kruskal 
A próxima aresta de menor peso a ser incluída na árvore será 𝑒8 = 3, 
conforme ilustrado a figura abaixo: 
Fonte: Autoria própria. 
Figura 12. Exemplo de Grafo. 
Algoritmo de Kruskal 
Na próxima iteração do algoritmo notamos a existência de três arestas com o 
mesmo peso: 𝑒2 = 4, 𝑒3 = 4 e 𝑒10 = 4. Caso nenhuma delas forme um ciclo na árvore 
geradora, todas poderão ser incluídas. Na inclusão das arestas 𝑒2 = 4, 𝑒3 = 4 será 
formado o ciclo, logo só poderá ser inclusa uma delas aleatoriamente. Optamos por 
incluir as arestas 𝑒3 = 4, e 𝑒10 = 10 e pela exclusão da aresta 𝑒2 = 4. 
Ver figura abaixo: 
Fonte: Autoria própria. 
Figura 13. Exemplo de Grafo. 
Algoritmo de Kruskal 
Seguindo com o algoritmo, a próxima aresta de menor peso será 𝑒5 = 5. 
Note que ao incluir essa aresta é observado que se as arestas 𝑒6 = 10 e 
𝑒9 = 6 forem incluídas na árvore será formado um ciclo, logo devemos 
exclui-las. Conforme a figura abaixo: 
Fonte: Autoria própria. 
Figura 14. Exemplo de Grafo. 
Algoritmo de Kruskal 
No grafo restaram apenas as arestas 𝑒4 = 6 e 𝑒11 = 6, logo poderá ser 
inclusa a aresta 𝑒4 = 6 ou 𝑒11 = 6. Optamos por incluir a aresta 𝑒11 = 6 e 
excluir as arestas 𝑒4 = 6 e 𝑒7 = 8, pois com a inclusão da aresta 𝑒11 = 6 
ao tentar incluir uma das outras duas restantes formaria um ciclo. 
Portanto, elas terão que ser excluídas. 
Figura 15: Exemplo de Grafo. 
Fonte: Autoria própria. 
Algoritmo de Kruskal 
Notamos que no grafo da figura abaixo à esquerda é visto que todos os 
vértices estão conectados. Portanto, é formada a árvore geradora mínima 
do grafo, conforme figura abaixo à direita. 
Fonte: Autoria própria. Fonte: Autoria própria. 
Figura 16. Grafo Original. Figura 17. Árvore geradora. 
Algoritmo de Fleury 
 
O Algoritmo de Fleury de 1883 é utilizado para a construção ou 
identificação de um ciclo Euleriano em um grafo Euleriano. 
Algoritmo de Fleury 
 
Para utilizar o algoritmo comece em um vértice arbitrário do grafo e 
percorra as arestas de forma aleatória, seguindo as seguintes regras: 
 
- Selecione arbitrariamente uma aresta incidente ao vértice escolhido. 
Escolha uma ponte se, e somente se, não houver alternativa. Uma 
aresta é dita ser uma ponte se a sua remoção torna o grafo desconexo; 
- Exclua as arestas depois de passar por elas; 
- Exclua os vértices isolados, caso ocorram; 
- Quando todos os vértices estiverem isolados, encontramos um circuito 
de Euler. 
Algoritmo de Fleury 
 
Inicialmente, verificaremos se o grafo da figura abaixo satisfaz as 
condições do Teorema de Euler. Note que 𝑔 𝑣1 = 𝑔 𝑣2 = 𝑔 𝑣5 = 2 e 
𝑔 𝑣3 = 𝑔 𝑣4 = 4, logo pelo teorema de Euler, temos que o grafo 
possui um ciclo Euleriano. 
Fonte: Autoria própria. 
Figura 18. Exemplo de Grafo. 
Algoritmo de Fleury 
 
Vamos aplicar o Algoritmo de Fleury para construir esse ciclo. A cada 
iteração vamos mostrando a ilustração do grafo e uma tabela (não 
nessa ordem) com duas colunas: Rota e Aresta. Na coluna rota ficaram 
os vértices que escolhemos e na coluna aresta as arestas que foram 
excluídas do grafo. 
Fonte: Autoria própria. 
Figura 19. Exemplo de Grafo. 
Algoritmo de Fleury 
 
Inicialmente, escolhemos um vértice aleatório do grafo da figura abaixo 
a esquerda. Vamos escolher 𝑣2. De 𝑣2, podemos ir para 𝑣3 ou 𝑣4, pois 
nenhum deles forma uma ponte. Escolhemos 𝑣4, conforme mostra a 
figura abaixo à direita. A primeira iteração é descrita na tabela abaixo. 
Rota Aresta 
𝑣2 𝑣2, 𝑣4 
Fonte: Autoria própria. 
Fonte: Autoria própria. 
Figura 20. Exemplo de Grafo. Figura 21. Exemplo de Grafo. 
Figura 22. Tabela. 
Fonte: Autoria própria. 
Algoritmo de Fleury 
 
De 𝑣4, podemos ir para 𝑣1, 𝑣3 ou 𝑣5 pois nenhum deles forma uma 
ponte. Escolhemos 𝑣5, conforme figura abaixo. A segunda iteração é 
descrita na tabela abaixo. 
Rota Aresta 
𝑣2 𝑣2, 𝑣4 
𝑣2, 𝑣4 𝑣4, 𝑣5 
Fonte: Autoria própria. 
Figura 23. Exemplo de Grafo. 
Figura 24. Tabela. 
Fonte: Autoria própria. 
Algoritmo de Fleury 
 
De 𝑣5, só nos resta seguir para 𝑣3, conforme figura abaixo. A terceira 
iteração é descrita na tabela abaixo. 
Rota Aresta 
𝑣2 𝑣2, 𝑣4 
𝑣2, 𝑣4 𝑣4, 𝑣5 
𝑣2, 𝑣4, 𝑣5 𝑣5, 𝑣3 
Fonte: Autoria própria. 
Figura 25. Exemplo de Grafo. 
Fonte: Autoria própria. 
Figura 26. Tabela. 
Algoritmo de Fleury 
 
De 𝑣3, podemos seguir para 𝑣1, 𝑣2 ou 𝑣4, no entanto, 𝑣2 forma uma 
ponte. Logo devemos escolher entre 𝑣1 ou 𝑣4. Escolhemos ir para 𝑣1. A 
figura abaixo mostra essa situação. A quarta iteração é descrita na 
tabela abaixo. 
Rota Aresta 
𝑣2 𝑣2, 𝑣4 
𝑣2, 𝑣4 𝑣4, 𝑣5 
𝑣2, 𝑣4, 𝑣5 𝑣5, 𝑣3 
𝑣2, 𝑣4, 𝑣5, 𝑣3 𝑣3, 𝑣1 
Fonte: Autoria própria. 
Figura 27. Exemplo de Grafo. 
Fonte: Autoria própria. 
Figura 28. Tabela. 
Algoritmo de Fleury 
 
De 𝑣1 , só nos resta seguir para 𝑣4 . A figura abaixo mostra essa 
situação. A quinta iteração é descrita na tabela abaixo. 
Rota Aresta 
𝑣2 𝑣2, 𝑣4 
𝑣2, 𝑣4 𝑣4, 𝑣5 
𝑣2, 𝑣4, 𝑣5 𝑣5, 𝑣3 
𝑣2, 𝑣4, 𝑣5, 𝑣3 𝑣3, 𝑣1 
Fonte: Autoria própria. 
Figura 29. Exemplo de Grafo. 
Fonte: Autoria própria. 
Figura 30. Tabela. 
Algoritmo de Fleury 
 
De 𝑣4, só nos resta ir para 𝑣3. A figura abaixo mostra essa situação. A 
sexta iteração é descrita na tabela abaixo. 
Rota Aresta 
𝑣2 𝑣2, 𝑣4 
𝑣2, 𝑣4 𝑣4, 𝑣5 
𝑣2, 𝑣4, 𝑣5 𝑣5, 𝑣3 
𝑣2, 𝑣4, 𝑣5, 𝑣3 𝑣3, 𝑣1 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1 𝑣1, 𝑣4 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1, 𝑣4 𝑣4, 𝑣3 
Fonte: Autoria própria. 
Figura 31. Exemplo de Grafo. 
Figura 32. Tabela. 
Fonte: Autoria própria. 
Algoritmo de Fleury 
 
De 𝑣3, só nos resta ir para 𝑣2. Todos os vértices do grafo da Figura 
abaixo estão desconectados, logo é um circuito euleriano. A sétima 
iteração é descrita na tabela abaixo. 
Rota Aresta 
𝑣2 𝑣2, 𝑣4 
𝑣2, 𝑣4 𝑣4, 𝑣5 
𝑣2, 𝑣4, 𝑣5 𝑣5, 𝑣3 
𝑣2, 𝑣4, 𝑣5, 𝑣3 𝑣3, 𝑣1 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1 𝑣1, 𝑣4 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1, 𝑣4 𝑣4, 𝑣3 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1, 𝑣4, 𝑣3 𝑣3, 𝑣2 
Fonte: Autoria própria. 
Fonte: Autoria própria. 
Figura 33. Exemplo de Grafo. 
Figura 34. Tabela. 
Algoritmo de Fleury 
 
Observe ainda que na última linha da Tabela abaixo chegamos à rota 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1, 𝑣4, 𝑣3, 𝑣2, ela indica o percurso do nosso circuito euleriano. 
Rota Aresta 
𝑣2 𝑣2, 𝑣4 
𝑣2, 𝑣4 𝑣4, 𝑣5 
𝑣2, 𝑣4, 𝑣5 𝑣5, 𝑣3 
𝑣2, 𝑣4, 𝑣5, 𝑣3 𝑣3, 𝑣1 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1 𝑣1, 𝑣4 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1, 𝑣4 𝑣4, 𝑣3 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1, 𝑣4, 𝑣3 𝑣3, 𝑣2 
𝑣2, 𝑣4, 𝑣5, 𝑣3, 𝑣1, 𝑣4, 𝑣3, 𝑣2 
Fonte: Autoria própria. 
Figura 35. Tabela. 
Algoritmos 
Resumo da apresentação 
 
Nesta apresentação abordamos três 
algoritmos com exemplos de aplicação. 
 
CRÉDITOS 
Autor 
Autores 
Marcelo Bruno Gomes Pedroza 
Graduado em Matemática 
Especialista em Matemática e Física 
 Mestre em Matemática 
 
Glauber Marcio Silveira Pereira 
Graduado em Matemática 
Mestre em Bioestatística 
Doutor em Estatística 
 
Erica Boizan Batista 
Graduada em Matemática 
Mestreem Matemática 
Doutora em Matemática 
REFERÊNCIAS 
BOAVENTURA NETTO, P. O. Grafos: Teoria, Modelos, Algoritmos. 3. ed. Rio de Janeiro: 
Edgard Blücher, 2003 
 
PEDROZA, M. B. G. Uma introdução à Teoria de Grafos Utilizando Problemas do Cotidiano 
(dissertação PROFMAT) – Universidade Federal do Cariri – UFCA, Juazeiro do Norte, 
Ceará, 2020. 
 
SILVA, A. A.; Uma abordagem heurística para o problema do carteiro chinês capacitado na 
coleta de lixo urbano (dissertação) – Universidade Federal de Pernambuco – UFPE, Recife, 
Pernambuco, 2020. 
 
 
 
O material Introdução à Teoria dos Grafos - Unidade 3: Algoritmos de Marcelo Bruno Gomes Pedroza, Glauber Márcio 
Silveira Pereira e Erica Boizan Batista está licenciado com uma Licença Creative Commons Atribuição-NãoComercial 4.0 
Internacional. 
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
http://creativecommons.org/licenses/by-nc/4.0/
28/10/2022 10:56 Grafos: Transcrição do vídeo da Unidade 4
https://cursos.poca.ufscar.br/mod/page/view.php?id=4210 1/3
Introdução à Teoria dos Grafos
Página inicial Meus cursos Grafos Transcrição do vídeo da Unidade 4
Transcrição do vídeo da Unidade 4
Transcrição do vídeo
Unidade 4 - Problemas Cotidianos
Sejam bem-vindos à Unidade 4 do curso de Introdução à Teoria dos Grafos.
Nesta unidade veremos alguns problemas inspirados em situações do cotidiano onde podemos aplicar recursos de Teoria dos
Grafos. Abordaremos quatro problemas cujos títulos são:
- O assassinato 
- A rota 
- Os turistas 
- As lojas
Primeiro Problema: O assassinato.
Neste primeiro problema nos deparamos com uma situação um tanto chocante… o assassinato de um milionário na sala de estar de
sua própria casa!
Após investigar a cena do crime e assistir aos vídeos das câmeras de segurança, os investigadores chegaram à conclusão que
ninguém entrou na casa durante o período em que o assassinato aconteceu.
Logo o crime só pode ter sido cometido por alguém que já estava na casa.
Assim, os investigadores reduziram a lista de suspeitos a duas pessoas: A Governanta e Arrumadeira. Durante o interrogatório a
Arrumadeira afirmou ter visto a Governanta usar a mesma porta para entrar e sair da sala de estar no período em que o assassinato
aconteceu. No entanto, a Governanta alegou inocência, e disse que a Arrumadeira estava mentindo ou havia se enganado, uma vez
que ela havia entrado na casa, passado por todas as portas uma única vez, e logo em seguida saiu da casa.
Como as câmeras de segurança mostravam apenas o exterior da casa, os investigadores se viram em uma situação difícil e decidiram
buscar a ajuda de Charlotte Gomes, uma especialista em Teoria dos Grafos.
Assim que se inteirou do problema Charlotte pediu para ver a planta da casa. Ao examinar a planta da casa a especialista construiu
um grafo, onde os vértices representam os cômodos da casa e as arestas representam as portas que ligam esses cômodos. Olhe para
o grafo apresentado. Quais são os graus de cada vértice?
Note que há dois vértices com grau 3 e dois vértices com grau 5.
Logo, pelo Teorema de Euler, este grafo não admite um ciclo euleriano, ou seja, não é possível passar por todas as arestas do grafo
uma única vez, pois apesar de ser conexo, apresenta quatro vértices de grau ímpar.
Assim, Charlotte concluiu que a Governanta mentiu em seu depoimento, e o caso foi concluído.
Efeito sonoro: porta de cela de cadeia sendo trancada
Nosso próximo problema fala a respeito de um caminhão de lixo que percorre diariamente as ruas ilustradas na Figura.
Para que o serviço seja mais eficiente, a empresa de coleta de lixo precisa determinar o trajeto que minimiza a distância percorrida
pelo caminhão, mas sem deixar de passar em nenhuma rua.
Considere então o grafo apresentado na figura b), onde as ruas serão representadas pelas arestas e as intersecções entre as ruas
serão representadas pelos vértices do nosso grafo.
Inicialmente, note que o grafo que construímos satisfaz às condições do teorema de Euler pois cada um de seus vértices têm grau par.
Logo, pelo teorema de Euler, temos que o grafo possui um ciclo Euleriano, ou seja, podemos percorrer o grafo passando por cada
aresta uma única vez.

https://cursos.poca.ufscar.br/
https://cursos.poca.ufscar.br/course/view.php?id=100&section=0
https://cursos.poca.ufscar.br/mod/page/view.php?id=4210
28/10/2022 10:56 Grafos: Transcrição do vídeo da Unidade 4
https://cursos.poca.ufscar.br/mod/page/view.php?id=4210 2/3
Para encontrar o ciclo Euleriano vamos aplicar o algoritmo de Fleury.
Inicialmente, escolhemos um vértice aleatório do grafo. Vamos escolher v1.
De v1, podemos ir para v2 ou v4, pois nenhum deles forma ponte. Escolhemos então v2.
Assim, a aresta que vai de v1 a v2 é a primeira aresta da nossa rota.
Agora note que de v2, podemos ir para v3, v4 ou v5 pois nenhum deles forma uma ponte. Escolhemos v4.
Assim a aresta que liga v2 a v4 passa a fazer parte da nossa rota.
Note que de v4, nós podemos seguir para v1, v3 ou v5, no entanto, v1 forma uma ponte. Portanto não poderemos escolher v1 como
nosso próximo vértice.
Logo como devemos escolher entre v3 ou v5. Escolhemos ir para v3.
Como nosso grafo tem 10 arestas nós repetiremos esse processo 10 vezes, até passar por todas as arestas. Ao final desse processo
vamos obter um trajeto que não é único, por que pode variar dependendo dos vértices escolhidos. Aqui apresentamos uma das
possíveis soluções para esse problema, onde a rota encontrada é composta pela seguinte sequência de ruas: começando pela rua A, e
passando pelas ruas E, D, C, F, H, G e B.
Efeito sonoro: caminhão
Nosso próximo problema é sobre as férias de uma família que quer conhecer região Nordeste passando por todas as capitais e
viajando de carro.
Para isso eles querem saber qual é o melhor itinerário, ou seja, como podem passar uma única vez por todas as capitais percorrendo
a menor distância possível.
Note que é possível transformar a situação problema em um grafo, onde os vértices representam as capitais, as arestas representam
o caminho ligando essas cidades e os pesos das arestas representam a distância entre elas.
Para resolver esse problema é necessário encontrar a árvore geradora mínima do grafo, e para isso usaremos o Algoritmo de Kruskal.
Com o objetivo de facilitar a visualização da solução colocaremos em vermelho as arestas que forem escolhidas para fazer parte da
solução e em verde as arestas descartadas.
O primeiro passo para aplicar o algoritmo de Kruskal é selecionar a aresta de menor peso, ou seja, a aresta que representa a menor
distância. Nesse caso, a aresta ligando João Pessoa a Recife. Esta será a primeira parte da rota. O próximo passo é escolher a próxima
aresta de menor peso. Essa aresta é a que liga as cidades de Natal e João Pessoa, cujo peso é 151.
Note que a inclusão dessa aresta, implica na exclusão da aresta que liga as cidades de Natal e Recife (de peso 253), pois ela forma
um ciclo com as duas arestas escolhidas.
A próxima aresta a ser escolhida para fazer parte da solução é a aresta que liga Aracajú a Maceió e que tem peso 201.
Note que não há arestas que completem um ciclo incluindo essa aresta e as demais arestas em vermelho. Logo não precisaremos
excluir nenhuma aresta nesse passo.
Seguindo com o Algoritmo de Kruskal, vamos incluir na solução a próxima aresta de menor peso, que nesse caso é a aresta que liga
as cidades de Recife e Maceió de peso 202.
Na figura vemos em vermelho as arestas selecionadas para fazerem parte do itinerário e em verde as arestas que foram excluídas.
Ao fim do processo obtemos o seguinte percurso:
Salvador, Aracaju, Maceió, Recife, João Pessoa, Natal, Fortaleza,Teresina e por fim São Luís.
Agora é só fazer as malas e embarcar na viagem.
Efeito sonoro: Buzina de carro
Para o nosso quarto e último problema, suponha que você é dono de uma determinada rede de lojas de departamentos e deseja
instalar uma loja em cada cidade da região do Cariri, no Ceará. No entanto, as instalações das lojas estão sujeitas a seguinte
restrição: não pode haver o mesmo produto (vestuário, mobiliário, decoração etc.) em lojas de cidades vizinhas.
Como podemos usar a teoria dos Grafos para determinar uma solução para esse problema?
Primeiro vamos considerar um grafo que representa a região do Cariri, onde cada vértice representa uma cidade e cada aresta
representa uma fronteira em comum.
Vamos considerar as categorias de produtos como cores a serem usadas para colorir os vértices do Grafo.

28/10/2022 10:56 Grafos: Transcrição do vídeo da Unidade 4
https://cursos.poca.ufscar.br/mod/page/view.php?id=4210 3/3
ORGULHOSAMENTE FEITO COM 
Feito com  por conecti.me
Então, pelo teorema das Quatro Cores, sabemos que existem soluções usando pelo menos quatro cores para esse problema.
Considere por exemplo que a cor azul representa produtos eletrônicos, a cor verde representa mobiliário, vermelho o vestiário e
amarelo são os cosméticos. Logo para responder o problema bastaria colorir o grafo lembrando sempre de colocar cores distintas em
vértices adjacentes.
Na figura apresentamos uma solução possível, mas que não é única. Note que aqui estamos usando apenas três cores: vermelho,
verde e azul.
Aqui vemos uma segunda solução para o mesmo problema, desta vez usando 4 cores: vermelho, amarelo, verde e azul.
Agora basta escolher uma das diversas soluções para a distribuição das lojas e começar a fazer negócios.
Efeito sonoro: caixa registradora
Chegamos então ao fim da nossa unidade.
Nesta apresentação abordamos alguns problemas inspirados em situações do cotidiano onde podemos utilizar a Teoria de grafos.
Participaram da produção dessa aula os professores Marcelo Bruno Gomes Pedroza, Glauber Marcio Silveira Pereira e Erica Boizan
Batista.
Agradecemos por você ter acompanhado o curso até aqui e gostaríamos de saber a sua opinião.
Para isso aguardamos o seu comentário no fórum do curso.
Até mais!
Última atualização: quarta-feira, 14 jul 2021, 16:40

Manter contato
Secretaria Geral de Educação a Distância
 http://www.sead.ufscar.br
 contato@poca.ufscar.br
 Resumo de retenção de dados
 Obter o aplicativo para dispositivos móveis
https://moodle.org/
http://conecti.me/
http://www.sead.ufscar.br/
mailto:contato@poca.ufscar.br
https://cursos.poca.ufscar.br/admin/tool/dataprivacy/summary.php
https://download.moodle.org/mobile?version=2021051708&lang=pt_br&iosappid=633359593&androidappid=com.moodle.moodlemobile
28/10/2022 11:42 Questionário: Revisão da tentativa
https://cursos.poca.ufscar.br/mod/quiz/review.php?attempt=635500&cmid=4171 1/8
Página inicial Meus cursos Grafos Atividade Questionário
Iniciado em sexta-feira, 28 out 2022, 11:39
Estado Finalizada
Concluída em sexta-feira, 28 out 2022, 11:42
Tempo
empregado
2 minutos 47 segundos
Avaliar 10,00 de um máximo de 10,00(100%)
Questão 1
Correto
Atingiu 1,00 de 1,00
Observe o grafo dado na figura. Identifique qual alternativa fornece uma árvore geradora para o grafo.
Escolha uma opção:
{ }
{ }
{ }
{ }
, , ,e1 e3 e4 e2
, , , ,e5 e6 e2 e4 e3
, , ,e5 e6 e2 e1
, , , ,e5 e3 e1 e2 e6
Sua resposta está correta.
https://cursos.poca.ufscar.br/
https://cursos.poca.ufscar.br/course/view.php?id=100&section=0
https://cursos.poca.ufscar.br/course/view.php?id=100&section=3
https://cursos.poca.ufscar.br/mod/quiz/view.php?id=4171
28/10/2022 11:42 Questionário: Revisão da tentativa
https://cursos.poca.ufscar.br/mod/quiz/review.php?attempt=635500&cmid=4171 2/8
Questão 2
Correto
Atingiu 1,00 de 1,00
Questão 3
Correto
Atingiu 1,00 de 1,00
Considere o grafo dado na figura, e indique qual das arestas do grafo tem peso 7.
 
 
Escolha uma opção:
A aresta que liga os vértices e .
A aresta que liga os vértices e .
A aresta que liga os vértices e .
A aresta que liga os vértices e .
v3 v4
v3 v5
v2 v4
v5 v4
Sua resposta está correta.
Considere o grafo dado na figura. Identifique qual alternativa fornece um ciclo Hamiltoniano para o grafo.
 
Escolha uma opção:
{ }
{ }
{ }
{ 0, }
, , ,e5 e4 e7 e8
, , ,e1 e2 e9 e8
, , , ,e6 e7 e8 e5 e4
e1 , , ,e3 e4 e8 e1
Sua resposta está correta.
28/10/2022 11:42 Questionário: Revisão da tentativa
https://cursos.poca.ufscar.br/mod/quiz/review.php?attempt=635500&cmid=4171 3/8
Questão 4
Correto
Atingiu 1,00 de 1,00
Assinale qual das alternativas apresenta o grafo Eureliano.
Escolha uma opção:

 
Sua resposta está correta.
28/10/2022 11:42 Questionário: Revisão da tentativa
https://cursos.poca.ufscar.br/mod/quiz/review.php?attempt=635500&cmid=4171 4/8
Questão 5
Correto
Atingiu 1,00 de 1,00
Questão 6
Correto
Atingiu 1,00 de 1,00
Considere as afirmações dadas abaixo a assinale a alternativa correta:
 I – Todo grafo completo é regular.
II – Todo grafo regular é completo.
III – Todo grafo trivial é bipartido.
 
Escolha uma opção:
É verdadeira apenas a afirmação II.
São verdadeiras as afirmações I e III.
É verdadeira apenas a afirmação III.
É verdadeira apenas a afirmação I.
São verdadeiras as afirmações II e III.
Sua resposta está correta.
Considere o grafo G dado na figura. Então é correto afirmar que:
 
Escolha uma opção:
G é um grafo regular.
G é um grafo direcionado.
G é um grafo completo.
G é um grafo completo.
G é um grafo misto.
Sua resposta está correta.
28/10/2022 11:42 Questionário: Revisão da tentativa
https://cursos.poca.ufscar.br/mod/quiz/review.php?attempt=635500&cmid=4171 5/8
Questão 7
Correto
Atingiu 1,00 de 1,00
Questão 8
Correto
Atingiu 1,00 de 1,00
Considere o grafo dado na figura, e indique qual das afirmações é verdadeira.
 
Escolha uma opção:
O vértice tem grau 4.
O vértice tem grau 4.
O vértice tem grau 4.
O vértice tem grau 4.
O vértice tem grau 4.
v4
v3
v2
v5
v1
Sua resposta está correta.
Identifique qual das alternativas apresenta o Algoritmo utilizado para encontrar Árvores geradoras mínimas:
Escolha uma opção:
Algoritmo de Euler.
Algoritmo do carteiro Chinês.
Algoritmo de Kruskal.
Algoritmo Hamiltoniano.
Sua resposta está correta.
28/10/2022 11:42 Questionário: Revisão da tentativa
https://cursos.poca.ufscar.br/mod/quiz/review.php?attempt=635500&cmid=4171 6/8
Questão 9
Correto
Atingiu 1,00 de 1,00
Questão 10
Correto
Atingiu 1,00 de 1,00
Considere o grafo dado na figura, e indique qual das afirmações é verdadeira.
Escolha uma opção:
O grafo é conexo.
O grafo é regular.
O grafo é completo.
O grafo é desconexo.
Sua resposta está correta.
Observe o grafo G dado na figura. Então podemos afirmar que:
 
Escolha uma opção:
G é um grafo Hamiltoniano.
G é um grafo Eureliano.
G possui um ciclo.
G é uma árvore.
Sua resposta está correta.
28/10/2022 11:42 Questionário: Revisão da tentativa
https://cursos.poca.ufscar.br/mod/quiz/review.php?attempt=635500&cmid=4171 7/8
28/10/2022 11:42 Questionário: Revisão da tentativa
https://cursos.poca.ufscar.br/mod/quiz/review.php?attempt=635500&cmid=4171 8/8
Atividade anterior
◄ Unidade 4 - Problemas Cotidianos
Seguir para...
Próxima atividade
Pesquisa de Satisfação ►
Manter contato
Secretaria Geral de Educação a Distância
 http://www.sead.ufscar.br
 contato@poca.ufscar.br
 Resumo de retenção de dados
 Obter o aplicativo para dispositivos móveis
https://cursos.poca.ufscar.br/mod/page/view.php?id=4206&forceview=1
https://cursos.poca.ufscar.br/mod/feedback/view.php?id=4173&forceview=1
http://www.sead.ufscar.br/
mailto:contato@poca.ufscar.br
https://cursos.poca.ufscar.br/admin/tool/dataprivacy/summary.php
https://download.moodle.org/mobile?version=2021051708&lang=pt_br&iosappid=633359593&androidappid=com.moodle.moodlemobile