Lista de exercícios de Teoria dos grafos com respostas

Lista de exercícios de Teoria dos grafos grátis para imprimir: 6 exercícios do nível fácil ao nível de prova, com gabarito. Imprima ou salve como PDF.

Nova lista de exercíciosPratique on-line com dicas

Para professores: pode imprimir, copiar e usar em aula gratuitamente. Cada nova folha tem novos valores e o seu próprio gabarito. Agradecemos um link para o ExamProblems na página da sua disciplina.

Nome: ____________________   Data: ____________

1.Fácil
AABBCCDDEEFF011000101010110000000011010101000110

A matriz de adjacência de um grafo simples não direcionado é mostrada. Encontre o grau deg(A) do vértice A.

deg(A) =
2.Fácil

Quantas arestas |E| tem o grafo completo K10?

K10
|E| =
3.Média

Quantos circuitos hamiltonianos diferentes H tem o grafo completo K4? Circuitos que diferem apenas no vértice inicial ou no sentido contam como o mesmo.

K4
H =
4.Média

Quantos circuitos hamiltonianos diferentes H tem o grafo completo K7? Circuitos que diferem apenas no vértice inicial ou no sentido contam como o mesmo.

K7
H =
5.Difícil
1614174861315ABCDEF

Encontre o peso total W de uma árvore geradora mínima do grafo ponderado.

|V| = 6|E| = 8
W =
6.Difícil
172121719813116ABCDEFG

O algoritmo de Prim constrói uma árvore geradora mínima a partir do vértice C. Clique na aresta que ele acrescenta como aresta de número 3.

início: Ck = 3
  1. 1aresta AB
  2. 2aresta BC
  3. 3aresta BD
  4. 4aresta DE
  5. 5aresta DF
  6. 6aresta EF
  7. 7aresta GB
  8. 8aresta GC
  9. 9aresta GD
  10. 10aresta GE

Gabarito

  1. 1. deg(A) = 2
  2. 2. |E| = 45
  3. 3. H = 3
  4. 4. H = 360
  5. 5. W = 47
  6. 6. aresta GE

Soluções completas passo a passo: pratique este tópico em examproblems.com.