Combinatorial optimization-minimum cut problem

Maximum flow problem of Typical problem and execution method It has a dual relationship with Tsutomu / items / 80e70da6717acacefa00), and has a max-flow min-cut theorem. % E3% 83% AD% E3% 83% BC% E6% 9C% 80% E5% B0% 8F% E3% 82% AB% E3% 83% 83% E3% 83% 88% E5% AE% 9A% E7 % 90% 86) holds

Minimum cut problem

Consider two groups that divide the start point $ v_s \ in V $ (source) and the end point $ v_t \ in V $ (sink) for the maximum flow of graph $ G = (V, E) $, and both ends are in both groups. Find the grouping (called a cut) that minimizes the sum of the flow rates of the sides to which it belongs.

Execution method

usage


Signature: nx.minimum_cut(G, s, t, capacity='capacity', flow_func=None, **kwargs)
Docstring:
Compute the value and the node partition of a minimum (s, t)-cut.

python


#CSV data
import pandas as pd, networkx as nx
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)
networkx_draw(g)
nx.minimum_cut(g, 5, 2)
>>>
(6, ({0, 1, 3, 4, 5}, {2}))

Divided into node 2 and others, the minimum cut is 6.

image

python


#Random number data
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
for i, j in g.edges():
    g.adj[i][j]['capacity'] = 1
pos = networkx_draw(g, nx.spring_layout(g))
nx.draw_networkx_edges(g, pos)
nx.minimum_cut(g, 5, 6)
>>>
(3, ({2, 5}, {0, 1, 3, 4, 6, 7, 8, 9}))

image

data

Recommended Posts

Combinatorial optimization-minimum cut problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem