Suppose that, in addition to edge capacities, a flow network has vertex capacities.That is each vertex has a limit l./ on how much flow can pass though . Showhow to transform a flow network G D .V; E/ with vertex capacities into an equiv-alent flow network G0 D .V 0; E0/ without vertex capacities, such that a maximumflow in G0 has the same value as a maximum flow in G. How many vertices andedges does G0 have?
Question
Suppose that, in addition to edge capacities, a flow network has vertex capacities.That is each vertex has a limit l./ on how much flow can pass though . Showhow to transform a flow network G D .V; E/ with vertex capacities into an equiv-alent flow network G0 D .V 0; E0/ without vertex capacities, such that a maximumflow in G0 has the same value as a maximum flow in G. How many vertices andedges does G0 have?
Solution
To transform a flow network G(V, E) with vertex capacities into an equivalent flow network G'(V', E') without vertex capacities, you can use the following steps:
-
For each vertex v in V, replace it with two vertices v_in and v_out.
-
Add an edge (v_in, v_out) with capacity equal to the vertex capacity of v in the original graph G.
-
For each edge (u, v) in E, replace it with two edges (u_out, v_in) and (v_out, u_in). The capacity of these new edges should be the same as the capacity of the original edge.
-
The source and target vertices in G' are the _out and _in vertices of the source and target in G, respectively.
The maximum flow in G' is the same as the maximum flow in G because the flow through each vertex v is limited by the capacity of the edge (v_in, v_out), which is equal to the vertex capacity of v in G.
The number of vertices in G' is twice the number of vertices in G because each vertex in G is replaced by two vertices in G'. The number of edges in G' is twice the number of edges in G plus the number of vertices in G because each edge in G is replaced by two edges in G' and an additional edge is added for each vertex in G.
Similar Questions
Suppose that you wish to find, among all minimum cuts in a flow network G withintegral capacities, one that contains the smallest number of edges. Show how tomodify the capacities of G to create a new flow network G0 in which any minimumcut in G0 is a minimum cut with the smallest number of edges in G.
Alice and Bob have an undirected graph of n nodes and three types of edges:Type 1: Can be traversed by Alice only.Type 2: Can be traversed by Bob only.Type 3: Can be traversed by both Alice and Bob.Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph. Example 1:Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]Output: 2Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.Example 2:Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]Output: 0Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.Example 3:Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]Output: -1Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable. Constraints:1 <= n <= 1051 <= edges.length <= min(105, 3 * n * (n - 1) / 2)edges[i].length == 31 <= typei <= 31 <= ui < vi <= nAll tuples (typei, ui, vi) are distinct.
What is the permanence for the node v in the following network?
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 3, 4, 5, 6, 7and 8. The maximum possible total weight that a minimum weight spanning tree of G can have is __.
What is the maximum number of edges in a complete undirected graph with n vertices?nn(n−1)/2n^2 2n
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.