UNIVERSIDAD FERMIN TORO

VICE RECTORADO ACADÉMICO

DEPARTAMENTO DE COMPUTACION

CABUDARE, EDO-LARA.

INTEGRANTE:

Gabriely Peña

CI: 23903149

SECCIÓN: AULA VIRTUAL SAIA

PROF: Edecio Freitez

ASIGNATURA: ESTRUCTURAS DISCRETAS II

EJERCICIOS

PROPUESTOS DE GRAFOS

Solución1:

a) Matriz de adyacencia

V1 V2 V3 V4 V5 V6 V7 V8

V1 0 1 1 0 0 1 1 1

V2 1 0 1 1 1 1 0 0

V3 1 1 0 1 1 0 1 1

Ma(G)= V4 0 1 1 0 1 1 1 1

V5 0 1 1 1 0 1 0 0

V6 0 1 0 1 1 0 1 0

V7 1 0 1 1 0 1 1 1

V8 1 0 1 1 0 0 1 0

b) Matriz de incidencia

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

a5 1 0 0 0 0 0 1 0

a6 1 0 0 0 0 1 0 0

a7 0 0 1 0 1 0 0 0

a8 0 1 0 1 0 0 0 0

a9 0 1 0 0 0 0 0 0

Mi(G)= a10 0 1 0 0 1 0 0 0

a11 0 0 1 0 0 0 0 1

a12 0 0 1 0 0 0 1 0

a13 0 0 1 1 0 0 0 0

a14 0 0 0 1 0 0 0 1

a15 0 0 0 0 0 0 1 1

a16 0 0 0 1 1 0 0 0

a17 0 0 0 1 0 0 1 0

a18 0 0 0 0 0 1 1 0

a19 0 0 0 1 0 1 0 0

a20 0 0 0 0 1 1 0 0

c) Es conexo? Justifique.

Si es conexo ya que, se cumple que para todo par de vértices se tiene que están conectados.

d) Es simple? Justifique.

Si es simple ya que, no tiene lazos y entre cada par de vértices distintos no hay más de una arista.

e) Es regular? Justifique.

No es regular ya que, no todos los vértices tienen el mismo grado.

f) Es completo? Justifique.

No es completo ya que, no tiene exactamente una arista entre cada par de vértices distintos.

g) Una cadena simple no elemental de grado 6

C= {V1, a1, V2, a3, V3, a7, V5, a10, V2, a8, V9, a13, V3

h) Un ciclo no simple de grado 5

C= {V1, a2, V3, a3, V2, a1, V1, a2, V3}

i) Árbol generador aplicando el algoritmo constructor

Paso 1: S1= V1 H1= {V1}

Paso 2: S2= V2 H2= H1 U {V2}= {V1, V2}

Paso 3: S3= V5 H3= H2 U {V5}= {V1, V2, V5}

Paso 4: S4= V6 H4= {V1, V2, V5, V6}

Paso 5: S5= V4 H5= {V1, V2, V5, V6, V4}

Paso 6: S6= V7 H6= {V1, V2, V5, V6, V4, V7}

Paso 7: S7= V8 H7= H6 U S7= {V1, V2, V5, V6, V4, V7, V8}

Paso 8: S8= V3 H7 U S8= {V1, V2, V5, V6, V4, V7, V8, V3} (ARBOL GENERADOR)

j) Subgrafo parcial

V1 V3 V2

V8 V4 V5

V7

V6

k) Demostrar si es euleriano aplicando el algoritmo de Fleury

Paso 1: V1

Paso 2: {V1, a1, V2}

Paso 3: V2 a3 V3

V3 a2 V1

V1 a4 V8

V8 a4 V3

V3 a2 V7

V3 a5 V1

V1 a6 V6

V6 a18 V3

V7 a15 V8

V8 a14 V7

V4 a17 V7

Como no tengo más aristas para otros vértices no es Euleriano.

l) Demostrar que es Hamiltoniano

Como la cantidad n de vértices es igual a 8, y la suma de los grados para cada par de vértices es n-1 o mayor o sea, 7 o más, entonces existe un paseo Hamiltoniano.

Solución 2:

a) Encontrar la matriz de conexión

V1 V2 V3 V4 V5 V6

V1 0 1 1 0 1 0

V2 0 0 1 1 0 1

Mc= 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.

Si es simple ya que, no hay lazos ni arcos paralelos.

c) Encontrar una cadena simple no elemental de grado 5

C= {V1, a1, V2, a2, V3, a8, V4, a9, V1, a1, V2}

d) Encontrar un ciclo simple

C= {V1, a1, V2, a3, V4, a9, V1}