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

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

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

![](

![](

![](

![](

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

📌 Respuestas

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

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

Aquí mis soluciones

Mis respuestas:

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

Comparto mis respuestas de estos ejercicios:

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

Comparto resultado . saludos cordiales

Respuesta a los ejércitos 2 y 3 de la segunda parte

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.

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:

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:
   

   
   

   

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
   
   

Resultados ejercicios teoría de grafos en Excel:

Ejercicios realizados, buen curso gracias

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.

mis resspuestas:
![](

![](

![](

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. 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.

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

Ejercicios:
![](

![](

![](

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

Hola esta es la respuesta del ejercicio 1 y 2:

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

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

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.

Les dejo mis apuntes y ejercicios relacionado al curso de matemáticas discretas 👉 https://observablehq.com/d/ae848018b11d54bc (Tarda algo en cargar), pueden hacerle fork y tener su propia versión.

Les recomiendo https://observablehq.com/ , es un bloc de notas programable, similar a Jupyter pero con javascript.

Saludos.

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.-

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

δ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

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

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:

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.

Estas son mis respuestas:

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.

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