点と線で、つながりを表す
グラフとは、点とそれをつなぐ線で、つながりを表したものです。地下鉄の路線図や、学内ネットワークの配線図は、グラフとして扱えます。
「この駅から、あの駅へ行けるか」「回線が1本切れても、全部つながるか」といった問いに、手順で答えられるようになります。
このレッスンのゴール
メモ
つながりをグラフで表して、2つの点を結ぶ経路があるかを調べることができる。
キーワード
| ことば | いみ |
|---|---|
| 頂点 | グラフの点 |
| 辺 | 2つの頂点をつなぐ線 |
| 次数 | 頂点につながっている辺の数 |
| 経路 | 辺をたどって、頂点から頂点へ行く道 |
| 連結 | どの2つの頂点の間にも、経路があること |
| 木 | 連結で、輪のないグラフ |
学生が入力するセルは、このプレビューでは空白です。
頂点と辺で、つながりを表す
グラフは、頂点(点)と辺(2つの頂点をつなぐ線)でできています。駅が頂点、駅と駅をつなぐ線路が辺です。
頂点につながっている辺の数を、その頂点の次数と呼びます。Python では、各頂点の隣を、辞書とリストで表せます。
例: 4つの駅の路線
| 頂点 | 隣の頂点 | 次数 |
|---|---|---|
| A | B、C | 2 |
| B | A、C | 2 |
| C | A、B、D | 3 |
| D | C | 1 |
| 次数の合計 | 8 | |
| 辺の数 | A-B、A-C、B-C、C-D | 4本(8 ÷ 2) |
学生が入力するセルは、このプレビューでは空白です。
次数と辺の数を数える
python3 -c "g = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['C']}; print([len(g[v]) for v in g], sum(len(g[v]) for v in g) // 2)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
辺をたどる経路と、連結
経路は、辺をたどって、ある頂点から別の頂点へ行く道です。表の例では、A から D へ、A → C → D という経路があります。
どの2つの頂点の間にも経路があるグラフを、連結と呼びます。1つでも行けない頂点があれば、連結ではありません。
近い頂点から順に調べる
行ける頂点は、近い順に調べると見つかります。まず出発点を「調べる列」に入れます。列の先頭を取り出し、その隣で、まだ見つけていない頂点を、列の後ろに足します。
列が空になったら終わりです。見つかった頂点が、出発点から行ける頂点です。
手順: A から行ける頂点
| 取り出す頂点 | 新しく見つけた頂点 | 列の中身 |
|---|---|---|
| はじめ | A | A |
| A | B、C | B、C |
| B | なし(A も C も見つけ済み) | C |
| C | D | D |
| D | なし | 空 |
学生が入力するセルは、このプレビューでは空白です。
列を使って行ける頂点を調べる
# 出発点 A から、行ける頂点を近い順に調べます。
graph = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"], "E": []}
found = ["A"]
queue = ["A"]
while len(queue) > 0:
current = queue.pop(0)
for neighbour in graph[current]:
if neighbour not in found:
found.append(neighbour)
queue.append(neighbour)
print("行ける頂点:", found)
print("連結ですか:", len(found) == len(graph))
# E をつなぐには、"D": ["C", "E"] と "E": ["D"] に書きかえて、もう一度実行します。
輪のない連結グラフが木
輪とは、同じ辺を2度通らずに、出発点へ戻る道のことです。木は、連結で、輪のないグラフです。フォルダの階層や会社の組織図が、木の例です。
頂点が n 個の木には、辺がちょうど n - 1 本あります。辺が1本欠けると連結でなくなり、1本増えると輪ができます。
頂点の数と辺の数
| グラフの辺 | 頂点 | 辺 | 連結か | 木か |
|---|---|---|---|---|
| A-B、B-C、C-D | 4 | 3 | はい | はい(辺が 3 = 4 - 1 本) |
| A-B、B-C、A-C、C-D | 4 | 4 | はい | いいえ(輪 A-B-C がある) |
| A-B、B-C、A-C、D だけ離れる | 4 | 3 | いいえ | いいえ(辺は3本でも、連結でない) |
学生が入力するセルは、このプレビューでは空白です。
頂点の数、辺の数、n - 1 との比較
python3 -c "g = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B', 'D'], 'D': ['C']}; n = len(g); e = sum(len(g[v]) for v in g) // 2; print(n, e, e == n - 1)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
「辺が頂点の数より1本少なければ、必ず木だ」と考える人が多くいます。表の3つ目は、辺が n - 1 本ですが、D が離れていて連結ではありません。木かどうかは、連結であることと、辺が n - 1 本であることの両方で決まります。
さらに挑戦
ケーブルが1本切れても、全体がつながったままのネットワークを考えます。木は、どの1本を切っても連結でなくなります。輪があれば、1本切れても残ります。
4台の機器を、どの1本が切れても連結なままつなぐには、辺が最少で何本必要でしょうか。