EJERCICIOS RESUELTOS DE GRAFOS Y DÍGRAFOS

Bachiller: José M. Meléndez

Carrillo

Estructuras Discretas II - Edecio

Freitez - SAIA A

DADO EL SIGUIENTE GRAFO:

1- MATRIZ DE ADYACENCIA

La matriz de adyacencia es una matriz cuadrada A, en la que sus entradas AIJ pertenecen al número de aristas que van desde VI hasta su vértice VJ.

0 1 1 1 0 0 1 1

1 0 1 0 1 1 0 1

1 1 0 1 1 1 1 0

1 0 1 0 1 0 1 0

0 1 1 1 0 1 1 1

0 1 1 0 1 0 0 1

1 0 1 1 1 0 0 1

1 1 0 0 1 1 1 0

Ma=

2- MATRIZ DE INCIDENCIA

La matriz de incidencia es una matriz M, en la que sus entradas MIJ son el número de veces que la arista J coincide en el vértice I.

1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0

0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0

0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1

0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0

0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1

M=

3- ¿Es conexo? El grafo dado es conexo debido a que existe una cadena entre cualquier par de vértices.

4- ¿Es simple? El grafo es simple ya que no tiene ciclos y no posee mas de una arista uniendo un par de vértices, se puede observar que para cada par de vértices que están unidos dicha unión es a través de una sola arista.

5- ¿Es regular? El grafo estudiado no es regular debido a que el grado de incidencia del vértice V1=5 y el del vértice V3, por lo tanto para que un grafo sea regular todos los vértices deberían de tener el mismo grado de incidencia.

6- ¿Es completo? Se puede observar que el grafo es completo porque el vértice V1 no esta conectado al vértice V5 y para que sea completo cada vértice debe estar conectado a cualquier otro vértice distinto.

7- Una cadena simple no elemental de grado 6.

Una simple no elemental de grado 6 (se repite el vértice V4) es:

V6 a20 V8 a19 V4 a17 V7 a15 V5 A11 V3 a13 V4.

8- Un ciclo no simple de grado 5.

Un ciclo no simple de grado 5 (se repite la arista a11) es: V3 a11 V5 a15 V7 a17 V4 a13 V3 a11 V5.

9 -ÁRB OL GENERADOR APLICANDO EL ALGORITMO CONSTRUCTOR:

Paso 1: Elegir S1=V1, y se coloca H1= {V1}

Paso 2: Se elige a a4 que conecta a V1 con V4 y se coloca

H2= {V1,V4}

Paso 3: Se elige la arista a15 que conecta V4 con V7 y se coloca

H3= {V1, V4, V7}.

Paso 4: Se elige la arista a17 que conecta V7 con V5 y se coloca

H4= {V1, V4, V7, V5}.

Paso 5: Se elige la arista a19 que conecta V5 con V8 y se coloca

H5= {V1, V4, V7, V5, V8}.

Paso 6: Se elige la arista a20 que conecta V8 con V6 y se coloca

H6= {V1, V4, V7, V5, V8, V6}.

Paso 7: Se elige la arista a10 que conecta V6 con V2 y se coloca

H7= {V1, V4, V7, V5, V8, V6, V2}.

Paso 8: Se elige la arista a3 que conecta V2 con V3 y se coloca

H7= {V1, V4, V7, V5, V8, V6, V2, V3}.

Con V= {V1, V4, V3, V2} y A= {a4, a2, a11, a3, a1}

10- SUBGRAFO PARCIAL.

11- Demostrar si es Euleriano aplicando el algoritmo de Fleury.

El grafo no es euleriano debido a que no es posible la construcción de un ciclo euleriano, ya que no todos los vértices tienen grado par.

12- Demostrar si es Hamiltoniano.

El numero de vértices que posee el grafo es8, el grado de V1 es Gr(V1) ≥ 4, el de V2 es Gr(V2) ≥ 4, el de V8 es Gr(V8) ≥ 4, además de ser un grafo simple, por lo tanto de es grafo es Hamiltoniano. En la siguiente figura podremos ver un ciclo Hamiltoniano..

DADO EL SIGUIENTE GRAFO:

1-MATRIZ DE CONEXIÓN

0 1 1 0 1 0

0 0 1 1 0 1

0 0 0 1 1 0

1 0 0 0 0 1

0 1 0 0 0 1

0 0 0 0 1 0

Ma=

2- ¿Es simple?

Se puede decir que el dígrafo es simple ya que no posee ni arcos ni lazos paralelos.

3- Una cadena no simple no elemental de grado 5.

Una cadena no simple elemental de grado 5 (se repite el vértice V4) es: V4 a3 V2 a2 V3 a7 V5 a11 V4 a12 V6.

4- Un ciclo simple.

C=V1 a6 V5 a11 V4 a9 V1

5 - D E M O S T R A R S I E S F U E RT E M E N T E C O N E XO U T I L I Z A N D O L A M AT R I Z D E

A C C E S I B I L I D A D.

0 1 1 0 1 0

0 0 1 1 0 1

0 0 0 1 1 0

1 0 0 0 0 1

0 1 0 0 0 1

0 0 0 0 1 0

MC=

0 1 1 1 1 1

1 0 0 1 1 0

1 1 1 1 0 1

0 1 1 0 1 0

1 0 1 1 0 1

0 1 0 1 0 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

0 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

MC2=

MC3=

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

MC4=

6 -LA DISTANCIA DE V2 A LOS DEMÁS VÉRTICES UTIL IZANDO EL ALGORITMO

DE DI JKSTRA.

Paso1: D0 (V2) = 0; U0= V2

Paso2:D1 (V1) = min (Inf, Inf) = InfD1 (V3) = min (Inf, 3) = 3D1 (V4) = min (Inf, 4) = 4D1 (V5) = min (Inf, Inf) = InfD1 (V6) = min (Inf, 3) = 3

U1= V3; D1 (U1) = 3

Paso 3: D2 (V1) = min (Inf, 3 + Inf) = InfD2 (V4) = min (4, 3 + 1) = 4D2 (V5) = min (Inf, 3 + 4) = 7D2 (V6) = min (Inf, 3) =3

U2= V6; D2 (U2) = 3

Paso 4: D3 (V1) = min (Inf, 3 + Inf) =InfD3 (V4) = min (4, 3 + Inf) =InfD3 (V5) = min (7, 3 + 3) =6

U3= V4; D3 (U3) = 4

Paso 5: D4 (V1) = min (Inf, 4 + 4) =8D4 (V5) = min (6, 4 + Inf) =6

U4= V5; D4 (U4) = 6

Paso 6: D5 (V1) = min (8, 6 + Inf) =8

U5= V1; D5 (V1) = 8 Entonces: D(V2, V1)= 8, D(V2, V2)= 0, D(V2, V3)= 3, D(V2, V4)= 4, D(V2,V5)= 6 y D(V2,V6)=3.