(1) write the full formulation of the max flow problem using Node 1 as the sourc
ID: 3602969 • Letter: #
Question
(1) write the full formulation of the max flow problem using Node 1 as the source and Node 5 as the destination using the complete problem data a. b. 2 2 8 6 4 6 get a formulation for the minimum cut problem on this graph You should indicate in your solution which primal constraints correspond to which dual variables, which primal variables correspond to which dual constraints, and comment on the intuition of the min cut formulation you have a) b) c) Python code for the max flow problem (using pulp) is provided. This is just another example file of the setup of a python file for a simple optimization model. You are not required to run this code as part of the assignment. rite a script (using either pulp or gurobipy) for in cut problem and a) b) c) get the optimal solution to the min cut problem Clearly state the value of your cut and which arcs make up the min cut. Using your solution, explain how you could use your solution to the max flow problem to get the minimum cut and vice versaExplanation / Answer
We can construct an undirected graph
G= (V, E) with guests as vertices, and
an edge between two vertices means the two guests know each other. Table T represents
the adjacency lists for the vertices. Two guests can sit at the same table if there is a
path between them
If we start from one vertex s and search the graph using breadth-first search (BFS) or
depth-first search (DFS), all the guests that are reachable from s can sit at the same
table, and additional tables are needed for vertices that are unreachable from s.
Hence, to find the minimum number of tables, we can iterate through
s
V
. If s is not
visited, increment the number of tables needed and call DFS-VISIT(s, T) or BFS(s, T),
marking vertices as visited during the traversal. Return the number of tables needed
after iterating through all the vertices.
This problem is equivalent to finding the number of connected components in the graph.
The running time is (V+E) because every vertex or edge is visited exactly once
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.