最小頂点被覆問題
無向グラフ$G=(V, E)$において頂点被覆$C$のうち重みの和が最小のものを求めよ。
実行方法
usage
Signature: min_node_cover(g, weight='weight')
Docstring:
最小頂点被覆問題
入力
g: グラフ
weight: 重みの属性文字
出力
頂点リスト
python
# CSVデータ
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw, min_node_cover
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
t = min_node_cover(g)
pos = networkx_draw(g, node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t)
plt.show()
print(t)
結果
[0, 2, 3, 5]
python
# 乱数データ
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import min_node_cover, networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
l = min_node_cover(g)
pos = networkx_draw(g, nx.spring_layout(g), node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=l)
plt.show()
