LegAut_Paseos_Circuitos

Paseos y Circuitos

Facilitador: Saúl Olaf Loaiza Melendez

Esto es un párrafo listo para contener creatividad, experiencias e historias geniales.

2021/2022

Matematicas Dicretas II

Ejemplo

Existen muchos problemas en los cuales se pretende determinar si existe un camino o un circuito en un grafo determinado o simplemente entre dos vértices cualesquiera. Pero, antes de definirlos, primero es necesario conocer qué es una sucesión de lados.Sucesión de ladosUna sucesión de lados es un conjunto de lados consecutivos donde termina un lado y comienza otro.

Caminos y Circuitos

Condición 3

Condición 2

Condición 1

Existen tipos especiales de paseos y circuitos, los cuales implican ciertas restricciones al momento de visitar o recorrer los vértices de un grafo dado, estos son los paseos y circuitos denominados de Euler (eulerianos) y de Hamilton (hamiltonianos).En primera instancia, se verán los de Euler.Paseo de EulerUn paseo de Euler (o euleriano) es un camino que incluye todos los lados de un grafo dado una y solo una vez.Circuito de EulerUn circuito de Euler (o euleriano) es un circuito que incluye todos los lados de un grafo dado una y solo una vez.Al recorrer todos los lados del grafo, también se recorren todos los vértices del grafo; sin embargo, no importa la repetición de vértices, mientras no se repitan los lados.

Paseo y Circuito de Euler

Ejemplo

Sea G(V, E) un grafo no dirigido y sean i y j dos vértices de G.Una sucesión de lados de i a j puede clasificarse como:a) Camino de longitud n de i a j, si va de i a j, y tiene n lados distintos entre sí. b) Camino simple de longitud n de i a j, si es de la forma (V0, V1, V2, … , Vn), donde V0 = i y Vn = j y V0, V1, V2, … , Vn son distintos entre sí.c) Circuito si es un camino de V a V. d) Circuito simple si es un circuito de la forma (V0, V1, V2, … , Vn), donde V0= Vn y V1, V2, … , Vn-1 son distintos entre sí.

Caminos y Circuitos

solución

Figura 4. Grafo No Dirigido

Sean los grafos no dirigidos de la Fgura 4 . Determinar cuáles de estos grafos tendrán un paseo o un circuito de Euler.

Ejemplo

Ejemplo

Un problema similar a la determinación de un paseo o un circuito de Euler, es el de determinar un paseo o circuito de Hamilton, los que se definen a continuación:Paseo de Hamilton Un paseo de Hamilton (o hamiltoniano) constituye un camino que pasa a través de cada uno de los vértices de un grafo dado exactamente una vez.Circuito de Hamilton Un circuito de Hamilton (o hamiltoniano) es un circuito que pasa a través de cada uno de los vértices de un grafo dado exactamente una vez.Al recorrer todos los vértices del grafo, no es importante si no se recorren todos los lados del grafo.

Paseo y circuitos Hamilton

En esta actividad se reforzó los conceptos orden, tamaño, incidencia, adyacencia y grado. Todos estos con respecto a los vertices de un grafo.Una de las características que siempre se cumplen en los grafos es el lema de las encajadas, con este lema más adelante se puede realizar grafos de acuerdo al grado de cada vértice.Figura 7. Lema de las encajadas.Figuf

Resumen

Ramón Espinoza, A. (2017). Capítulo XVII Grafos dirigidos En Matemáticas Discretas (2da. ed., pp. 429-451). AlfaomegaVillalpando Becerra, J. F., & Gacría Sandoval, A.(Eds.). (2014). Capítulo 6, Teoría de grafos. En Matemáticas discretas aplicaciones y ejercicios (1ra ed., pp. 185-233) Grupo Editorial Patria.EPP, S. (2012). Capítulo 10 Grafos y árboles En Matemáticas discretas con aplicaciones (4ta. ed., pp. 625-675). Cengage Learning.Johnsonbaugh R. (2005). Capítulo 8 Teoría de gráficas En Matemáticas discretas (6ta. ed., pp. 318-377). Educación Pearson.Tremblay, J. P. & Manohar. R. (Eds.). (1999). Capítulo 5 Teoría de gráficas En Matemáticas discretas con aplicación a las ciencias de la computación (1ra. ed., pp. 463-488). CECSA Figufds

Referencias

Esto es un párrafo listo para contener creatividad, experiencias e historias geniales.

¡Gracias!