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
ABCDEF

Exatamente um vértice do grafo tem grau 3. Clique nele.

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
2.Fácil

Um grafo 4-regular tem 7 vértices (todo vértice tem grau 4). Quantas arestas |E| ele tem?

n = 7k = 4
|E| =
3.Média
ABCDECircuito 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| = 5|E| = 6
  1. 1Circuito euleriano
  2. 2Caminho euleriano, sem circuito
  3. 3nenhuma das duas
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
111513911116ABCDEF

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
24181211320637ABCDEFG

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

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

Gabarito

  1. 1. D
  2. 2. |E| = 14
  3. 3. Circuito euleriano
  4. 4. H = 360
  5. 5. d(F) = 23
  6. 6. aresta BD

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