Redes de Flujo

El valor de flujo que pasa por un nodo es igual a la suma de los flujos de las aristas entrantes a ese nodo

• Verdadero

• Falso

El flujo de entrada de un nodo es igual al flujo de salida del mismo nodo

• Verdadero

• Falso

La capacidad de un nodo nunca puede ser mayor que el flujo que pasa por ese nodo

• Verdadero

• Falso

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

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

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

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

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

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

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

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

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

• 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.

La capacidad del corte mínimo de una red de flujo es igual al valor del flujo máximo de la misma

• Verdadero

• Falso

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

• Polinomial

• Pseudopolinomial

• óptimo

• exponencial

• no tratable

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 es posible satisfacer la demanda

• Todos los anteriores

El grafo residual ...

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

• permite visualizar los flujos residuales en cada uno de los ejes

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

• Todos los opciones

• Ninguna de la opciones

El cuello de botella ...

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

• Puede ser mayor al valor del corte mínimo

• Todas las opciones

• Ninguna de las opciones