長ったらしい記号的表現： ラベル付き有向グラフを例として

例えば、有向グラフやラベル付き有向グラフの説明をするとき、当然に記号的表現を使うわけです、 $`\mathrm{Graph}(A, B)`$ とか。ふと、使っている記号的表現 $`\mathrm{Graph}(A, B)`$ を文脈から切り離して眺めてみました。「文脈無しで、$`\mathrm{Graph}(A, B)`$ ってどんな意味だろう？」と。‥‥ サッパリ分からない！

これは当然の話です。記号的表現を解釈するための大部分の情報は文脈側に含まれるので、記号的表現それ自体だけを見ても分からなくて当たり前。

しかしですね、大部分の情報を文脈側に含ませると、読む側の文脈分析と文脈記憶の負担が増大します。文脈分析と文脈記憶って、実は大変な作業で、誰でもが出来るってわけでもないんですよ。

それじゃ、記号的表現の側に色々な情報を添えたらどうか？ そうすると、長ったらしい記号的表現となり、煩雑でやってられない。特に、計算のときは鬱陶しくて我慢ならない事態になります。

この問題は、ここ数年の僕の悩みの種*1です。この記事では、実験的に、説明に出てくる記号的表現を長ったらしい形で書いてみます。長ったらしい記号的表現が実用にならないとしても、通常の短い記号的表現がどのくらい省略をしているかを明らかにする効果はあるでしょう。$`
\newcommand{\mrm}[1]{ \mathrm{#1} }
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\msf}[1]{\mathsf{#1}}
%\newcommand{\mbb}[1]{\mathbb{#1}}
%\newcommand{\hyp}{\text{－} }
\newcommand{\Q}[1]{\text{'#1'}}
\newcommand{\T}[1]{\text{#1}}
\newcommand{\In}{ \text{ in } }
%\newcommand{\twoto}{\Rightarrow }
%\newcommand{\ot}{\leftarrow}
%\newcommand{\Imp}{\Rightarrow }
`$

内容：

圏かそれとも集合か

$`\mbf{Set}`$ 、$`\mbf{Graph}`$ などの太字の名前（固有名）は習慣として圏を表します。その対象達の集合は $`|\mbf{Set}|`$ 、$`|\mbf{Graph}|`$ と書けばいいのですが、圏を考える前に集合を考えるときがあります。例えば、“グラフ達の圏”より前に“グラフ達の集合”を考える、とかです。

ここだけの一時的〈実験的〉記法ですが、集合の固有名はサンセリフ体で書くことにします。“小さい集合達の大きい集合”と、“小さいグラフ達の大きい集合”は次のように書きます。

$`\quad \msf{Set}`$, $`\msf{Graph}`$

太字〈ボールド体〉とサンセリフ体の区別は注意深く見ないと分かりにくいかも。

今までの話の文脈で、実は次のことを暗黙に仮定していました。

• 単に「グラフ」と言えば、有向グラフのことである。

そもそも「グラフ」に対して関数のグラフと解釈する人がいるかも知れませんが、グラフ理論の意味のグラフです。

誤認・誤解を防ぐひとつの方法は、単に「グラフ」の代わりにちゃんと「有向グラフ」と言うことです。記号的表現も次のように変更します。

• 有向グラフ達の圏： $`\mbf{DiGraph}`$
• 有向グラフ達の集合：$`\msf{DiGraph}`$

これでもまだ Di = directed という短縮形を使っています。短縮形の規則は文脈側に持たせてます。その文脈（暗黙の前提）を知らないと「Di ってなんだ？」となるかも知れません。

集合や圏のサイズ（小さい／大きい）に関する仮定も文脈のなかに暗黙化されることがほとんどです。この記事でも、毎回「小さい／大きい」という形容詞を付けることはしません。「サイズについては察してください」という態度です。

ちなみに、上記のボールド体とサンセリフ体の区別のように、文字種・フォントなどを使った約束事はすぐに破綻します。種別（広義の型）が4種類あって、一般名〈変数名〉と固有名を区別しようとすると、8種類の文字種・フォントが必要になりますよね。8種類も文字種・フォントがないし、あってもどうせ覚えきれない。結局、文脈を見ながら区別するに頼らざるを得ないのです、残念ながら。

有向グラフ

有向グラフとは、頂点の集合と辺の集合があり、辺の始点と終点が決まっている構造です。記号的表現を使えば； $`G`$ が有向グラフ〈directed graph〉だとは、頂点〈ノード〉の集合 $`V`$ と辺の集合 $`E`$ があり、辺にその始点を対応させる写像 $`\mrm{src}`$ と、辺にその終点を対応させる写像 $`\mrm{trg}`$ が備わっていることです。

有向グラフ $`G`$ の構成素を箇条書きで並べれば：

1. 頂点の集合 $`V`$
2. 辺の集合 $`E`$
3. 始点〈ソース〉写像 $`\mrm{src} : E\to V`$
4. 終点〈ターゲット〉写像 $`\mrm{trg} : E\to V`$

このことをまとめて、次のように書きます。

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

例えば、有向グラフの具体例として次の有向グラフを考えます（すぐ下に絵あり）。

1. 頂点の集合 $`\{1, 2, 3\}`$
2. 辺の集合 $`\{4, 5, 6\}`$
3. 始点〈ソース〉写像
   1. $`4 \mapsto 1`$
   2. $`5 \mapsto 1`$
   3. $`6 \mapsto 2`$
4. 終点〈ターゲット〉写像
   1. $`4 \mapsto 2`$
   2. $`5 \mapsto 2`$
   3. $`6 \mapsto 2`$

これを図示すれば次のようになります。

今定義した有向グラフの具体例に、 $`\msf{g1}`$ （サンセリフ体小文字を使用）という固有名を付けて参照します。

まったく同じ形状のグラフを、違う頂点の集合、辺の集合で定義してみましょう。以下で、$`\Q{A}`$ は、ラテンアルファベットの最初の大文字のことです。$`A`$ と書くと変数名と間違われるのを警戒してそう書いてますが、通常、いちいちこんな書き方はしません*2。

1. 頂点の集合 $`\{\Q{A}, \Q{B}, \Q{C}\}`$
2. 辺の集合 $`\{\Q{a}, \Q{b}, \Q{c}\}`$
3. 始点〈ソース〉写像
   1. $`\Q{a} \mapsto \Q{A}`$
   2. $`\Q{b} \mapsto \Q{A}`$
   3. $`\Q{c} \mapsto \Q{B}`$
4. 終点〈ターゲット〉写像
   1. $`\Q{a} \mapsto \Q{B}`$
   2. $`\Q{b} \mapsto \Q{B}`$
   3. $`\Q{c} \mapsto \Q{B}`$

有向グラフの二番目の具体例に $`\msf{g2}`$ という固有名を付けて参照します。

有向グラフの絵を見たとき、図に現れる文字 $`A`$ が、頂点そのものなのか、頂点を表す変数なのか、あるいは頂点に割り当てられたラベルが $`A`$ なのかを文脈から判断する必要があります。今ここの文脈では、図に現れる文字 $`A`$ はラテンアルファベットの最初の大文字 $`\Q{A}`$ のことで、それは頂点そのもの（頂点の集合の要素）です。

有向グラフのテキスト記述方式

有向グラフの絵をいちいち描くのは面倒なので、テキスト形式で有向グラフを表現することを考えましょう。

一般に、有向グラフ $`G`$ に対して、次の約束をします。

1. $`\mrm{Vert}(G)`$ は、$`G`$ の頂点の集合
2. $`\mrm{Edge}(G)`$ は、$`G`$ の辺の集合
3. $`\mrm{src}_G`$ は、$`G`$ の始点写像
4. $`\mrm{trg}_G`$ は、$`G`$ の終点写像

この約束を使うと、前節の、有向グラフの最初の具体例 $`\msf{g1}`$ は、以下のような定義の等式を並べて記述できます。

1. $`\mrm{Vert}(\msf{g1}) := \{1, 2, 3\}`$
2. $`\mrm{Edge}(\msf{g1}) := \{4, 5, 6\}`$
3. $`\mrm{src}_{\msf{g1}} := \{4 \mapsto 1, 5 \mapsto 1, 6 \mapsto 2\}`$
4. $`\mrm{trg}_{\msf{g1}} := \{4 \mapsto 2, 5 \mapsto 2, 6 \mapsto 2\}`$

有向グラフのテキスト記述の別な方法として、次のような書き方もあります。

$`\T{digraph }\msf{g1}\: \{\\
\quad \T{vertex }1, 2, 3\\
\quad \T{edge }4: 1 \to 2\\
\quad \T{edge }5: 1 \to 2\\
\quad \T{edge }6: 2 \to 2\\
\}`$

この書き方は、GrapvizのDOT言語に似ています。

その他にもテキスト記述の方法・方式は色々あります。同じ記述方式でも細部のバリエーションは山のようにあります。が、どうでもいい書き方の違いは無視することが重要です。

すべての有向グラフ達の集合

「圏かそれとも集合か」で決めた約束に従うと、すべての有向グラフ達の集合は、サンセリフ体で次のように書きます。（サンセリフ体とボールド体の違いに注意。）

$`\quad \msf{DiGraph}`$

$`G \in \msf{DiGraph}`$ を、次のように書くとも約束しました。

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

これは、次のように短く書いてもかまいません。

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

なぜなら、$`V = \mrm{cod}(\mrm{src}), E = \mrm{dom}(\mrm{src})`$ として、集合 $`V, E`$ は再現できるからです。別な言い方をすると、$`(V, E, \mrm{src}, \mrm{trg})`$ という書き方は冗長だったのです。冗長な書き方はよく利用されるし、別に悪いことではありません。

次が成立します。

$`\quad (\mrm{src}, \mrm{trg})\in \mrm{Map}(E, V)\times \mrm{Map}(E, V)`$

つまり、有向グラフ $`G \in \msf{DiGraph}`$ は、関数集合の直積の要素です。

$`\quad G \in \mrm{Map}(E, V)\times \mrm{Map}(E, V)`$

頂点の集合 $`V`$ と辺の集合 $`E`$ を、すべての集合に渡って動かせば、すべての有向グラフ達の集合が得られます。このことは次のように書けます。下付きで小さい $`\msf{Set}`$ はサンセリフ体です*3。

$`\quad \msf{DiGraph} =
{\displaystyle \sum_{(V, E) \in \msf{Set}\times \msf{Set}}} \mrm{Map}(E, V)\times \mrm{Map}(E, V)
`$

これは、集合のペア $`(V, E)`$ を動かして、関数集合の直積 $`\mrm{Map}(E, V)\times \mrm{Map}(E, V)`$ をすべて（直和で）足し合わせた集合です。膨大な総和をとるので、できた集合は大きな集合〈large set〉ですが、まー集合ではあります。

$`\mrm{Map}(E, V)\times \mrm{Map}(E, V) \cong \mrm{Map}(E, V\times V)`$ を使って、わずかに短く書くことができます。

$`\quad \msf{DiGraph} =
{\displaystyle \sum_{(V, E) \in \msf{Set}\times \msf{Set}}} \mrm{Map}(E, V\times V)
`$

ラベル付き有向グラフ

単なる有向グラフとラベル付き有向グラフを区別できてない人はけっこういそうです。なぜなら、絵に描いたとき、有向グラフとラベル付き有向グラフの区別は困難だからです。

まずはラベル付き有向グラフを定義します。ラベル付き有向グラフ〈labeled directed graph | directed labeled graph〉は、有向グラフにラベリング関数を追加した構造です。その構成素を列挙すると：

1. 頂点の集合 $`V`$
2. 辺の集合 $`E`$
3. 始点〈ソース〉写像 $`\mrm{src} : E\to V`$
4. 終点〈ターゲット〉写像 $`\mrm{trg} : E\to V`$
5. 頂点に付けるラベルの集合 $`A`$
6. 辺に付けるラベルの集合 $`B`$
7. 頂点ラベリング関数 $`\mrm{vlabel} : V \to A`$
8. 辺ラベリング関数 $`\mrm{elabel} : E \to B`$

先に出した具体例 $`\msf{g1}`$ にラベリング関数を追加して、ラベル付き有向グラフの具体例を作りましょう。

1. 頂点の集合 $`\{1, 2, 3\}`$
2. 辺の集合 $`\{4, 5, 6\}`$
3. 始点〈ソース〉写像
   1. $`4 \mapsto 1`$
   2. $`5 \mapsto 1`$
   3. $`6 \mapsto 2`$
4. 終点〈ターゲット〉写像
   1. $`4 \mapsto 2`$
   2. $`5 \mapsto 2`$
   3. $`6 \mapsto 2`$
5. 頂点に付けるラベルの集合 $`\{\Q{A}, \Q{B}, \Q{C}\}`$
6. 辺に付けるラベルの集合 $`\{\Q{a}, \Q{b}, \Q{c}\}`$
7. 頂点ラベリング関数
   1. $`1 \mapsto \Q{A}`$
   2. $`2 \mapsto \Q{B}`$
   3. $`3 \mapsto \Q{C}`$
8. 辺ラベリング関数
   1. $`4 \mapsto \Q{a}`$
   2. $`5 \mapsto \Q{b}`$
   3. $`6 \mapsto \Q{c}`$

これを図に描くと次のようになります。赤い矢印は、$`\mapsto`$〈maps to〉の矢印です。

ラベルを、頂点／辺のすぐそばに書き込むと、次のようです。

もし、頂点そのもの／辺そのもの（$`1, 2, 3, 4, 5, 6`$）を省略してラベルだけを書き込むことにすると、以下です。

この絵は、先の具体例 $`\msf{g2}`$ と区別できません（実は同じ絵です）。

「有向グラフとラベル付き有向グラフの区別が困難」とは、こういう事情です。有向グラフとラベル付き有向グラフの形式的定義をきちんと理解して、文脈に注意すればもちろん区別できます。しかし一般に、絵や式に出現する名前や番号を「何に付けられた名前／番号か」を意識し追跡し続けることが容易なわけではありません。

長ったらしい記号的表現： ラベルの集合を固定

すべてのラベル付き有向グラフからなる集合を $`\msf{LabeledDiGraph}`$ （サンセリフ体）とします。ラベル付き有向グラフ $`H\in \msf{LabeledDiGraph}`$ は次のように書けます。

$`\quad H = (V, E, \mrm{src}, \mrm{trg}, A, B, \mrm{vlabel}, \mrm{elabel})`$

$`V, E, A, B`$ は冗長なので、次のように書いてもかまいません。

$`\quad H = (\mrm{src}, \mrm{trg},\mrm{vlabel}, \mrm{elabel})`$

有向グラフのときと同様な議論で、$`\msf{LabeledDiGraph}`$ は次のように書けます。

$`\quad \msf{LabeledDiGraph} \\
= {\displaystyle
\sum_{(V, E, A, B) \in \msf{Set}^4 }
\mrm{Map}(E, V)\times\mrm{Map}(E, V)\times\mrm{Map}(V, A)\times\mrm{Map}(E, B)
}
`$

ここで例えば、“頂点ラベルの集合”と“辺ラベルの集合”を固定して話をしたいとします。$`A, B`$ は（一時的には）動かさないことになるので、次のように書けばよいでしょう。

$`\quad \msf{LabeledDiGraph}(A, B) \\
=
{\displaystyle
\sum_{(V, E) \in \msf{Set}^2 }
\mrm{Map}(E, V)\times\mrm{Map}(E, V)\times\mrm{Map}(V, A)\times\mrm{Map}(E, B)
}
`$

この書き方は、$`\msf{LabeledDiGraph}`$ に2つの引数を持たせた形です。第一引数は頂点ラベルの集合、第二引数は辺ラベルの集合です。が、引数の順番ではなくて、明示的に名前を付けたほうが分かりやすいです。次のように。

$`\quad
\msf{LabeledDiGraph}(\T{vertLabelSet} := A, \T{edgeLableSet} := B)
`$

何を省略したか

冒頭で述べたように、前節最後の記号的表現を僕が何気なく書くなら $`\mrm{Graph}(A, B)`$ です。

$`\mrm{Graph}(A, B)`$ と書くとき、何が省略されているか（何を文脈に押し付けるか）を考えてみましょう。

1. 「有向グラフ〈directed graph〉」を省略して「グラフ〈graph〉」と呼ぶ。「有向」という情報は暗黙の前提。
2. 「ラベル付き有向グラフ〈labeled directed graph〉」も単に「グラフ〈graph〉」と呼ぶかも知れない。「ラベル付き」かどうかは文脈から判断。
3. 固有名も一般名もローマン体で書く。フォントを変えてないので、名前の種別は文脈から判断。
4. 引数の意味は、引数の順番（第一引数か第二引数か）で判断する。

長ったらしい記号的表現

$`\quad \msf{LabeledDiGraph}(\T{vertLabelSet} := A, \T{edgeLableSet} := B)`$

は、文脈からの情報にできるだけ頼らず、明示的な記述をしています。もちろん、欠点は長ったらしいことです。

長ったらしい記号的表現を常用するのは無理だと思いますが、ここ数年の僕の悩みの種への対処としては、長ったらしい記号的表現も適宜利用する必要があると思います。

*1:どうでもいいことですが、このブログ内では「悩みの種」と「悩みのタネ」が半々くらい。

*2:プログラミング言語では、ほとんどの場合、名前、文字データ、文字列データを区別して書きます。

*3:上付き・下付きで文字が小さくなると、フォントの違いを判断するのが難しくなります。その意味で、上付き・下付きは（便利ですが）良い書き方とは言えません。