Ejercicios - Teoría de gráficas

Acá mis ejercicios!

![](

PARTE 1
Ejercicio 1

• Hay camino euleriano

Ejercicio 2

• No hay ciclo hamiltoniano ya que el vertice d es de grado 1
• Si hay camino hamiltoniano

1. Identifique el gráfico a partir de la matriz de adyacencia:

   

2. Identifique el gráfico a partir de la matriz de incidencia:

   

Hola,
Aquí subo la primera parte de los ejercicios de Teoría de Gráficas
Elena Nuñez

buenas tardes, aqui mis ejercicios, gracias
![](

![](

![](

![](

![](

Este es el desarrollo del taller de ejercicios sobre teoría de gráficas:

Hola,
Aquí subo la segunda parte de los ejercicios de Teoría de Gráficas
Elena Nuñez

Ejemplo 1
No hay camino ni ciclo euleriano, ya que hay tres nodos con aristas impares y la regla dice máximo dos. Aparte que por esa razón no se podría salir de uno y terminar en otro impar, quedaría uno libre.
Ejercicio 1.
El grado total es 24, si hay camino eulerino y ciclo euleriano, ya que las los vértices tienen grado par todos.
Ejercicio 2.
Si hay ni camino hamiltoniano pero no ciclo hamiltoniano.
Si se ejecuta la fórmula: G(u)+G(v)>=n-1, no cumple ya que hay un vértice de grado 1
Ejemplo 2.
1100001
1010001
0101110
0010100
0011010
0010101
1100010
Práctica 1
0100001
0010000
0000111
0011000
0000000
0000100
0100010

Buenas tardes, envío la respuestas de los ejercicios relacionados con matrices de adyacencia y de incidencia.

Hola esta es la respuesta del ejercicio 1 y 2:

En el ejercicio 3 donde dice “matriz de adyacencia” debe decir “matriz de incidencia”.

1.- Sí hay un camino euleriano porque hay 2 vértices (e y c) con nodos impar, los demás con nodos par
2.-

3.-

Ejercicios:
![](

![](

![](

Ejercicios realizados, buen curso gracias

Ejercicio 2 Grafos:

• No hay ciclo hamiltoniano: hay un vértice con grado 1.
• No es un grafo hamiltoniano
• Si hay caminos hamiltonianos.

Ejercicio 1 Grafos:
Na:2 Nb:4 Nc:3
Nd:2 Ne:3 Nf:2
Ng:4 Nh:4

• Si hay un camino euleriano: hay únicamente dos vértices con grado impar
• No hay ciclo euleriano: Todos los grados de los vértices deberían ser pares.

Ejercicio 1- matriz de grafo dirigido
a b c d e f g
a 0 1 0 0 0 0 1
b 0 0 1 0 0 0 0
c 0 1 0 0 1 1 1
d 0 0 1 0 1 0 0
e 0 0 0 0 0 0 0
f 0 0 0 0 1 0 0
g 0 1 0 0 0 1 0

A 2
B 4
C 3
D 2
E 3
F 2
G 4
H 4

Dado que tiene dos vértices impares puede decirse que hay un camino euleriano, pero no un ciclo.

No hay un ciclo hamiltoniano porque hay un vértice de grado uno.

a b c d e f g
a 1 1
b 1
c 1 1 1 1
d 1 1
e
f 1
g 1 1

1. Ejercicio #1
   𝛿( a ) = 2
   𝛿( b ) = 4
   𝛿( c ) = 3
   𝛿( d ) = 2
   𝛿( e ) = 3
   𝛿( f ) = 2
   𝛿( g ) = 4
   𝛿( h ) = 4
   Es un camino euleriano ya que no hay más de dos vértices con grado impar. No es un ciclo euleriano, ya que no todos los vértices terminan con grado impar.

1. Ejercicio #2
   Si hay un camino hamiltoniano, ya que se pueden recorrer todos los vértices una sola vez. No es un ciclo hamiltoaniano, ya que debido a que el vértice d solo tiene grado 1.

1. Ejercicio #3
   
   

1. Ejercicio #4
   
   

1. Ejercicio #5
   
   

Les comparto mi solución:

1. Determine el grado de cada uno de los vértices y concluya si hay un camino euleriano o no, concluya si hay un ciclo euleriano o no y por qué:

   
   δa= 2
   δb= 4
   δc= 3
   δd= 2
   δe= 3
   δf= 2
   δg= 4
   δh= 4
   Es un camino euleriano, ya que tiene 2 nodos de grado impar

2. Analice la gráfica y determine si hay un camino hamiltoniano y si hay un ciclo hamiltoniano:

   
   δa= 2
   δb= 4
   δc= 2
   δd= 1
   δe= 3
   δf= 4
   n = 6
   Grado(d) + Grado(a) ≥ n - 1
   1 + 2 ≥ 6 - 1
   3 ≥ 5
   No es posible determinar si hay un camino hamiltoniano
   No hay un ciclo hamiltoniano porque existe un nodo con grado 1

3. Determine la matriz de adyacencia del siguiente grafo dirigido:
   

   
   

   

4. Identifique el gráfico a partir de la matriz de adyacencia:
   

   
   

   

5. Identifique el gráfico a partir de la matriz de incidencia:
   

   
   

   

En el primer ejercicio hay caminos pero no ciclos eulerianos porque c y e tienen grado impar. En el segundo ejercicio pesar de que el teorema para ciclos y caminos hamiltonianos no se cumple, si hay caminos hamiltonianos (por ejemplo la ruta dfcbea). No hay ciclos hamiltonianos porque el grade de d es de 1.

Ejericio 1:
a2/b4/c3/d2/e3/f2/g4/h4
Si existe camino Euleriano, porque tiene hasta un máximo de dos vértice de grado impar.
No existe ciclo Euleriano, porque existe vértices de grado impar, y para que sea ciclo euleriano necesita que todos los vertiv¿ces sean de grado par.

Ejercicio 2:
Camino Hamiltoniano: Si
Ciclo Hamiltoniano: NO

1. Hay camino (2 nodos con 3 líneas, hay que empezar por c o e y terminar por el otro). No hay ciclo.
2. Sí hay camino, pero se da el problema matemático ese que comentaba, porque tomando D y F vemos que los grados son 4 y los nodos son 6, así que no se cumple la condición. Sin embargo es obvio que sí hay un camino para recorrer todos los nodos sin repetir. Lo que no hay es ciclo porque D solo tiene un camino, así que hay que pasar por F dos veces sí o sí.
   –
   1,
   0 1 0 0 0 0 1
   0 0 1 0 0 0 0
   0 0 0 0 1 1 1
   0 0 1 0 1 0 0
   0 0 0 0 0 0 0
   0 0 0 0 1 0 0
   0 1 0 0 0 1 0

2,

3,

Y en el enunciado de la última habría que sustituir matriz de adyacencia por incidencia (creo)

Espero que esté todo bien.

δa= 2
δb= 4
δc= 3
δd= 2
δe= 3
δf= 2
δg= 4
δh= 4
si hay camino euleriano
a-b-h-c-d-e-f-g-a
si hay ciclo euleriano por que se puede formar un ciclo.
2.
si hay camino hamiltoniano.
no hay ciclo, por que la arista final no coincide con la primera.
1
–a-b-c-d-e-f-g
a-0-1-0-0-0-0-1
b-1-0-2-0-0-0-1
c-0-2-0-1-1-1-1
d-0-0-1-0-1-0-0
e-0-0-1-1-0-1-0
f-0-0-1-0-1-0-1
g-1-1-1-0-0-1-0

2

3

a=2 Si hay un camino Eureliano porque no hay mas de dos vértices de grado impar.
b=4 No hay un ciclo Eureliano porque hay vértices impares.
c=3
D=2
e=3
f=2
g=4
h=4

1. Si hay un camino Hamiltoniano porque recorremos todas las vértices una vez.
   No hay un ciclo Hamiltoniano porque hay una vértice de grado uno

1- Sí hay camino euleriano porque no hay 2 vértices de grado impar(cumple la condición de que no hayan más de 2 vértices con grado impar).
No hay ciclo euleriano ya que hay 2 vértices con grado impar(no cumple con la condición de que todos sus vértices tengan grado par.

2-Sí existe un camino Hamiltoniano(d,f,c,b,a,e)

1. Aunque sí hay camino hamiltoniano (d,f,c,b,a,e), No hay ciclo hamiltoniano. El vertice d es singular, no hay forma de volver a él por camino diferente a f-d, es decir este se usa dos veces.

Resultados ejercicios teoría de grafos en Excel:

1.Determine el grado de cada uno de los vértices y concluya si hay un camino euleriano o no, concluya si hay un ciclo euleriano o no y por qué:

Grado de a 2
Grado de b 4
Grado de c 3
Grado de d 2
Grado de e 3
Grado de f 2
Grado de g 4
Grado de h 4

Conclusión: como tiene 2 nodos de grado impar el grafo posee camino euleriano y como no todos los grados de sus nodos son pares entonces no tiene ciclo euleriano
.
2.Analice la gráfica y determine si hay un camino hamiltoniano y si hay un ciclo hamiltoniano:
Grado de a 2
Grado de b 4
Grado de c 2
Grado de d 1
Grado de e 3
Grado de f 4
Conclusión: No se puede afirmar que posea camino hamiltoniano pues no cumple que para cualquier par de vértices u y v que no sean adyacentes y cumplan que grado(v) + grado(u) ≥ n -1 y no posee ciclo hamiltoniano pues tiene un nodo de grado 1
.
1.Determine la matriz de adyacencia del siguiente grafo dirigido:

.
2. Identifique el gráfico a partir de la matriz de adyacencia:

.
3. Identifique el gráfico a partir de la matriz de incidencia:

Comparto resultado . saludos cordiales

Ejercicio 1.1
δa= 2
δb= 4
δc= 3
δd= 2
δe= 3
δf= 2
δg= 4
δh= 4

Vemos que existe 2 vertices con grado impar, por tanto si existe un camino euleriano pero no un ciclo euleriano.

Ejercicio 1.2
δa= 2
δb= 4
δc= 2
δd= 1
δe= 3
δf= 4

n=6

Vemos que existen vertices con grados menores a n-1 pero a un así existe camino hamiltoniano, mas no asi un ciclo hamiltoniano.

Ejercicio 2.1
0 1 0 0 0 0 1
0 0 1 0 0 0 0
0 1 0 0 1 1 0
0 0 1 0 1 0 0
0 0 0 0 0 0 0
0 0 0 0 1 0 0
0 1 0 0 0 1 0

Ejercicio 2.2

Ejercicio 2.3

Mis respuestas:

Comparto mis respuestas de estos ejercicios:

Yo si hago los ejercicios, no más no se como subir las fotografías de los ejercicios jeje

Los hago en mi cuaderno de apuntes

Ejercicio 1
δa=2
δb= 4
δc= 3
δd= 2
δe= 3
δf= 2
δg= 4
δh= 4
es Euleriano porque pasa por todos los caaminos sin repetir, además que no hay más de dos vértices con grado mayor a 3.

Ejercicio 2
Hay camino Hamiltoniano pero no hay ciclo porque se puede iniciar pero no terminar donde se inicia el camino

Ejercicio 1
a b c d e f g grado
a 0 1 0 0 0 0 1 2
b 0 0 1 0 0 0 0 1
c 0 1 0 0 1 1 1 4
d 0 0 1 0 1 0 0 2
e 0 0 0 0 0 0 0 0
f 0 0 0 0 1 0 0 1
g 0 1 0 0 0 1 0 2

📌 Respuestas

Aquí mis soluciones

En el ejercicio de determinar si hay un camino y ciclo hamiltoniano tengo una confusión.
De manera visual parece que sí hay camino y no hay ciclo.
Pero si se utiliza el teorema para verificar el camino utilizando las vértices a y c, no se cumple la condición necesaria.

	g(a) + g(c) >= n - 1
	2 + 2 >= 6 - 1
	4 >= 5 // No se cumple

Se supone que debería funcionar con cualquier vértice.

1. δa= 2
   δb= 4
   δc= 3
   δd= 2
   δe= 3
   δf= 2
   δg= 4
   δg= 4

¿Camino euleriano?
Si tiene camino Euleriano porque únicamente tiene 2 vértices con grado impar. C y E
.
¿Ciclo euleriano?
No tiene ciclo euleriano porque existe al menos un vértice de grado impar.

1. δa= 2
   δb= 4
   δc= 2
   δd= 1
   δe= 4
   δf= 3

¿Camino hamiltoniano ?
Grado (a) + Grado © >= n - 1

2+2 >= 6-1
		
4 >= 5
No se cumple la condición 
		
¿Ciclo hamiltoniano ?
	no se cumple el ciclo porque d tiene es un vértice de grado 1.

Ejercicio 2: gráfico a partir de la matriz de adyacencia:

Ejercicio 3. Identifique el gráfico a partir de la matriz de adyacencia:

Ejercicios de práctica:
1)Hay camino euleriano y no hay ciclo.
2)Hay camino y no hay ciclo hamiltoniano.

Estas son mis respuestas:

a - 2
b - 4
c - 3
d - 2
e - 3
f - 2
g - 4
h - 4
Sólo hay dos nodos de grado impar, luego sí existe la posibilidad de un ciclo euleriano en el grafo.