Solve the maximum flow problem for the following network. Each label 

 denotes both the flow  pushed through an edge  and the capacity  of this edge


Evaluate (Correct/Wrong) each option:

I. This is the residual network after finding the maximum flow:

II. This is the network after finding the maximum flow:



III. This is the network after finding the maximum flow:



    
Considering Correct as True and Wrong as False, pick the correct letter respectively:

A. True, False, False

B. False, True, False

C. True, True, False

D. True, False, True

E. None of the above


Original idea by: Raphael Adamski

Comentários

  1. Joao Meidanis28 de setembro de 2025 às 18:01

    Bela questão, mas porque as arestas vermelhas? Ficou esquisito. Também você não colocou seu nome. Ainda por cima, esqueceu um pauzinho no III.

    ResponderExcluir
    Respostas
    1. Raphael Adamski29 de setembro de 2025 às 07:56

      As arestas vermelhas sao das imagens originais da fonte https://www.ida.liu.se/~TDDD95/timetable/le6_2018.pdf
      Consertado os outros comentarios

      Excluir

Postar um comentário

Postagens mais visitadas deste blog

Imagem
Solve the Travel Salesperson Problem for the following undirected weighted graph and pick the best answer: A) Path ABCDEA and length 24 B) Path ABCEDA and length 20 C) Path ADEBCA and length 18 D) Path AEBCDA and length 19 E) None of the above Original question by: Raphael Adamski Original images from https://graphicmaths.com/computer-science/graph-theory/travelling-salesman-problem/
Leia mais
Given the properties of BFS (Breadth First Search) and DFS (Depth First Search) algorithms, select the most suitable algorithm for each application: Find the shortest path between 2 nodes Cycle detection Strongly connected components detection Bipartite graphs A) BFS - DFS - DFS - BFS B) BFS - DFS - DFS - BFS C) BFS - BFS - DFS - DFS D) DFS - BFS - DFS - BFS E) None of the above
Leia mais
About Strongly Connected Components (SCC) concepts and Kosaraju-Sharir's algorithm, please select the correct answer regarding the three statements:  Kosaraju-Sharir's algorithm allow us to convert a direct cyclic graph into a directed acyclic graph (DAG) The advantage of detecting SCC in graphs is to be able to apply topologically ordering over any graph, even if there are cycles. Kosaraju-Sharir's algorithm is the only algorithm to find SCC in DAGs A) True-True-False B) True-False-True C) False-True-False D) True-False-False E) None of the above 
Leia mais