Redes de Flujo - 1c2024

La ejecución del algoritmo de Ford Fulkerson nos retorna como resultado

• a)El flujo máximo de una red de flujo y una asignación de flujo para alcanzarlo

• b)La existencia de un ciclo de costo negativo en el grafo

• c)Los caminos mínimos entre la fuente y el sumidero

• d)El corte máximo de una red de flujo como un corte S-T

• e)El flujo mínimo de una red de flujo y el corte mínima de la misma

Se conoce como 'condición de conservación de flujo' a

• a)Todas las anteriores

• b)La ausencia de perdida de flujo ocurrida a causa de su transporte dentro de un eje.

• c)La suma de los flujos de los ejes entrantes sea igual a la suma de los flujos de los ejes salientes en los nodos internos

• d)La cantidad de flujo que ingresa a la fuente es la misma que produce el sumidero

Llamamos “restricción de capacidad”

• a)Al flujo máximo que puede transportar una red de flujo calculado por su corte mínimo

• b)Al limite inferior de flujo que debe transportar un eje por un requerimiento del problema

• c)A la utilización de capacidades en los ejes de valores enteros positivos

• d)Al limite de flujo superior que puede transportar un eje según su capacidad

Un camino de aumento es ...

• a)Un camino desde el nodo fuente al sumidero que utiliza unicamente ejes hacia adelante

• b)Un camino desde la fuente hasta el sumidero que tiene capacidad disponible en sus ejes

• c)Un camino desde el nodo fuente a algún otro nodo que transporta al menos una unidad de flujo

• d)Un camino desde el nodo fuente a al algún otro nodo que tiene capacidad residual en sus ejes

El cuello de botella ...

• a)Ninguna de las opciones

• b)Todas las opciones

• c)Disminuye su valor en cada iteración y finaliza en cero

• d)Puede ser mayor al valor del corte mínimo

El grafo residual ...

• a)Todas los opciones

• b)permite encontrar el corte mínimo utilizando los ejes en adelanto

• c)permite visualizar las capacidades residuales en cada uno de los ejes

• d)se utiliza parar reencauzar caminos de aumento previamente establecidos para maximizar el flujo

• e)Ninguna de la opciones

Si comparamos la capacidad del corte mínimo de la red de flujo y su flujo máximo ...

• El flujo máximo es mayor o igual al corte mínimo

• El flujo máximo es menor o igual al corte mínimo

• El flujo máximo corresponde al máximo de los cortes mínimos

• Son iguales

• Son valores que no tienen relación

En un problema de flujo máximo, se puede reconocer al corte mínimo como

• el valor de flujo menor que satura todos los cuellos de botella de la instancia del grafo

• un corte A-B en el grafo residual separándolo en 2 partes en el que todos los ejes que pasan desde la parte A a la B están saturados.

• el número teórico que indica cuántos caminos de aumento realizar antes de finalizar la aplicación del algoritmo de Ford-Fulkerson

• el valor de flujo final al aplicar el algoritmo de Ford-Fulkerson

En cuanto a su complejidad Ford Fulkerson es un algoritmo ...

• óptimo

• Pseudopolinomial

• Polinomial

• no tratable

• exponencial

El objetivo de resolver un problema de demandas de flujo es ...

• Encontrar el corte mínimo del grafo

• Maximizar el flujo entre los vértices 'productores' y 'consumidores'

• Determinar si todo el flujo demandado puede ser satisfecho por el flujo producido

• Resolver problemas de flujo que tienen valores mínimos en sus ejes