“ファイバーの計算”（「ファイバーの計算 基本概念」参照）に関する一連の記事のひとつとして、木と林の話を書き始めたのですが、独立した話題として扱えるので、シリーズ記事からは外れた記事にします。木と林は有向グラフの種類のことで、現実世界の植物の話ではありません。
木と林は、“ファイバーの計算”やコンテナ（「有向コンテナと多項式コモナド」、「2-コンテナ」参照）と密接な関係があります。$`\newcommand{\mrm}[1]{ \mathrm{#1} }
\newcommand{\hyp}{\text{－} }
\newcommand{\In}{\text{ in }}
\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\F}[1]{ {{#1}^{-1}} } % fiber
\newcommand{\obj}[1]{ {{#1}\!\downarrow} }
\newcommand{\dimU}[2]{ {{#1}\!\updownarrow^{#2}} }
`$
内容：
グラフの圏と反射的グラフの圏
この記事では有向グラフしか扱わないので、単に「グラフ」と言ったらそれは有向グラフのことだとします。グラフを、圏論的に余前層として定義します。まず、次の図式形状〈shape of diagram〉を考えます。
$`\quad \xymatrix@C+1pc{
\mrm{edge} \ar@/^1pc/[r]^{\mrm{src}} \ar@/_1pc/[r]_{\mrm{trg}}
& \mrm{vert}
}`$
この形状を $`{\bf graph}`$ とします。$`{\bf graph}`$ を圏として扱う必要があれば、2つの恒等射を追加します。
グラフ〈graph〉とは、形状 $`{\bf graph}`$ から集合圏への共変関手のことです。集合圏への共変関手を余前層〈copresheaf〉とも呼びます。グラフの圏〈category of graphs〉は、余前層の圏〈関手圏〉として定義されます。
$`\quad {\bf Graph} := [{\bf graph}, {\bf Set}] \; \in |{\bf CAT}|`$
実は、図式形状がグラフなので、「グラフの定義にグラフ概念を使っている」と指摘されれば、おっしゃるとおりです。しかし、形状の定義には“より素朴な定義”を採用すれば、素朴な定義に基づいて洗練された定義をしているので、循環論法にはなりません。
同じ定義方法で、反射的グラフも定義します。次の形状と等式の組み合わせを $`{\bf refGraph}`$ とします。$`{\bf refGraph}`$ は、圏とみなします。
$`\quad \xymatrix@C+1pc{
\mrm{edge} \ar@/^1pc/[r]^{\mrm{src}} \ar@/_1pc/[r]_{\mrm{trg}}
& \mrm{vert} \ar[l]|{\mrm{self}}
}\\
\quad \mrm{self};\mrm{src} = \mrm{id}_{\mrm{vert} }\\
\quad \mrm{self};\mrm{trg} = \mrm{id}_{\mrm{vert} }
`$
反射的グラフ〈reflexive graph〉*1とは、形状 $`{\bf refGraph}`$ から集合圏への余前層のことです。
$`\quad {\bf RefGraph} := [{\bf refGraph}, {\bf Set}] \; \in |{\bf CAT}|`$
グラフ $`G`$ は、形状 $`{\bf graph}`$ からの共変関手なので、次の値を指定すれば決まります。
- $`G(\mrm{vert}) \in |{\bf Set}|`$
- $`G(\mrm{edge}) \in |{\bf Set}|`$
- $`G(\mrm{src}) \in \mrm{Mor}({\bf Set})`$
- $`G(\mrm{trg}) \in \mrm{Mor}({\bf Set})`$
習慣により、次のように書きます。
- $`\mrm{Vert}(G) \in |{\bf Set}|`$
- $`\mrm{Edge}(G) \in |{\bf Set}|`$
- $`\mrm{src}_G \in \mrm{Mor}({\bf Set})`$
- $`\mrm{trg}_G \in \mrm{Mor}({\bf Set})`$
まとめて書けば：
$`\quad G = (\mrm{Vert}(G), \mrm{Edge}(G), \mrm{src}_G, \mrm{trg}_G) \;\in |{\bf Graph}|`$
反射的グラフなら：
$`\quad G = (\mrm{Vert}(G), \mrm{Edge}(G), \mrm{src}_G, \mrm{trg}_G, \mrm{self}_G) \;\in |{\bf Graph}|`$
グラフの圏 $`{\bf Graph}`$ の射は、グラフのあいだの準同型写像〈準同型射 | homomorphism〉、グラフ射〈graph morphism〉などと呼ばれます。
グラフ $`G, H`$ のあいだの準同型射 $`f`$ は、自然変換なのでその成分で決まります。
- $`f_{\mrm{vert}} : \mrm{Vert}(G) \to \mrm{Vert}(H) \In {\bf Set}`$
- $`f_{\mrm{edge}} : \mrm{Edge}(G) \to \mrm{Edge}(H) \In {\bf Set}`$
まとめて書けば：
$`\quad f = (f_{\mrm{vert}}, f_{\mrm{edge}}) \;: G \to H \In {\bf Graph}`$
自然変換の自然性は次の可換図式になります。
$`\require{AMScd}
\quad
\begin{CD}
\mrm{Edge}(G) @>{f_{\mrm{vert}}}>> \mrm{Edge}(H) \\
@V{\mrm{src}_G}VV @VV{\mrm{src}_H}V \\
\mrm{Vert}(G) @>{f_{\mrm{vert}}}>> \mrm{Vert}(H)
\end{CD}\\
\quad
\begin{CD}
\mrm{Edge}(G) @>{f_{\mrm{edge}}}>> \mrm{Edge}(H) \\
@V{\mrm{trg}_G}VV @VV{\mrm{trg}_H}V \\
\mrm{Vert}(G) @>{f_{\mrm{edge}}}>> \mrm{Vert}(H)
\end{CD}\\
\quad
\text{commutative }\In {\bf Set}
`$
慣用の記法のせいで“自然変換の自然性”に見えないなら、それらしい記法に戻せばいいでしょう。
$`\require{AMScd}
\quad
\begin{CD}
G(\mrm{edge}) @>{\varphi_{\mrm{vert}}}>> H(\mrm{edge}) \\
@V{G(\mrm{src} )}VV @VV{H(\mrm{src} )}V \\
G(\mrm{vert}) @>{\varphi_{\mrm{vert}}}>> H(\mrm{vert})
\end{CD}\\
\quad
\begin{CD}
G(\mrm{edge}) @>{\varphi_{\mrm{edge}}}>> H(\mrm{edge}) \\
@V{G(\mrm{trg}) }VV @VV{H(\mrm{trg} )}V \\
G(\mrm{vert}) @>{\varphi_{\mrm{edge}}}>> H(\mrm{vert})
\end{CD}\\
\quad
\text{commutative }\In {\bf Set}
`$
反射的グラフに関しても同様です。
ついでに、Diag構成（「Diag構成： 圏論的構成法の包括的フレームワークとして」参照）の事例として捉えると、グラフの圏は次のように書けます（反射的グラフの圏はもう少し複雑です）。
$`\quad {\bf Graph} := \mrm{Diag}^{ {\bf Graph}, \mrm{FreeCat}}[{\bf graph}]({\bf Set}) \; \in |{\bf CAT}|
`$
この定義は、ほんとに「$`{\bf Graph}`$ により $`{\bf Graph}`$ を定義している」ので循環論法です*2が、言いたいことは伝わるでしょう。
グラフの構成法
グラフではないナニカからグラフを作ることを考えます。グラフではないナニカとしては次を考えましょう。
- 集合〈set〉
- 順序集合〈ordered set〉（全順序集合である必要はない。）
- 単純遷移系〈simple transition system〉
- 小さい圏〈small category〉
単純遷移系〈simple transition system〉とはラベル付き遷移系〈labeled transition system〉のラベルが1個しかない構造です。集合 $`X`$ と自己写像 $`\alpha :X \to X`$ のペア $`(X, \alpha)`$ として定義できます。単純遷移系は、次の形状に対する余前層としても定義できます。
$`\quad \xymatrix{
\cdot \ar@(ul, ur)[0,0]
}`$
単純遷移系のあいだの準同型写像 $`f`$ も自然変換なので、次の自然性（遷移を保つ）を満たします。
$`\quad \begin{CD}
X @>{f}>> Y\\
@V{\alpha}VV @VV{\beta}V\\
X @>{f}>> Y
\end{CD}\\
\quad \text{commutative }\In {\bf Set}
`$
集合と関数〈写像〉の圏、順序集合と単調関数の圏、単純遷移系と準同型写像の圏、小さい圏と関手の圏（自然変換は考えない）をそれぞれ次のように書きます。
- $`{\bf Set}`$
- $`{\bf Ord}`$
- $`{\bf SimpTranSys}`$
- $`{\bf Cat}^1`$ （右肩の 1 は、2-圏ではなくて1-圏であることを示す。）
集合 $`X`$ を頂点集合とする離散グラフ〈discrete graph〉を $`\mrm{Disc}(X)`$ とします。同様に、集合 $`X`$ を頂点集合とする反射的離散グラフ〈reflexive discrete graph〉を $`\mrm{RefDisc}(X)`$ とします。$`\mrm{RefDisc}(X)`$ は、$`X`$ と同型な辺の集合を持ちます。これらは、グラフを構成する関手になります。
$`\quad \mrm{Disc} : {\bf Set} \to {\bf Graph} \In {\bf CAT}\\
\quad \mrm{RefDisc} : {\bf Set} \to {\bf RefGraph} \In {\bf CAT}
`$
順序集合からグラフを構成する関手は次のように書くとします。
$`\quad \mrm{GOS} : {\bf Ord} \to {\bf Graph} \In {\bf CAT}`$
"GOS" の三文字は Graph from Ordered Set からです。順序集合 $`(X, \le)`$ に対する $`\mrm{GOS}( (X, \le) )`$ は次のようなグラフです。
- 頂点集合は、順序集合の台集合 $`X`$ とする。
- $`x \le y`$ であるとき、頂点 $`x`$ から 頂点 $`y`$ への1本の辺があるとする。
- それ以外の辺はない。
順序集合から作ったグラフは、自動的に反射的グラフになります。よって、次のような構成〈関手〉だと思ってもいいです。
$`\quad \mrm{RGOS} : {\bf Ord} \to {\bf RefGraph} \In {\bf CAT}`$
単純遷移系からグラフを構成する関手は次のように書くとします。
$`\quad \mrm{GSTS} : {\bf SimpTranSys} \to {\bf Graph} \In {\bf CAT}`$
"GSTS" の四文字は Graph from Simple Transition System からです。単純遷移系 $`(X, \alpha)`$ に対する $`\mrm{GSTS}( (X, \alpha) )`$ は次のようなグラフです。
- 頂点集合は、単純遷移系の台集合〈状態空間〉 $`X`$ とする。
- $`y = \alpha(x)`$ であるとき、頂点 $`x`$ から 頂点 $`y`$ への1本の辺があるとする。
- それ以外の辺はない。
小さい圏からグラフ／反射的グラフを構成する関手は次のように書くとします。同じ名前 $`U`$ をオーバーロード〈多義的使用〉します。
$`\quad U : {\bf Cat}^1 \to {\bf Graph} \In {\bf CAT}\\
\quad U : {\bf Cat}^1 \to {\bf RefGraph} \In {\bf CAT}
`$
$`U`$ は圏の構造の一部を忘れる忘却関手〈forgetful functor〉です。
グラフからグラフではないナニカを作る構成法〈関手〉もありますが、今それには触れません。
グラフからグラフを作る構成法をみっつ挙げておきます。ひとつめは、辺の向きの反転です。
$`\quad (\hyp)^\mrm{op} : {\bf Graph} \to {\bf Graph} \In {\bf CAT}`$
グラフ $`G`$ に対して、$`G^\mrm{op}`$ は、辺〈有向辺〉の向きを逆にしたグラフです。$`G`$ の反対グラフ〈opposite graph〉と呼びます。
ふたつめの構成法； 2つのグラフの直積グラフを作れます。
$`\quad (\times) : {\bf Graph}\times {\bf Graph} \to {\bf Graph} \In {\bf CAT}`$
$`G, H`$ がグラフのとき、これらの直積グラフ〈direct product〉を作るには、頂点集合も辺集合も直積をとります。ソース写像とターゲット写像の定義は次のようです。
$`\quad \mrm{scr}_{G\times H} := \mrm{src}_G \times \mrm{src}_H \;: \\
\qquad \mrm{Edge}(G)\times \mrm{Edge}(H) \to \mrm{Vert}(G)\times \mrm{Vert}(H) \In {\bf Set}\\
\quad \mrm{trg}_{G\times H} := \mrm{trg}_G \times \mrm{trg}_H \;: \\
\qquad \mrm{Edge}(G)\times \mrm{Edge}(H) \to \mrm{Vert}(G)\times \mrm{Vert}(H) \In {\bf Set}
`$
みっつめの構成法； 2つのグラフの直和グラフ〈direct sum〉を作れます。頂点集合も辺集合も直和をとります。ソース写像とターゲット写像も直和をとります。
$`\quad (+) : {\bf Graph}\times {\bf Graph} \to {\bf Graph} \In {\bf CAT}`$
特殊なグラフ
無サイクルグラフ〈非輪状グラフ | 非循環グラフ | directed acyclic graph〉は、サイクルを持たないグラフです。DAG〈ダグ〉と略称されます。サイクルがないと色々と扱いやすいのでDAGはよく使われます。
2頂点（同一頂点でもよい）のあいだの辺が1本以下であるグラフは単純グラフ〈simple graph〉と呼びます。圏論の言葉「やせた」を使うなら、やせたグラフ〈thin graph〉となります。単純グラフは、頂点集合のあいだの自己関係〈endo-relation〉と同一視できるので、関係〈relation〉に関する議論を使えます。
グラフ $`G`$ とその頂点 $`v\in \mrm{Vert}(G)`$ に対して、$`v`$ から出る辺〈out-going edge〉達の集合と、$`v`$ に入る辺〈in-coming edge〉達の集合を次のように定義します。
$`\quad \mrm{Out}(G, v) := \{e\in \mrm{Edge}(G) : \mrm{src}(e) = v\} \\
\quad \mrm{In}(G, v) := \{e\in \mrm{Edge}(G) : \mrm{trg}(e) = v\}
`$
$`G`$ の代わりに反対グラフ $`G^\mrm{op}`$ を考えると $`\mrm{Out}`$ と $`\mrm{In}`$ は入れ替わります。
$`\quad \mrm{Out}(G^\mrm{op}, v) = \mrm{In}(G, v)\\
\quad \mrm{In}(G^\mrm{op}, v) = \mrm{Out}(G, v)
`$
入る辺／出る辺の個数〈基数〉に関する条件を付けることがあります。例えば次のような条件です（集合の基数〈cardinality〉は $`\mrm{card}(\hyp)`$ と書き、基数が有限なら、集合の基数は自然数と同一視します）。
- $`\forall v\in \mrm{Vert}(G). \, \mrm{card}(\mrm{Out}(G, v)) \le 1`$
- $`\forall v\in \mrm{Vert}(G). \, \mrm{card}(\mrm{In}(G, v)) \le 1`$
林〈フォレスト | forest〉は次のようなグラフです。
- 無サイクルである。
- すべての頂点で、出る辺は1本以下である（上の一番目の条件）
- （少なくとも1つの）出る辺がない頂点が存在する。出る辺がない頂点をルート〈root | 根〉と呼ぶ。
- どの頂点からも、ルートに至るパスが存在する。
頂点集合と辺集合の有限性を仮定するなら、3番目と4番目の条件は不要です。通常は、頂点集合と辺集合の有限性を仮定しますが、ここでは有限性は仮定しません。
ルートがひとつだけ在る林をツリー〈tree | 木〉と呼びます。ここでは、辺の向きはルートに向かう方向ですが、逆向きで定義することもできます。どちらの向きを採用するかは目的によりますが、単なる気まぐれで決めるときもあります。
林の条件の1番と2番だけを満たすグラフを、ここではプレ林〈pre-forest〉と呼ぶことにします。有限なプレ林は林です。
プレ林 $`F`$ において、ルートの集合を $`\mrm{Root}(F)`$ とします。入る辺がない頂点をリーフ〈leaf | 葉〉と呼び、リーフの集合を $`\mrm{Leaf}(F)`$ とします。
グラフの例
プレ林、林、ツリーの例を挙げます。
$`n \in {\bf N}`$ に対して、長さ〈高さ〉$`n`$ の竹〈bamboo〉は次のように定義します。
- 頂点集合は $`\{0, 1, \cdots, n\}`$ 。頂点は $`(n + 1)`$ 個。
- $`k = 1, \cdots, n`$ に対して、$`k`$ から $`k - 1`$ への辺がある。
- それ以外の辺はない。
長さ $`n`$ の竹を $`\mrm{bamboo}(n)`$ と書きます。$`\mrm{bamboo}(n)`$ はツリーで：
$`\quad \mrm{Root}(\mrm{bamboo}(n)) = \{0\}\\
\quad \mrm{Leaf}(\mrm{bamboo}(n)) = \{n\}
`$
有限個／可算個のグラフの直和を作れるので、竹を寄せ集めて竹林〈bamboo forest〉を作ります。
$`\quad \mrm{Bamboo}_n := \sum_{i = 0}^n \mrm{bamboo}(i)\\
\quad \mrm{Bamboo}_\infty := \sum_{i = 0}^\infty \mrm{bamboo}(i)
`$
$`\mrm{Bamboo}_n, \mrm{Bamboo}_\infty`$ は林で：
$`\quad \mrm{Root}(\mrm{Bamboo}_n) \cong \{0, 1, \cdots, n\} \\
\quad \mrm{Leaf}(\mrm{Bamboo}_n) \cong \{0, 1, \cdots, n\} \\
\quad \mrm{Root}(\mrm{Bamboo}_\infty) \cong {\bf N} \\
\quad \mrm{Leaf}(\mrm{Bamboo}_\infty) \cong {\bf N}
`$
集合 $`{\bf N}`$ 上の自己写像 $`\mrm{suc}`$ を $`\mrm{suc}(n) = n + 1`$ で定義します。$`({\bf N}, \mrm{suc})`$ は単純遷移系になります。$`\mrm{GSTS}( ({\bf N}, \mrm{suc}))`$ はグラフになります。このグラフはプレ林ですが、ルートは存在しません。
$`\quad \mrm{Root}(\mrm{GSTS}( ({\bf N}, \mrm{suc})) ) = \emptyset\\
\quad \mrm{Leaf}(\mrm{GSTS}( ({\bf N}, \mrm{suc})) ) = \{0\}
`$
このグラフの反対グラフは、ルートを持ちますがリーフは存在しません。
$`\quad \mrm{Root}(\mrm{GSTS}( ({\bf N}, \mrm{suc}))^\mrm{op} ) = \{0\}\\
\quad \mrm{Leaf}(\mrm{GSTS}( ({\bf N}, \mrm{suc}))^\mrm{op} ) = \emptyset
`$
直和グラフ $`\mrm{GSTS}( ({\bf N}, \mrm{suc})) + \mrm{GSTS}( ({\bf N}, \mrm{suc}))^\mrm{op}`$ を考えると、プレ林でルートもリーフも存在しますが、林にはなりません。
直積グラフ $`\mrm{GSTS}( ({\bf N}, \mrm{suc}))^\mrm{op} \times \mrm{RefDisc}( {\bf N})`$ を考えると、プレ林で可算無限個のルートを持ちますが、林にはなりません。
自然数の通常の大小順序 $`({\bf N}, \le)`$ から $`\mrm{GOS}( ({\bf N}, \le))`$ を作ると、このグラフの各頂点から出る辺の集合は無限です。
$`\quad \mrm{Out}(\mrm{GOS}( ({\bf N}, \le)), n) \cong {\bf N}\\
\quad \mrm{In}(\mrm{GOS}( ({\bf N}, \le)), n) \cong \{0, 1, \cdots, n\}
`$
このグラフはDAGですが、プレ林にはなっていません。
自然数の集合 $`{\bf N}`$ にトップ $`\top`$ を付け足して、$`n \prec \top`$ という順序を定義した順序集合を $`({\bf N}\cup\{\top \}, \preceq)`$ とします。グラフ $`\mrm{GOS}( ({\bf N}\cup\{ \top \}, \preceq) )`$ はツリーになります。
$`\quad \mrm{Root}( \mrm{GSTS}( ({\bf N}\cup\{\top \}, \preceq) ) ) = \{ \top \}\\
\quad \mrm{Leaf}( \mrm{GSTS}( ({\bf N}\cup\{\top \}, \preceq) ) ) \cong {\bf N}
`$
高さ
以下、$`F`$ は林だとします。林の頂点（ノード〈node〉ともいう）は、その頂点からルートに至るパスを持ちます。パスは有限の長さを持ちます。この“パスの長さ”を、その頂点の高さ〈height〉と定義します。高さが一意的に決まることは確認する必要がありますが、ちゃんと決まるので、高さは関数です。
$`\quad \mrm{height} = \mrm{height}_F \;: \mrm{Vert}(F) \to {\bf N} \In {\bf Set}`$
頂点〈ノード〉$`v`$ がルートならば、$`\mrm{height}_F(v) = 0`$ です。
無限個の頂点を許すと、関数 $`\mrm{height}_F`$ が有界とは限らないので、高さの最大値が在ることは保証できません。関数 $`\mrm{height}_F`$ に最大値があるとき、その最大値を林 $`F`$ の高さ〈height〉とします。$`\mrm{height}_F`$ に最大値がないときは、便宜上、$`F`$ の高さは $`\infty`$ とします。空な林の高さは未定義です。ツリーは、ルートが1個だけの林なので、ツリーの高さは林の高さで定義できます。高さが 0 の林は、すべての頂点がルートで、辺集合が空なグラフです。
頂点〈ノード〉の高さと林／ツリーの高さは、関連してますが別な概念なので混同しないようにしましょう。
