Exercícios de Grafos

EXERCÍCIO DE GRAFOS

1. Construa um grafo simples conexo, com as seguintes sequências de graus:

a) (1, 1, 2, 3, 3, 4, 4, 6)

b) (3, 3, 3, 3, 3, 5, 5, 5).

2. 2. Para o grafo a seguir, responda:

a) é um grafo simples?

b) é um grafo completo?

c) é um grafo conexo?

d) existem dois caminhos entre os vértices 3 e 6?

e) o grafo possui algum ciclo?

f) o grafo possui algum arco cuja remoção o tornaria um grafo acíclico?

g) o grafo possui algum arco cuja remoção o tornaria desconexo?

3. Escreva a sequência de graus para os grafos a, b e c.

4. Quantos vértices um grafo simples precisa ter para poder ter 100 arestas?

5. É verdadeira a afirmação de que dois grafos isomorfos possuem o mesmo número de vértices e de arestas?

6. É verdadeira a afirmação, que dois grafos isomorfos possuem a mesma sequência de graus em seus vértices? Se dois gragos possuem a mesma sequência de graus, são obrigatoriamente isomorfos?
7. Os grafos G e H descritos a seguir são isomorfos? G = (VG ,EG) VG = {a, b, c, d, e, f, g}

H = (VH,EH) VH = {h, i, j, k, l, m, n} E se trocarmos hk por hn em EH ?

EG = {ab, bc, cd, cf, fe, gf, ga, gb} EH = {hk, nj, jk, lk, lm, li, ij, in}

8. Na figura abaixo, quais dos grafos (a, b ou c) são subgrafos do grafo H?

9. Explique porque é que a sequência ACEDBCA não é um circuito Hamiltoniano para o grafo a seguir. Este grafo admite um circuito Hamiltoniano? Justifique.

10. Para os grafos a seguir, informe quais admitem caminho ou um ciclo Euleriano.

11. Para os grafos a seguir, informe quais admitem caminho ou um ciclo Hamiltoniano.
12. Considere os seguintes dígrafos:

a) Mostre a sequência em que os vértices são visitados na busca em largura e em profundidade a partir do vértice 1;

b) Mostre a classificação das arestas.

13. Mostre uma ordem dos