Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Caminos eulerianos, hamiltonianos y de longitud mínima.

Caminos eulerianos, Caminos hamiltonianos y Caminos de longitud mínima
by

Quetzali Madera

on 28 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Caminos eulerianos, hamiltonianos y de longitud mínima.

a
b
c
d
e
f
a
b
c
d
e
a
b
c
d
e
f
g
Instituto Tecnológico de Tijuana
ISC. Elizabeth Quetzali Madera Hernández
4
3
6
8
10
8
6
1
2
8.5 Caminos eulerianos y hamiltonianos
8.6 Caminos de longitud mínima

Camino y circuito Euleriano
La ciudad prusiana de Königsberg (hoy en día llamada Kaliningrado, forma parte de Rusia) estaba dividida en cuatro partes por los dos brazos en los que se bifurca el río Pregel. Estas cuatro partes eran las dos regiones a orillas del río Pregel, la isla de Kneiphof y la región que quedaba entre ambos brazos del Pregel. Siete puentes conectaban entre sí estas regiones en el siglo XVIII.
Un
circuito euleriano
de un grafo G es un circuito simple que contiene a todas las aristas de G.
Un
camino euleriano
es un camino simple que contiene a todas las aristas de G.
Grafos no dirigidos
Grafos dirigidos
Condiciones necesarias y suficientes para la existencia de circuitos y caminos eulerianos
Teorema: Un grafo conexo contiene un circuito euleriano si, y sólo si, cada uno de sus vértices tiene grado par.
Cada vez que un circuito pasa por un vértice contribuye con dos unidades al grado de este vértice, ya que el circuito entra en el vértice por una arista incidente con ese vértice y sale de él por medio de otra arista incidente. Finalmente, el circuito termina donde comenzó, de nuevo contribuyendo con una unidad al grado de a. Por tanto, δ(a) tiene que ser par, puesto que el circuito contribuye con uno cuando comienza, con uno cuando acaba y con dos cada vez que pasa por a.
Grafo conexo que contiene un circuito euleriano.
Recomendación para construir un circuito euleriano en un grafo conexo.
Podemos dividir un grafo G en subgrafos y comenzar a resolverlo por partes.
Separamos del grafo G un subgrafo H y un subgrafo I. Construimos un camino simple en el subgrafo H eligiendo tantas aristas como sea posible iniciando y terminado en la arista c, para después hacer lo mismo con el subgrafo I.
Grafo conexo G
Subgrafo H.
Subgrafo I.
Determina si los grafos siguientes contiene o no un circuito euleriano. Construye uno en caso de que exista. Si no existe ningún circuito euleriano, determina si el grafo contiene o no un camino euleriano y construye uno en caso de que exista.
Ejemplos
Más Ejemplos
Determina si los grafos siguientes contiene o no un circuito euleriano. Construye uno en caso de que exista. Si no existe ningún circuito euleriano, determina si el grafo contiene o no un camino euleriano y construye uno en caso de que exista.
Ejercicios
Determina si los grafos siguientes contiene o no un circuito euleriano. Construye uno en caso de que exista. Si no existe ningún circuito euleriano, determina si el grafo contiene o no un camino euleriano y construye uno en caso de que exista.
TIP: Para construir un camino euleriano se inicia en un vertice impar y se termina en el otro vertice impar.
Caminos y circuitos Hamiltonianos
Se dice que un camino x , x ,..., x ,x del grafo G=(V,E) es un
camino hamiltoniano
si V={x , x ,..., x , x } y x ≠ x para 0 ≤ i < j ≤ n. Se dice que un circuito x , x ,..., x , x , x (con n > 1) del grafo G=(V,E) es un
circuito hamiltoniano
si x , x ,..., x , x es un camino hamiltoniano.
0
1
n-1
n
0
1
n-1
n
0
0
1
n-1
n
0
1
n-1
n
i
j
Cuantas más aristas tenga un grafo, más probable es que exista algún circuito hamiltoniano.
Teorema de Dirac:
Sea G un grafo simple con n vértices para n ≥ 3 tal que todos los vértices de G tienen grado mayor o igual que n/2 . Entonces, G contiene un circuito hamiltoniano.
/Eli.Quetz
Teorema de Ore:
Sea G un grafo simple con n vértices para n ≥ 3 tal que δ(u)+δ(v) ≥ n para cada par de vértices no adyacentes u y v de G. Entonces, G contiene un circuito hamiltoniano.
Grafo G1 Grafo G2 Grafo G3
Ejemplos
Determina si los grafos siguientes contienen o no un circuito hamiltoniano. Construye uno en caso de que exista. En caso contrario, argumenta tu respuesta y determina si contiene o no un camino hamiltoniano y constrúyelo. En caso contrario, argumenta tu respuesta.
Mas Ejemplos
Determina si los grafos siguientes contienen o no un circuito hamiltoniano. Construye uno en caso de que exista. En caso contrario, argumenta tu respuesta y determina si contiene o no un camino hamiltoniano y constrúyelo. En caso contrario, argumenta tu respuesta.
Ejercicios
Para cada uno de estos grafos, determina si se puede o no utilizar el Teorema de Dirac o el Teorema de Ore para demostrar que el grafo contiene un circuito hamiltoniano.
1
2
3
4
5
6
7
8
9
10
11
12
13
llamamos
grafos ponderados
a los grafos en los que se asigna un número a cada una de las aristas.
Grafo ponderado de una linea aérea
14
Algoritmo de Dijkstra
Caminos de longitud mínima
El algoritmo de Dijkstra nos ayuda a calcular la longitud del camino más corto entre 2 vertices.
16
15
Teorema:
El algoritmo de Dijkstra determina la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido.
Teorema:
El algoritmo de Dijkstra realiza O(n ) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.
2
El problema del viajante
Un viajante quiere visitar exactamente una vez cada ciudad de un conjunto de n ciudades para finalmente regresar al punto de partida.
Ejemplos
17
18
Ejercicios
Determina la longitud de un camino de longitud mínima entre a y e en el grafo ponderado G1.
Resuelve el problema del viajante para el grafo G2, calculando el peso total de todos los circuitos hamiltonianos y determinando un circuito con peso total mínimo.
Determina la longitud de un camino de longitud mínima entre a y z en el grafo ponderado correspondiente.
Una vez elegido el punto de partida, hay (n-1)!/2 circuitos hamiltonianos distintos que examinar.
G1 G2
Full transcript