巡回セールスマン問題

巡回セールスマン問題（Traveling Salesman Problem）は、すべての都市を一度だけ訪れ、最短距離で戻ってくる経路を求める問題です。

以下は、NetworkXを使用して巡回セールスマン問題を解く例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import networkx as nx
import matplotlib.pyplot as plt

# 5つの都市の座標を設定
positions = {1: (0, 0), 2: (1, 1), 3: (2, 0), 4: (3, 1), 5: (4, 0)}

# 距離を計算する関数を定義
def distance(u, v):
    x1, y1 = positions[u]
    x2, y2 = positions[v]
    return ((x1-x2)**2 + (y1-y2)**2)**0.5

# グラフを作成
G = nx.Graph()
G.add_nodes_from(positions.keys())
for u in positions:
    for v in positions:
        if u < v:
            G.add_edge(u, v, weight=distance(u, v))

# 巡回セールスマン問題を解く
tsp = list(nx.algorithms.approximation.traveling_salesman_problem(G))

# 解を表示
print("最短距離の順序：", tsp)
print("最短距離：", sum(distance(u, v) for u, v in zip(tsp, tsp[1:]+tsp[:1])))

# グラフを可視化
pos = positions
nx.draw(G, pos=pos, with_labels=True)
nx.draw_networkx_edges(G, pos=pos, edgelist=[(u, v) for u, v in zip(tsp, tsp[1:]+tsp[:1])], edge_color='r')
plt.show()

このコードでは、5つの都市の座標を定義し、距離を計算する関数を定義しています。

その後、座標をノードとし、距離をエッジとしたグラフを作成します。

nx.algorithms.approximation.traveling_salesman_problem関数を使用して、巡回セールスマン問題を解きます。

解は、最短距離の順序として返されます。

最後に、解を表示しグラフを可視化しています。

[実行結果]

全点対最短経路問題

全点対最短経路問題（All-Pairs Shortest Path Problem）は、グラフ理論の基本的な問題の一つで、ある重みつきグラフにおいて、すべての頂点の間の最短経路を求める問題です。

具体的には、グラフの任意の2つの頂点u, vに対して、uからvへの最短経路の重みを求めます。

この問題は、ワーシャル-フロイド法やダイクストラ法などのアルゴリズムを使用して解決できます。

全点対最短経路問題は、多くの実世界の問題に適用されます。

例えば、都市間の移動にかかる最小コストを求める問題や、ネットワークの最小距離を求める問題などがあります。

また、グラフが静的である場合には、問題の解決に多項式時間がかかりますが、グラフが動的である場合には、解決が困難であることが知られています。

例題

すべての頂点のペアの最短経路を求めてみます。

NetworkXは、ワーシャル-フロイド法を実装した関数 shortest_pathを提供しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import networkx as nx

# 無向グラフの定義
G = nx.Graph()

# 頂点の追加
G.add_nodes_from([1, 2, 3, 4, 5])

# 辺の追加
G.add_edge(1, 2, weight=5)
G.add_edge(1, 3, weight=2)
G.add_edge(1, 4, weight=6)
G.add_edge(2, 3, weight=3)
G.add_edge(2, 4, weight=2)
G.add_edge(3, 4, weight=1)
G.add_edge(3, 5, weight=4)
G.add_edge(4, 5, weight=6)

# 全点対最短経路を求める
all_shortest_paths = dict(nx.shortest_path(G))

# 結果を表示する
for source in all_shortest_paths:
    for target in all_shortest_paths[source]:
        if source != target:
            print(f"{source} から {target} までの最短経路: {all_shortest_paths[source][target]}")

まず、グラフを定義します。

nx.Graph() によって空の無向グラフを定義し、add_nodes_from メソッドを使用して頂点を追加し、add_edge メソッドを使用して辺を追加しています。

また、各辺には weight 属性を設定して、重みつきグラフとして定義しています。

次に、shortest_path 関数を使用して、すべての頂点のペアの最短経路を求めます。

ただし、この方法は全点対最短経路を求めるために必要な計算量が大きくなってしまい、大きなグラフには適用しづらい場合があります。

[実行結果]

1 から 2 までの最短経路: [1, 2]
1 から 3 までの最短経路: [1, 3]
1 から 4 までの最短経路: [1, 4]
1 から 5 までの最短経路: [1, 3, 5]
2 から 1 までの最短経路: [2, 1]
2 から 3 までの最短経路: [2, 3]
2 から 4 までの最短経路: [2, 4]
2 から 5 までの最短経路: [2, 3, 5]
3 から 1 までの最短経路: [3, 1]
3 から 2 までの最短経路: [3, 2]
3 から 4 までの最短経路: [3, 4]
3 から 5 までの最短経路: [3, 5]
4 から 1 までの最短経路: [4, 1]
4 から 2 までの最短経路: [4, 2]
4 から 3 までの最短経路: [4, 3]
4 から 5 までの最短経路: [4, 5]
5 から 3 までの最短経路: [5, 3]
5 から 4 までの最短経路: [5, 4]
5 から 1 までの最短経路: [5, 3, 1]
5 から 2 までの最短経路: [5, 3, 2]

すべての頂点のペアの最短経路を求めることができました。

問題

ある男女10人のグループがあり、男女間には好意があると仮定します。

このグループを、男女のペアを作ることができるようにマッチングさせることを考えます。

ただし、それぞれの男性・女性が同時に複数の異性とのペアを持てないものとします。

以下の男女間の好意度が与えられています。

この好意度を最大化するように、マッチングを決定してください。

解法

NetworkXライブラリを使ってグラフを作成します。

このグラフのノードは男女それぞれの番号で表されます。

辺には好意度に対応する重みが付いています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import networkx as nx

# グラフを定義する
G = nx.Graph()
G.add_nodes_from(["F1", "F2", "F3", "F4", "F5"], bipartite=0)
G.add_nodes_from(["M1", "M2", "M3", "M4", "M5"], bipartite=1)
G.add_weighted_edges_from([
    ("F1", "M1", 70), ("F1", "M2", 90), ("F1", "M3", 80), ("F1", "M4", 80), ("F1", "M5", 70),
    ("F2", "M1", 60), ("F2", "M2", 10), ("F2", "M3", 80), ("F2", "M4", 70), ("F2", "M5", 60),
    ("F3", "M1", 70), ("F3", "M2", 70), ("F3", "M3", 100), ("F3", "M4", 70), ("F3", "M5", 60),
    ("F4", "M1", 80), ("F4", "M2", 80), ("F4", "M3", 80), ("F4", "M4", 50), ("F4", "M5", 60),
    ("F5", "M1", 90), ("F5", "M2", 90), ("F5", "M3", 90), ("F5", "M4", 90), ("F5", "M5", 30)
])

# 最大重みマッチングを求める
max_matching = nx.max_weight_matching(G)
print(max_matching)

NetworkXライブラリを用いて、与えられたグラフの最大重みマッチングを求めています。

まず、nx.Graph()を使って空のグラフを定義し、Gという変数に格納しています。

次に、add_nodes_fromを使って、グラフのノードを追加しています。

ここでは、[“F1”, “F2”, “F3”, “F4”, “F5”]と[“M1”, “M2”, “M3”, “M4”, “M5”]という2つの集合を作り、それぞれに対してbipartite=0とbipartite=1という属性を付与しています。

これによって、グラフが二部グラフであることを示しています。

その後、add_weighted_edges_fromを使って、グラフの辺を追加しています。

ここでは、各辺に対して、始点、終点、重みを設定しています。

最後に、nx.max_weight_matchingを使って、最大重みマッチングを求め、結果をmax_matchingに格納しています。

[実行結果]

{('F4', 'M1'), ('F1', 'M2'), ('M4', 'F5'), ('M3', 'F3'), ('F2', 'M5')}

最大重みマッチングによって、以上のような男女のペアを作ることができました。

SNS分析

SNS上で、あるユーザーが自分の友達の友達の中で最も人気がある人を見つけるために、ネットワーク分析を行いたいと考えています。

この問題を解決するために、与えられたSNSグラフ内で、指定されたユーザーの友達の友達の中で最も人気がある人を見つける関数を実装してください。

解法

以下は、この問題に対するNetworkXによる実装例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import networkx as nx

def find_most_popular_friend_of_friends(G, user):
    """
    指定されたユーザーの友達の友達の中で最も人気がある人を見つける関数

    Parameters
    ----------
    G : NetworkXのグラフオブジェクト
        SNSグラフ
    user : ノード
        検索対象のユーザー

    Returns
    -------
    ノード
        最も人気があるユーザー
    """
    # userの友達を取得
    friends = set(nx.neighbors(G, user))

    # userの友達の友達を取得
    friends_of_friends = set()
    for friend in friends:
        friends_of_friends.update(nx.neighbors(G, friend))

    # userとその友達の友達を除く
    friends_of_friends.discard(user)
    friends_of_friends.difference_update(friends)

    # 各ノードの次数を計算
    degrees = G.degree(friends_of_friends)

    # 次数の降順にソート
    sorted_degrees = sorted(degrees, key=lambda x: x[1], reverse=True)

    # 最も人気のあるユーザーを返す
    return sorted_degrees[0][0]

この関数は、与えられたSNSグラフ内で指定されたユーザーの友達の友達の中で最も人気がある人を見つけるために使用できます。

与えられたユーザーの友達の友達を取得し、各ノードの次数を計算して、次数が最大のノードを返します。

動作確認

テスト用のデータを作成して、上記の関数を使用して解決してみましょう。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import networkx as nx

# SNSグラフを作成
G = nx.Graph()
G.add_edges_from([
    ('Alice', 'Bob'),
    ('Alice', 'Charlie'),
    ('Bob', 'David'),
    ('Bob', 'Eve'),
    ('Charlie', 'David'),
    ('Charlie', 'Frank'),
    ('David', 'Eve'),
    ('Eve', 'Frank'),
    ('Eve', 'Grace'),
    ('Frank', 'Grace')
])

# 'Alice'の友達の友達で最も人気がある人を見つける
most_popular_friend_of_friends = find_most_popular_friend_of_friends(G, 'Alice')

print(f"Most popular friend of friends of Alice: {most_popular_friend_of_friends}")

このコードでは、GというSNSグラフを作成し、find_most_popular_friend_of_friends関数を使用して、’Alice’の友達の友達で最も人気がある人を見つけています。

出力結果は以下の通りになります。

[実行結果]

Most popular friend of friends of Alice: Grace

与えられたSNSグラフ内で指定されたユーザーの友達の友達の中で最も人気がある人を見つけることができました。

強連結グラフ

強連結グラフとは、グラフ上の任意の2つの頂点間に有向パスが存在するグラフのことです。

強連結グラフの判定には、コサラージュのアルゴリズムが使用されます。

1. 与えられたグラフGに対して、グラフGの転置グラフGTを作成する。
2. Gの任意の頂点vからDFSを行い、訪れた頂点をスタックに追加する。
3. スタックの頂点を逆順にした順序で、GTに対してDFSを行い、訪れた頂点の集合を得る。
4. スタックに残っている頂点がある場合、その頂点からDFSを再開し、訪問順を追加していく。
5. 2-4を繰り返し、スタックが空になった場合、グラフGが強連結グラフであることが示される。

以下は、上記のアルゴリズムをPythonコードで実装した例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import networkx as nx

# グラフの作成
G = nx.DiGraph()
G.add_nodes_from([1, 2, 3, 4])
G.add_edges_from([(1, 2), (2, 3), (3, 1), (3, 4)])

# 転置グラフの作成
GT = G.reverse(copy=True)

# DFSを行い、スタックに追加
stack = []
visited = set()
for v in G.nodes:
    if v not in visited:
        visited.add(v)
        stack.append(v)
        while stack:
            node = stack[-1]
            neighbors = list(G.neighbors(node))
            unvisited = [n for n in neighbors if n not in visited]
            if unvisited:
                n = unvisited[0]
                visited.add(n)
                stack.append(n)
            else:
                stack.pop()

# スタックから頂点を逆順にして、転置グラフに対してDFSを行う
visited = set()
while stack:
    node = stack.pop()
    if node not in visited:
        visited.add(node)
        t_neighbors = list(GT.neighbors(node))
        for n in t_neighbors:
            if n not in visited:
                stack.append(n)

if len(visited) == len(G.nodes):
    print("グラフは強連結グラフです")
else:
    print("グラフは強連結グラフではありません")

上記のコードは、与えられたグラフが強連結グラフである場合、”グラフは強連結グラフです”と出力します。

強連結グラフが強連結グラフでない場合、”グラフは強連結グラフではありません”と出力されます。

このアルゴリズムは、与えられたグラフGに対して、転置グラフGTを作成し、GとGTのDFSを行うことで、強連結グラフであるかどうかを判断します。

GとGTのDFSを行うことで、G上の任意の2つの頂点間に有向パスが存在することを確認することができます。

そして、Gが強連結グラフであるためには、GとGTのDFSによって訪れた頂点が全て同一である必要があります。

このアルゴリズムは、時間計算量がO(V+E)であり、高速に強連結グラフかどうかを判断できます。

グラフ理論では、強連結グラフは重要な役割を持っており、多くのアルゴリズムに応用されます。

強連結グラフの判定アルゴリズムを理解することで、グラフ理論の基礎的な概念を深く理解することができます。

最大流問題

最大流問題は、与えられたグラフにおいて、ある2つの頂点を指定して、それらの間に最大量の流れを流す問題です。

以下は、NetworkXを使用して最大流問題を解く例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import networkx as nx

# グラフを作成
G = nx.DiGraph()

G.add_nodes_from(['S', 'A', 'B', 'C', 'D', 'T'])

G.add_edges_from([('S', 'A', {'capacity': 10}),
                  ('S', 'C', {'capacity': 5}),
                  ('A', 'B', {'capacity': 9}),
                  ('A', 'D', {'capacity': 4}),
                  ('B', 'T', {'capacity': 8}),
                  ('C', 'D', {'capacity': 3}),
                  ('C', 'T', {'capacity': 7}),
                  ('D', 'B', {'capacity': 6}),
                  ('D', 'T', {'capacity': 9})])

# 最大流を求める
max_flow_value, flow_dict = nx.maximum_flow(G, 'S', 'T', capacity='capacity')

# 結果を表示する
print('Maximum Flow Value:', max_flow_value)
print('Flow Dictionary:', flow_dict)

上記の例では、6つの頂点を持つグラフが与えられています。

SとTはそれぞれ始点と終点を表し、他の頂点は中間点として機能します。

各辺は容量を持ち、それが最大流を制限するものです。

maximum_flow関数は、グラフ、始点、終点、容量属性を受け取り、最大流量とフローの辞書を返します。

capacity引数は、各辺の容量を指定する属性名を表します。

実行結果は以下のようになります。

[実行結果]

Maximum Flow Value: 15
Flow Dictionary: {'S': {'A': 10, 'C': 5}, 'A': {'B': 8, 'D': 2}, 'B': {'T': 8}, 'C': {'D': 0, 'T': 5}, 'D': {'B': 0, 'T': 2}, 'T': {}}

この結果により、グラフの始点から終点に15の最大流量が流れることがわかります。

また、各辺のフローも辞書として表示されます。

ループ検出

ループ検出の例題として、以下のような有向グラフを考えてみましょう。

A -> B -> C -> D -> E

このグラフにはループが含まれていません。

しかし、次のようなグラフを考えてみましょう。

A -> B -> C -> D -> E -> A

このグラフには、ノードAからノードEに至るループが含まれています。

このグラフでループを検出するには、NetworkXのsimple_cycles関数を使用することができます。

以下は、コード例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import networkx as nx

# グラフを作成する
G = nx.DiGraph()
nodes = "ABCDE"
for i in range(len(nodes)):
    G.add_node(nodes[i])
    if i < len(nodes) - 1:
        G.add_edge(nodes[i], nodes[i+1])
G.add_edge(nodes[-1], nodes[0])

# ループを検出する
loops = list(nx.simple_cycles(G))
if len(loops) > 0:
    print("ループを検出しました:")
    print(loops)
else:
    print("ループは検出されませんでした。")

出力結果は以下のようになります。

[実行結果]

ループを検出しました:
[['D', 'E', 'A', 'B', 'C']]

このように、simple_cycles関数を使用することで、グラフ上のループを検出することができます。

次数

グラフ理論において、頂点の次数とは、その頂点に接続された辺の本数のことを指します。

グラフ理論では、次数は頂点の重要な特徴量の1つであり、グラフの性質を表すために用いられます。

例えば、無向グラフにおいて全ての頂点の次数が偶数である場合、オイラー路と呼ばれる全ての辺を1度だけ通るパスが存在することが知られています。

問題

以下のグラフの各頂点の次数を求めて下さい。

   1---2---3
      /    |
     /     |
   4-------5

ソースコード

以下のようにPythonコードを書くことができます。

1
2
3
4
5
6
7
8
9

import networkx as nx

# グラフを作成する
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2, 4), (4, 5), (5, 3)])

# 各頂点の次数を計算する
degrees = dict(G.degree())
print(degrees)

実行すると、以下のような出力が得られます。

[実行結果]

{1: 1, 2: 3, 3: 2, 4: 2, 5: 2}

これは、頂点1の次数が1、頂点2の次数が3、頂点3の次数が2、頂点4の次数が2、頂点5の次数が2であることを示しています。

クラスタリング問題

クラスタリング問題とは、データセットをグループに分割する問題です。

グループ内のデータは互いに似ており、異なるグループのデータとは異なる特徴を持っています。

この問題は、機械学習やデータマイニング、ネットワーク解析などの分野でよく用いられます。

クラスタリングによって得られたグループは、同じグループ内のデータが似ているため、そのグループに属するデータの特徴をより深く理解することができます。

また、異なるグループのデータの違いを明確にすることができます。

クラスタリングは、顧客分類、マーケティング分析、医療診断、画像処理、自然言語処理などの分野で幅広く使用されています。

例題

クラスタリング問題の例を１つ挙げます。

Zachary’s karate clubとして知られる、34人のメンバーとそのつながりを示すグラフを用いて、クラスタリングを行います。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import networkx as nx
import matplotlib.pyplot as plt
from networkx.algorithms import community

# グラフの読み込み
G = nx.karate_club_graph()

# グラフの可視化
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
plt.show()

# クラスタリング
communities = community.greedy_modularity_communities(G)

# クラスタリング結果の表示
for i, c in enumerate(communities):
    print("Cluster ", i+1, ": ", c)

# クラスタリング結果をグラフに反映
color_map = []
for node in G:
    for i, c in enumerate(communities):
        if node in c:
            color_map.append(i)
nx.draw(G, pos, node_color=color_map, with_labels=True)
plt.show()

このコードでは、まずグラフを読み込み、可視化します。

次に、community.greedy_modularity_communities()を使用して、グラフをクラスタリングします。

最後に、クラスタリング結果をグラフに反映し、色分けして表示します。

この例では、Zachary’s karate clubグラフは3つのクラスターに分割されます。

各クラスターは、それぞれのメンバーのつながりを考慮して形成されていることがわかります。

[実行結果]

自然災害問題

自然災害に関する問題の一つとして、道路ネットワーク上での交通渋滞の発生があります。

以下のようなシナリオを考えてみましょう：

🔹ある地域において、地震が発生し、複数の道路が通行不能になった。
🔹この地域には複数の車両が存在し、それぞれの車両が目的地に到達するために、どのルートを取るかを決定しなければならない。
🔹通行可能なルートは限られており、道路の通行状況は車両数に応じて変化する。
🔹車両が選択するルートによって、交通渋滞が発生する可能性がある。

このような問題を解くために、以下のような手順でNetworkXを使用することができます。

1. 道路ネットワークのグラフを作成する。
   グラフのノードは交差点や道路の始点・終点とし、エッジは道路とし、エッジの重みはその道路の通行可能度合いとする。
2. 車両の現在地と目的地をノードとして指定する。
3. NetworkXの最短経路アルゴリズムを使用して、車両が最短時間で目的地に到達できる経路を計算する。
4. 計算された最短経路を実際に走行した場合の交通渋滞の発生確率を評価する。

解法・ソースコード

交通渋滞の発生確率を評価する上記の例題をnetworkxを用いて実装します。

具体的には、以下の手順でグラフを作成し、最短経路を計算して、最短経路上での交通渋滞の発生確率を評価しています。

1. グラフを作成する

1
2

G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2, 4), (4, 5)])

まず、NetworkXを用いてグラフを作成します。ここでは、4つのノードと4つのエッジを持つグラフを作成しています。

2. エッジに重みを付ける

1
2

for (u, v) in G.edges():
    G[u][v]['weight'] = random.uniform(0.1, 1.0)

次に、各エッジにランダムな重みを付けます。

ここでは、0.1から1.0の範囲の乱数を用いて重みを設定しています。

3. ノード1からノード5への最短経路を計算する

1
2

path = nx.shortest_path(G, source=1, target=5, weight='weight')
print(f"Shortest path: {path}")

nx.shortest_path関数を用いて、ノード1からノード5までの最短経路を計算します。

weight引数には、エッジの重みを指定しています。

計算された最短経路をpath変数に格納し、print関数を用いて表示しています。

4. 計算された最短経路を実際に走行した場合の交通渋滞の発生確率を評価する

1
2
3
4
5
6
7
8

prob = 1.0
for i in range(len(path) - 1):
    u = path[i]
    v = path[i + 1]
    weight = G[u][v]['weight'] + random.uniform(-0.1, 0.1)
    G[u][v]['weight'] = max(weight - 0.1, 0)  # 通行可能度合いを減少させる
    prob *= weight  # 経路上のエッジの通行可能度合いの積を計算する
print(f"Probability of traffic congestion: {1 - prob:.3f}")

最後に、計算された最短経路上での交通渋滞の発生確率を評価します。

prob変数には、経路上のエッジの通行可能度合いの積を格納します。

forループで、最短経路上の各エッジについて、エッジの通行可能度合いをランダムに減少させ、prob変数にそのエッジの通行可能度合いを乗じます。

最後に、1 - probを計算することで、交通渋滞の発生確率を評価します。

なお、エッジの通行可能度合いの減少幅は、0から0.1の範囲の乱数を用いて決定しています。

以上の手順で、最短経路上での交通渋滞の発生確率を評価することができます。

[実行結果（例）]

Shortest path: [1, 2, 4, 5]
Probability of traffic congestion: 0.953

ノード1からノード5への最短経路は[1, 2, 4, 5]となりました。

そして、この経路上のエッジの通行可能度合いの積を計算することで、交通渋滞の発生確率を評価しました。

結果として、この経路上で交通渋滞が発生する確率は0.953となりました。