トライアドコードとグラフ理論 #2

f:id:dafuyafu:20180711202812p:plain

見切れている数式はスクロールすると読めます

dafuyafu.hatenablog.com

今回は前回の記事の続きです．定義などは前回の記事に倣います．

今回からはトライアドコードグラフを同型を除いて分類することを考えます．トライアドコードグラフは構成の定義から高々 $55$ 個しかありません．なので，全部書いてみて分類するのでもいいですが，やはり数学的に分類を与えてみたいところです．

まず，トライアドコードグラフが非連結である場合を考え，その次に連結な場合を考えます．

非連結なトライアドコードグラフの分類

命題 2.1 トライアドコードグラフ $\gg(m,n)$ について， $\gg(m,n)$ が連結であることと，ある $a,b \in \zz/ 12\zz$ が存在して $am + bn = 1$ となることは同値である．

証明
(if part)
$\gg(m,n)$ は連結なので，点 $0$ と点 $1$ の間に道が存在する．この道は $\gg(m,n)$ の構成から， $0$ から $m$ をいくつか足し，さらに $n$ をいくつか足すことで到達できるので，それらの回数をそれぞれ $m,n$ とすれば $am + bn = 1$ を得る． f:id:dafuyafu:20180730043625j:plain

(only if part)
$0$ から $am+bn (=1)$ へ， $am+bn (=1)$ から $2 (am + bn) (=2)$ へ，同様に $11$ まで辺で繋がっているので連結である． $\square$
f:id:dafuyafu:20180730043640j:plain

注 (2.1)はほとんどの場合において， $m,n$ が互いに素であれば，またそのときに限り $\gg(m,n)$ が連結であるということを主張している．しかし $\zz/12\zz$ はGCD整域でないため，最大公約数が一意的に定まらない．例えば， $(m,n) = (5,10)$ のときは（一般的な意味での）最大公約数は $5$ となり連結でないように思われるが， $\zz /12 \zz$ においては，

$1 \cdot 5 + 2 \cdot 10 = 25 = 1$

となるので， $\gg(5,10)$ は連結である．実際 $\gg(5,10) \simeq \gg(5,7)$ となりsus4グラフと同型であり，これは前回の記事にも書いたように連結グラフである．

sus4グラフのトーラス埋め込み pic.twitter.com/dlODkdaWL5
— だふやふ🍟🍚 (@dafuyafu) 2018年7月9日

注 (2.1)は環論の言葉で言えば， $\gg(m,n)$ が連結であることと $(m,n) = (1 + 12\zz)$ であることが同値であるとも言える．このとき， $m$ と $n$ の線形結合で任意の $\zz /12\zz$ の元を表せる，と言い換えられるので， $0$ が任意の点と辺で繋がっている(道がある)，つまり連結である，と簡潔に言及できるので，なんか嬉しい．

注群論の知識を使うと，(2.1)における $am+bn=1$ の部分は $am+bn=5,7$ および $11$ でもよい．これらの数は $\zz/12\zz$ を巡回群としてみたときの生成元であることに注意する．

(2.1)の対偶を取ればトライアドコードグラフが非連結であるための必要十分条件を得る．そしてそれは，多少の誤謬を認めて簡単に言えば $m,n$ が $1$ より大きい約数を持つことである．以下ではより正確に記述していく．

定義グラフ $G$ について，その連結成分数を $\omega(G)$ と表す．また， $G$ の同型による同値類を $\left[ G\right]$ と表す．

補題 2.2 任意の $\gg(m,n)$ は正則である．

(略証) 頂点 $i$ は

$i+m, i+n, i-n, i-m, i-n+m, i-m+n$

と辺で繋がっている．

f:id:dafuyafu:20180716024628p:plain

このうち，

$m+n=0$
$2m=n$
$2n=m$

のいずれかが成り立つときに頂点が重なる事があるが，これらは $i$ によらず一定．つまり，重なり方は $m,n$ のみによって決まるので任意の頂点の次数は等しい．

補題 2.3 $\omega(\gg(m,n)) = 1,2,3 \ \mathrm{or}\ 4$

証明これらの値を取るグラフは実際に構成できるので，これ以上にならないことを示せば良い．トライアドコードグラフは構成の定義から3次完全グラフ $K_3$ の組み合わせから成るので，任意の頂点の次数は $2$ 以上でなければならない．しかし $\omega \geq 5$ の場合は少なくとも1つ次数が $1$ 以下の点が存在するので矛盾する． $\square$

以上より非連結なトライアドコードグラフは連結成分数が $2,3$ および $4$ であることがわかった．連結成分数がそれぞれの値を取るのはどのような場合かを考察する．

命題 2.4 $G = \gg(m,n)$ について以下が成り立つ．

$\omega(G)) = 4 \Leftrightarrow G \in \left[ \gg(4,8) \right]$

証明
(only if part) 書けばわかる．

f:id:dafuyafu:20180730040139p:plain

(if part) $12$ 個の頂点からなる正則なグラフにおいて， $4$ つある連結成分の頂点は必ず $3$ つでなければならない．実際，頂点が $2$ つからなる連結成分が存在するとき，その連結成分の頂点の次数は $1$ 以下となり矛盾．よってそのグラフは $K_3$ が4つからなるグラフとなり，それはすなわち $\gg(4,8)$ である． $\square$

注 $\gg(4,8)$ は音楽におけるオーグメントコードを表していた．

f:id:dafuyafu:20180730040546p:plain

オーグメントコードは根音，長3度，短6度からなるトライアドコードである．聞いてみればわかるが，若干濁ったコードであり，

VIm → V#aug → I → II

のようにして主に展開系として用いられる．なお， $\gg(4,8)$ と同型なグラフは自分自身だけであるので，実際は $\left[ \gg(4,8) \right] = \gg(4,8)$ である．

命題 2.5 $G = \gg(m,n)$ について以下が成り立つ．

$\omega(G)) = 3 \Leftrightarrow G \in \left[ \gg(3,6) \right]$

証明
(only if part) 書けばわかる．

f:id:dafuyafu:20180730041858p:plain

(if part) 3つある連結成分の頂点数は全て4でなければならない．もし，頂点数が3以下の連結成分があるとすると，その連結成分の頂点の次数は2になるが，正則性から他の頂点の次数も2になる．すると，頂点数が5以上の連結成分で頂点の次数が2になると，それは $K_3$ の組み合わせで構成されることと矛盾する．よって条件を満たすグラフは $\left[ \gg(3,6) \right]$ のみである． $\square$