ejercicios grafos digrafos as

10
Ejercicios de Grafos y Dígrafos Universidad Fermín Toro Ingeniería de Computación Cátedra: Estructuras Discretas II Participante: Asisclo Serrano

Upload: asisclos

Post on 05-Aug-2015

383 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Ejercicios Grafos digrafos AS

Ingeniería y Sociedad

Ejercicios de Grafos y Dígrafos

Universidad Fermín ToroIngeniería de Computación

Cátedra: Estructuras Discretas II

Participante: Asisclo Serrano

Page 2: Ejercicios Grafos digrafos AS

Estructuras Discretas II

a) Matriz de adyacencia

v4 v5 v6

v7

v8

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

1) Grafo

Page 3: Ejercicios Grafos digrafos AS

Estructuras Discretas II

b) Matriz de incidenciaV1 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

c) Es conexo, ya que se cumple que para cada par de vértice se encuentran conectados.

d) Es simple, ya que ningún vértice tiene lazo y para cada par no se repiten las aristas.

e) No es regular, ya que sus vértice tienen grados diferentes.

f) No es Completo, ya que existen par de vértices distintos que no son unidos por la misma arista.

Page 4: Ejercicios Grafos digrafos AS

Estructuras Discretas II

g) Cadena Simple no elemental de Grado 6

C= [v1,a1,v2,a8,v5,a13,v3,a12,v7,a18,v8,a9,v2]

v1 v2a1

v5

a8

a13a12

v7

v8

a18

a9

v3

h) Ciclo no simple de grado 5

v7

v4

v1

v3

a15

a4

a2

a11

C= [v7,a15,v4,a4,v1,a2,v3,a11,v4,a15,v7]

Page 5: Ejercicios Grafos digrafos AS

Estructuras Discretas II

i) Árbol generador aplicandoEl algoritmo constructor

v4

v1

v7

v3

v5

v2

v6

v8

j) Subgrafo parcial

v1

v7

v3

v5

v2

v6

v8

v4

a2 a3

a15a17

a19a20

k) No es Euleriano, ya que no se encontró camino donde no se repitan aristas

Page 6: Ejercicios Grafos digrafos AS

Estructuras Discretas II

k) Grafo Hamiltoneano

v4

v1

v7

v3

v5

v2

v6

v8

a1

a3a6

a15 a17

a16

a20

Page 7: Ejercicios Grafos digrafos AS

Estructuras Discretas II

2) Dígrafo

a) Matriz de conexión

V1 V2 V3 V4 V5 V6V1 0 1 1 0 1 0V2 0 0 1 1 0 1V3 0 0 0 1 1 0V4 1 0 0 0 0 1V5 0 1 0 1 0 1V6 0 0 0 0 1 0

b) No es simple, ya que contiene aristas paralelas V5, V6

Page 8: Ejercicios Grafos digrafos AS

Estructuras Discretas II

c) Cadena no simple no Elemental de grado 5

a6

v1

v5

v4

v6

a12a11

a13

a14

C= [v1,a6,v5,a11,v4,a12,v6,a14,v5,a13,v6]

d) Ciclo Simple

v5

v4

v6

a12a11

a14

C= [v5,a11,v4,a12,v6,a14,v5]

Page 9: Ejercicios Grafos digrafos AS

Estructuras Discretas II

e) Demostrar si es fuertemente conexo utilizando matriz de accesibilidad

V1 V2 V3 V4 V5 V6V1 0 1 1 0 1 0V2 0 0 1 1 0 1V3 0 0 0 1 1 0V4 1 0 0 0 0 1V5 0 1 0 1 0 1V6 0 0 0 0 1 0

Ma(D)=

M2(D)=

V1 V2 V3 V4 V5 V6V1 0 0 1 1 1 1V2 1 0 0 1 1 1V3 1 1 0 1 0 1V4 0 1 1 0 1 0V5 1 0 1 1 1 1V6 0 1 0 1 0 1

M3(D)=

V1 V2 V3 V4 V5 V6V1 1 1 1 1 1 1V2 1 1 1 1 1 1V3 1 1 1 0 1 1V4 0 1 1 1 1 1V5 0 1 1 1 1 1V6 1 0 1 1 0 1

M4(D)=

V1 V2 V3 V4 V5 V6V1 1 1 1 1 1 1V2 1 0 1 1 1 1V3 0 1 1 1 1 1V4 1 1 0 1 1 1V5 1 1 1 1 1 1V6 1 1 1 1 0 1

M5(D)= Acc(D)=bin

V1 V2 V3 V4 V5 V6V1 1 1 1 1 1 1V2 1 1 1 1 1 1V3 1 1 1 1 1 1V4 1 1 1 1 1 1V5 1 1 1 1 1 1V6 1 0 1 1 0 1

V1 V2 V3 V4 V5 V6V1 3 4 5 4 5 4V2 4 2 5 5 5 5V3 3 4 3 4 4 4V4 4 4 3 5 4 4V5 3 4 4 5 4 5V6 3 3 3 4 1 4

Acc(D)=bin

V1 V2 V3 V4 V5 V6V1 1 1 1 1 1 1V2 1 1 1 1 1 1V3 1 1 1 1 1 1V4 1 1 1 1 1 1V5 1 1 1 1 1 1V6 1 1 1 1 1 1

Componentes con 0 quedan como 0

Componentes diferentes de 0 quedan como 1

Dígrafofuertemente conexo

Page 10: Ejercicios Grafos digrafos AS

Estructuras Discretas II

f) Distancia de v2 a los demás vértices utilizando algoritmo de Dijkstra

[0,](0)[2,2](1)

[3,2](1)

[3,2](1)

[3,2](1)

[4,2](1)

2

34

33