Redes De Flujo
Páginas: 4 (974 palabras)
Publicado: 24 de enero de 2013
-------------------------------------------------
Redes de flujo
En teoría de grafos, una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se leasocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales se mantiene la leyde corrientes de Kirchoff, en donde la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el tráfico en un sistema deautopistas, fluidos viajando en tuberías, corrientes eléctricas en circuitos eléctricos o sistemas similares por lo que viaje algo entre nodos.
Teoría de flujo máximo
En teor´ıa de grafos, un grafo dirigidocon pesos es tambi´en conocido como una red.
En los problemas de flujo en redes, las aristas representan canales por los que puede
circular cierta cosa: datos, agua, coches, corriente el´ectrica,etc. Los pesos de las aristas
representan la capacidad m´axima de un canal: velocidad de una conexi´on, volumen m´aximo de agua, cantidad m´axima de tr´afico, voltaje de una l´ınea el´ectrica, etc.;aunque es
posible que la cantidad real de flujo sea menor.
El problema del flujo m´aximo consiste en lo siguiente: dado un grafo dirigido con
pesos, G = (V, A, W), que representa las capacidadesm´aximas de los canales, un nodo
de inicio s y otro de fin t en V , encontrar la cantidad m´axima de flujo que puede circular
desde s hasta t. En la figura 5.33 se muestra un ejemplo de problema y lasoluci´on. El grafo
de la izquierda, G, pintado con l´ıneas continuas, representa las capacidades m´aximas; ser´ıa
la entrada del problema. El grafo de la derecha, F, representado con l´ıneasdiscontinuas,
indica los flujos reales; es una posible soluci´on para el problema.
Teorema de Ford-Fulkerson
Lester Randolph Ford Jr. al continuar los pasos de su padre Ford Sr. también hizo una enorme...
Redes de flujo
En teoría de grafos, una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se leasocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales se mantiene la leyde corrientes de Kirchoff, en donde la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el tráfico en un sistema deautopistas, fluidos viajando en tuberías, corrientes eléctricas en circuitos eléctricos o sistemas similares por lo que viaje algo entre nodos.
Teoría de flujo máximo
En teor´ıa de grafos, un grafo dirigidocon pesos es tambi´en conocido como una red.
En los problemas de flujo en redes, las aristas representan canales por los que puede
circular cierta cosa: datos, agua, coches, corriente el´ectrica,etc. Los pesos de las aristas
representan la capacidad m´axima de un canal: velocidad de una conexi´on, volumen m´aximo de agua, cantidad m´axima de tr´afico, voltaje de una l´ınea el´ectrica, etc.;aunque es
posible que la cantidad real de flujo sea menor.
El problema del flujo m´aximo consiste en lo siguiente: dado un grafo dirigido con
pesos, G = (V, A, W), que representa las capacidadesm´aximas de los canales, un nodo
de inicio s y otro de fin t en V , encontrar la cantidad m´axima de flujo que puede circular
desde s hasta t. En la figura 5.33 se muestra un ejemplo de problema y lasoluci´on. El grafo
de la izquierda, G, pintado con l´ıneas continuas, representa las capacidades m´aximas; ser´ıa
la entrada del problema. El grafo de la derecha, F, representado con l´ıneasdiscontinuas,
indica los flujos reales; es una posible soluci´on para el problema.
Teorema de Ford-Fulkerson
Lester Randolph Ford Jr. al continuar los pasos de su padre Ford Sr. también hizo una enorme...
Leer documento completo
Regístrate para leer el documento completo.