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

Uma árvore tem 24 vértices. Quantas arestas |E| ela tem?

|V| = 24
|E| =
2.Fácil

Quantas arestas |E| tem o grafo bipartido completo K6,5?

K6,5
|E| =
3.Média

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

|V| = 10|E| = 17
k =
4.Média
ABCDEFGCircuito 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| = 7|E| = 7
  1. 1Circuito euleriano
  2. 2Caminho euleriano, sem circuito
  3. 3nenhuma das duas
5.Difícil
81115431214471563ABCDEFG

O algoritmo de Dijkstra parte de A. Clique no vértice que é fixado (tornado permanente) na rodada 4; o próprio A é a rodada 1.

início: Arodada 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
6.Difícil
149146191317853ABCDEFG

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 4.

início: Ck = 4
  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 GB
  10. 10aresta GC
  11. 11aresta GD

Gabarito

  1. 1. |E| = 23
  2. 2. |E| = 30
  3. 3. k = 8
  4. 4. nenhuma das duas
  5. 5. D
  6. 6. aresta GD

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