ejercicio-algoritmo circuito de hamilton

EJERCICIO 4

Determinar, si es posible, un circuito de Hamilton en el siguiente grafo.

RESPUESTA:

V = {v1, v2, v3, v4, v5}

E = {(v1, v1, (v1, v3), (v2, v3), (v2, v4), (v2, v5), (v3, v4), (v4, v5), (v5, v1)}

Matriz De Adyacencia:

n = cantidad de vértices

matriz = n*n               matriz = 5*5 = 25

EJEMPLO

EJERCICIO
5

Determinar el siguiente grafo.

¿Tiene un camino de Euler?

¿Tiene un circuito de Euler?

¿Tiene un circuito de Hamilton?

Obtener:

     El conjunto de vértices (V)

     Conjunto de aristas (A)

     Conjunto de lazos (L)

     Conjunto de lazos paralelos (P)

Obtener la matriz de adyacencia

RESPUESTA:

a) No tiene camino de Euler porque un vértice tiene 3 ramas impares, y por lo tanto, no puede regresar por una arista para ir pasando por cada una.

b) No tiene circuito de Euler porque hay que pasar varias veces por un vértice, y el circuito de Euler dice que el ciclo debe recorrer todos los vértices pasando por todos los lados solamente una vez.

c) No tiene circuito de Hamilton porque pasaría por un vértice varias veces.

d)
- El conjunto de vértices (V)

V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

- Conjunto de aristas (A)

A = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, ñ, o, p, q}

- Conjunto de lazos (L)

L = {f, p}

- Conjunto de lazos paralelos (P)

P = {q, e}

e) Obtener la matriz de adyacencia:

n = 10

matriz = 10*10 = 100

A = {0 1 1 0 1 1 0 0 0 0}

       {1 0 0 0 0 1 0 0 0 0}

       {1 0 1 0 0 0 0 1 0 0}

       {0 0 0 0 0 0 0 1 0 1}

       {1 0 0 0 0 1 0 1 0 0}

       {1 1 0 0 1 0 1 0 0 0}

       {0 0 0 0 0 1 0 0 1 1}

       {0 0 1 1 1 0 0 0 1 0}

       {0 0 0 0 0 0 1 1 0 1}

       {0 0 0 1 0 0 1 0 1 1}