LegAut_Paseos_Circuitos

Matematicas Dicretas II

Paseos y Circuitos

2021/2022

Facilitador: Saúl Olaf Loaiza Melendez

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

Caminos y Circuitos

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 lados Una sucesión de lados es un conjunto de lados consecutivos donde termina un lado y comienza otro.

Ejemplo

Paseo y Circuito de Euler

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 Euler Un paseo de Euler (o euleriano) es un camino que incluye todos los lados de un grafo dado una y solo una vez. Circuito de Euler Un 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.

Condición 1

Condición 2

Condición 3

Caminos y Circuitos

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

Ejemplo

Ejemplo

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

Figura 4. Grafo No Dirigido

solución

Paseo y circuitos Hamilton

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.

Ejemplo

Resumen

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

Referencias

Ramón Espinoza, A. (2017). Capítulo XVII Grafos dirigidos En Matemáticas Discretas (2da. ed., pp. 429-451). Alfaomega Villalpando 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

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

¡Gracias!