Question 3 – Network Flow

 The contractors for the new "Alphaville Barão Geraldo" luxury allotment have hired the brilliant students of the MO412 class to design a high-capacity water distribution network. The project's goal is to pump water from the campus lake (Node Lago) through a series of seven interconnected retention dams (Nodes A through G) to the development site (Node Alpha).

The contract specifies that the network must be able to deliver a minimum of 30,000 liters of water per minute. The students have produced the following design, with pipe capacities also measured in thousands of liters per minute:


Analyze the following propositions regarding the network's performance and limitations.

  • I. Suppose that, to budget cuts, the pipe from Dam E to Dam G must be downgraded to a capacity of 5,000 L/min. With this hypothetical change, the contractual minimum delivery of 30,000 liters/minute would still be met.

  • II. To improve performance, a proposal is made to upgrade the pipe from Dam A to Dam D to a capacity of 18,000 L/min. This upgrade alone is sufficient to increase the network's total maximum flow.

  • III. If a critical failure shuts down the pipe from the Lago to Dam A (capacity becomes 0 L/min), the contractual minimum of 30,000 L/min can still be satisfied by rerouting flow through Dam B.

  • IV. In the original, unmodified network, the pipe connecting Dam D to Dam F must operate at its full capacity of 5,000 L/min in order to achieve the maximum network flow.


    Based on your analysis, choose the correct option:

    A) Only propositions I and IV are correct.

    B) Only proposition II is correct.

    C) Only propositions I, III, and IV are correct.

    D) Only propositions I and II are correct.

    E) None of the above


    Original idea by: Eduardo Bouhid

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Question 2 - Strongly Connected Components

Imagem
Barabasi's  Network Science   book describes the World Wide Web as a directed network where nodes are web pages and links are URLs. Imagine a small portion of this network for a university department: A Homepage (H) links to an About page (A) and a Research page (R).  The About page (A) links back to the Homepage (H). The Research page (R) links to three specific Publication pages (P1, P2, P3). Each Publication page (P1, P2, P3) links back to the main Research page (R). Based on the concept of Strongly Connected Components (SCCs) and the Kosaraju-Sharir algorithm, consider the following propositions: Propositions: I. An SCC is any set of nodes where every node is mutually reachable from every other. Therefore, because a path exists from R to P1 and back, the set {R, P1} is a valid SCC. II. In the context of the World Wide Web, an SCC represents a maximal set of web pages where a user can navigate between any pair of pages within that set. Based on this, the set {H, A} is...
Leia mais

Question 1 - BFS

Consider the following five statements regarding the Breadth-First Search (BFS) algorithm: I. For any given unweighted graph, the length of the shortest path found by BFS between two nodes is always less than or equal to the length of the path found by a Depth-First Search (DFS) between the same two nodes.  II. A single execution of BFS starting from an arbitrary node s is sufficient to identify all connected components in any given undirected graph.  III. An undirected graph can be tested for its bipartiteness by running BFS from a source node ' s'  and ensuring that every edge connects two vertices that lie in layers of opposite parity (one at an even distance from  s , the other at an odd distance). IV. The BFS algorithm can be implemented using a stack data structure instead of a queue and will still fulfill its function of finding the shortest path in unweighted graphs.  Which statements are correct?  a) II and IV b) I and III ...
Leia mais