このページでは、有向グラフと無向グラフ、オイラーグラフとハミルトングラフの違い、隣接行列での表し方、ダイクストラ法で最短経路を求める手順がわかります。
-
記号の書き方(このメモのルール):
- 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬A、集合なら Aᶜ と書く
- 2乗などのべき乗は 2³、σ² のように書く。log の底は log₂ のように書く
-
一言で言うと:
- 点(頂点)と線(辺)のつながりを扱う話。ネットワークの経路探索、工程の順番、最短経路などの土台になる。
向きの有無(有向・無向)→ 閉路の有無(サイクリック)→ グラフの種類 → コンピュータでの表し方 → 最短経路(重みつきグラフ)
覚え方の軸
- グラフは2つの切り口で分ける:
- 向きがあるか(有向/無向)、ぐるっと戻れるか(サイクリック/非サイクリック)
- 「1回だけ通る」のが辺か頂点か:
- オイラー=すべての辺を1回ずつ(一筆書き)、ハミルトン=すべての頂点を1回ずつ
- 表し方は3つ:
- 配列、行列(隣接行列)、リスト。行列は大きくなりやすいので、0が多い(疎な)ときはリスト
- 隣接行列 M の M² は「辺2本の経路の数」
- ダイクストラ法は「近い頂点から1つずつ確定」
有向グラフ・無向グラフ:線に向きがあるか
- グラフ:
- 頂点の集合Vと、2つの頂点を結ぶ辺の集合Eからなる図形。G=(V,E)と書く
- 頂点(Vertex):
- 節点ともいう
- 辺(Edge):
- 枝ともいう
- 有向グラフ:
- 辺に向き(vᵢ→vⱼ)があるグラフ
- 無向グラフ:
- 辺に向きがないグラフ
- 順序対(vᵢ,vⱼ):
- 有向グラフで、辺の向きを表したもの
- 始点:
- vᵢ(辺が出ていく頂点)
- 終点:
- vⱼ(辺が入ってくる頂点)
- vᵢとvⱼは「隣接している」という
- vᵢをvⱼの先行点、vⱼをvᵢの後続点ともいう
- 入次数:
- 頂点に入ってくる辺の数
- 出次数:
- 頂点から出ていく辺の数
- 次数:
- 入次数と出次数の和
- 自己ループ:
- 始点と終点が同じ頂点である辺
- 多重辺(並列辺):
- 始点と終点が同じ組である、複数の辺
サイクリックグラフ:ぐるっと戻れるか
- 閉路(cycle):
- ある頂点から出発して、同じ頂点に戻ってこられる道
- サイクリックグラフ:
- 閉路をもつ有向グラフ
- 非サイクリックグラフ:
- 閉路をもたない有向グラフ
- トポロジカル順序:
- 非サイクリックグラフで、すべての辺(vᵢ,vⱼ)について、iがjより前になるように頂点を一列に並べた順序
- 例:
- 辺が A→B、A→C、B→D、C→D なら、A−B−C−D や A−C−B−D がトポロジカル順序
- 1つのグラフに、トポロジカル順序が複数あることもある
小道(trail)と経路(path)
- 歩道:
- 連続した頂点と辺を結んだもの。(v₁,e₁,v₂,e₂,…)のように頂点と辺を交互に書く
- 小道(trail):
- すべての辺が異なる歩道(同じ頂点は2回通ってもよい)
- 経路(path):
- すべての頂点が異なる歩道
- 回路(circuit):
- 同じ頂点に戻る小道(辺が全部異なる)
- 閉路(cycle):
- 同じ頂点に戻る経路(頂点が全部異なる)
グラフの種類
| 種類 | 中身 |
|---|---|
| 多重グラフ | 自己ループや多重辺をもつグラフ |
| 完全グラフ | どの2頂点の間も1本の辺で結ばれているグラフ。頂点数nの完全グラフを Kₙ と書く |
| 2部グラフ | 頂点を2つのグループV₁とV₂に分けられ、どの辺もV₁とV₂をまたいでいるグラフ(同じグループどうしを結ぶ辺がない) |
| オイラーグラフ | すべての辺をちょうど1回ずつ通って出発点に戻る回路(オイラー回路)をもつグラフ。一筆書きができる |
| ハミルトングラフ | すべての頂点をちょうど1回ずつ通って出発点に戻る閉路(ハミルトン閉路)をもつグラフ |
| 正則グラフ | すべての頂点の価数(その頂点につながる辺の本数)が等しいグラフ |
- 単純グラフ:
- 自己ループも多重辺もないグラフ
- 2部グラフの関係:
- V₁∪V₂=V、V₁∩V₂=∅(全部をちょうど2つに分ける)
- ★試験:
- 2部グラフとハミルトン閉路は午前(科目A)で、オイラーグラフは午後(科目B)で出題されている
グラフの表現:コンピュータでどう持つか
- 例のグラフ:
- 頂点①〜④、辺は ①−②、②−③、③−④、④−① の4本(無向。四角形の形)
- 配列表現:
- 辺の両端の頂点を、2つの配列に入れる
- 例:
- vᵢ=[①,①,②,③]、vⱼ=[②,④,③,④]
- 行列表現:
- 隣接行列(頂点数×頂点数の正方行列)で表す。vᵢとvⱼを結ぶ辺があれば要素(i,j)を1、なければ0
- 例の隣接行列 M:
| ① | ② | ③ | ④ | |
|---|---|---|---|---|
| ① | 0 | 1 | 0 | 1 |
| ② | 1 | 0 | 1 | 0 |
| ③ | 0 | 1 | 0 | 1 |
| ④ | 1 | 0 | 1 | 0 |
- 1行2列の1は、①と②を結ぶ辺があるという意味
- 短所:
- 頂点が多いと行列が大きくなり、記憶域が膨大になる。多くのグラフアルゴリズムは行列の掛け算が必要なので、処理時間もかかる
- 疎(そ):
- 行列の要素のほとんどが0であること。隣接行列が疎なら、動的なデータ構造を使えるリスト表現のほうが効率的
- 接続行列:
- 行が頂点、列が辺に対応する行列。頂点vᵢと辺eⱼがつながっていれば(i,j)を1、それ以外は0
- リスト表現:
- 行列表現の各行を、線形リストで表したもの。隣接リストともいう
- 例:
- ①→②→④、②→③、③→④(④からは何もない)
- 無向グラフでは「①−②」と「②−①」は同じ辺なので、行列の右上部分だけを表せばよく、記憶域を節約できる
- 行列表現の応用(★):
- 隣接行列Mの要素mᵢⱼを「vᵢとvⱼを直接結ぶ辺の本数」とするとき、M²の(i,j)要素は、vᵢとvⱼが1つの頂点をはさんで結ばれる経路(辺2本の経路)の数
- 例のM²:
| ① | ② | ③ | ④ | |
|---|---|---|---|---|
| ① | 2 | 0 | 2 | 0 |
| ② | 0 | 2 | 0 | 2 |
| ③ | 2 | 0 | 2 | 0 |
| ④ | 0 | 2 | 0 | 2 |
- M²の1行3列は、Mの1行目と3列目の掛け算の合計(ベクトルの内積):
- (①①の辺数×①③の辺数)+(①②×②③)+(①③×③③)+(①④×④③)= 0×0+1×1+0×0+1×1 = 2
- 意味:
- ①−②−③ と ①−④−③ の2つの経路がある
- M²の1行2列が0なのは、①から②へ「辺ちょうど2本」で行く経路がないから(四角形の隣どうしは、2本では行けない)
重みつきグラフ:最短経路を探す
- 重みつきグラフ:
- 辺に値(距離やコスト)をもたせたグラフ。重みつきネットワークともいう
- 最短経路問題:
- 始点から目的点までの最短の経路を求める問題
- ダイクストラ法(★):
- 始点の隣から、いちばんコストが小さい頂点を1つずつ確定していき、範囲を広げて、すべての頂点への最小コストを求める
- 手順:
- ①まだ確定していない頂点のうち、始点からのコストが最小の頂点を選んで確定する(*を付ける)
- ②確定した頂点を経由する経路のコストを計算し直す。始点から同じ頂点に入る経路が複数あれば、大きいほうを消す
- ③全部確定するまで①②を繰り返す
- 例:
- 辺:A→B 4、A→C 2、C→B 1、B→D 5、C→D 8
- ①Aの隣で最小はC(2)→ Cを確定(2)
- ②Cを経由:A→C→B=3(A→B 4より小さいので4を消す)、A→C→D=10
- ③残りで最小はB(3)→ Bを確定(3)。Bを経由:A→C→B→D=8(10より小さいので10を消す)
- ④Dを確定(8)
- 確定する順番は C → B → D、最小コストは 8、経路は A→C→B→D
- ★試験では、最小コストだけでなく、各頂点のコストが確定していく順番も問われる
混同しやすいペア
- 有向グラフ(向きあり)/無向グラフ(向きなし)
- 入次数(入ってくる)/出次数(出ていく)/次数(その和)
- 自己ループ(自分に戻る辺)/多重辺(同じ2頂点を結ぶ複数の辺)
- サイクリック(閉路あり)/非サイクリック(閉路なし。トポロジカル順序がある)
- 小道(辺が全部異なる)/経路(頂点が全部異なる)
- 回路(戻る小道)/閉路(戻る経路)
- オイラー(辺を1回ずつ。一筆書き)/ハミルトン(頂点を1回ずつ)
- 完全グラフ(全部の2頂点がつながる)/正則グラフ(全頂点の価数が同じ)/2部グラフ(2グループをまたぐ辺だけ)
- 隣接行列(頂点×頂点)/接続行列(頂点×辺)
- 行列表現(大きいが計算しやすい)/リスト表現(疎なとき省スペース)