ACA 2 Proyecto de Aula Segunda Entrega
Jonathan Macías Gómez
Ingenieria de Sistemas, CUN - Corporación Unificada Nacional de Educación
Superior
Algebra Moderna/55534
William Alexander Sierra Moreno
25 de Diciembre de 2022
1
2
3
Introducción
El presente trabajo se refiere a los grafos de Euler y grafos de Hamilton en
matemáticas discretas, En la teoría de grafos, un camino euleriano es un camino que
pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino
cerrado que recorre cada arista exactamente una vez, Si el grado de cada uno de los
vértices de este grafo es mayor o igual que la mitad del número total de vértices, y
esto se cumple para todos y cada uno de los vértices de G, entonces
este grafo es Hamiltoniano.
En nuestro mundo educativo no solo hay números y letras, Actualmente está
muy atestado de imágenes, Las imágenes que forman parte de nuestras vidas
cotidiana son además tipos muy diversos. Junto a las de nuestro entorno natural, nos
rodea fotografías de todo tipo, y en medio de todas ellas, esquemas no convencionales,
La teoría de grafos es un esquema que permite resolver muchos problemas
interesantes y forman ya parte de la matemática actual
El presente trabajo se desarrollara los ejercicios descritos por el profesor, por
medio de los Grafos de Euler llamado (teorema de euler) grafo plano y grafos de
Hamilton llamado ciclo o juego hamiltoniano y así llegar a la ejecución de los ejercicios.
4
Objetivo
Objetivo General:
Desarrollar los ejercicios descriptos por el docente en la teoría de grafos y
Utilizar conceptos o tipos de la teoría de grafos para darle una solución a los ejercicios
del trabajo
Objetivos Específicos:
Identificar los componentes y tipos de la teoría de grafos
Aplicar los distintos componentes y tipos de teoría de grafos
Resolver ejercicios de teoría de grafos con los conocimientos
adquiridos
Examinar cual es la mejor solución para el problema
Aprender más conceptos teoría de grafos y aplicarlos a la vida
cotidiana
Desarrollar los ejercicios descriptos
Justificar la solución de los ejercicios
5
1.
Trace la Ruta más corta a cada uno de los siguientes grafos pasando por todas las
estaciones.
A.
El grafo tiene dos caminos hamiltonianos:
𝑢⇒𝑣⇒𝑤⇒𝑥⇒𝑦⇒𝑧 y el camino 𝑢 ⇒ 𝑥 ⇒ 𝑣 ⇒ 𝑤 ⇒ 𝑦 ⇒ 𝑧
Pero el camino mas corto es el camino 𝑢 ⇒ 𝑥 ⇒ 𝑣 ⇒ 𝑤 ⇒ 𝑦 ⇒
𝑧 𝑐𝑜𝑛 𝑢𝑛 𝑣𝑎𝑙𝑜𝑟 𝑒𝑛 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑒 8 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠
6
𝑢 ⇒ 𝑥 ⇒ 𝑣 ⇒ 𝑤 ⇒ 𝑦 ⇒ 𝑧 = 8 𝑈𝑁𝐼𝐷𝐴𝐷𝐸𝑆
El grafo tiene dos caminos hamiltonianos:
El grafo grafo tiene dos caminos de hamiltoniano:
el camino: 𝐴 ⇒ 𝐵 ⇒ 𝐶 ⇒ 𝐷 ⇒ 𝐸 ⇒ 𝐹 ⇒ 𝐺 ⇒ 𝑍Y
𝐴 ⇒ 𝐷 ⇒ 𝐶 ⇒ 𝐵 ⇒ 𝐺 ⇒ 𝐹 ⇒ 𝐸 ⇒ 𝑍 = 28 unidades siendo el camino más corto
7
En el cual el mas corto es el camino 𝐴 ⇒ 𝐷 ⇒ 𝐶 ⇒ 𝐵 ⇒ 𝐹 ⇒ 𝐸 ⇒ 𝑍 ⇒ 𝐺, el cual
tiene un valor en unidades de 28 unidades siendo el camino más corto de
Hamilton haciendo la observación de que debe pasar por cada uno de los
puntos, punto de origen “A” y final “Z”
𝐴 ⇒ 𝐷 ⇒ 𝐶 ⇒ 𝐵 ⇒ 𝐹 ⇒ 𝐸 ⇒ 𝑍 ⇒ 𝐺 = 28 𝑈𝑁𝐼𝐷𝐴𝐷𝐸𝑆
C.
8
OBSERVACION GRAFO DIRIGIDO:
Se confirma camino de Hamilton con el menor valor es El grafo tiene un camino
hamiltoniano: 1 ⇒ 2 ⇒ 3 ⇒ 5 ⇒ 4 ⇒ 6, con un peso de 11 unidades en total
camino mas corto que pase por todos los vértices
1 ⇒ 2 ⇒ 3 ⇒ 5 ⇒ 4 ⇒ 6 = 11 𝑈𝑁𝐼𝐷𝐴𝐷𝐸𝑆
Se confirma el camino de Hamilton y el camino más corto del GRAFO, el
siguiente camino y más corto 0⇒ 𝐴 ⇒ 𝐵 ⇒ 𝐶 ⇒ 𝐸 ⇒ 𝐷 ⇒ 𝑇 valor en unidades 15
, lo cual lo hace el camino más corto
9
0⇒ 𝐴 ⇒ 𝐵 ⇒ 𝐶 ⇒ 𝐸 ⇒ 𝐷 ⇒ 𝑇 = 15 𝑈𝑁𝐼𝐷𝐴𝐷𝐸𝑆
E.
10
En base al siguiente grafo el camino más corto es:
El grafo tiene un camino hamiltoniano: 0 ⇒ 𝐴 ⇒ 𝐵 ⇒ 𝐶 ⇒ 𝐸 ⇒ 𝐷 ⇒ 𝑇 , con un valor de 9
unidades lo cual lo convierte en el camino mas corto desde el punto “0” al punto “T”.
0 ⇒ 𝐶 ⇒ 𝐵 ⇒ 𝐴 ⇒ 𝐷 ⇒ 𝐸 ⇒ 𝑇 = 8 𝑈𝑁𝐼𝐷𝐴𝐷𝐸𝑆
11
2
12
Conclusiones
Durante el desarrollo de los Ejercicios de este trabajo llegamos a la conclusión
que:
Durante este trabajo realizamos un recorrido en la teoría de grafos
de Euler y grafos de Hamilton y sus aplicaciones lo cual nos ayudó a dar forma
al concepto de la conjetura de evasivita en grafos, a través de la identificación de
las principales definiciones y formas de clasificar grafos que han sido muy
relevantes para el desarrollo de la teoría
La compresión de los conceptos de teoría de grafos resultaron de
gran importancia para la solución de los ejercicios Y darnos cuenta que nos
pueden ser útiles en la vida diaria.
Buscamos de alguna manera poder darle solución a los ejercicios
descriptos con los diferentes componentes y tipos de teoría de grafos de Euler y
grafos de Hamilton
Ampliamos nuestros conocimientos en la teoría de grafos y como
nos pueden ayudar en la búsqueda de soluciones a problemas
En los ejercicios desarrollados evidenciamos que este tipo de
problemas nos pueden ayudar a resolver problemas que se ven a diario en
nuestra vida cotidiana y que nos bridan más herramientas para llegar a la
solución de los mismos.
