조합 최적화 - 최소 절단 문제
최소 절단 문제
그래프 $G=(V,E)$의 최대 흐름에 대해, 시작점 $v_s\in V$(소스)와 종점$v_t\in V$(싱크)를 나누는 2개의 그룹을 생각해, 양단이 양 그룹에 속하는 변의 유량의 합이 최소가 되는 그룹 분할(컷이라고 부른다)을 구해라.
실행 방법
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.
파이썬
# CSVデータ
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}))
노드 2와 그 이외로 나누어져, 최소 컷은 6이 된다.
파이썬
# 乱数データ
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}))
데이터
Reference
이 문제에 관하여(조합 최적화 - 최소 절단 문제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/SaitoTsutomu/items/eb1d96e35cb24bed35ae텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)