グラフ理論

このページでは、有向グラフと無向グラフ、オイラーグラフとハミルトングラフの違い、隣接行列での表し方、ダイクストラ法で最短経路を求める手順がわかります。

  • 記号の書き方(このメモのルール):

    • 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬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グループをまたぐ辺だけ)
  • 隣接行列(頂点×頂点)/接続行列(頂点×辺)
  • 行列表現(大きいが計算しやすい)/リスト表現(疎なとき省スペース)

← 01 基礎理論の目次に戻る

タイトルとURLをコピーしました