teoria de grafos

Nombres:
Turcott Rodríguez Fernanda
Josue Daniel Castillo Cruz
Hugo Adan Carreño Arellano
Maissa Villela

Ruta más corta

Descripción del problema

Métodos de Solución

Ejemplo: Encontrar la distacia mas corta iniciando en el nodo A y regresar al mismo nodo A, visitando todos los nodos solo 1 vez y ver cual es la ruta mas corta. Problema del agente viajero

Solución: fuerzabruta, posibles soluciones
ADBCA
ADCBA
ABDCA
ACDBA
ABCDA
ACBDA

Quitando las soluciones inversas solo tenemos 3 soluciones factibles, y solo 1 es solución optima

ADBCA =7+10+15+8=40
ADCBA=7+4+15+19=35
ABDCA9+10+4+8=31 solucion optima






Ejemplo: pasar por todos los nodos empezando por A, y terminando en A sin pasar por un nodo dos veces. Metodo del vecino mas cercano.Solución:
ADCBA=7+4+15+9=35, esta solucion no es una solución optima, pero es una solución bastante rápida, buena cuando tenemos bastantes nodos.
Ejemplo: Dado un cierto numero de ciudades y una tabla de costos al viajar de una ciudad a otra. Encontrar el viaje redondo mas barato que incluya todas las ciudades.

 
Toronto

Ottawa
Montreal
quenebec
Calgary
Winnipeg
Vancouver
Toronto
 399
539
730
3434
2099
4412
Ottawa
399
 
190
381
3553
2218
4531
Montreal
539
190
 
191
3743
2408
4721
quenebec
730
381
191
 
3934
2599
4912
Calgary
3434
3553
3743
3934
 
1336
977
Winnipeg
3099
2218
2408
2599
1336
 
2152
Vancouver
4412
4531
4721
4912
977
2152
 

Empezando en Toronto tenemos:
ottawa
montreal
quenebec
winnipeg
calgaryvancuver
toronto
total
399
190
191
2599
1336
977
4412
10104

El viaje redondo sigue la ruta mostrada con un costo total de 10104. Es la solución optima, las flechas indican la ciudad de origen a la ciudad de destino.
Aplicaciones
Es usada por ejemplo para encontrar en una serie de ciudades conectadas por carreteras, la ruta para llegar de una ciudad a otra, siguiendo una trayectoriamínima. 
Diseño de redes de telecomunicaciones
Redes de fibra óptica
Redes de computadoras
Redes telefónicas
Redes de Internet
Diseño de línea de transmisión eléctrico

Flujo máximo

Descripción del problema
Métodos de Solución
Ejemplo: Una ciudad es atrevesada por una red interestatal de carreteras de norte a surque le permite alcanzar un nivel de 15,000 vehiculos/hora en el hporario pico.Debido a un programa de mantenimiento general, el cual exige cerrar dichas vías, un grupo de ingenieros ha propuesto una red de rutas alternas para cruzar la ciudad de norte a sur, la cual incorpora avenidas importantes. La red propuesta es la siguiente, indica el numero de vehículos en miles que pueden circular por esa ruta.



1. ¿puede la red propuesta dar cabida a un flujo máximo de15,00 v/h de norte a sur?
2. ¿Cuál es el flujo máximo de vehículos que permite la red ahora?
3. ¿Qué flujo debe canalizar sobre cada rama?

Solución 1. 1-2-5-7 3.

Solución 1. 1-2-5-7 3.
Solución 2. 1-3-6-7 6.


Solución 1. 1-2-5-7 3.
Solución 2. 1-3-6-7 6.
Solución 3. 1-4-6-7 1.

Solución 1. 1-2-5-7 3.
Solución 2. 1-3-6-7 6.
Solución 3. 1-4-6-7 1.Solución 4. 1-4-6-5-7 1.

Solución 1. 1-2-5-7 3.
Solución 2. 1-3-6-7 6.
Solución 3. 1-4-6-7 1.
Solución 4. 1-4-6-5-7 1.
Solución 5. 1-2-3-5-7 2.

Solución optima es 3+6+1+1+2=13

El flujo máximo que esta ruta puede soprtar es de 13,000 v/h, por lo tanto no se satisface la circulación de los autos



Aplicaciones

Diseño de una red de tubería
Diseño de redesde transporte
Vías ferroviarias
Carreteras

Corte mínimo

Descripción del problema
Métodos de Solución
Ejemplo: Una compañia de gas tiene su propio gaseoducto, que conecta secciones de bombeo desde su campo a su centro principal de distribución. La red de la figura 1 representa la dirección en el cual el gas es bombeado. El sistema consta de 6 enlaces (numerados del 1 al 6) actualmente...