Instituto Politécnico Nacional
Escuela Superior de Cómputo
1er ENTREGA DE EXPOSICIÓN
Integrantes:
Alatorre González Víctor Alexis
Higareda Madrigal Armando Osmar
Unidad de Aprendizaje: Matemáticas Discretas
Profesora: Claudia Jisela Dorantes Villa
Fecha: 16/11/24
ÍNDICE
CIRCUITOS Y CAMINOS DE EULER.......................................................1
EJEMPLOS:...............................................................................................1
EJERCICIOS..............................................................................................3
REFERENCIAS.........................................................................................4
CIRCUITOS Y CAMINOS DE EULER
Un camino de Euler, en una gráfica o multígrafo, es un recorrido por el
gráfico que usa cada borde exactamente una vez. Un circuito de Euler es un
camino de Euler que comienza y se detiene en el mismo vértice. Nuestro
objetivo es encontrar una manera rápida de verificar si una gráfica (o
multígrafo) tiene una ruta o circuito de Euler.
PROPIEDADES
1) Un grafo no dirigido G tiene un paseo de Euler si y solo si hay como
máximo dos vértices con grado impar.
2) Una gráfica tiene un circuito de Euler si y sólo si el grado de cada
vértice es par.
3) Si un grafo no dirigido G tiene un circuito de Euler entonces todo
vértice de G tiene valencia par, además de ser conexo.
4) Si G es un grafo no dirigido con vértices {v 1, v2, ..., vn} y la suma
δ ( v 1 ) , δ ( v 2) , … , δ (v n) es par, entonces el grafo tiene un circuito de Euler.
5) Un grafo G tiene un camino de Euler de v ≠ w si y solo si v y w son los
únicos vértices de valencia impar.
Si empezamos en un vértice y trazamos a lo largo de los bordes para llegar
a otros vértices, creamos un recorrido por la gráfica. Más precisamente, un
paseo en una gráfica es una secuencia de vértices tal que cada vértice de la
secuencia es adyacente a los vértices antes y después de él en la
secuencia. Si la caminata recorre cada borde exactamente una vez,
entonces la caminata se llama sendero de Euler (o caminata de Euler). Si,
además, los vértices inicial y final son los mismos (por lo que trazas a lo
largo de cada borde exactamente una vez y terminas donde empezaste),
entonces la caminata se llama circuito de Euler (o recorrido de Euler). Por
supuesto que, si una gráfica no está conectada, no hay esperanza de
encontrar tal camino o circuito.
1
EJEMPLOS:
Verificar si los siguientes grafos no dirigidos tienen un paseo o circuito de
Euler.
Camino
SI SI SI SI SI
de Euler
Circuito
NO SI NO NO NO
de Euler
En un grafo dirigido el grado o valencia de entrada de un vértice es el
número de lados incidentes hacia este y el grado de salida es el número de
lados que son incidentes desde este.
Un grafo dirigido tiene un circuito de Euler si y solo si es conexo y el grado
de entrada de cualquier vértice es igual a su salida.
Un grafo dirigido tiene un paseo de Euler si y solo si es conexo y el grado de
entrada de cualquier vértice es igual a su grado de salida con la posible
excepción de solo dos vértices. Para estos dos vértices el grado de entrada
de uno de ellos es mayor que su grado de salida y el grado de entrada del
otro es menor que su grado de salida.
Ejemplo:
Verificar si los siguientes grafos dirigidos tienen un paseo o circuito de Euler.
2
Camino
SI SI
de Euler
Circuito
SI NO
de Euler
Ejemplos sencillos de GRAFO EULERIANO
Grafo Euleriano: No
Tour: v1 e1 v2 e2 v3 e3 v4 e4 v2 e1 v1
Tour Euleriano: No tiene, porque tiene vértices de
grado impar
Camino Euleriano: v1 e1 v2 e2 v3 e3 v4 e4 v2
Grafo Euleriano: Si
Tour: v2 e1 v1 e2 v3 e3 v2
Tour Euleriano: v1 e1 v2 e3 v3 e2 v1
Camino Euleriano: v1 e1 v2 e3 v3 e2 v1
EJERCICIOS
ADF
3
REFERENCIAS
Levin O. (2 de noviembre de 2022). 4.4: Caminos y circuitos de Euler.
LibreTexts Español. Recuperado el 15 de noviembre de 2024, de:
[Link]
s_Discretas/Matem%C3%A1ticas_Discretas_(Levin)/4%3A_Teor
%C3%ADa_de_las_Gr%C3%A1ficas/
4.4%3A_Caminos_y_circuitos_de_Euler
5.4.1 PASEOS y CIRCUITOS EULERIANOS. (s.f.). Mate Cucei. Recuperado
el 15 de noviembre de 2024, de:
[Link]
CIRCUITO DE EULER: Fuente del saber. (s.f.). Fuente del saber.
Recuperado el 15 de noviembre de 2024, de: [Link]
[Link]/matematicas-de-2do-bgu/grafos/circuito-de-euler-/
