Skip to content

Functional Graph

概要

N 頂点 N 辺の有向グラフの内、それぞれの頂点の出次数が 1 のものを Functional Graph と呼ぶ。各頂点から \(t = f(v)\) のように遷移先が決定するから。

下記のような性質がある。

  1. 各連結成分ごとに閉路が存在する。つまり 連結成分の個数 = 閉路の個数 となる
  2. 閉路は各連結成分ごとに 1 つのみ
  3. 連結成分ごとに必ず閉路が存在する + 辺数が N = 任意の点から N 回移動したときの頂点は閉路上の頂点になる。

参考