グラフ・ネットワークのためのパッケージ NetworkX
import networkx as nx  # networkxモジュールを nx という別名で読み込み
import matplotlib.pyplot as plt  # 描画用モジュールの読み込み

# 図の表示用のマジックコマンド
%matplotlib inline

グラフ理論

グラフ $G=(V,E)$ とは,点集合 $V$ と枝集合 $E$ から構成される概念である. 点集合の要素を点(vertex, node)とよび, $u, v (\in V)$ などの記号で表す. 枝集合の要素を枝(edge, arc)とよび, $e (\in E)$ と表す. 2点間に複数の枝がない場合には,両端点 $u,v$ を決めれば一意に枝が定まるので,枝を両端にある点の組として $(u,v)$ もしくは $uv$ と表すことができる.

枝に「向き」をつけたグラフを有向グラフ(directed graph, digraph)とよび,有向グラフの枝を有向枝(directed edge, arc)とよぶ. 一方,通常の(枝に向きをつけない)グラフであることを強調したいときには,グラフを無向グラフ(undirected graph)とよぶ.

ネットワーク(network)とは,有向グラフに枝上を流れる「もの」(フロー)を付加した概念である. ネットワーク上の最適化理論は 1950年代にはじまり,その実務的な重要性と理論的な美しさから,急速に発展した分野である.

networkXでは,点をnode,枝をedgeとよんでいる.

グラフの生成法

グラフクラス Graph もしくは有向グラフクラス DiGraph から生成する.

import networkx as nx

G = nx.Graph()     #(無向)グラフ G の生成

D = nx.DiGraph()   #有向グラフ D の生成
G = nx.Graph()
G
<networkx.classes.graph.Graph at 0x7fc7d075bd60>

点と枝の追加方法

  • 点の追加
G.add_node(n)

で,グラフGに点nを追加する. n は不変オブジェクトなら何でも良い.

  • 枝の追加
G.add_edge(u,v)

はグラフGに枝(u,v)を追加する. 枝を追加すると点は自動的に追加される.

G.add_node("Tokyo")
G.add_edge(1, 2)

グラフの情報

G.nodesで点の情報,G.edgesで枝の情報を得ることができる.

print(G.nodes)
print(G.edges)
['Tokyo', 1, 2]
[(1, 2)]

点,枝に属性を付与

G.add_node(n,attr_dict)

で,第2引数 attr_dict に任意の属性を名前付き引数として付加することもできる.以下に例を示す.

G.add_node(1)
G.add_node('Tokyo')
G.add_node(5, demand=500)
G.add_node(6, product=['A','F','D'])
G.add_edge(u,v,attr_dict)

で,第3引数attr_dictに任意の属性を名前付き引数として付加することもできる.以下に例を示す.

G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,3, weight=7, capacity=15.0)
G.add_edge(1,4, cost=1000)

一度にたくさん追加

  • 複数の点を一度に追加
G.add_nodes_from(L)

はリストL内の各要素を点としてグラフGに追加する.引数はリストLのかわりに集合,辞書,文字列,グラフオブジェクトなども可能である.

  • 複数の枝を一度に追加
G.add_edges_from(L)

は長さ2のタプル(u,v)を要素としたリストL内の要素を枝(u,v)として追加する. 以下に例を示す.

G.add_edges_from([(1,2),(1,3),(2,3),(1,4)]

G.add_weighted_edges_from(L)は長さ3のタプル(u,v,w)を要素としたリストL内の要素を, 枝(u,v)ならびに重みを表す属性wとして追加する.重みの属性名の既定値はweightである. 以下に例を示す.

G.add_weighted_edges_from([('s',1,5),('s',2,8),(2,1,2),(1,'t',8),(2,3,5),(3,'t',6)])

グラフの生成と描画

3点からなる完全グラフ(すべての点の間に枝がある無向グラフ)を生成して,描画せよ.

以下の3通りの方法を示す.

  • 一番簡単で単純な方法(これが基本)

  • forループを使う方法(点の数が増えてきたらこれを使う)

  • 関数を使って一発

G=nx.complete_graph(3)

描画はdraw関数を用いる.引数はグラフのインスタンスである.

Jupyter環境で %matplotlib inline と宣言している場合にはmatplotlibの描画関数 plt.show() は省略できる.

G = nx.Graph()  # グラフのインスタンスを生成
G.add_edge(1, 2)  # 枝を追加
G.add_edge(1, 3)  # 枝を追加
G.add_edge(2, 3)  # 枝を追加
nx.draw(G)  # グラフを描画
print(G.nodes)
print(G.edges)
[1, 2, 3]
[(1, 2), (1, 3), (2, 3)]
G = nx.Graph()  # グラフのインスタンスを生成
for i in range(3):
    for j in range(3):
        if i < j:  # 無向グラフなので,iより大きいjの場合だけ枝を生成
            G.add_edge(i, j)
nx.draw(G)  # グラフを描画
G = nx.complete_graph(3)  # 完全グラフを生成するcomplete_graph関数を利用
nx.draw(G)

pyvisで動くグラフを描画

pyvisというパッケージ (https://pyvis.readthedocs.io/en/latest/index.html) を使うと,動かせるグラフを生成できる.

Google Colab.の場合は,

!pip install pyvis

でインストールし,

from pyvis.network import Network
net = Network()

とpyvisのグラフ netを生成する.

Jupyter Notebook (Lab.) の場合には,引数の notebookをTrueにして生成する.

from pyvis.network import Network
net= Network(notebook=True)

NetworkXのグラフはfrom_nxメソッドでpyvisのグラフに変換できる.

Google Colab.の場合には,その場で描画できないので,生成されたグラフ(graph.html)をダウンロードしてからブラウザで開く.

from pyvis.network import Network

net = Network(notebook=True)
net.from_nx(G)
net.show("graph.html")

問題(グラフの生成と描画)

  • 5点の完全グラフを生成し,描画せよ. ここで完全グラフ(complete graph)とは,すべての点間に枝があるグラフである.

  • $3 \times 3$ の格子グラフを生成し,描画せよ. ここで格子グラフ(grid graph)とは,2次元平面上に 座標 $(i,j) (i=1,2,\ldots,n; j=1,2,\ldots,m)$ をもつように $n m$個の点を配置し, 座標 $(i,j)$ の各点に対して,右の点 $(i+1,j)$ もしくは上の点 $(i,j+1)$ が存在するなら枝をはることによって得られるグラフであり, grid_2d_graph(n,m)関数で生成できる.

点・枝の情報

ここでは,点と枝に関する情報にアクセスする方法について述べる.

  • G.nodesメソッドはグラフGに含まれる点の集合(のようなもの;Viewと呼ばれる)を返す.

  • G.nodes[n]は点nの属性の情報を辞書として返す.

  • for n in GはグラフGの点に対する反復を行う.

D = nx.DiGraph()
D.add_node("Customer", demand=500)
D.add_node("Plant", product=["A", "F", "D"])
D.add_edge("Plant", "Customer")

print(D.nodes)
print(D.nodes["Customer"], D.nodes["Plant"])
for n in D:
    print(n)
['Customer', 'Plant']
{'demand': 500} {'product': ['A', 'F', 'D']}
Customer
Plant
  • G.edgesメソッドはグラフGに含まれるすべての枝の集合(のようなもの;Viewと呼ばれる)を返す.

  • for e in G.edges() でグラフGの枝に対する反復を行うことができる.

  • G.neighbors(u)は点uに隣接する(有向グラフの場合には後続する)点のイテレータを返す.

以下の例では,点1に隣接する点は2,3,4であり,点2に隣接する点は1,3,点3に隣接する点は1,2, 点4に隣接するのは点1だけである.

G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (1, 4)])
for n in G.neighbors(1):
    print(n)
for n in G:
    print(n, list(G.neighbors(n)))
2
3
4
1 [2, 3, 4]
2 [1, 3]
3 [1, 2]
4 [1]
  • G[u]は点uに隣接する点vをキーとし,枝(u,v)に付加された情報を値とした辞書を返す.

以下の例では,点1に隣接する点は2,3,4であり,接続する枝の重みはそれぞれ100,200,50である.

  • G[u][v]は枝(u,v)に付加された属性の情報を辞書として返す.

つまり,枝(1,2)の重みは100である.

G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 100), (1, 3, 200), (2, 3, 60), (1, 4, 50)])
print(G[1])
print(G[1][2])
{2: {'weight': 100}, 3: {'weight': 200}, 4: {'weight': 50}}
{'weight': 100}
  • D.successors(u)は有向グラフDに対する点uの後続点のイテレータを返す.

  • D.predecessors(u)は有向グラフDに対する点uの先行点のイテレータを返す.

for n in D.successors("Plant"):
    print(n)
Customer

問題

$3 \times 3$ の格子グラフを生成し,枝の重みをランダムに設定せよ.

描画の引数

関数 draw の代表的な引数は以下の通り.

  • posで点をキー,座標($x,y$のタプル)を値とした辞書を与える.これによって点の座標を指定できる. 省略された場合にはバネ法(後述)によって計算された座標に描画する.

  • with_labelsで点の名称の表示の有無を指定できる.既定値はFalse.

  • nodelistで描画する点のリストを指定できる.
  • edgelistで描画する枝のリストを指定できる.
  • node_sizeで描画する点の大きさを指定できる.既定値は $300$.
  • node_colorで描画する点の色を指定できる.既定値は'r'(赤).
  • widthで描画する枝の幅を指定できる.既定値は $1.0$.
  • edge_colorで描画する枝の色を指定できる.既定値は'k'(黒).

描画の際の点の位置posを求めるための関数として,以下のものが準備されている.

  • spring_layout(G)は隣接する点の間に反発するバネがあると仮定して得られるレイアウト(バネのレイアウト)の座標を返す. これが既定値であるので,引数posを省略して描画した場合には,バネのレイアウトになる.
  • circular_layout(G)は点を円上に配置したレイアウト(円上レイアウト)の座標を返す.
  • random_layout(G)は点を正方形内にランダムに配置したレイアウト(ランダム・レイアウト)の座標を返す.
  • shell_layout(G,nlist)は点を同心円状に配置したレイアウト(同心円レイアウト)の座標を返す. nlistは点のリストのリストであり,各リストは同心円に含まれる点集合を表す.
  • spectral_layout(G)はLaplace行列(次数対角行列から隣接行列を減じたもの)の固有値を用いたレイアウト(スペクトル・レイアウト)の座標を返す.
  • kamada_kawai_layout(G)はKamada-Kawaiによる枝の重み(距離)を考慮したレイアウトの座標を返す.

例として円上レイアウトでグラフを描画する.

G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (1, 4), (1, 5)])
# pos=nx.circular_layout(G)
pos = nx.kamada_kawai_layout(G)
nx.draw(G, pos=pos, edge_color="r", node_color="y", with_labels=True)

問題

  • 以下のグラフ生成から好きなものを3つ生成し,描画せよ.
G=nx.cycle_graph(6)
G=nx.balanced_tree(2,2)
G=nx.complete_graph(5)
G=nx.complete_bipartite_graph(3,3)
G=nx.grid_2d_graph(3,3)
G=nx.hypercube_graph(4)
G=nx.chvatal_graph()
G=nx.cubical_graph()
G=nx.octahedral_graph()
G=nx.dodecahedral_graph()
G=nx.icosahedral_graph()
G=nx.petersen_graph()
G=nx.truncated_cube_graph()
G=nx.truncated_tetrahedron_graph()
G=nx.tutte_graph()
G=nx.fast_gnp_random_graph(30,0.1)
G=nx.random_geometric_graph(10,0.2)
G=nx.bipartite.random_graph(10,30,0.3)
G=nx.bipartite.gnmk_random_graph(10,30,50)
  • 各グラフを、円上レイアウト, バネのレイアウト, スペクトルレイアウトのいずれかを1つずつ選び、描画せよ.

グラフに対する基本操作

ここではグラフに対する基本的な操作を紹介する.

  • complement(G)は補グラフを返す. ここでグラフ $G=(V,E)$ の補グラフ(complement)とは,点集合 $V$ をもち,$(u,v) \not\in E$ のときに $u,v$ 間に枝をはったグラフである.

  • reverse(G)は有向グラフの枝を逆にしたものを返す.

G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (0, 3)])
pos = nx.spring_layout(G)
nx.draw(G, pos=pos, edge_color="y", with_labels=True)

C = nx.complement(G)
print(C.edges())
nx.draw(C, pos=pos, edge_color="r", with_labels=True)
[(1, 2), (1, 3), (2, 3)]
  • compose(G, H)はグラフGとHの和グラフを返す.ただしGとHに共通部分があってもよい. ここで$G=(V_1,E_1)$ と $H=(V_2,E_2)$ の和グラフ(union graph)とは, 点集合 $V_1 \cup V_2$ と枝集合 $E_1 \cup E_2$ をもつグラフである.

  • union(G, H)はグラフGとHの和グラフを返す. ただしGとHに共通部分があってはいけない. (もし,共通部分があった場合には例外を返す.)

  • intersection(G, H)は同じ点集合をもつグラフGとHに対して,両方に含まれている枝から成るグラフ(交差グラフ)を返す.

  • difference(G, H)は同じ点集合をもつグラフGとHに対して,Gには含まれているがHには含まれていない枝から成るグラフ(差グラフ)を返す.

  • symmetric_difference(G, H)は同じ点集合をもつグラフGとHに対して,GまたはHに含まれており,かつ両者に含まれていない枝から成るグラフ(対称差グラフ)を返す.

G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (0, 3)])
pos = nx.spring_layout(G)
nx.draw(G, pos=pos, edge_color="y", with_labels=True)
H = nx.cycle_graph(4)
nx.draw(H, pos=pos, edge_color="r", with_labels=True)
# C = nx.union(G,H)
# C = nx.intersection(G,H)
# C = nx.difference(G,H)
# C = nx.difference(H,G)
C = nx.symmetric_difference(G, H)
print(C.edges())
nx.draw(C, pos=pos, edge_color="g", with_labels=True)
[(0, 2), (1, 2), (2, 3)]
  • cartesian_product(G, H)はグラフGとHに対する直積(Cartesian product)グラフを返す. ここで,グラフ $G=(V_1,E_1)$ と $H=(V_2,E_2)$ の直積グラフとは, 点集合 $V_1 \times V_2 = \{ (v_1,v_2) | v_1 \in V_1, v_2 \in V_2 \}$ (点集合 $V_1,V_2$ の直積)と, 以下を満たす枝集合から構成されるグラフである.

直積グラフの枝 $((u,x),(v,y))$ が存在 $\Leftrightarrow$ 「$x=y$ かつ $(u,v) \in E_1$」もしくは「$u=v$ かつ $(x,y) \in E_2$」

  • lexicographic_product(G, H)はグラフGとHに対する辞書的積(lexicographic product)グラフを返す. ここで,グラフ $G=(V_1,E_1)$ と $H=(V_2,E_2)$ の辞書的積グラフとは, 点集合 $V_1 \times V_2$ と, 以下を満たす枝集合から構成されるグラフである.

辞書的積グラフの枝 $((u,x),(v,y))$ が存在 $\Leftrightarrow$ 「$(u,v) \in E_1$」もしくは「$u=v$ かつ $(x,y) \in E_2$」

  • tensor_product(G, H)はグラフGとHに対するテンソル積(tensor product)グラフを返す. ここで,グラフ $G=(V_1,E_1)$ と $H=(V_2,E_2)$ のテンソル積グラフとは, 点集合 $V_1 \times V_2$ と, 以下を満たす枝集合から構成されるグラフである.

テンソル積グラフの枝 $((u,x),(v,y))$ が存在 $\Leftrightarrow$ 「$(u,v) \in E_1$ かつ $(x,y) \in E_2$」

  • strong_product(G, H)はグラフGとHに対する強積(strong product)グラフを返す. ここで,グラフ $G=(V_1,E_1)$ と $H=(V_2,E_2)$ の強積グラフとは, 点集合 $V_1 \times V_2$ と, 以下を満たす枝集合から構成されるグラフである.

強積グラフの枝 $((u,x),(v,y))$ が存在 $\Leftrightarrow$ 「$((u,x),(v,y))$ が直積グラフの枝もしくはテンソル積グラフの枝」

以下の例では,グラフ $G$ が商品 $0,1,2$ の関連, グラフ $H$ が店舗 $A,B,C$ 間の競合を表すものとする.

直積グラフの点は,各店舗で売られている各商品を表しており, 同じ店で販売されている関連する商品,もしくは競合する店で販売されている同じ商品に 対して枝がはられていると解釈できる.

G = nx.Graph()
H = nx.Graph()
G.add_edges_from([(0, 1), (0, 2)])
H.add_edges_from([("A", "B"), ("A", "C")])
Product = nx.cartesian_product(G, H)
nx.draw(Product, with_labels=True, node_size=1000, node_color="y")

問題

上の例題に対して辞書的積, テンソル積, 強積を計算し,描画せよ. それぞれ,どのような意味を持つか考察せよ.

マッチングとEuler閉路

以下を参照

マッチング

https://scmopt.github.io/opt100/30matching.html

Euler閉路

https://scmopt.github.io/opt100/64euler.html

問題(マッチングとEuler閉路)

以下のグラフは奇数の次数をもつ点があるので,Euler閉路(すべての枝をちょうど1回通過する閉路:すべての点の次数が偶数であるのが,Euler閉路をもつための必要十分条件である)をもたない. 奇数の次数をもつ点集合に対して,点間の最短距離を計算し,最小距離のマッチング(点の次数が1以下の部分グラフ)を求めよ. マッチングに含まれる枝をもとのグラフに加えるとEuler閉路をもつようになる(なぜか?理由を考えよ). マッチングを加えたグラフに対するEuler閉路を求めよ.

(ヒント:上のサイトのどこかに解答がある.)

G = nx.grid_2d_graph(3, 4)
nx.draw(G)

問題(最小木)

  1. $5 \times 5$ の格子グラフ(枝の重みはすべて $1$)の最小木(枝の重みの合計が最小の閉路を含まない連結グラフ)を求めよ.

  2. $5 \times 5$ の格子グラフの枝の重みをランダムに設定した上で,最小木を求め,最小木に含まれる枝を異なる色で描画せよ.

  3. 枝上に距離が定義された無向グラフ $G=(V,E)$ を考える. このグラフの点集合 $V$ を $k$個に分割したとき,分割に含まれる点同士の最短距離を最大化するようにしたい.これは最小木に含まれる枝を距離の大きい順に $k-1$ 本除くことによって得ることができる. ランダムに距離を設定した $5 \times 5$ の格子グラフに対して $k=5$ の分割を求めよ.

(ヒント:上のサイトのどこかに解答がある.)

最短路

最短路問題の詳細については,以下を参照

https://scmopt.github.io/opt100/03sp.html

例題:

八千代緑が丘から越中島までの電車による経路を求めたい.

枝ごとの移動時間と移動費用を入力して,最短時間パスと最小費用パスを求めよ.

乗り換えの待ち時間は無視してよいが,徒歩の時間は考慮せよ.

G = nx.Graph()
G.add_edge("八千代緑が丘", "西船橋", weight=15, cost=490)
G.add_edge("西船橋", "門前仲町", weight=20, cost=230)
G.add_edge("門前仲町", "越中島", weight=10, cost=0)
G.add_edge("西船橋", "越中島", weight=24, cost=380)

path = nx.dijkstra_path(G, "八千代緑が丘", "越中島")
print("最短時間パス", path)

path = nx.dijkstra_path(G, "八千代緑が丘", "越中島", weight="cost")
print("最小費用パス", path)
最短時間パス ['八千代緑が丘', '西船橋', '越中島']
最小費用パス ['八千代緑が丘', '西船橋', '門前仲町', '越中島']

問題

自宅から大学(越中島)までの最短時間と最小費用のパスを求めるためのネットワークを作成し,最短時間パスと最小費用パスを求めよ. ただし大学から徒歩圏の学生は,自宅もしくは親戚の家からのパスを求めよ.

問題

$3\times 3$ の格子グラフを生成するプログラムを作成し,枝の重みをランダムに設定した上で, 左上の点から右下の点までの最短路を求め,最短路を異なる色で描画せよ.

問題 (PERT)

あなたは航空機会社のコンサルタントだ.あなたの仕事は,着陸した航空機をなるべく早く離陸させるためのスケジュールをたてることだ. 航空機は,再び離陸する前に幾つかの作業をこなさなければならない. まず,乗客と荷物を降ろし,次に機内の掃除をし,最後に新しい乗客を搭乗させ,新しい荷物を積み込む. 当然のことであるが, 乗客を降ろす前に掃除はできず,掃除をした後でないと新しい乗客を入れることはできず, 荷物をすべて降ろし終わった後でないと,新しい荷物は積み込むことができない. また,この航空機会社では, 乗客用のゲートの都合で,荷物を降ろし終わった後でないと新しい乗客を搭乗させることができないのだ.

作業時間は,乗客降ろし $13$ 分,荷物降ろし $25$ 分,機内清掃 $15$ 分,新しい乗客の搭乗 $27$ 分, 新しい荷物積み込み $22$ 分とする. さて,最短で何分で離陸できるだろうか?

ヒント: 最短離陸時間を出すにはグラフの最長路を求める必要がある. 枝の重みを負にして最短路を解けば良い. 枝の重みが負なので, Dijkstra法でなくBellman-Ford法を使う.

問題 (難)

Dijkstra法を自分で実装せよ.

NetworkXモジュールのDijkstra法と自分で作成したDijkstra法を大規模な格子グラフで実験し,計算時間を比較せよ.

問題(最大流問題)

ランダムな2部グラフを作成し,最大マッチングを最大流問題を解くことによって求めよ.

ここで最大流問題(maximum flow problem)とは,以下に定義される問題である.

$n$ 個の点から構成される点集合 $V$ および $m$ 本の枝から構成される枝集合 $E$, 有向グラフ $G=(V,E)$, 枝上に定義される非負の容量関数 $C: E \rightarrow R_+$, 始点 $s \in V$ および終点 $t \in V$ が与えられたとき, 始点 $s$ から終点 $t$ までの「フロー」で, その量が最大になるものを求めよ.

フロー(flow)とは枝上に定義された実数値関数 $x: E \rightarrow R$ で, 以下の性質を満たすものを指す.

  • フロー整合条件: $$ \sum_{v: vu \in E} x_{vu} - \sum_{v: uv \in E} x_{uv} =0 \ \ \ \forall u \in V \setminus \{s,t\} $$

  • 容量制約と非負制約: $$ 0 \leq x_{e} \leq C_{e} \ \ \ \forall e \in E $$

ヒント:ダミーの始点と終点を追加せよ.

G = nx.bipartite.random_graph(10, 5, 0.5)
top = nx.bipartite.sets(G)[0]
pos = nx.bipartite_layout(G, top)
nx.draw(G, pos=pos)

問題(割当問題)

4人の作業員 A,B,C,D を4つの仕事 $0,1,2,3$ を1つずつ割り当てることを考える. 作業員が仕事を割り当てられたときにかかる費用が,以下のようになっているとき,最小費用の割当を求めよ.

$$ \begin{array}{ l l l l l} & 0 & 1 & 2 &3 \\ \hline A & 25 & 20 & 30 & 27 \\ B & 17 & 15 & 12 & 16 \\ C & 25 & 21 & 23 & 19 \\ D & 16 & 26 & 21 & 22 \end{array} $$

この問題は,最小費用流問題に帰着できる.

最小費用流問題(minimum cost flow problem)は,以下のように定義される問題である.

有向グラフ $G=(V,E)$, 枝上に定義される重み(費用)関数 $w: E \rightarrow R$, 枝上に定義される非負の容量関数 $C: E \rightarrow R_+ \cup \{ \infty \} $, 点上に定義される流出量関数 $b: V \rightarrow R$ が与えられたとき, 「実行可能フロー」で,費用の合計が最小になるものを求めよ. ただし,$\sum_{v \in V} b_v =0$ を満たすものとする.

cost = [[25, 20, 30, 27], [17, 15, 12, 16], [25, 21, 23, 19], [16, 26, 21, 22]]

問題(輸送問題)

あなたは,スポーツ用品販売チェインのオーナーだ. あなたは,店舗展開をしている5つの顧客 (需要地点)に対して, 3つの自社工場で生産した製品を運ぶ必要がある. 調査の結果, 工場での生産可能量(容量), 顧客への輸送費用,ならびに各顧客における需要量は, 以下のようになっていることが分かった. さて,どのような輸送経路を選択すれば,総費用が最小になるであろうか?

顧客の需要量,工場から顧客までの輸送費用,ならびに工場の生産容量: $$ \begin{array}{c c c c c c c } \hline 顧客 & 1 & 2 & 3 & 4 & 5 & \\ \hline 需要量 &80 & 270 & 250 & 160 & 180 & \\ \hline 工場 & 輸送費用 & & & & & 容量 \\ \hline 1 & 4 & 5 & 6 & 8 & 10 & 500 \\ 2 & 6 &4 & 3 & 5 & 8 & 500 \\ 3 & 9 & 7 & 4 & 3 & 4 & 500 \\ \hline \end{array} $$

ヒント: 最小費用流問題においては,需要(供給は負の需要とみなす)の合計が $0$ でなくてはいけない. 仮想の点を追加することによって,最小費用流問題に帰着せよ.

問題(多期間生産計画問題)

1つの製品の生産をしている工場を考える. 在庫費用は1日あたり,1トンあたり1万円とする. いま7日先までの需要が分かっていて,7日分の生産量と在庫量を決定したい. 各日の需要は,以下の表のようになっている. 工場の1日の稼働時間は $8$時間,製品1トンあたりの製造時間は$1$時間としたとき, 稼働時間上限を満たした最小費用の生産・在庫量を決定せよ.

1 2 3 4 5 6 7
需要量 5 7 8 2 9 1 3

問題(下限制約)

以下の図に示す最小費用流問題を考える.枝上の数値は「単位フローあたりの費用(容量)」であり,点 $0$ から点 $4$ に $10$ 単位のものを最小費用で流したい.

ただし,点2から点3へ向かう枝のフロー量が $4$以上でなければならないものとする.

このフロー量の下限制約を取り除くことを考える. 下限 $4$ を超過した量を新たなフロー量として $x'_{23}$ と記す.元のフロー量 $x_{23}$ とは $x_{23}= 4+x'_{23}$ の関係がある. 変数 $x_{23}$ を $x'_{23}$ に置き換えることによって, 点2におけるフロー整合条件から点2の需要量は $4$ 増え, 点3におけるフロー整合条件から点3の需要量は $4$減る. また,枝$(2,3)$ の容量(フロー量上限)は,$1(=5-4)$に変更される.

この観察を用いて,下限制約付きの最小費用流を求めよ.

G = nx.DiGraph()
G.add_node(0, demand=-10)
G.add_node(4, demand=10)
capacity = {(0, 1): 5, (0, 2): 8, (1, 4): 8, (2, 1): 2, (2, 3): 5, (3, 4): 6}
G.add_weighted_edges_from(
    [(0, 1, 10), (0, 2, 5), (1, 4, 1), (2, 1, 3), (2, 3, 1), (3, 4, 6)]
)
for (i, j) in G.edges():
    G[i][j]["capacity"] = capacity[i, j]
pos = {0: (0, 1), 1: (1, 2), 2: (1, 0), 3: (2, 0), 4: (2, 2)}
edge_labels = {}
for (i, j) in G.edges():
    edge_labels[i, j] = f"{ G[i][j]['weight'] }({ G[i][j]['capacity']})"
plt.figure()
nx.draw(G, pos=pos, with_labels=True, node_size=1000)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()

問題(ナプキンのクリーニング) (難)

あなたはホテルの宴会係だ.あなたは1週間に使用するナプキンを手配する必要がある. 各日の綺麗なナプキンの需要量は平日は $100$枚,土曜日と日曜日は $125$枚だ. 新しいナプキンを購入するには $100$円かかる. 使用したナプキンはクリーニング店で洗濯して綺麗なナプキンにすることができるが, 早いクリーニング店だと1日で1枚あたり $30$円かかり, 遅いクリーニング店だと2日で1枚あたり $10$円かかる. 月曜の朝のナプキンの在庫が $0$ としたとき,需要を満たす最適なナプキンの購入ならびにクリーニング計画をたてよ.

ヒント: この問題は下限付きの最小費用流問題に帰着できる.

さらに、上のナプキンのクリーニング問題において, 日曜末の在庫を月曜の朝に使うことができると仮定したときの最適なナプキンのクリーニング計画をたてよ.

クリーク

最大クリーク問題については,以下を参照

https://scmopt.github.io/opt100/18clique.html

問題 ($8$-クイーン問題)

$8 \times 8$ のチェス盤に $8$個のクイーンを置くことを考える. チェスのクイーンとは,将棋の飛車と角の両方の動きができる最強の駒である. クイーンがお互いに取り合わないように置く配置を1つ求めよ.

将棋を知らない人のために言い換えると,$8 \times 8$ のマス目に,同じ行(列)には高々1つのクイーンを置き, 左下(右下)斜めにも高々1つのクイーンを置くような配置を求める問題である.

ヒント: 実は,この問題は安定集合問題の特殊形である. グラフは $i$ 行,$j$ 列のマス目を点とみなして,クイーンが取り合うとき点の間に枝をはれば良い.

ちなみに斜めでクイーンが取り合うかどうかを判定するのは,$i-j$ が同じ(右下の斜め)か $i+j$ が同じか(左下の斜め)で判定すれば良い.