$NetworkX$¶

注意：$Jupyter$上でグラフを描画する際，大きなグラフを描画しないこと．¶

1. グラフの作成¶

以下の図のネットワークを作成せよ¶

%matplotlib inline
import networkx as nx
G = nx.Graph()
G.add_edges_from([("Gaddafi", "Beth"), ("Gaddafi", "Reagan"),("Gaddafi", "Clinton"),("Gaddafi", "Mitterand"), ("Gorbachev","Beth"), ("Clinton", "Beth")])
nx.draw(G, with_labels = True)

問1 山手線と中央線と丸ノ内線の駅名をノードとしたグラフを生成せよ（ノード名はローマ字）¶

但し，サーバーに対する負荷を軽減するため，以下の制約の元実行せよ．¶

$山手線：新宿，池袋，田端，渋谷，品川，東京$
$中央線：新宿～東京の区間$
$丸ノ内線：新宿，四谷，霞が関，東京$

問2 ノードのカラーを変更せよ¶

$山手線：黄緑色$
$中央線：橙色$
$丸ノ内線：赤色$
$乗換駅：白色$

問3 緯度経度を参照し，位置情報を与えよ¶

参考URL：http://www.odekakemap.com/station/

但し，緯度の数値は2倍したものを入れよ¶

2. クリーク¶

例題の最大安定集合を求めよ¶

G_bar = nx.complement(G)
print(nx.graph_clique_number(G_bar))

問1. Twitterにおける相互フォロー間の会話¶

Twitterは，自分の投稿と予め「フォロー」をしたユーザーの投稿が見えるものである．
以下のテキストデータは，前者が後者をフォローしていることを表している．（上から順に，AさんがBさんをフォローしている，AさんがCさんをフォローしている…）
まずは，以下のテキストデータを読み込み，相互フォローをしている人たちのネットワークを構成せよ．
$Hint:$前者，後者両方から枝を伸びているものを抽出する

問2．最大安定集合の値を求めよ（相互フォローが最大となる集合）¶

問3. 最大安定集合の値を持つ組み合わせを全て列挙せよ．¶

3.閉路¶

G=nx.Graph ( )
G.add_edges_from([(1, 2), (1, 5), (2, 3), (2, 6), (3, 4), (3 ,7), (4, 8),
                                (5, 6), (6, 7), (7, 8), (2, 9), (6, 9), (3, 10), (7, 10)])
print(nx.is_eulerian(G))
for e in nx.eulerian_circuit(G):
    print(e, end=" ")

G=nx.grid_2d_graph(2,2)
for e in nx.eulerian_circuit(G):
    print(e, end=" ")

問枝が一本ずつあるグラフ2種類（G.edges=[(0,1)], H.edges=[("a","b")]）のデカルト積グラフのオイラー閉路を求めよ¶

4．マッチング¶

G=nx.grid_2d_graph(3,4)
print(nx.maximal_matching(G))
print(nx.max_weight_matching(G))

問 Twitter問題のフォロー間における極大マッチング，最大マッチングを求めよ¶

注意：今回作成するグラフは，片方から枝が伸びているものも含めるものとする．（相互フォローではなくても枝とみなす）¶

5. 最小木¶

G=nx.Graph()
G.add_weighted_edges_from([("Arigator","WhiteBear",2),("Arigator","Bull",1),
                                                  ("Bull","WhiteBear",1),("Bull","Shark",3),
                                                  ("WhiteBear","Condor",3),("WhiteBear","Shark",5),
                                                  ("Shark","Condor",4)])
print(nx.minimum_spanning_tree(G).edges())

問下図のグラフの最小木を求めよ¶

5地点間に敷設計画のある道路があるとする．
数値は地点間の距離として捉え，最小の距離で全ての地点間を行き来できる道路の敷設計画を完成させよ

6. 最短路¶

枝の数字は，運賃を表す．

G=nx.DiGraph()
G.add_edges_from([("s",1),("s",2),(1,2),(1,"t"),(2,1),(2,3),(3,"t")])
print(nx.has_path(G,"s","t"))
path=nx.shortest_path(G)
path["s"]["t"]
print(nx.single_source_shortest_path(G,"s"))
print(nx.predecessor(G,"s"))
print(nx.bellman_ford(G,"s"))

G=nx.DiGraph()
G.add_weighted_edges_from([("s",1,10),("s",2,5),(1,2,2),(1,"t",1),(2,1,3),(2,3,2),(3,"t",6)])
print(nx.dijkstra_path(G,"s","t"))
print(nx.single_source_dijkstra_path(G,"s"))

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

問2. グラフの作成で出題したグラフを使用し，枝に時間と料金の属性を与えて新宿から東京までの最短経路をそれぞれ求めよ．¶

7. 最大流¶

枝の数字は移動可能量を表す．

G=nx.DiGraph()
G.add_weighted_edges_from([("s",1,5),("s",2,8),(1,"t",8),(2,1,2),(2,3,5),(3,"t",6)])
print(nx.maximum_flow(G,"s","t",capacity="weight"))
print(nx.minimum_cut(G,"s","t",capacity="weight"))

問地点4から地点3までの最大流を求めよ¶

7. 最小費用流¶

枝に付随する数字は地点間の輸送費用，括弧内の数字は移動可能量の上限を表す．

G=nx.DiGraph()
G.add_node("s",demand=-10)
G.add_node("t",demand=10)
G.add_edge("s",1,weight=10, capacity=5)
G.add_edge("s",2,weight=5, capacity=8)
G.add_edge(2,1,weight=3,capacity=2)
G.add_edge(1,"t",weight=1,capacity=8)
G.add_edge(2,3,weight=2,capacity=5)
G.add_edge(3,"t",weight=6,capacity=6)
print(nx.network_simplex(G))

例題と同様な形で，10単位の氷を以下のグラフで地点1から地点6に運ぶときにどのように氷を運べば最も安い費用で氷を運ぶことが可能であるか求めよ