一般化ハイパーグラフ

「スケマティック」で述べたように、スケマティック集合は、“絵図的手法による一般化された代数系”の台〈underlying thing | carrie〉となる構造です。

スケマティック集合は、集合に組み合わせ幾何的構造が載った対象物です。有向グラフ、無向グラフ、球体集合、単体集合などはスケマティック集合の例になります。スケマティック集合〈組み合わせ幾何的対象物〉は非常に多様ですが、比較的に扱いやすいスケマティック集合のクラスとして、この記事で、一般化ハイパーグラフのクラスを定義します。

一般化ハイパーグラフのクラスには、有向グラフ、無効グラフ、通常のハイパーグラフ、複グラフ、多グラフなどが含まれます。$`
%\newcommand{\cat}[1]{ \mathcal{#1} }
\newcommand{\mbf}[1]{ \mathbf{#1} }
\newcommand{\mrm}[1]{ \mathrm{#1} }
%\newcommand{\o}[1]{ \overline{#1} }
%\newcommand{\id}{ \mathrm{id} }
\newcommand{\In}{ \text{ in }}
%\newcommand{\op}{ \mathrm{op}}
`$

内容：

有向グラフの再定義

標準的な定義によると、有向グラフ $`G`$ は、次のように書かれます。

$`\quad G = (V, E, \mrm{src}, \mrm{trg})`$

ここで：

1. $`V`$ は集合（$`V\in |\mbf{Set}|`$ ）
2. $`E`$ は集合（$`E\in |\mbf{Set}|`$ ）
3. $`\mrm{src}`$ は $`E\to V`$ という写像
4. $`\mrm{trg}`$ は $`E\to V`$ という写像

この定義を次の形に書き換えます。

$`\quad G = (\mrm{Sq}, V, E, \mrm{bdry})`$

1. $`\mrm{Sq}`$ は、集合を直積の意味で平方〈square〉するコンストラクタ（集合を受け取り集合を返す写像）：
   $`\mrm{Sq}(X) := X\times X`$
2. $`V`$ は集合（$`V\in |\mbf{Set}|`$ ）
3. $`E`$ は集合（$`E\in |\mbf{Set}|`$ ）
4. $`\mrm{bdry}`$ は $`E\to \mrm{Sq}(V)`$ という写像

$`\mrm{bdry}`$ と $`\mrm{src}, \mrm{trg}`$ の関係は次のようになります。

$`\quad \mrm{bdry} := \langle \mrm{src}, \mrm{trg}\rangle \; : E \to V\times V\\
\text{Where }\langle \mrm{src}, \mrm{trg}\rangle(e) := (\mrm{src}(e), \mrm{trg}(e))
`$

一番目の（標準的な）定義で与えられた有向グラフと、二番目の定義で与えられた有向グラフは一対一対応するので、どちらで定義しても同じことです。二番目の定義の仕方が、一般化ハイパーグラフに繋がる定義になります。

一般化ハイパーグラフ

前節二番目の有向グラフの定義にならって、一般化ハイパーグラフの定義をします。一般化ハイパーグラフ〈generalized hypergraph〉 $`H`$ は次の構成を持ちます。

1. $`P : |\mbf{Set}| \to |\mbf{Set}| \In \mbf{SET}`$
2. $`V \in |\mbf{Set}|`$
3. $`E \in |\mbf{Set}|`$
4. $`\mrm{bdry} : E \to P(V) \In \mbf{Set}`$

集合 $`V`$ を頂点の集合〈set of vertices〉、集合 $`E`$ を辺の集合〈set of edges〉と呼びます。$`E`$ の要素をハイパー辺〈hyperedge〉とも呼びますが、ここでは単に辺〈edge〉としておきます。

集合 $`P(V)`$ の要素を境界プロファイル〈boundary profile〉と呼ぶことにします。境界プロファイルを単に境界〈boundary〉、あるいは単にプロファイル〈profile〉とも呼びます。

コンストラクタ（集合を受け取り集合を返す写像）$`P`$ はプロファイル・コンストラクタ〈profile constructor〉と呼ぶことにします。プロファイル・コンストラクタは、与えられた頂点集合から、境界プロファイル達の集合を作り出します。

写像 $`\mrm{bdry}`$ は境界写像〈boundary map〉と呼びます。境界写像は、辺にその境界プロファイルを対応させます。

プロファイル・コンストラクタを $`\mrm{Sq}`$（直積の意味の平方）と置くと前節の有向グラフの定義になります。

通常（無向な）ハイパーグラフと呼ばれているモノは、プロファイル・コンストラクタを $`\mrm{FinPow}`$（すべての有限部分集合からなる集合）と置いて得られます。つまり、無向ハイパーグラフ $`H`$ は、次の形です。

$`\quad H = (\mrm{FinPow}, V, E, \mrm{bdry})`$

通常の無向グラフでは、辺の接続する頂点は2個ですが、無向ハイパーグラフでは、辺に接続する頂点は何個でもかまいません。

複グラフと多グラフ

一般化ハイパーグラフの定義において、プロファイル・コンストラクタを次のよう置いて得られる一般化ハイパーグラフは複グラフ〈multigraph〉です。

$`\text{For }X \in |\mbf{Set}|\\
\quad \mrm{MP}(X) := \mrm{List}(X)\times X
`$

'MP' は multi-profile のつもりです。頂点を型とみなせば、このプロファイルは n-in 1-out の入出力仕様になります。

一般化ハイパーグラフの定義において、プロファイル・コンストラクタを次のよう置いて得られる一般化ハイパーグラフは多グラフ〈polygraph〉です。

$`\text{For }X \in |\mbf{Set}|\\
\quad \mrm{PP}(X) := \mrm{List}(X)\times\mrm{List}(X)
`$

'PP' は poly-profile のつもりです。頂点を型とみなせば、このプロファイルは n-in m-out の入出力仕様になります。

複グラフの辺を複辺〈multiedge〉、多グラフの辺を多辺〈polyedge〉と呼びます。

前節の無向ハイパーグラフの（無向な）ハイパー辺、複辺、多辺の実例を図示すると以下のようです。黒丸が頂点、青い部分が辺〈ハイパー辺〉、黒の矢印はリストにおける並び順を表し、赤い矢印は辺の向きを示します。

ストリング図

一般化ハイパーグラフの図示法として、標準的な図の双対となるストリング図を描く方法があります。ストリング図〈string diagram〉はボックス＆ワイヤー図〈boxes-and-wires diagram〉とも呼ばれます。

ストリング図においては、辺がノード（あるいはボックス）となり、辺に接続する境界頂点達は、ノード〈ボックス〉のポートとして描かれます。ノードは好みと目的により、丸、三角形、四角形などで描き、ポートは短い棒で描きます。ポートの並び順は明示的に描いてませんが、左から右です。

そしてそれから

一般化ハイパーグラフの種類は、プロファイル・コンストラクタで決まります。この記事で出したプロファイル・コンストラクタは以下でした。

1. $`V \mapsto V\times V`$ （有向グラフ）
2. $`V \mapsto \mrm{FinPow}(V)`$ （無向ハイパーグラフ）
3. $`V \mapsto \mrm{List}(V) \times V`$ （複グラフ）
4. $`V \mapsto \mrm{List}(V) \times \mrm{List}(V)`$ （多グラフ）

他のプロファイルコンストラクタ、例えば $`\mrm{List}(V)`$ 、$`\mrm{Bag}(V)`$ 、$`\mrm{Bag}(V)\times\mrm{Bag}(V)`$ などにより、また別な種類の一般化ハイパーグラフが定義できます。

スケマティック集合〈組み合わせ幾何的対象物〉が一般化ハイパーグラフで尽くされるわけではありませんが、かなりの範囲のスケマティック集合が一般化ハイパーグラフとして記述できそうです。