조합 최적화 - 일반적인 문제 - 최대 절단 문제

일반적인 문제와 실행 방법

최대 절단 문제

무향 그래프 $G=(V, E)$에 있어서, 각 변 $e_{ij}=(v_i,v_j)\in E$에 비부의 가중치 $w_{ij}$가 부여되어 있다고 한다. 이때 $\sum_{v_i\in V_1, v_j\in V_2}{w_{ij}}$를 최대화하는 $V_1, V_2(=V\setminus V_1)$를 구하라.

실행 방법

usage

Signature: maximum_cut(g, weight='weight')
Docstring:
最大カット問題
入力
    g: グラフ(node:weight)
    weight: 重みの属性文字
出力
    カットの重みの合計と片方の頂点番号リスト

파이썬

# CSVデータ
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw, maximum_cut
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
t = maximum_cut(g)
pos = networkx_draw(g, node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()
print(t)

결과

(27.0, [2, 4, 5])

파이썬

# pandas.DataFrame
from ortoolpy.optimization import MaximumCut
MaximumCut('data/node0.csv','data/edge0.csv')[1]

id
x
y
demand
weight




2
2
10
5
0
1


4
4
2
2
1
2


5
5
0
5
1
1



파이썬

# 乱数データ
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 4)
for i, j in g.edges():
    g.adj[i][j]['weight'] = 1
t = maximum_cut(g)
pos = networkx_draw(g, nx.spring_layout(g), node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()

데이터

data/node0.csv

data/edge0.csv