このブログの更新は X（旧Twitter）アカウント @m_hiyama で通知されます。
Follow @m_hiyama

ご連絡は上記 X アカウントに DM にてお願いします。

［参照用 記事］

属性付きn-グラフはいけてる

雑記／備忘

「属性付き2-グラフのスノーグローブ現象」に書いたように、属性付き2-グラフではメタ巡回〈循環〉的状況が生じます。しかし、これは困ったことではなくて、むしろ望ましいことである気がします。

「属性付き2-グラフのスノーグローブ現象 // おわりに」より：

またしてもスノーグローブ現象／マイクロコスモ原理に出会ってしまったのですが、今回はそれほど困惑するような状況ではありません。むしろ、メタレベルの梯子を積極的に昇ることにより、図式言語の表現力を増大させることが出来ます。

属性付き2-グラフ（より一般には属性付きn-グラフ）のメタ巡回的状況（スノーグローブ現象／マイクロコスモ原理）は、積極的に活用すべき“機能性”です。

属性付きグラフは汎用のデータ構造ですが、特に圏論とは相性が良く、圏論を語る言葉を提供します。自然言語の語句や文、あるいは文書はテキスト（文字の並び）ですが、図式言語の語句・文・文書はいずれも属性付きn-グラフです。属性付きn-グラフは、構文論と意味論の両方ともカバーできるデータ構造です。$`\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\msc}[1]{\mathscr{#1}}
\newcommand{\In}{\text{ in }}
%\newcommand{\twoto}{\Rightarrow }
%\newcommand{\op}{\mathrm{op} }
%\newcommand{\id}{\mathrm{id}}
%\newcommand{\u}[1]{\underline{#1}}
%\newcommand{\o}[1]{\overline{#1}}
%\newcommand{\hyp}{ \text{－} }
%\newcommand{\Iff}{ \Leftrightarrow }
%\newcommand{\Imp}{ \Rightarrow }
%\newcommand{\incto}{\hookrightarrow }
%\newcommand{\fibto}{\twoheadrightarrow}
\newcommand{\T}[1]{\text{#1}}
\newcommand{\SWArrow}{\style{display: inline-block; transform: rotate(-45deg)}{\Leftarrow} }
`$

内容：

n-グラフ

有向グラフを単にグラフと呼びます。圏に関する言葉とグラフに関する言葉を次の対応で揃えます。

圏 グラフ
1-圏 ＝ 圏 1-グラフ ＝ グラフ
0-圏 ＝ 集合 0-グラフ ＝ 集合
2-圏 2-グラフ
n-圏 n-グラフ
高次圏 高次グラフ

n-グラフはn-圏から代数構造を抜き去った台構造〈underlying structure〉です。0-グラフ, 1-グラフ、2-グラフまでは比較的容易に定義できますが、n ≧ 3 のn-グラフの定義は難しくなります。我々が扱うのは主に2-グラフまでです。

(n + 1)-セルを「n-セルのあいだの等式」と解釈する場合は、等式的n-グラフと呼ぶことにします。

圏 グラフ
集合と、その要素のあいだの等式 等式的0-グラフ
圏と、その射のあいだの等式 等式的1-グラフ ＝ 等式的グラフ
2-圏と、その2-射のあいだの等式 等式的2-グラフ

等式的2-グラフについては以下の過去記事に書いています。

n-グラフとn-コンピュータッド〈n-computad〉、n-ポリグラフ〈n-polygraph〉は同義語です。2-コンピュータッド（＝2-グラフ）については以下の過去記事に書いています。

だいぶ以前（10年くらい昔）は、n-グラフの同義語に「箙〈えびら〉」という言葉を使っていました。

一時期、グラフ類似構造を「一般化ハイパーグラフ」と呼んでいました。が、誤解をまねきそうなのでやめました。その経緯は以下の過去記事で分かります。

ほぼ同一の構造に対する呼び名の紆余曲折は：

  1. n次元の箙〈えびら〉 -- 10年くらい前
  2. n次元のコンピュータッド -- 5年くらい前から
  3. n次元の一般化ハイパーグラフ -- 2024年末から2025年初頭
  4. n次元のグラフ -- 今ここ

ストリンググラフ／半グラフと属性付きグラフ

最近の記事では、図式としてペースティング図を扱っていました。図式にはストリング図もあります。ストリング図をグラフとして扱う方法として、ストリンググラフ〈string graph〉があります。ストリンググラフでは、ノード頂点とワイヤー頂点という二種の頂点を使います。以下の過去記事にストリンググラフの説明があります。

半グラフ〈semigraph〉を使ってもストリング図の定義ができます。

半グラフに関する記事はけっこうな量あります。

ストリンググラフ／半グラフは、頂点が三色に色分けされた頂点色付きグラフとしても表現できます。以下の図は、ハックニー／ロバーツォン／ヤウの論文（図のすぐ下）からのコピーです。


左側の無向半グラフ（半グラフのデフォルトは無向です）に対して、右側は三色の頂点を持つ無向グラフです。赤は開放端〈open end〉あるいは境界頂点を示します。白は辺〈ワイヤー〉を代表する頂点です。そして黒はもともとの頂点です。

頂点を三色に色付けすることは、属性で表現できます。$`\T{color}`$ という属性名に、$`\mrm{Red}, \mrm{White}, \mrm{Black}`$ のどれかの属性値を割り当てればいいのです。もちろん、「色」は比喩的なので、もっとそれらしい属性名・属性値でもかまいません。いずれにしても、ストリンググラフ／半グラフは属性付きグラフとして表現可能です。

予約属性と形状・図式・テンプレート

「属性付き2次元グラフ： 図式言語の基本 // 属性とその書き方」で述べたように、id属性とval属性は意味と目的が完全に決まっています。決まった意味・目的以外には使えません。つまり、予約された属性です。

「属性付き2次元グラフ： 図式言語の基本 // 識別子、名前、値」で述べたname属性も予約属性とします。以下のグラフのラベルはid属性でもval属性でもなく、name属性がラベルされています。$`X, f`$ は単なる名前です。具体的な集合や写像（あるいは対象や射）ではありません。

$`\quad \xymatrix@C+1.5pc@R+1pc{
{X} \ar[r]^{f}\ar[d]_{f}
\ar@{}[dr]|{\SWArrow }
&{X } \ar[d]^{f}
\\
{X } \ar@{=}[r]
&{X }
}`$

「属性付き2次元グラフ： 図式言語の基本 // 矢印の属性の表現方法」で出したclass属性も予約属性とします。ここでのクラスとは、圏のすべての射達の集合の部分集合、または、圏のすべての対象の集合の部分集合のことです。

どんな圏においても、次の射クラス〈class of morphisms | 射のクラス〉（「射のクラスと制約付きスパン // 圏の射のクラス」参照）は存在します。

  • idクラス： すべての恒等射達からなるクラス
  • isoクラス： すべての同型射達からなるクラス
  • monoクラス： すべてのモノ射〈monic morphism | monomorphism〉達からなるクラス
  • epiクラス： すべてのエピ射〈epic morphism | epimorphism〉達からなるクラス

$`\mrm{id}, \mrm{iso}, \mrm{mono}, \mrm{epi}`$ は、予約された属性classの予約された属性値だとします。

以上に説明した id属性、val属性、name属性、class属性は、任意のセルに付与可能です。class属性は予約された値を持ちますが、その他の値を追加するのは自由です。val属性がまったく指定されてないn-グラフは形状〈shape〉です。すべてのセルにval属性が指定されていれば、そのn-グラフは図式〈diagram〉です。テンプレート〈template〉は、形状も図式も含む一般的な概念です（「属性付き2-グラフのスノーグローブ現象」参照）。

属性付きn-グラフはなぜいけてるのか

次元nが3以上になるとn-グラフの定義は難しいですが、次元2以下のn-グラフ（0-グラフ、1-グラフ、2-グラフ）なら、非常に具体的・直感的でハッキリした定義を持ちます。属性という概念も難しいものではありません。つまり、低次元の属性付きn-グラフは理解容易な対象物です。

val属性は付けても付けなくてもかまいません。val属性をまったく付けないなら、n-グラフは純粋な形状（何かを表わすわけではない）になります。val属性に何を割り当てるかも場面ごとに決めればいいもので、事前の制限はありません。自然数値 $`5`$ をval属性に割り当ててもいいし、“すべての大きい圏を対象とする2-圏 $`\mbf{CAT}`$”をval属性に割り当ててもかまいません。val属性の無制限さ・自由さが属性付きn-グラフの応用範囲を非常に広くしています。

属性付きn-グラフは、圏論のペースティング図やストリング図の定式化です。しかし、同じ概念は、グラフに基づく形式言語理論や書き換えシステム、知識表現やデータベース分野などにも現れます。データ構造としての属性付きn-グラフの利用場面は圏論に限らないのです。

「属性付き2次元グラフ： 図式言語の基本 // おわりに（プロモーション）」で述べたように、テキストで書かれた“テキスト文”から、属性付きn-グラフで描かれた“図式文”へと切り替えれば、とんでもなくリッチな表現力が手に入るのです。