UNIVERSIDAD FERMÍN TORO

ESCUELA DE INGENIERIA

ALUMNO:

Benítez Carlos C.I: 14.585.103

Sección: SAIA-A

Profesora: Edicio Freitez

DADO EL SIGUIENTE GRAFO

A) Determinar MATRIZ DE ADYACENCIA

V1 V2 V3 V4 V5 V6 V7 V8

V1 0 1 1 1 1 0 1 0

V2 1 0 1 0 0 1 1 1

V3 1 1 0 1 1 1 0 1

V4 1 0 1 0 1 1 0 0

V5 1 0 1 1 0 1 1 0

V6 0 1 1 1 1 0 1 1

V7 1 1 0 0 1 1 0 1

V8 0 1 1 0 0 1 1 0

B) Matriz de Incidencia

C) Es Conexo? Justifique su respuesta.

Se dice Conexo si para cualquier par de vértices de a y b en G existe al menos una

trayectoria (una secuencia de vértices adyacentes que no repita vértices) de a á b.

De acuerdo con la definición, si es conexo ya que, para todo par de vértices se encuentran

conectados o tienen un camino que los una.

D) Es Simple? Justifique su respuesta.

Si es un grafo simple, debido a que se cumple que ningún vértice tiene lazo, además cada

vértice esta unido por una sola arista; pero todos los vértices poseen un grado diferente,

siendo no regular.

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 a18 a19 a20

V1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

V2 1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

V3 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0

V4 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0

V5 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0

V6 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0

V7 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1

V8 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1

E) Es Regular? Justifique su respuesta.

¿Regular?: Es un grafo donde cada vértice tiene el mismo grado o valencia.

Grado de un vértice es: El número de aristas que inciden en el vértice.

No es un grafo regular, ya que hay vértices que tienen grados o valencias diferentes.

F) Es Completo? Justifique su respuesta.

Completo?: Es aquel grafo con N vértices, en las que existe únicamente una arista por

cada par de vértices. No hay aristas paralelas o sub. Grafos.

En conclusión podemos decir que NO es Completo, porque posee aristas paralelas y más de

una arista por cada par de vértices, dando origen a los sub. Grafos.

G) Una cadena simple no elemental de grado 6.

Una cadena simple es una secuencia finita alternada de vértices y aristas, sin repetir aristas,

no elemental indica que puede repetirse los vértices. El grado nos indica la cantidad de

aristas que debe contener la cadena, en esta oportunidad son seis (6).

Ejemplo:

V3= GRADO 6

V6= GRADO 6

H) Un ciclo no simple de grado 5

Ciclo simple es: Es el ciclo que a su vez es una cadena simple.

Ciclo no simple: Es un ciclo que no es una cadena simple.

No se puede demostrar, ya que todas las aristas son distintas del grafo. No

hay cadenas no simples de ningún grado.

I) Árbol generador aplicando el algoritmo constructor.

1er paso: Seleccionar un vértice S1, hacer H1= { S1}

2do paso: Seleccionamos una arista a1 que tenga un extremo en H1 y el otro extremo

en un vértice S2 H1. Hacer H1 { S2}

3er paso: Seleccionamos una arista a2 que tenga un extremo en H2, y el otro extremo

en un vértice S3 H2. Hacer H2 { S3}

Seleccionamos el vértice v1 H1 ={v1}

Seleccionamos la arista a4 H2 = {v1,v4}

A15 H3= {v1,v4, v5}

A12 H4= {v1,v4, v5, v3}

A13 H5= {v1,v4, v5, v3, v6}

A8 H6= {v1,v4, v5, v3, v6, v2}

A10 H7= {v1,v4, v5, v3, v6, v2, v8}

A20 H8= {v1,v4, v5, v3, v6, v2, v8, v7}

Por lo tanto se comprueba que en un árbol dos vértices cualesquiera están unidos por un

único camino, se demuestra con al poseer árbol generador que es un grafo conexo, y que G

es un árbol entonces el número de aristas es igual al número de vértices menos 1.

A = {a4, a15, a12, a3, a8, a10, a20}

V = { v1,v4, v5, v3, v6, v2, v8, v7}

V1

V4

a4

V4

V1

V5

V3

V6

V1

V4

V5

V6

V3 V2

V8

V3

V1

V4

V5

V6

V2

V8

V7

Numero de vértices = 8 -1 =7

Numero de aristas = 7

J) Subgrafo Parcial.

Un subgrafo parcial se obtiene al conservar todos los nodos o vértices de G y se

suprimen algunas aristas.

Tenemos

K) Demostrar si es euleriano aplicando el algoritmo de Fleury

Si el grafo es euleriano a partir de un vértice cualquiera de G se puede construir una cadena

simple de manera que no se repitan las aristas y no se elijan aristas de corte a no ser que no

se encuentre otra alternativa, al haber agotado las aristas decimos que tenemos un tour

euleriano.

Luego de experimentar en repetidas ocasiones el recorrido del grafo sin repetir aristas, no

ha sido posible encontrar un camino euleriano donde no se repitan aristas, por lo tanto no se

cumple que el Grafo sea Euleriano.

V8

V1

V4

V5

V6

V3

V2

V7

a2

a3

a15

a17

a19 a20

I) Demostrar si es Hamiltoniano

Un grafo es hamiltoniano si contiene un ciclo hamiltoniano, en el cual se debe cumplir que

atraviese cada vértice del grafo exactamente una vez.

el ciclo C=[v1, a3, v2, a10, v8, a20, v7, a19, v6, a17, v5, a15, v4, a11, v3, a2, v1]

Notamos que Vo = Vk

DADO EL SIGUIENTE DIGRAFO

a10 V3

V1

V4

V5

V6

V2

V7

a2

a3

a15

a17

a19 a20

V8

a11

2

A) Encontrar matriz de conexión

B) Es Simple? Justifique su respuesta.

Se cumple que el Dígrafo es simple, ya que no tiene lazos y no existen arcos paralelos que

partan de un mismo vértice a otro.

C) Encontrar una cadena no simple no elemental de grado 5

En las cadenas no simples se pueden repetir los arcos durante el recorrido y que sea no

elemental, también nos permite repetir vértices. El grado 5 nos indica el número de arcos

que tendrá nuestra cadena.

T = [v4, 9, v1, 5, v3, 8, v4, 9, v1, 6, v5]

D) Encontrar un ciclo simple.

El ciclo simple inicia y termina con el mismo vértice y en ella no se pueden repetir arcos.

C = [v6, 14, v5, 11, v4, 9, v1, 1, v2, 4, v6]

E) Demostrar si es fuertemente conexo utilizando la matriz de accesibilidad.

Para comprobar que un grafo es conexo podemos realizar los siguientes pasos:

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14

V1 0 0 0 0 0 0 0 0 1 0 0 0 0 0

V2 1 0 0 0 0 0 0 0 0 1 0 0 0 0

V3 0 1 0 0 1 0 0 0 0 0 0 0 0 0

V4 0 0 1 0 0 0 0 1 0 0 1 0 0 0

V5 0 0 0 0 0 1 1 0 0 0 0 0 0 1

V6 0 0 0 1 0 0 0 0 0 0 0 1 1 0

1) Hallar la matriz de adyacencia y se eleva a la enésima potencia.

2) Se calcula la suma de las potencias de A hasta An.

3) Si todos sus elementos son distintos de cero, el grafo es conexo.

Matriz de Adyacencia

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

Elevamos la matriz al cuadrado para encontrar los caminos de tamaño dos (02)

V1 V2 V3 V4 V5 V6

V1 0 0 1 1 1 1

V2 1 0 0 1 1 1

V3 1 1 0 1 0 1

V4 0 1 1 0 1 0

V5 1 0 1 1 1 1

V6 0 1 0 1 0 1

Ma(D)=

M2(D)=

Elevamos la matriz al cubo para encontrar los caminos de tamaño tres (03)

V1 V2 V3 V4 V5 V6

V1 1 1 1 1 1 1

V2 1 1 1 1 1 1

V3 1 1 1 0 1 1

V4 0 1 1 1 1 1

V5 0 1 1 1 1 1

V6 1 0 1 1 0 1

Elevamos la matriz a cuatro para encontrar los caminos de tamaño cuatro (04)

V1 V2 V3 V4 V5 V6

V1 1 1 1 1 1 1

V2 1 0 1 1 1 1

V3 0 1 1 1 1 1

V4 1 1 0 1 1 1

V5 1 1 1 1 1 1

V6 1 1 1 1 0 1

Elevamos la matriz a la cinco para encontrar los caminos de tamaño cinco (05)

V1 V2 V3 V4 V5 V6

V1 1 1 1 1 1 1

V2 1 1 1 1 1 1

V3 1 1 1 1 1 1

V4 1 1 1 1 1 1

V5 1 1 1 1 1 1

V6 1 1 1 1 0 1

M3(D)=

M4(D)=

M5(D)=

Ahora calculamos la Matriz de Accesibilidad

Acc(D) = bin [I6 + M + M2 + M3 + M4 + M5]

V1 V2 V3 V4 V5 V6

V1 3 4 5 4 5 4

V2 4 2 5 5 5 5

V3 3 4 3 4 4 4

V4 4 4 3 5 4 4

V5 3 4 4 5 4 5

V6 3 3 3 4 1 4

Luego transformamos la matriz de la manera siguiente

a) Componente que sea igual a cero (0), permanece como cero (0)

b) Componente diferente de cero (0), convertirla a 1.

V1 V2 V3 V4 V5 V6

V1 1 1 1 1 1 1

V2 1 1 1 1 1 1

V3 1 1 1 1 1 1

V4 1 1 1 1 1 1

V5 1 1 1 1 1 1

V6 1 1 1 1 1 1

Como la matriz Acc(D) no tiene componentes nula se dice entonces según el

colorario 1.2 que el dígrafo es fuertemente conexo.

Acc(D)= bin

Acc(D)= bin

F) Encontrar la distancia V2 a los demás vértices utilizando el algoritmo de

DIJKSTRA

Pasos:

1) Ubicar el vértice de inicio.

2) Luego ubicar los vértices mas cercanos al V2 para estudiarlo, lo que esté

directamente a él.

3) Agregar etiquetas a cada vértice estudiado, la misma se realiza así:

4) Luego colocar la ponderación de la arista + la ponderación de la etiqueta ante rior

que esta directamente al vértice estudiado.

5)Colocara al lado de la etiqueta el numero de iteración que se esta realizando.

6) Luego se estudian las distancias y se escoge la menor, si hay 2 igual se escoge

cualquiera de la dos.