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

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

グラフから作る道の余代数

「モノイドと圏はやっぱり似ているね」に、一部イイカゲンなことを書いてしまったので、このエントリーで修正します。

グラフの道

Gを有向グラフだとします。話を簡単にするために、単純グラフだけを扱います。つまり、Gにループや多重辺はありません。頂点a, bに対して、aからbへの辺があるとしても1本なので、その辺は[a, b]と書きます。ループを持たないと仮定したので、[a, b]が辺なら a≠b です。

辺の一般化として道(path)を定義します。道は[a0, a1, ..., an]のような形で記します。ここで、[ai, ai+1]は必ず辺になっているとします。例えば、[a, b, c]が道だとは、[a, b]と[b, c]が辺となっていることです。道[a0, a1, ..., an]の長さはnだとします。だから、[a, b, c]は長さ2の道。特に、辺は長さ1の道とみなせますね。さらに、頂点aに対して[a]という形の道も認めて、その長さは0だとします。

以上の定義で、単純有向グラフGが与えられたとき、その道全体の集合Path(G)が決まります。グラフGが有向サイクル(閉じた道)を持てば、Gが有限でもPath(G)は無限集合になります。以下、Gは固定するとして、Path(G)をPと略記しましょう。それと、適当なスカラー体Kも選んで固定しておきます(K = R とか)。

道の分解と余乗法

道α∈Pの分解(正確には2分解)とは、α=β;γ となるβ、γの組のことです。記号「;」は道の連接です。もっと具体的に言えば、α = [a0, a1, ..., an] を分解するとは、適当なkを選んで、β = [a0, ..., ak]、γ = [ak, ..., an] とすることです。例えば、[a, b, c] = [a, b];[b, c] のように。

誤解しやすいのは、辺=長さ1の道の分解で、[a, b]は分解できないように思えますが、[a, b] = [a];[a, b]、[a, b] = [a, b];[b] という分解ができます。道αの長さをlen(α)とすると、αの分解の個数は len(α) + 1 になります。

道の集合Pから、K係数で自由生成したベクトル空間(道の空間)をAとして、Aを余代数にします。AはPから生成されているので、α∈Pに対する余乗法Δ(α)∈A(×)A と 余単位ε(α)∈K さえ定義しておけば、後は線形に拡張して Δ:A→A(×)A、ε:A→K が作れます。

Δ(α) は、「モノイドと圏はやっぱり似ているね」で既に述べたように、道の分解ごとにテンソル積を作って足したものです。例えば、

  • Δ([a, b, c]) = [a](×)[a, b, c] + [a, b](×)[b, c] + [a, b, c](×)[c]

Δの余結合律は、Δ;(Δ(×)id) = Δ;(id(×)Δ) ですが、これは、道の3分解を数えあげるだけのことです。

道の余単位

僕が勘違いしていたところです。α∈P に対する余単位ε(α)の定義は:

  • αが[a]の形をしている(長さ0)なら ε(α) = 1
  • それ以外 ε(α) = 0

左余単位律は、Δ;(ε(×)id) = id ですが、α = [a, b, c] に対してなら、

  • (ε(×)id)([a](×)[a, b, c] + [a, b](×)[b, c] + [a, b, c](×)[c])

となります。ε([a, b]) = 0, ε([a, b, c]) = 0 なので、生き残るのは (ε(×)id)([a](×)[a, b, c]) = ε([a])id([a, b, c]) = [a, b, c] で、もとに戻ります。もちろん、右余単位律も同じです。