symmetry of Kauts digraph

質問

ここが適切な場所か分からないのですが・・・。

　Kautz digraphは、対称グラフなのでしょうか。K(d, k)として、d=2のときはそのような気がしますが、自信が持てません。また、d>3のときについてはカイモク見当もつきません。

　どなたかご存知の方、ご教授頂ければ幸いです。

回答No.4

stomachman · ベストアンサー

再帰性について再び。
本来のご質問の意味はKautz digraphを適当にアークをちょん切っていくつかの部分グラフに分けたときに、それぞれがKautz digraphにできるか、という問題だったんですね。
d,kがうんと小さいときを除くと、一般に丁度２種類の文字を含む語があって、これらの語は３種類以上の文字を含むKautz digraphに含まれてしまいます。つまり文字xを含まない語によるKautz digraphは部分グラフとして存在しますが、文字y(y≠x)を含まない語による部分グラフと共通のノードを持ってしまいます。アルファベットを二つに分割してA=B+C (B∩C=φ)とすれば、B,Cそれぞれのアルファベットだけによる部分グラフがKautz digraphになるけど、両方の文字を含む大量の語が余ってしまう。そして、この余った語の一部でKautz digraphを構成しようとすると、Bだけの文字を含む語がどうしても含まれなくてはならない。つまり<xyxyxy....>という形の語がどの部分Kautz digraphにも必要なので、うまく分割できないように思われます。無理じゃないかな、という感じはするんですが。

やっぱり専門家に出てきて貰わんとアキマヘンな、こりゃ。
どうもすいません。

補足

stomachmanさん

>やっぱり専門家に出てきて貰わんと
　いやいやいや、ここで書かれていることは相当(あるいは完璧に)的を射ていると思いますよ。私がstomachmanさんを混乱させてしまったのは、言葉をちゃんと定義できなかったからです(対称性についてもそうです)。

　ホントにグラフプロパーの方じゃないんですか?

回答No.5

stomachman

みたび、再帰性についてです。
K(d,k)はK(d-1,k)を部分グラフとして含んでいます。K(d-1,k)は、アルファベットA
のなかのどれか１文字を使わない、という語だけからなる部分グラフですから、
K(d,k)に含まれるK(d-1,k)は(d+1)通りあります。
同様にして、それぞれの部分グラフK(d-1,k)はd通りの部分グラフK(d-2,k)を含んで
おり、..... それぞれの部分グラフK(2,k)は２通りのK(1,k)を含んでいます。
ですから（共通の語があるので）分割はできませんが、このような入れ子構造になっ
てる。これが「再帰性」のもう一つの意味ということでは如何でしょうか。

お礼

stomachmanさん

　もちろんそれも「再帰性」といえないことはないと思います。が、それは言葉の定義のしかただと思います(私はこれを厳密にできませんでした)。グラフの世界ではこういうことはいわないでしょう(ただし、Xというグラフの中に別のYというグラフをembeddingすることができる、ということは論文になります)。

回答No.3

stomachman

なるほど、「どのノードから見ても同じに見える」とおっしゃる意味がやっと理解できました。先にstomachmanが書いたのは語の文字を置換する話なので、語の構造を保存するような変換しか許しません。この意味での対称性は自明ですが、語の構造が違う任意のノード同士を対応付けることはできないですね。ですからご質問の本来の意図における「対称性」に関しては、多分「対称でない」というのが答だと思います。実際反例を挙げていらっしゃるのだから、あとは「対称性」をきちんと定義しさえすれば、問題は解決したことになるのでは？

　「再帰性」に関しては、もっと美しい構造があるのかも知れませんが、何しろ初学者なもので....

　なお、Kautz digraphはk文字分の記憶を持つ非同期の有限オートマトンの状態遷移図（つまり入力が変化した時に状態遷移を起こし、新しい入力がcであるとき<pR>→<Rc>へ移る）と見なすことができるように思われます。

回答No.2

stomachman

●仰る意味での対称性は自明に成り立っています。
stomachmanが書いたKautz digraphの定義において、語をノード（頂点）と同一視していることがポイントです。アルファベットAの要素を適当な順番で枚挙したものS=<a[0],a[1],a[2],a[3],......,a[d]>を決めて、写像fをたとえば
f(a[d])=a[0], f(a[n]) = a[(n+1)] (n=0,1,....,d-1) z
と定義します。さらに語x=<x[1],x[2],....,x[k]>に対しても、
F(x)=F(<x[1],x[2],....,x[k]>) = <f(x[1]),f(x[2]),....,f(x[k])>
と定義します。
すると、あるKautz digraph K(d,k)に対しても
F(K(d,k)) = K(d,k)の各ノードxをf(x)で置き換えたもの
が定義できます。このとき、F(K(d,k))=K(d,k)となることはK(d,k)の定義から自明でしょう。一般にSをどのように並べても良いし、fは置換でありさえすれば何でも良い。
　この先、厳密な証明を書き上げるのはお任せしましょう。

●また、再帰構造をしているか(あるサイズのKautz digraphを、更に小さいサイズのいくつかのKautz digraphに分解できるか)に関しては、きちんと議論するには再び「分解」の意味を確認する必要がありそうですが....
　d=2ぐらいで見ているとdを変えたときに再帰的になっているような気がするかも知れません。ですが、たとえば(A-{a[n]})というアルファベットを使って作られるグラフK(d-1,k)[n]は、K(d,k)の中に埋め込まれています。もちろん取り除く文字がn=0～dのどれであってもK(d-1,k)[n]はK(d-1,k)と同型です。K(d-1,k)[n]の語のうち、文字a[m](m≠n)をa[n]で置き換えたものを考えると、これはK(d-1,k)[m]に他なりません。文字a[m]もa[n]も含まない語だけによる部分グラフK(d-2,k)[n,m]は、K(d-1,k)[n]とK(d-1,k)[m]に共通です。だからK(d,k)はK(d-1,k)[n]とK(d-1,k)[m]とには分解されません。

●むしろ「再帰性」と仰っているのは以下のような意味ではないでしょうか。
　K(d,k)の語の集合をW(k)とします。K(d,k)において語 <pqR> (１文字目がp、２文字目がqでその後に長さk-2の文字列Rが続く語）から出ているアークが繋がっている語の集合は｛<qRc>｜∀c∈A∧<qRc>∈W(k)｝ですが、<sqR>(∀s≠p)に対しても｛<qRc>｜∀c∈A∧<qRc>∈W(k)｝が繋がっている。K(d,k-1)を考えます。つまり語の最初の文字が何であっても同一視し、K(d,k)の語d個づつを一つにまとめてしまうことにします。すると、K(d,k)における<pqR> も<sqR>(∀s≠p,q)も一つの語<<qR>>にまとめられてしまい（K(d,k-1)の語は<<>>と書くことにします。）つまり<<qR>>={<pqR>|∀p∈A∧<pqR>∈W(k)｝、それに繋がるのは｛<<Rc>>｜∀c∈A∧<<Rc>>∈W(k-1)｝である。ここに<<Rc>> = {<qRc>|∀q∈A∧<qRc>∈W(k)｝。
　そこでK(d,k-1)において、<<qR>>→<<Rc>>という、一対の語と一つのアークにまとめられちゃったものが、もとのK(d,k)ではどういう構造を持っていたかを反省してみますと、まず
｛<pqR>|∀p∈A∧<pqR>∈W(k)｝→｛<qRc>|∀q∈A∧<qRc>∈W(k)｝
というアークに関してはそのまんま束ねられただけです。問題は｛<pqR>|∀p∈A∧<pqR>∈W(k)｝の要素間でのアークがどうなっていたかですが、<pqR>∈W(k)だからp≠qであり、従って{<pqR>}の要素同士の間にはアークは存在しない。また、{<qRc>|∀q∈A∧<qRc>∈W(k)｝の内部でのアークはどうか？これも最後の文字が全部同じcであるから、相互にアークは存在しない。
　従ってK(d,k)の語長kの語（互いにアークはない）について、最初の文字だけが異なる物をd個まとめて語長(k-1)の一つの語と見なすという操作は、実に単純な構造を持っています。この縮約をkをひとつづづ減らしながら幾らでも行うことができ、最後にK(d,1)に行き着きます。これは(d+1)角形の完全グラフに他なりません。
　たとえばK(2,3)位で眺めてみる（Excelか何かで、グラフを行列で表現してみる）と、K(2,2)と同じ構造をしているのがよく分かると思いますよ。

◎ついでながら、ぜひKautz digraphがどんな分野でどのように使われるものなのか、簡単な解説を補足していただけないでしょうか。Stomachmanも今回初めて勉強したもんですから....この話専門的すぎて分かんない、という方（stomachmanを含む）のためにも。

補足

stomachmanさん、再びどうもです。

　対称性についてですが、だんだん分からなくなってきました。

　下に書いたように、私は対称性のことを「どのノードから見てもグラフが同じように見える」と認識していたので、今までKautzグラフは非対称だと思っていました(なぜなら、例えばK(2, 3)ですとノード010を含む長さ2のサイクルが存在しますが、ノード012についてはそのようなサイクルは存在しないからです)。しかし、自己同型写像が存在するか、ということでいえば、恐らくするのでしょう(詳しく詰めてはいません)。

　また、再帰構造についてですが、どちらかといえば上に書かれたことが私の意図しているものに近いようです。具体的にどのように書けばいいのかが分からないのですが・・・。

　例えば、hypercubeを例にとりますと、n-hypercube はふたつの(n-1)-hypercubeに分割することができます(ノードを余すことなく)。また、n-star graphは、n個の(n-1)-star graphに分割することができます(こちらもノードは余りません)。同様に、K(d, k)が例えばd個のK(d-1, k)、またはk個のK(d, k-1)、さもなくばdk個のK(d-1, k-1)に分割できるのか、ということが知りたかったわけです。ここでは、いくつかのノードを束ねる、ということは考えません。

Definition 1: An n-dimensional hypercube consists of $2^n$ nodes whose address are represented by n-bit binary numbers. A node x has n adjacent nodes whose address are ontained by reverting, one by one, each bit of its address.

Definition 2: An n-dimensional star graph consists of $n!$ nodes whose address are represented by the permutations of the set {1, 2, ..., n}. A node x has n-1 adjacent nodes whose address are ontained by interchanging the first symbol with the ith symbol.

　Kautzグラフの用途についてですが、別に他のグラフと違った使われ方をするものではありません。このグラフの特長としては、直径に対して頂点数が多いということが挙げられます。

回答No.1

stomachman

先ず用語の確認からです。
●「Kautz digraph」
Kautz digraph, あるいはdirected Kautz graphのことですね。（Kautsじゃないです。）
K(d,k)は以下のように定義されているとして良いでしょうか？
まず(d+1)個の要素を持つ文字の集合（アルファベット)Aが決まっている。そして、この文字k個を連ねて語xを作る。すなわちx=<x[1],x[2],....,x[k]> (x[j]∈A, j=1,2,...,k)　ただし、この語の中に同じ文字が２文字続く所があってはいけない。このような条件を満たす語の集合をNとすると、その個数は|N|=(d+1)(d^k)である。
　この|N|個の語をノード（バーテックス）とする有向グラフを考える。どのノードx=<x[1],x[2],....,x[k]>についても、<x[2],x[3],....,x[k],c>である全てのノード（もちろんc∈A, c≠x[k]）へアーク（エッジ、辺）が繋がっている。（その他にはアークはない。）

●「対称グラフ」
どのアークについても、ノードxからノードyへのアークがあるならば、必ずノードyからノードxへのアークがある。（つまり無向グラフである。）

　こういう意味で宜しいでしょうか。だとしますと、答はもう自明でしょう。
d=2, k=2の場合を考えてみると<01>,<10>,<12>は確かにK(2,2)のノードである。で、<01>←→<10>ですが、<01>→<12>に関しては<12>から<01>へのアークはない。だから対称になりません。

　ではd=1の場合を考えてみますと、kが偶数のときノードは<010...1>,<101...0>の２つしかない。kが奇数のときは<010...0>,<101..1>の２つしかない。いずれも対称グラフになります。

◎どうもご質問における「対称」の意味が、この回答とは微妙に違っているようにしか思えません。（余りに自明だもん。）お考えになっている「対称」を定義していただけませんでしょうか。

補足

stomachmanさん、回答ありがとうございます。

　回答を見せて頂いてから気付いたのですが、私が知りたいのは対称かどうかではなく、再帰構造をしているか(あるサイズのKautz digraphを、更に小さいサイズのいくつかのKautz digraphに分解できるか)でした。すいません。お詫びして訂正します。

　ところで、「対称」の定義についてですが、stomachmanさんのと私のとではかなり違うようです。私の中では、「対称」とは、平たく書けば、「どの頂点から見てもグラフが同じように見える」ということです(堅く書けば、グラフの任意の二頂点i, jに対して、iからjへの自己同型写像が存在するということです)。ちなみに、Kautzと並べられることの多いde Bruijnは対称ではなく、再帰構造もしていません。hypercubeは対称ですし、再帰構造をしています。また、rotator graphは有向グラフですが、対称で再帰構造をしています(と私は認識しています)。