estructura grafos y digrafos

República Bolivariana de Venezuela Ministerio del Poder Popular para la Educación Superior

Vicerrectorado académico Escuela de computación

Alejandro Fernandez C.I. 24400634

SAIA A – 20/11/2015

Grafos y Dígrafos

EJERCICIOS PROPU EST O S

Dado el siguiente grafo, encontrar:

a) Matriz de adyancencia b) Matriz de incidencia c) Es conexo?. Justifique su respuesta d) Es simple?. Justifique su respuesta e) Es regular?. Justifique su respuesta

f) Es completo? Justifique su respuesta g) Una cadena simple no elemental de grado 6 h)

Un ciclo no simple de grado 5 i) Arbol generador aplicando el algoritmo constructor j) Subgrafo parcial k) Demostrar si es euleriano aplicando el algoritmo de Fleury l) Demostrar si es hamiltoniano

v1 a1 v2 a2 v3 a3

a5 a6 a7 a8 a9 a10 a4

a12

a11 a13

v4 v5 a14

a16 v6

a15 a19 a17

v8

a18 v7

a)

a20

V V1 V2 V3 V4 V5 V6 V7 V8

V1 0 1 1 1 0 0 1 1

V2 1 0 1 0 1 1 0 1

V3 1 1 0 1 1 1 1 0

V4 1 0 1 0 1 0 1 0

V5 0 1 1 1 0 1 1 1

V6 0 1 1 0 1 0 0 1

V7 1 0 1 1 1 0 0 1

V8 1 1 0 0 1 1 1 0

b)

c) Es conexo ya que todos sus vértices están conectados entre sí. d) Es simple porque entre cada vértice no hay más de una arista.

e) Es regular ya que los vértices suman un grado total (r) que se le denominaría Grafo regular de grado regular (r).

f) Es completo ya que tiene exactamente una arista entre cada par de vértices. g) C1={V1,a5,v7,a17,v5,a19,v8,a9,v2,a8,v5,a13,v3} Gr(C1) = 6

h) C2={v1,a4,v4,a15,v7,a17,v5,a14,v4,a4,v1} i) Paso 1: Seleccionar v4, H1= [V4]

Paso 2: Seleccionar arista 11, H2 = [V4,V3] V3

A11

V4

Paso 3: Seleccionar V1, H3 [V4,V3.V1] Y arista 2

V-A V1 V2 V3 V4 V5 V6 V7 V8 A1 1 1 0 0 0 0 0 0 A2 1 0 1 0 0 0 0 0 A3 0 1 1 0 0 0 0 0 A4 1 0 0 1 0 0 0 0 A5 1 0 0 0 0 0 1 0 A6 1 0 0 0 0 0 0 1 A7 0 0 1 0 0 1 0 0 A8 0 1 0 0 1 0 0 0 A9 0 1 0 0 0 0 0 1

A10 0 1 0 0 0 1 0 0 A11 0 0 1 1 0 0 0 0 A12 0 0 1 0 0 0 1 0 A13 0 0 1 0 1 0 0 0 A14 0 0 0 1 1 0 0 0 A15 0 0 0 1 0 0 1 0 A16 0 0 0 0 1 1 0 0 A17 0 0 0 0 1 0 1 0 A18 0 0 0 0 0 0 1 1 A19 0 0 0 0 1 0 0 1 A20 0 0 0 0 0 1 0 1

V1 A1

V3 A11

V4

Paso 4: Selecciono v2, arista 1 H4=[V4,V3,V2,V1] V2

A1 V1 A2

V3 A11

V4

Paso 5: Seleccionar arista 7, V6 H=[V4,V3,V1,V5,V6] V2

A1

V1 A2 A7 V3 V6

A11 V4

Paso 6: Seleccionar arista 20, y V8 H=[V4,V3,V1,V2,V6,V8] V2 A1

A2 A7 V1 V6 V3

A20 V4 A11 V8

Paso 7: Seleccionar arista 19 y V5 H=[V4,V3,V1,V2,V6,V8,V5]

V2 A1

A2 a7 V1 v3 v6

A11 v5 a20 V4 a14 v8

Paso 8: Seleccionar arista 12 y V7 H={v4,v3,v2,v1,v6,v8,v5,v7}

V2 A1

A2 V3 a7 v6 V1 A11 V5 a20

V4 a12 A14

V7 v8

Árbol Generador

j) v1 a1 v2

a4 v3 a10 v4 v6 a13

a15 v5 a19 v8

V7

l) C=[v1,a1,v2,a10,v6,a20,v8,a18,v7,a15,v4,a14,v5,a13,v3,a2,v1] a1

v1 v2 a10

a2 v6 v8

a13 v5 a20

a14 v7 v4 v8

a15 a18

Dígrafo

a) Encontrar matriz de conexión

V V1 V2 V3 V4 V5 V6

V1 0 1 1 0 1 0

V2 0 0 1 1 0 1

V3 0 0 0 1 1 0

V4 1 0 0 0 0 1

V5 0 1 0 1 0 1

V6 0 0 0 0 1 0

b) Es simple?. Justifique su respuesta

Es simple porque en el dígrafo no existen lazos ni arcos paralelos

c) Encontrar una cadena no simple no elemental de grado 5 C=[V2,A4,V6,A14,V5,A13,V6,A14,V5,A11,V4,A5,V1]

d) Encontrar un ciclo simple C=[V1,A1,V2,A3,V4,A9,V1

e) Demostrar si es fuertemente conexo util izando la matriz de accesibilidad

M=

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 1 0 1

0 0 0 0 1 0

M^2=

0 1 1 1 1 1

1 0 0 1 1 1

1 1 0 1 0 1

0 1 1 0 1 0

0 1 0 1 0 1

M^3=

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 0 1 1 1 1

M^4=

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

f) Encontrar la distancia de v2 a los demás vértices util izando el algoritmo de Dijkstra

Pasos Vertices Datos a desarrolar

Calculo de di+l Selección v*l+l

0 Vo=[v2] Vo*=v2

Do[vo*]=0 Do[V1]= infinito

Do[V2]= infinito Do[V3]= infinito Do[V4]= infinito Do[V5]= infinito

D1[V1]= infinito

D1[V3]=3 D1[V4]=4

D1[V5]= infinito D1[V6]=3

VI*=V3

1 V1=[v2,v1] VI*=V3

D1[vl*]=3 D1[v4]= 4

D1[v5]= infiito D1[v6]= 3

D2[V1]= infinito

D2[V4]=4 D2[V5]=7

D2[V6]= infinito

V2*=V4

2 V4=[v2,v3,v2*] V2*=V4 D2[V1]= infinito D2[V4]= infinito D2[V6]= infinito

D2[V2*]=4

D3[V1]= 7 D3[V5]= infinito

D3[V6]=6

V*3=6

3 V3=[v2,v3,v4,v3*] V3*=V6 D3[V3*]=6 D3[V1]=7

D3[V5]= infinito

D3[V1]= infinito D3[V5]= 10

V*5= V1

4 V4=[v2,v3,v4,v6,vl] V*4=V5 D3[V4*]=10

D3[V1]= infinito

D4[v1]=13 V*5=V1

5 V5=[v2,v3,v4,v6,v5]