EJERCICIOS

EJERCICIO 1:

Encontrar los posibles caminos empezando de la ‘a’ y terminando en la ‘e’ en donde la longitud de todo el trayecto sea el menor.

RESPUESTA:

         Trayectoria:                     Longitud:

1.-     a, b, c, d, e                            21

2.-     a, b, d, c, e                            28

3.-     a, c, b, d, e                            24

4.-     a, c, d, b, e                            26

5.-     a, d, b, c, e                            27

6.-     a, d, c, b, e                            22

EJERCICIO 2:

En un torneo, el Nieve venció a los Faisanes una vez, el Rascacielos venció al Tuna, el Nieve venció al Rascacielos dos veces, los Faisanes vencieron al Rascacielos una vez. En los ejercicios 1 al 4, use gráfica para modelar el torneo. Los equipos son los vértices. Describa el tipo de gráfica usada (no dirigida, dirigida o simple).

a) Hay una arista entre los equipos si los equipos jugaron.

b) Hay una arista entre los equipos para cada juego jugado.

c) Hay una arista del equipo ti al tj si ti venció al tj al menos una vez.

d) Hay una arista del equipo ti al equipo tj por cada victoria de ti sobre tj

RESPUESTA:

a)  

      Es un gráfica simple

      b)

      Es una gráfica no dirigida

      c)

      Es una gráfica dirigida

      d)

      Es un gráfica dirigida

EJERCICIO 3:

Determinar un circuito de Euler en el siguiente grafo.

 Paso 1:

a, c

Paso 2:

a, c, b

Paso 3:

a, c, b, e

Paso 4:

a, c, b, e, c

Paso 5:

a, c, b, e, c, f

Paso 6:

a, c, b, e, c, f, e

Paso 7:

a, c, b, e, c, f, e, d

Paso 8:

a, c, b, e, c, f, e, d, b

Paso 9:

a, c, b, e, c, f, e, d, b, a

EJERCICIO 4:

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

RESPUESTA:

EJERCICIO 5:

Determinar el siguiente grafo.

a) ¿Tiene un camino de Euler?

b) ¿Tiene un circuito de Euler?

c) ¿Tiene un circuito de Hamilton?

d) Obtener:

     - El conjunto de vértices (V)

     - Conjunto de aristas (A)

     - Conjunto de lazos (L)

     - Conjunto de lazos paralelos (P)

e) 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}