ejercicios grafos digrafos as
TRANSCRIPT
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
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
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.
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]
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
Estructuras Discretas II
k) Grafo Hamiltoneano
v4
v1
v7
v3
v5
v2
v6
v8
a1
a3a6
a15 a17
a16
a20
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
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]
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
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