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
AABBCCDDEEFF010000101010010000000011010100000100

A matriz de adjacência de um grafo simples não direcionado é mostrada. Quantas arestas |E| o grafo tem?

|E| =
2.Fácil

Um grafo simples tem 7 vértices com graus 3, 2, 2, 2, 2, 2, 1. Quantas arestas |E| ele tem?

deg: 3, 2, 2, 2, 2, 2, 1
|E| =
3.Média

Uma árvore tem 3 vértices de grau 3, 2 vértices de grau 4, 4 vértices de grau 5, e todos os seus outros vértices são folhas (grau 1). Quantas folhas L ela tem?

3 × deg 32 × deg 44 × deg 5
L =
4.Média
ABCDEFCircuito eulerianoCaminho euleriano, sem circuitonenhuma das duas

O grafo conexo tem um circuito euleriano, um caminho euleriano que não é circuito, ou nenhum dos dois? Clique na sua resposta.

|V| = 6|E| = 6
  1. 1Circuito euleriano
  2. 2Caminho euleriano, sem circuito
  3. 3nenhuma das duas
5.Difícil
922114397ABCDEF

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) =
6.Difícil
19145148172091511ABCDEFG

O algoritmo de Kruskal constrói uma árvore geradora mínima. Clique na aresta que ele acrescenta como aresta de número 5; as arestas descartadas não contam.

k = 5
  1. 1aresta AB
  2. 2aresta AC
  3. 3aresta BC
  4. 4aresta BD
  5. 5aresta CE
  6. 6aresta DE
  7. 7aresta DF
  8. 8aresta EF
  9. 9aresta GC
  10. 10aresta GD
  11. 11aresta GE

Gabarito

  1. 1. |E| = 5
  2. 2. |E| = 7
  3. 3. L = 21
  4. 4. Caminho euleriano, sem circuito
  5. 5. d(F) = 14
  6. 6. aresta GC

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