UNIVERSIDAD "FERMÍN TORO"

SISTEMA INTERACTIVOS DE
EDUCACIÓN A DISTANCIA. (SAIA)
CABUDARE

Grafos

Autor. Ivismar M. Colmenarez B.

C.I.29778119
Sección. Saia B
Tutor. Edecio Freítez
Dado el siguiente grafo, encontrar:

a) Matriz de adyacencia h) Un ciclo no simple de grado 5

b) Matriz de incidencia i) Arbol generador aplicando el
c) Es conexo?. Justifique su respuesta algoritmo constructor
d) Es simple?. Justifique su respuesta j) Subgrafo parcial
e) Es regular?. Justifique su respuesta k) Demostrar si es euleriano
f) Es completo? Justifique su aplicando el algoritmo de Fleury
respuesta l) Demostrar si es hamiltoniano
g) Una cadena simple no
elemental de grado 6

v1 a1 v2
a2
a3
v3
a7 a8 a9 a10
a5 a6
a4 a12
a11 a13
a16
a14
a15
a19

a17
a20
a18
A)
Repuesta:

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)
Respuesta:

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

v 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
v 1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
2
v 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0
3
v 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0
4
v 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0
5
v 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0
6
v 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1
7
v 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1
8
C) D)
Respuesta: Respuesta:

Conexo: si cada par de vértices está Si, es un grafo simple ya que lo más existe una
conectado por un camino; es decir, si para arista uniendo dos vértices cualesquiera. Esto es
cualquier par de vértices (a, b), existe al equivalente a decir que una arista cualquiera es la
menos un camino posible desde a hacia b. única que une dos vértices específicos.
Un grafo que no es simple se denomina multígrafo.

E) F)
Respuesta: Respuesta:
No, ya que un grafo regular es
un grafo donde cada vértice tiene el mismo No, porque existen uniendo todos los pares
grado o valencia. Un grafo regular con posibles de vértices. Es decir, todo par de
vértices de grado k es llamado grafo k- vértices (a, b) debe tener una arista
regular o grafo regular de grado k. e que los une.

H)
G)
Respuesta:
Respuesta:
• Un ciclo simple es un ciclo que tiene como longitud al menos
Una cadena simple es un 3 y en el que el vértice inicial coincide con el vértice final
secuencia finita
Alternada de vértice y arista, sin • Grafo no Simple: Grafo no dirigido que tiene lados paralelos y
repetir arista, no elemental. lazos. Un grafo trivial es aquel grafo vacío con un único
vértice. Un grafo vacío es el grafo cuyo conjunto de aristas
es vacío.
 I)
Respuesta:

• Seleccionar una vértice S1, hacer H1=(S1) A15=> H3= (V1, V4, V5)
• Seleccionamos una arista a1 que tenga un A12=> H4=(V1, V4, V5, V3)
extremo en H1 y el otro extremo en un vértice A13=> H5= (V1, V4, V5, V3, V6)
S2 € H2. Hacer H2 U (S3) 3) Seleccionamos
una arista a2 que tenga un extremo en H2 y el
otro extremo en un vértice S3 H2. Hacer H2 U
(S3)

1) Seleccionamos el vértice v1 =>

H1=(V1) =>
2) 2) Seleccionamos la arista a4
H2=(V1,V4)

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)
 J) K)
Respuesta: Respuesta:

El subgrafo es aquel grafo que tiene por Un grafo dirigido es euleriano si es conexo
conjunto de vértices V (G) − {v} y por y cada vértice tiene grados internos
conjunto de aristas E(G−v) a todas las aristas iguales a los externos. Un grafo no dirigido
del grafo G excepto las incidentes con el se dice que es susceptible de ser recorrido
vértice v. (en inglés: traversable) si es conexo y dos
Se comprueba que en un árbol dos vértices en el grafo tienen grado impar.
vértices cualesquiera están unidos por un
único camino. Se demuestra 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.
L)
Respuesta:

Si un grafo bipartito balanceado con mínimo grado al menos cuatro tal que para cada agregado
independiente balanceado de cardinalidad cuatro vértices se tiene que la suma de sus grados es al
menos la mitad del total de los vértices del grafo mas uno, entonces el grafo es hamiltoniano.

Camino Hamiltoniano: Es un camino simple (que no repite vértices) que incluye todos los vértices de
G.
 Dado el siguiente grafo

A) Encontrar matriz de conexión

B) Es simple?. Justifique su respuesta
C )Encontrar una cadena no simple no elemental de grado 5
D) Encontrar un ciclo simple
E) Demostrar si es fuertemente conexo utilizando la matriz de accesibilidad
F) Encontrar la distancia de v2 a los demás vértices utilizando el algoritmo de Dijkstra

V1 a1
v2
a2
a6 a5 a3 a4
a9
a8 v4
v3
v7

a12
a10 a11

V5 a13
v6
a14
A)
Respuesta:

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 0 0
B) C)
Respuesta: Respuesta:

En las cadenas no simple se puede repetir los arcos

El diágrafo es simple ya que no tiene durante el camino y que no sea elemental también
vínculos y no existe arcos paralelos que lo puede repetir el vértice. El grado 5 nos apunta el
dividan. numero de arcos.

D) E)
Respuesta: Respuesta:

El ciclo simple inicia y termina con el mismo Para saber que un grafo es conexo se realiza los
vértice y ella no puede repetir arcos. Ejemplo: siguientes pasos:

C= (v6, a14, v5, a11, v4, a9, v1, a1, v2, a4, v6). • lograr la matriz de adyacencia y se eleva a la
enésima potencia.

• Se calcula la suma de las potencias de A.

• Si todos sus elementos son distintos de cero.

 Elevamos la matriz al cuadrado para
Matriz adyacencia
conseguir el tamaño de dos.

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

Elevamos la matriz al cubo para conseguir Elevamos la matriz al cubo para conseguir
el tamaño tres el tamaño cuatro.

V1 V2 V3 V4 V5 V6 V1 V2 V3 V4 V5 V6
V1 1 1 1 1 1 1 V1 1 1 1 1 1 1
V2 1 1 1 1 1 1 V2 1 0 1 1 1 1
V3 1 1 1 0 1 1 V3 0 1 1 1 1 1
V4 0 1 1 1 1 1 V4 1 1 0 1 1 1
V5 0 1 1 1 1 1 V5 1 1 1 1 1 1
V6 1 0 1 1 0 1 V6 1 1 1 1 0 1
Elevamos la matriz al cubo para conseguir Calculamos la matriz de accesibilidad
el tamaño cinco. Acc(D).

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

A) Elemento que sea igual a cero sigue en 0.

B) Elemento diferente a cero se transforma en 1.

Como la matriz Acc(D) no tiene elementos nulos se

puede decir que el diágrafo es conexo
 F)
Respuesta:

1) Conseguir el vértice.
2) Conseguir después los vértices mas cercanos al V2.
3) Añadir etiquetas a cada vértice.
4) Después colocar la ponderación de la arista mas la ponderación de la etiqueta anterior.
5) Poner al lado de la etiqueta el numero de iteración.
6) Después se estudian las distancias y se escoge la menor .

[3,1]
Símbolo de iteración Vértice estudiado

Ponderación de arista
mas lo que deriva
 GRACIAS
POR SU ATENCIÓN