29326728
Description
Mind Map by marxismo pelage, updated more than 1 year ago
|
Created by marxismo pelage
over 3 years ago
|
|
Caminos y Paseos de Euler y Hamilton
- Euler
- Paseo
- Si una gráfica tiene un paseo euleriano cerrado,
entonces todos sus vértices tienen grado par; las
aristas donde se empieza y se acaba se pueden
aparear para dar ahí el grado par.
- Siempre deben ser conexo
- Un camino de Euler es una
trayectoria que contiene todas las
aristas de G y recorre cada arista
exactamente una vez
- Caminos de Euler: {a,b,e,d,c,f,g,d,h,h,i,g}
{g,i,h,h,d,g,f,c,d,e,b,a}
- Si una gráfica tiene un paseo euleriano cerrado,
entonces todos sus vértices tienen grado par; las
aristas donde se empieza y se acaba se pueden
aparear para dar ahí el grado par.
- Circuitos
- 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.
- Teroema 1
- Sea G un grafo o multigrafo no dirigido.
Entonces G tiene un ciclo de Euler si, y
solo si, es conexo y todo vértice tiene
grado par. Diremos que es un grafo
Euleriano.
- Sea G un grafo o multigrafo no dirigido.
Entonces G tiene un ciclo de Euler si, y
solo si, es conexo y todo vértice tiene
grado par. Diremos que es un grafo
Euleriano.
- Teorema 2
- Sea G un grafo o multigrafo no dirigido. Entonces
G tiene un camino de Euler si, y solo si, es conexo
y tiene solo dos vértices de grado impar. Diremos
que el grafo es semi-Euleriano.
- Sea G un grafo o multigrafo no dirigido. Entonces
G tiene un camino de Euler si, y solo si, es conexo
y tiene solo dos vértices de grado impar. Diremos
que el grafo es semi-Euleriano.
- 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.
- Paseo
- Hamilton
- Paseos
- Un ciclo hamiltoniano es un ciclo
simple que contiene todos los
vértices de G.
- Un pase hamiltoniano es un paseo que lpasa a travez de
cada un adde los vertices exactamente una vez
- Un ciclo hamiltoniano es un ciclo
simple que contiene todos los
vértices de G.
- Circuitos
- Un paseo hamiltoniano es un paseo que pasa
a través de cada un de los vértices
exactamente una vez.
- Un ciclo hamiltoniano es una trayectoria que empieza y termina
en el mismo vértice y pasa por cada vértice una sola vez.
- Un paseo hamiltoniano es un paseo que pasa
a través de cada un de los vértices
exactamente una vez.
- El nombre de hamiltoniano se debe a William
Rowan Hamilton (1805- 1865). Ideó un puzle que
consistía en un dodecaedro con puntas clavadas
en sus vértices y cada vértice rotulado con el
nombre de una ciudad. Una cuerda iba unida a
una de las ciudades. El objetivo era recorrer todos
los clavos con la cuerda pasando una sola vez por
cada uno de ellos. Para hacer el puzle más
interesante, Hamilton indicaba las primeras
ciudades del recorrido
- Paseos
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.