Network Flow

In the Push-Relabel algorithm for finding the maximum flow in a network, the state of an intermediate node u is defined by its excess flow e(u) and its height h(u).


Consider this snapshot for node u:

  • Excess flow: e(u) = 8
  • Current heights: h(u) = 4; h(v) = 4; h(w) = 5
  • Residual capacities: c(u, v) = 5; c(u, w) = 10


What is the next operation for node u?


A) Push to node v, sending 5 units of flow.

B) Relabel node u, new height becomes h(u) = 5.

C) Push to node w, sending 8 units of flow.

D) Relabel node u, new height becomes h(u) = 6.


Original idea by: Maria Luiza Ramos da Silva

Comentários

Postar um comentário

Postagens mais visitadas deste blog

DFS vs BFS

You are analyzing a directed graph that represents a complex network of dependencies between software modules. You need to ensure the system is free of circular dependencies and find the minimum number of steps to reach a specific module from the source. Based on the properties of Breadth-First Search (BFS) and Depth-First Search (DFS) presented in the course, which statement correctly identifies the best approach? A) BFS should be used to find the shortest path (minimum steps) because it provides parent links with a distance guarantee, while DFS is required to detect circular dependencies by identifying "backward edges." B) DFS should be used to find the shortest path because its "finishing times" represent the most efficient order, while BFS is the only tool capable of "edge classification" to find cycles. C) In this directed graph, both BFS and DFS will naturally identify "forward" and "cross" edges, making them equally effective ...
Leia mais

Barabási-Albert

In the study of complex networks, the Barabási-Albert model describes how a node's connectivity evolves over time using the following equation: ki(t) = m * (t / ti)^0.5 In this formula, ti represents the time node i was introduced to the network, and t is the current time. Based on this dynamics, what fundamental conclusion can be drawn regarding the formation of major "hubs"? A) A node's growth rate is purely linear and depends exclusively on the number of new connections (m) added at each step, regardless of the entry time. B) There is a "first-mover advantage," meaning that older nodes are more likely to become hubs because they have been exposed to the preferential attachment mechanism for a longer period. C) A node's degree tends to decrease as the network grows (as t increases toward infinity), allowing newer nodes to quickly reach the same level of connectivity as veteran nodes. D) The resulting degree distribution is independent of the nodes...
Leia mais