質問: ここが適切な場所か分からないのですが・・・。 Kautz digraphは、対称グラフなのでしょうか。K(d, k)として、d=2のときはそのような気がしますが、自信が持てません。また、d>3のときについてはカイモク見当もつきません。 どなたかご存知の方、ご教授頂ければ幸いです。
回答: なるほど、「どのノードから見ても同じに見える」とおっしゃる意味がやっと理解できました。先にstomachmanが書いたのは語の文字を置換する話なので、語の構造を保存するような変換しか許しません。この意味での対称性は自明ですが、語の構造が違う任意のノード同士を対応付けることはできないですね。ですからご質問の本来の意図における「対称性」に関しては、多分「対称でない」というのが答だと思います。実際反例を挙げていらっしゃるのだから、あとは「対称性」をきちんと定義しさえすれば、問題は解決したことになるのでは? 「再帰性」に関しては、もっと美しい構造があるのかも知れませんが、何しろ初学者なもので.... なお、Kautz digraphはk文字分の記憶を持つ非同期の有限オートマトンの状態遷移図(つまり入力が変化した時に状態遷移を起こし、新しい入力がcであるとき→へ移る)と見なすことができるように思われます。