ejercicios resueltos

8
REPÚBLICA BOLIVARIANA DE VENEZUELA MINISTERIO DEL PODER SUPERIOR UNIVERSITARIO UNIVERSIDAD FERMIN TORO CABUDARE ESTADO LARA María F Aponte G. C.I: 24.565.531 Estructuras Discretas II Saia EJERCICIOS PROPUESTOS Cabudare 2015

Upload: maria-fernanda-aponte-gutierrez

Post on 14-Apr-2017

226 views

Category:

Education


0 download

TRANSCRIPT

Page 1: Ejercicios Resueltos

REPÚBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER SUPERIOR UNIVERSITARIO

UNIVERSIDAD FERMIN TORO

CABUDARE ESTADO LARA

María F Aponte G. C.I: 24.565.531

Estructuras Discretas II

Saia

EJERCICIOS PROPUESTOS

Cabudare 2015

Page 2: Ejercicios Resueltos

Dado el siguiente grafo, encontrar:

a) Matriz de adyancencia

0 1 1 0 0 1 1 1

1 0 1 1 1 0 0 1

1 1 0 1 1 1 1 0

0 1 1 0 1 0 0 1

0 1 1 1 0 1 1 1

1 0 1 0 1 0 1 0

1 0 1 0 1 1 0 1

1 1 0 1 1 0 1 0

Ma =

Page 3: Ejercicios Resueltos

b) Matriz de incidencia

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

c) Es conexo?. Justifique su respuesta

Es Conexo, porque cumple para los par de vértices {U,V} se tiene U y V

están conectados.

d) Es simple?. Justifique su respuesta

Es simple porque no posee lazo

e) Es regular?. Justifique su respuesta

No es regular porque los vértices tienen el mismo grado

f) Es completo? Justifique su respuesta

No es complejo ya que es un grafo simple que tiene exactamente una

arista entre cada par de vértices distintos.

g) Una cadena simple no elemental de grado 6

D= [V7, a18, V8, a9, V2, a8, V5, a13, V3, a12, V7, a15, V6]

Mi =

Page 4: Ejercicios Resueltos

h) Un ciclo no simple de grado 5

D= [V1, a4, V6, a11, V3, a13, V5, a14, V6, a4, V1]

i) Árbol generador aplicando el algoritmo constructor

H1 = {1}

H2 = {V1, V7}

H3 = {V1, V7, V3}

H4 = {V1, V7, V3, V2}

H5 = {V1, V7, V3, V2, V4}

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

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

Page 5: Ejercicios Resueltos

j) Subgrafo parcial

k) Demostrar si es euleriano aplicando el algoritmo de Fleury

El grafo no es euleriano, ya que aplicando el algoritmo de Fleury y

partiendo desde cualquier vértice no es posible obtener un ciclo euleriano.

l) Demostrar si es hamiltoniano

Si es hamiltoniano:

D = [V1, a1, V2, a3, V3, a11, V6, a14, V5, a16, V4, a20, V8, a18, V7, a5, V1]

Page 6: Ejercicios Resueltos

Dado el siguiente dígrafo

a) Encontrar matriz de conexión

0 1 1 0 1 0

0 0 1 1 1 0

0 0 0 1 1 0

1 0 0 0 0 1

0 1 0 1 0 1

0 0 0 0 1 0

b) Es simple?. Justifique su respuesta

Es simple porque debido a que no existen lazos en ningún vértice y

tampoco arcos paralelos

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

A = [V1, a1, V2, a2, V3, a8, V4, a9, V1, a1, V2]

Md =

Page 7: Ejercicios Resueltos

d) Encontrar un ciclo simple

A = [V6, a14, V5, a11, V4, a12, V6]

e) Demostrar si es fuertemente conexo utilizando la matriz de

accesibilidad

4 5 5 4 5 4

4 5 4 5 5 4

4 4 4 5 4 4

3 4 4 4 4 4

4 4 4 5 5 5

3 3 3 4 4 5

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 utilizando el

algoritmo de Dijkstra

Md=

M2 =

0 1 1 0 1 0

0 0 1 1 1 0

0 0 0 1 1 0

1 0 0 0 0 1

0 1 0 1 0 1

0 0 0 0 1 0

0 1 1 1 1 1

1 1 0 1 1 1

1 1 0 1 0 1

0 1 1 0 1 0

1 0 1 1 1 1

0 1 0 1 0 1

Acc(D)-bin =

Acc(D) =

Page 8: Ejercicios Resueltos

M3 =

M4 =

M5 =

M1 =

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

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

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

1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1