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
ABCDE

Encontre a soma dos graus de todos os vértices do grafo mostrado, Σ deg.

|V| = 5
Σ deg =
2.Fácil

Uma floresta (um grafo sem ciclos) tem 13 vértices e 3 componentes conexas. Quantas arestas |E| ela tem?

|V| = 13c = 3
|E| =
3.Média

Um grafo conexo tem 14 vértices e 21 arestas. Quantas arestas k devem ser removidas para sobrar uma árvore geradora?

|V| = 14|E| = 21
k =
4.Média

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

K8
H =
5.Difícil
2195161361518127ABCDEFG

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

início: Ek = 5
  1. 1aresta AB
  2. 2aresta AC
  3. 3aresta BD
  4. 4aresta CE
  5. 5aresta DE
  6. 6aresta DF
  7. 7aresta EF
  8. 8aresta GC
  9. 9aresta GD
  10. 10aresta GE
6.Difícil
4388121061321ABCDEFG

Use o algoritmo de Dijkstra para encontrar o comprimento d(F) do caminho mais curto de A até F no grafo ponderado.

início: Afim: F
d(F) =

Gabarito

  1. 1. Σ deg = 12
  2. 2. |E| = 10
  3. 3. k = 8
  4. 4. H = 2520
  5. 5. aresta DF
  6. 6. d(F) = 16

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