Scribd
Cargar
53 vistas5 páginas

Overleaf

Este documento presenta una introducción a varios tipos de problemas de redes, incluidos el problema de flujo máximo, el problema de la ruta más corta y el problema del árbol de recorrido mínimo. Explica brevemente cada problema y su marco teórico, características del modelo, aplicaciones y conclusiones. El problema de flujo máximo trata de encontrar la cantidad máxima de flujo que puede transmitirse entre dos nodos en una red, mientras que el problema de la ruta más corta busca la ruta más corta entre dos nodos y el

Cargado por

Mayra Marin
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
53 vistas5 páginas

Overleaf

Este documento presenta una introducción a varios tipos de problemas de redes, incluidos el problema de flujo máximo, el problema de la ruta más corta y el problema del árbol de recorrido mínimo. Explica brevemente cada problema y su marco teórico, características del modelo, aplicaciones y conclusiones. El problema de flujo máximo trata de encontrar la cantidad máxima de flujo que puede transmitirse entre dos nodos en una red, mientras que el problema de la ruta más corta busca la ruta más corta entre dos nodos y el

Cargado por

Mayra Marin
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

2.2.

2 Tipos de Redes

Introducción

Palabras claves

Marco Teórico

Características del modelo

Aplicación

Conclusiones y Recomendaciones

2.2.3 Problema de flujo Máximo

Introducción
El problema del flujo máximo trata de encontrar la cantidad máxima de una variable
objetivo que se puede transmitir entre dos vértices fuente y destino de una red. El
estudio de este tipo de problemas comienza con trabajos en programación lineal,
estimulados por el trabajo de Ford y Fulkerson. Posteriormente se han propuesto una
serie de mejoras que han mejorado la eficiencia de los algoritmos de redes de flujo,
siendo un tema en el que todavía se presentan nuevas mejoras y algoritmos cada vez
más eficientes a pesar de que han transcurrido más de 60 años desde que se comenzaron
a investigar este tipo de problemas.

Palabras claves

Marco Teórico

Características del modelo

Se trata de enlazar un nodo fuente y un nodo destino a través de una


red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo
admisible. El objetivo es el de obtener la máxima capacidad de flujo
entre la fuente y el destino.

[Link] flujo a través de una red conexa dirigida se origina en un nodo,


llamado fuente, y termina en otro nodo llamado destino.

[Link] nodos restantes son nodos de trasbordo.

[Link] permite el flujo a través de un arco sólo en la dirección indicada


por la flecha, donde la cantidad máxima de flujo está dad por la
capacidad del arco. En la fuente, todos los arcos señalan hacia fuera.
En el destino, todos señalan hacia el nodo.

[Link] objetivo es maximizar la cantidad total de flujo de la fuente al


destino. Esta cantidad se mide en cualquiera de las dos maneras
equivalentes, esto es, la cantidad que sale de la fuente o la cantidad
que entra al destino

Aplicación
El problema del flujo máximo tiene numerosas aplicaciones en el mundo real. Los algoritmos
de flujo máximo se aplican a la vida cotidiana para resolver problemas de gestión de recursos,
reparto en empresas de logística, control de vuelos con escalas en aerolíneas, gesti´on de
selecci´on de proyectos o para calcular las intensidades m´aximas en un circuito el´ectrico,
entre otros. En las siguientes subsecciones se describen algunas de ellas

Conclusiones y Recomendaciones
2.2.4 Problema de la ruta mas corta.

Introducción

Palabras claves

Marco Teórico

Se trata de un modelo de red (debido a la forma de


Se trata de un modelo de red (debido a la forma de
diagrama de red usado para su representación),
donde cada arco o rama que une dos nodos
(elementos) que forman dicha red, viene
caracterizado por un valor que representa la
distancia (costo o tiempo) desde el nodo origen
hasta el nodo destino. Si denominamos ruta o
camino, a cualquier secuencia de arcos que conecte
el nodo origen con el destino, la resolución consiste
en encontrar la más corta posible. Usualmente los
arcos no están orientados, es decir, se permite el
tráfico en ambos sentidos, salvo que se indique lo
contrario (por ejemplo en una calle de dirección.

Características del modelo

Aplicación
Conclusiones y Recomendaciones

2.2.5 Problema del árbol del mínimo recorrido.

Introducción

Palabras claves

Marco Teórico

Características del modelo

Aplicación

Conclusiones y Recomendaciones

2.2.6 Problema del costo mínimo .

Introducción

Palabras claves
Marco Teórico

Características del modelo

Aplicación

También podría gustarte