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

Um grafo simples tem 5 vértices com graus 4, 2, 2, 2, 2. Quantas arestas |E| ele tem?

deg: 4, 2, 2, 2, 2
|E| =
2.Fácil

Quantas arestas |E| tem o grafo bipartido completo K3,4?

K3,4
|E| =
3.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
4.Média

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

4 × deg 34 × deg 5
L =
5.Difícil
39713821015418ABCDEFG

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

início: Bk = 3
  1. 1aresta AB
  2. 2aresta AC
  3. 3aresta BC
  4. 4aresta DE
  5. 5aresta DF
  6. 6aresta EF
  7. 7aresta GB
  8. 8aresta GC
  9. 9aresta GD
  10. 10aresta GE
6.Difícil
ABCDE

Quantos passeios fechados de comprimento 2 começam e terminam em E? Um passeio pode repetir vértices e arestas. Chame o número de N.

M = matriz de adjacênciaL = 2
N =

Gabarito

  1. 1. |E| = 6
  2. 2. |E| = 12
  3. 3. Caminho euleriano, sem circuito
  4. 4. L = 18
  5. 5. aresta GB
  6. 6. N = 3

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