「スケマティック系のために： 雑多な予備知識」の最後で次のように述べました。
スケマティック系を定義するために必要そうな雑多な予備知識は他にもあります。
...[snip]...
これらについては「その2」として述べるかも知れません。
この記事は「その2」に相当します。ただし、予告された内容とは違い、半グラフに関する予備知識です。また、「雑多な」という言葉は印象が良くないので「諸概念」にしました -- ある程度は系統的になるように記述してますし。$`\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\In}{\text{ in } }
\newcommand{\bdry}{\partial }
\newcommand{\Imp}{\Rightarrow }
\newcommand{\Iff}{\Leftrightarrow }
\newcommand{\hyp}{\text{－} }
\newcommand{\base}[1]{ {{#1}\!\lrcorner} }
`$
内容：
- 半グラフの幾何的・位相的概念
- 半グラフの一点コンパクト化と一点削除
- ボリソフ／マニン／望月半グラフ
- 半グラフのグリフ〈抽象形状〉の可換モノイド
- 大きい集合圏上のコレクションモナド
- 半グラフの生け垣と林
- マッチャー
- 半グラフの接合
半グラフの幾何的・位相的概念
グラフにも色々な種類がありますが、次の呼び名を使います。
| 有向 | 無向 | |
|---|---|---|
| 半辺ベース | 有向半グラフ | 半グラフ |
| 辺ベース | グラフ | 無向グラフ |
半辺ベースとは、半辺〈half-edge〉という概念を基本として、辺は半辺から（同値類として）定義する定式化を採用する組み合わせ構造です。開放辺〈外部辺 | 外辺 | 外線〉を持ってもよいことが特徴です。一方、辺ベースは、辺を基本にします。辺の両端には必ず頂点があるので、開放辺は持てません。詳しくは以下の過去記事を参照してください。
半辺はフラグ〈flag〉とも呼びます。この記事では「半辺」より「フラグ」を使います。
半グラフは、幾何的または組み合わせ的に定義できます。そのことについては、以下の過去記事（の最初の節）を参照してください。
組み合わせ半グラフは、（どのように定義しても）対応する幾何半グラフを持つので、それを組み合わせ半グラフの幾何実現〈geometric realization〉と呼びます。幾何実現を経由して、半グラフの位相的な性質を定義できます。
半グラフが連結〈connected〉であるとは、その幾何実現 $`X = (X_0, X_1)`$ の $`X_1`$ が位相的に連結なことです。$`X_1`$ が位相的に連結とは； 以下のような開集合のペア $`S, T \in \mrm{Open}(X_1)`$ が存在しないことです。（$`\mrm{Open}(\hyp)`$ は開集合達の集合。）
- $`S \ne \emptyset`$
- $`T \ne \emptyset`$
- $`S \cup T = X_1`$
幾何半グラフ（半グラフの幾何実現）は、1次元多様体を貼り合わせたタチの良い空間なので、位相的連結性と弧状連結性は一致します。弧状連結性を模倣した組み合わせ的定義は次のようになります。$`V`$ は頂点の集合とします。
- 任意の2つの異なる頂点 $`v, w\in V`$ に対して、$`v`$ と $`w`$ を繋ぐパスが存在する。
後述の例外辺／例外ループがないときは、上記の組み合わせ的連結性を連結性の定義に採用できますが、一般的にはうまくないので、半グラフの連結性は幾何的に定義します（対応する組み合わせ的定義も可能ですが）。
幾何半グラフのコンパクト性〈compactness〉は、外部辺〈開放辺〉を持つかどうかで決まります。
- 半グラフが外部辺を持たない ⇔ 幾何半グラフがコンパクト
- 半グラフが外部辺を持つ ⇔ 幾何半グラフがコンパクトではない
外部辺を持たない半グラフは通常の無向グラフ（ただし有限頂点・有限辺）なので：
- 半グラフが無向グラフ ⇔ 幾何半グラフがコンパクト
連結性やコンパクト性の概念は、組み合わせ半グラフに対してもそのまま使います。つまり、組み合わせ半グラフが「連結だ」とか「コンパクトだ」という言い方をします。しかし、後で（この記事ではないがいずれ）定義する内部無向グラフ〈interior undirected graph〉という概念は位相的内部とは関係なくて純組み合わせ的概念です。
幾何半グラフの0次と1次のベッチ数〈Betti number〉は半グラフを特徴付ける重要な量です。半グラフ $`\alpha`$ の0次のベッチ数 $`b_0(\alpha)`$ は、$`\alpha`$ の連結成分の個数です。$`\alpha`$ の1次のベッチ数 $`b1(\alpha)`$ は、$`\alpha`$（の幾何実現）内に含まれる独立なサイクルの個数です。バーガー／カウフマン〈Clemens Berger, Ralph M. Kaufmann〉は、$`(b_0(\alpha), b_1(\alpha))`$ を $`\alpha`$ の位相型〈topological type〉と呼んでいます。
位相型をもう少し精密化した位相特性〈topological feature〉 $`\mrm{tf}_\alpha`$ を以下のように定義しましょう； $`C(\alpha)`$ を $`\alpha`$ の連結成分の集合だとして、位相特性は次の形の関数です。
$`\quad \mrm{tf}_\alpha : C(\alpha) \to {\bf N} \In {\bf Set}`$
$`\mrm{tf}_\alpha(c)`$ は、連結成分 $`c`$ の1次ベッチ数です。$`\alpha`$ 全体の1次ベッチ数は次のようになります。
$`\quad b_1(\alpha) = \sum_{c\in C(\alpha)} \mrm{tf}_\alpha(c)`$
半グラフの一点コンパクト化と一点削除
半グラフに関する基本的な用語・記法は「半グラフ変形とDead-Or-Alive構造 // 半グラフに関する用語・記法」にあります。
半グラフが非コンパクトとは、（組み合わせ的に言えば）外部辺〈開放辺〉を持つことでした。位相的な一点コンパクト化〈one-point compactification〉と同じことを組み合わせ的に定義します。
$`\alpha = (V(\alpha), F(\alpha), \bdry_\alpha, \iota_\alpha)`$ を非コンパクト半グラフ（外部辺を持つ半グラフ）とします。頂点集合に含まれない一点 $`p`$ を選んで、新しい半グラフ $`\beta`$ を作ります。
- $`V(\beta) := V(\alpha) \cup \{p\}`$
- $`F(\beta) := F(\alpha) + \mrm{Tail}(\alpha)`$
- $`\bdry_\beta, \iota_\beta`$ はすぐ下に記述。
$`F(\alpha) + \mrm{Tail}(\alpha)`$ は直和なので、$`0, 1`$ でタギングしたタグ付き合併〈tagged union〉とします。
$`\quad F(\alpha) + \mrm{Tail}(\alpha) := (\{0\}\times F(\alpha) ) \cup (\{1\}\times \mrm{Tail}(\alpha) )`$
$`\bdry_\beta`$ は、$`\{0\}\times F(\alpha)`$ 上では $`\bdry_\alpha`$ と同じで、$`\{1\}\times \mrm{Tail}(\alpha)`$ 上での値は $`p`$ と定義します。$`\iota_\beta`$ は、$`\{0\}\times \mrm{Body}(\alpha)`$ 上では $`\iota_\alpha`$ と同じで、$`\{0\}\times \mrm{Tail}(\alpha)`$ と $`\{1\}\times \mrm{Tail}(\alpha)`$ の対応する要素（タグだけが違う要素）がペアになるように定義します。
このように定義した $`\beta`$ が、$`\alpha`$ の（組み合わせ的）一点コンパクト化〈one-point compactification〉です。幾何的にみると、$`\alpha`$ のすべての開いた端点を、点 $`p`$ にアタッチすることになります。組み合わせ的には、フラグを増やす必要があります。増やしたフラグの集合が $`\{1\}\times \mrm{Tail}(\alpha)`$ です。
一点コンパクト化で追加した頂点を無限遠点〈{point | vertex} at infinity〉と呼ぶことにします。「無限遠」に深い意味があるわけではなくて、単なる符丁です。追加したフラグ達は、無限遠点の近傍を形成します（近傍については「半グラフのあいだのエタール射 // 半グラフのあいだのエタール射」参照）。
一点コンパクト化では一点を追加しましたが、逆に一点を削除する操作を定義します。$`v\in V(\alpha)`$ として、$`v`$ を取り除いた半グラフ $`\beta`$ を定義します。以下で出てくる $`\mrm{NbF}_\alpha(v)`$ は、「半グラフのあいだのエタール射 // 半グラフのあいだのエタール射」で定義している近傍フラグ集合です。
- $`V(\beta) := V(\alpha) \setminus \{v\}`$
- $`F(\beta) := F(\alpha) \setminus \mrm{NbF}_\alpha(v)`$
- $`\bdry_\beta := \bdry_\alpha|_{F(\beta)}`$
- $`\iota_\beta`$ はすぐ下に記述。
$`\iota_\alpha(f) \in \mrm{NbF}_\alpha(v)`$ だったフラグ $`f`$ に対しては、$`\iota_\beta(f) = f`$ と変更します。すると、次のような状況が生じます。
- $`f`$ が非ループ内部辺のかたわれ〈パートナー〉だったのなら、$`f`$ はテールフラグになる（外部辺を構成する）。
- $`f`$ がテールだったのなら、$`f`$ は例外辺〈例外外部辺 | exceptional {external}? edge〉を構成する特殊なフラグになる。
ここで出てきた「例外辺を構成する特殊なフラグ」に関しては後で説明します。一点削除を定義するには、例外的構成素〈exceptional constituent〉が必要になります。
このように定義した $`\beta`$ を、一点削除〈{one-point | one-vertex} removal〉と呼びます。$`v`$ に接続していた非ループ内部辺は外部辺に変わり、$`v`$ を頂点とした自己ループ辺〈単頂点ループ〉は無くなり、$`v`$ に接続していた外部辺は例外辺に変わります。一点コンパクト化した後で、無限遠点を一点削除すると、もとの半グラフに戻ります。
この定義とは別に、$`F(\beta) := F(\alpha)`$ とする一点削除が必要になるかも知れません（今のところ、用途がハッキリしません）。
ボリソフ／マニン／望月半グラフ
前節の一点削除を実現するには、例外辺を扱う必要があります（例外辺に関しては「半グラフのあいだのエタール射 // 幾何半グラフと組み合わせ半グラフ」参照）。ボリソフ／マニン流の半グラフの定義では例外辺を扱えません。望月流の定義なら例外辺を扱えます（「半グラフの様々な定義」参照）。ボリソフ／マニンの定義に望月の定義をミックスしてみます。そうすると、例外辺だけでなく例外ループも扱えるようになります。
ボリソフ／マニン半グラフに対して、わずかな変更を加えます。境界写像〈boundary map〉が部分写像〈partial map〉でもよいとします。半グラフを定義する図式は次のようになります。$`\bot`$ は未定義を表す特殊な要素です。
$`\quad \xymatrix{
% @(inDir, outDir)
F \ar@(ul, dl)[0,0]_{\iota} \ar[r]^-{\bdry}
& V + \{\bot\}
}\\
\quad \iota; \iota = \mrm{id}_F
`$
フラグ $`f\in V`$ が $`\bdry(f) = \bot`$ のとき、$`f`$ の境界頂点〈端点〉は無いと考えます。端点を持たないフラグを例外フラグ〈exceptional flag〉と呼びます。境界写像が部分写像であることは、例外フラグ〈端点なしフラグ〉を許すことと同じです。例外フラグの集合を $`\mrm{Excep}(\hyp)`$ で表します。
ペアリング対合 $`\iota`$ には次の制約を加えます。
- $`f`$ が例外フラグなら、$`\iota(f)`$ も例外フラグ。
例外フラグと通常フラグがペアになることは禁止されます。
例外フラグの集合の定義と共に、「半グラフ変形とDead-Or-Alive構造 // 半グラフに関する用語・記法」にある定義を繰り返すと：
$`\quad \mrm{Excep}(\alpha) := \{f\in F(\alpha) \mid \bdry_\alpha(f) = \bot\}\\
\quad \mrm{Tail}(\alpha) := \{f\in F(\alpha) \mid \iota_\alpha(f) = f\}\\
\quad \mrm{Body}(\alpha) := \{f\in F(\alpha) \mid \iota_\alpha(f) \ne f\}
`$
先の制約から、集合 $`\mrm{Excep}(\alpha)`$ はペアリング対合 $`\iota_\alpha`$ に関して閉じています。例外フラグであってテールフラグでもあるフラグは、それだけで外部辺を構成します。この外部辺を例外外部辺〈exceptional external edge〉、または単に例外辺〈exceptional edge〉と呼びます。例外フラグであってボディフラグでもあるフラグは、パートナーと共に内部辺（ボディフラグの二元集合）を構成します。この内部辺は無頂点ループだとみなして例外ループ〈exceptional loop〉と呼びます。
幾何的には、例外辺は開いた2つの端点（頂点ではない）を持つ開区間（あるいは直線）、例外ループは開いた端点も頂点も持たない円周とみなします。円周は、2つの例外フラグが繋がって作られたとみなします。
境界写像を部分写像に変更したボリソフ／マニン半グラフを、ボリソフ／マニン／望月半グラフと呼ぶことにします。以下で、単に「半グラフ」と言ったらボリソフ／マニン／望月半グラフのことだとします。ボリソフ／マニン／望月半グラフにより、任意の幾何半グラフをエンコードできます。
半グラフのグリフ〈抽象形状〉の可換モノイド
半グラフの定義をボリソフ／マニン／望月半グラフに変更しても、半グラフ射の定義はそのまま使えます。半グラフ射は、写像の組 $`(f_V, f_F)`$ で境界写像とペアリング対合を保つものです。写像 $`f_V, f_F`$ がどちらも同型〈双射〉のとき、半グラフのあいだの同型射〈可逆射〉を定義します。
ボリソフ／マニン／望月半グラフを対象として、そのあいだの半グラフ射を射とする圏を定義できます。この圏も以前と同じ名前 $`{\bf SemiGraphC}`$ で参照します。末尾の C は、半グラフ二重圏と区別するためです。
半グラフを扱う場合、頂点集合やフラグ集合が具体的に何であるかはどうでもいいことが多いです。その場合は、すべての半グラフの集合 $`|{\bf SemiGraphC}|`$ を半グラフ同型射による同値関係（同型同値）で割った商集合を考えます。次のような集合です。
$`\quad |{\bf SemiGraphC}|/\!\cong`$
この商集合の要素、つまり同型同値類を（半グラフの）抽象形状〈abstract shape〉またはグリフ〈glyph〉と呼びます。抽象形状／グリフは組版の用語ですが、具体的な形状を抽象化し類別した概念です。
$`\alpha`$ を半グラフとして、$`\alpha`$ が所属するグリフ〈抽象形状〉を $`[\alpha]`$ と書きます。定義より、次が成立します。
$`\quad [\alpha] = [\beta] \Iff (\alpha \cong \beta \In {\bf SemiGraphC})`$
「半グラフ」と言っても、実際には半グラフのグリフを指していることが多いですね。
さて、2つの半グラフの直和があるので、直和を使ってグリフの足し算を定義できます。
$`\quad [\alpha] + [\beta] := [\alpha + \beta]`$
直和（モノイド積）は up-to-iso で結合的・単位的なので、グリフの足し算は厳密に結合的・単位的になります。また、直和は対称的なので、グリフのレベルでは足し算が可換となります。
以上から、半グラフのグリフの集合は、直和から誘導される足し算で可換モノイドになります（ゼロは空グラフの同値類）。可換群が$`{\bf Z}`$-加群であるのと同様に、グリフの可換モノイドは$`{\bf N}`$-半加群とみなせます。つまり、自然数係数の線形結合が自由にできます。
半グラフのグリフの可換モノイドを次のように書きます。
$`\quad {\bf Glyph} = \mrm{Glyph}({\bf SemiGraphC}) = (|{\bf SemiGraphC}|/\!\cong, +, [\emptyset])`$
$`{\bf Glyph}`$ をグリフ可換モノイド〈glyph commutative monoid〉と呼びます。グリフ可換モノイドを圏とみなしたいときは、恒等射だけを射とする離散対称モノイド亜群と考えます。
大きい集合圏上のコレクションモナド
コレクションモナドの正確な定義があるわけではないのですが、集合 $`X`$ が与えられたとき、$`X`$ の要素を有限個取り出して作った集まりをコレクションと呼び、$`X \mapsto \text{all-colections}(X)`$ として定義される関手を台とするモナドを（曖昧に）コレクションモナドと呼びます。
次のモナドは、集合圏 $`{\bf Set}`$ 上のコレクションモナドです。
- リストモナド〈list monad〉
- バッグモナド〈bag monad〉
- 有限部分集合モナド〈finite subset monad〉
他に、リーフ値付きツリーのモナド（「ツリーデータ型のモナド」参照）もコレクションモナドと言っていいでしょう。
集合圏 $`{\bf Set}`$ 上のコレクションモナドは、大きな集合圏（大きな集合〈large set〉も対象として含む集合圏）$`{\bf SET}`$ 上でも定義できます。例えば、$`\mrm{List}(|{\bf Set}|)`$ などはそのようなコレクションモナドの使用例です。
ここでは、$`{\bf SET}`$ 上のモナド（通常モナドのラージ・バージョン）であっても、$`{\bf Set}`$ のときと同じ名前を流用〈オーバーロード〉します。上に挙げたモナドのラージ・バージョンの台関手は次のようです。
$`\quad \mrm{List} : {\bf SET} \to {\bf SET} \In \mathbb{CAT}\\
\quad \mrm{Bag} : {\bf SET} \to {\bf SET} \In \mathbb{CAT}\\
\quad \mrm{FinSub} : {\bf SET} \to {\bf SET} \In \mathbb{CAT}
`$
リスト関手の対象パートは次のように書けます。
$`\text{For } X\in |{\bf SET}|\\
\quad \mrm{List}(X) := \sum_{n\in {\bf N}}\mrm{Map}(\bar{n}, X)`$
ここで、$`\bar{n} := \{1, \cdots, n\}`$ で、$`\mrm{Map}(\hyp, \hyp) := {\bf SET}(\hyp, \hyp)`$ です。小さい集合間の写像でも大きい集合間の写像でも $`\mrm{Map}(\hyp, \hyp)`$ をオーバーロードします。
バッグ関手の対象パートは次のように書けます。
$`\text{For } X\in |{\bf SET}|\\
\quad \mrm{Bag}(X) := \sum_{n\in {\bf N}} \mrm{Map}(\bar{n}, X)/\!\mrm{Aut}(\bar{n})`$
ここで、$`\mrm{Aut}(\bar{n})`$ は、$`\bar{n} \to \bar{n}`$ の双射からなる群で、$`\mrm{Map}(\bar{n}, X)`$ へ作用していると考えて商集合〈軌道空間〉を作っています。詳しくは「順列・組み合わせと群作用の軌道空間」をみてください。
また、$`\mrm{FinSub}`$ を使った次の表示も可能です。
$`\text{For } X\in |{\bf SET}|\\
\quad \mrm{Bag}(X) := \sum_{A\in \mrm{FinSub}(X)} \mrm{Map}(A, {\bf N}_{\ge 1})`$
関数 $`m \in \mrm{Map}(A, {\bf N}_{\ge 1})`$ はバッグ（マルチセットとも呼ぶ）の多重度〈重複度〉を表す関数です。
モナドの乗法と単位を表すには、$`\mu, \eta`$ をオーバーロードして使いますが、必要があれば $`\mu^\mrm{List}`$ のようにして区別します。
半グラフの生け垣と林
半グラフの圏 $`{\bf SemiGraphC}`$ の部分圏を幾つか挙げます。
- $`{\bf Plant}`$ ： 植物を対象とする充満部分圏。植物〈plant〉とは、連結な半グラフです（「コステロの半グラフ圏から二重関手意味論へ // 半グラフ、植物、林〉参照）。対象の位相型は $`(1, n)`$ です。
- $`{\bf Tree}`$ ： ツリーを対象とする充満部分圏。ツリー〈tree〉とは、連結でサイクルを持たない半グラフです。対象の位相型は $`(1, 0)`$ です。
- $`{\bf Corolla}`$ ： カローラを対象とする充満部分圏。カローラ〈corolla〉とは、単一の頂点を持ち、内部辺を持たない半グラフです。対象の位相型は $`(1, 0)`$ です。
- $`{\bf Rose}`$ ： バラを対象とする充満部分圏。バラ〈rose〉とは、単一の頂点を持つ（自己ループ辺を持ってもよい）半グラフです。対象の位相型は $`(1, n)`$ です。
- $`{\bf FinUGraph}`$ ： 有限無向グラフ〈finite undirected graph〉を対象とする充満部分圏。外部辺・例外辺・例外ループを持たない半グラフが有限無向グラフです。対象はコンパクトな半グラフです。
- $`{\bf CFinUGraph}`$ ： 連結な有限無向グラフ〈connected finite undirected graph〉を対象とする充満部分圏。対象は位相型 $`(1, n)`$ のコンパクトな半グラフです。
これらの部分圏の同型射〈可逆射〉からなる亜群を考える場合も多いです。以下、$`\cat{S}`$ は $`{\bf SemiGraphC}`$ の部分圏だとします。$`\cat{S}`$ が直和（モノイド積）で閉じている事は仮定しません。
$`{\bf FinSetG}`$ は、有限集合を対象として、同型写像〈可逆写像 | 双射〉を射とする亜群〈groupoid〉とします。末尾の G は groupoid のつもりです。$`{\bf FinTotOrdG}`$ は、有限な全順序集合〈線形順序集合〉を対象として、順序同型写像〈同型単調写像〉を射とする亜群とします。2つの有限全順序集合のあいだの順序同型写像は、あってもひとつです。つまり、$`{\bf FinTotOrdG}`$ はやせた亜群〈thin groupoid〉です。
$`\cat{S}`$ の生け垣の圏〈category of hedges〉と林の圏〈category of forests〉は、「スケマティック系のために： 雑多な予備知識 // Diag構成」と「Diag構成： 圏論的構成法の包括的フレームワークとして」で述べたDiag構成を使えば手短に記述できます（具体的な構成法も下で述べますが）。
$`\quad \cat{S}{\bf Hedge} := \mrm{Diag}^{{\bf FinTotOrdG}, \mrm{Disc}}(\cat{S})\\
\quad \cat{S}{\bf Forest} := \mrm{Diag}^{{\bf FinSetG}, \mrm{Disc}}(\cat{S})
`$
$`\mrm{Disc}`$ は、集合を離散圏とみなす関手です。順序集合の場合はその台集合を離散圏とみなします。$`\cat{S}`$ を具体化してみると、例えば：
- $`{\bf TreeHedge}`$ ： ツリーを成分とする生け垣の圏
- $`{\bf PlantForest}`$ ： 植物を成分とする林の圏
ここからは、生け垣と林を具体的に説明します。まずは生け垣から。
$`(I, \le)`$ を有限全順序集合とします。写像 $`h: I \to |\cat{S}| \In {\bf SET}`$ を、$`\cat{S}`$ の生け垣〈hedge〉と呼びます。$`I`$ に全順序が入っているので、生け垣は、圏 $`\cat{S}`$ の対象を順番に並べたものです。$`h`$ が単射であることを要求してないので、同じ対象が重複して現れてもかまいません。
$`h:I \to |\cat{S}|`$ と $`k: J\to |\cat{S}|`$ を生け垣として、そのあいだの射 $`\varphi`$ は、次の2つの構成素を持ちます。
- ベースパート $`\base{\varphi} : (I, \le) \to (J, \le)\In {\bf FinTotOrdG}`$ ： 順序同型写像
- ファイバーパート $`\varphi^\flat`$ ： $`(\varphi^\flat_i : h(i) \to k(\base{\varphi}(i)) \In \cat{S})_{i\in I}`$
今使った記法は、「Diag構成の変種とその書き方」で約束した記法です。
生け垣を簡単に扱いたいなら、一般的な有限全順序集合の代わりに $`(\bar{n}, \le)`$ だけを考えます。そうすると、$`\cat{S}`$ の生け垣の集合は $`\mrm{List}(|\cat{S}|)`$ となります。生け垣のあいだの射は、次の形になります。
$`\quad (\varphi_i : h(i) \to k(i) \In \cat{S})_{i\in \bar{n}}`$
これは、$`\cat{S}`$ の射のリストです。単純化した生け垣の圏は $`\mrm{List}(\mrm{Mor}(\cat{S}))`$ と $`\mrm{List}(\mrm{Obj}(\cat{S}))`$ をもとにして定義することもできます。
次に林を定義しましょう； $`I`$ を有限集合とします。写像 $`f: I \to |\cat{S}| \In {\bf SET}`$ を、$`\cat{S}`$ の林〈forest〉と呼びます。$`I`$ に順序は無いので、$`f`$ で列挙した$`\cat{S}`$ の対象達のあいだに順番はありません。$`f`$ が単射であることを要求してないので、同じ対象が重複して現れてもかまいません。
$`f:I \to |\cat{S}|`$ と $`g: J\to |\cat{S}|`$ を林として、そのあいだの射 $`\psi`$ は、次の2つの構成素を持ちます。
- ベースパート $`\base{\psi} : I \to J \In {\bf FinSetG}`$ ： 任意の同型写像
- ファイバーパート $`\psi^\flat`$ ： $`(\psi^\flat_i : h(i) \to k(\base{\varphi}(i)) \In \cat{S})_{i\in I}`$
林を簡単に扱いたいなら、一般的な有限集合の代わりに $`\bar{n}`$ だけを考えます。そうすると、$`\cat{S}`$ の林の集合は $`\mrm{List}(|\cat{S}|)`$ となります。林のあいだの射は生け垣のときと違ってきます。次の形になります。
$`\quad (\psi_i : f(i) \to g(\sigma(i) ) \In \cat{S})_{i\in \bar{n}} \text{ for some }\sigma \in \mrm{BijMap}(\bar{n}, \bar{n})`$
これは、$`\cat{S}`$ の射のリストですが、置換 $`\sigma`$ が介入しています。絵に描くときは、$`\sigma`$ によるワイヤーブレイディング〈組み紐〉（対称ブレイディング*1）を作って、ワイヤー達に射 $`\psi_i`$ 達を乗せればいいでしょう。
単純化した林の圏も、生け垣の場合と同様に $`\mrm{List}(\mrm{Mor}(\cat{S}))`$ と $`\mrm{List}(\mrm{Obj}(\cat{S}))`$ をもとにして定義できますが、置換によるワイヤーブレイディングを考慮する必要があります。
マッチャー
2つの半グラフの接合〈grafting〉は、架橋〈bridging〉だけで構成されるグラフ変形として定義できます。が、半グラフの二項演算として定義しておく価値があります。二項演算とは言っても、単一の二項演算があるわけではなくて、二項演算の族〈ファミリー〉があります。この族は“マッチャー”によりインデックス付けられます。この節でマッチャーを定義します。
“両側単射スパンの同型同値類”、“部分単射”、“二部部分対合”という3つの概念を定義します。これらは同値な概念です。同値な概念がマッチャーを定義します。
まず“両側単射スパン”から； 次のような集合圏のスパンを考えます。
$`\require{AMScd}
\quad \begin{CD}
X @<{l}<< I @>{r}>> Y
\end{CD} \In {\bf Set}
`$
このスパンの左脚 $`l`$ も右脚 $`r`$ も単射であるとき、両側単射スパン〈two-sided injective span〉と呼びます。もうひとつの両側単射スパンとの同型は次の図式で与えられます。
$`\quad \xymatrix {
{}
& I \ar[dl]_{l} \ar[dr]^{r} \ar[dd]^{\cong}
& {}
\\
X
& {}
& Y
\\
{}
& I' \ar[ul]^{l'} \ar[ur]_{r'}
& {}
}\\
\quad \In {\bf Set}
`$
両側単射スパン達を上記の同型で同一視した同値類を両側単射スパンの同型同値類〈isomorphic class of two-sided injective spans〉と呼びます。有限集合の圏で考えているときは、同値類における $`I`$ の代表に $`\bar{n}`$ を取れます。
次に“部分単射”； 部分写像 $`i: X \to Y \In {\bf Partial}`$ が、その定義域 $`\mrm{def}(f)`$ 上の写像 $`\mrm{def}(f) \to Y \In {\bf Set}`$ とみたとき単射なら部分単射〈partial injection〉と呼びます。
最後に“二部部分対合”； 集合 $`Z`$ 上の部分対合〈partial involution〉とは、部分集合 $`S \subseteq Z`$ 上で定義された対合 $`j:S \to S \In {\bf Set}`$ です。直和集合 $`X + Y`$ で定義された部分対合 $`j`$ が二部部分対合〈bipartite partial involution〉だとは、次を満たすことです*2。
- $`x\in X`$ に対して $`j(x)`$ が定義されているなら、$`j(x) \in Y`$ 。
- $`y\in X`$ に対して $`j(y)`$ が定義されているなら、$`j(y) \in X`$ 。
集合 $`X, Y`$ に対して、次の3つの概念は事実上同じものです（同一視可能）。
- $`X, Y`$ を左右の足とする両側単射スパンの同型同値類
- $`X`$ から $`Y`$ への部分単射
- 直和集合 $`X + Y`$ 上の二部部分対合
これら3つの概念のどれか（したがってすべて）で定義される部分的一対一対応をマッチャー〈matcher〉と呼びます。マッチャーは、集合 $`X`$ の一部の要素と、集合 $`Y`$ の一部の要素のあいだのペアリングを指定します。$`X \cap Y \ne \emptyset`$ のときは、自分自身とのペアリングも生じ得ます。
集合 $`X, Y`$ のあいだの（この順での）マッチャーの集合を $`\mrm{Matcher}(X, Y)`$ とします。マッチャーを部分単射と解釈すると、$`\mrm{Matcher}(X, Y) \subseteq \mrm{PartialMap}(X, Y)`$ だと分かります。
半グラフの接合
マッチャーの定義は、両側単射スパン（の同型同値類）、部分単射、二部部分対合のどれを採用してもいいのですが、とりあえず マッチャー＝部分単射 とします。
$`\alpha, \beta`$ を半グラフとします。$`m : \mrm{Tail}(\alpha) \to \mrm{Tail}(\beta)`$ をマッチャー〈部分単射〉とします。マッチャー $`m`$ による半グラフの接合〈graphting〉を定義できます。
マッチャー〈部分単射〉 $`m`$ は、直和集合 $`\mrm{Tail}(\alpha) + \mrm{Tail}(\beta)`$ の二部部分対合とみなせます。$`\mrm{Tail}(\alpha) + \mrm{Tail}(\beta) = \mrm{Tail}(\alpha + \beta)`$ なので、マッチャー $`m`$ は直和半グラフ $`\alpha + \beta`$ の仮想辺〈virtual edge〉を定義します（「半グラフの二重圏と半グラフ変形」参照）。マッチャーで生成されたすべての仮想辺を架橋〈bridging〉した半グラフが接合演算の結果です。
$`\alpha`$ と $`\beta`$ のマッチャー $`m`$ による接合（の結果）を次のように書きます。
$`\text{For } \alpha, \beta \in |{\bf SemiGraphC}|\\
\text{For }m \in \mrm{Matcher}(\mrm{Tail}(\alpha), \mrm{Tail}(\beta))\\
\quad \alpha \odot_m \beta \; \in |{\bf SemiGraphC}|
`$
$`\alpha, \beta`$ が何であれ、空なマッチャー（記号を流用して $`\emptyset`$ と書く）はあるので、空なマッチャーによる接合は常に定義可能です。そしてそれは半グラフの直和です。
$`\quad \alpha \odot_\emptyset \beta = \alpha + \beta`$
接合はグラフ変形の特別なものですが、それでも、マッチャーを色々と選べるので、かなり多様な半グラフ操作ができます。
