極大部分群の生成に成功した!

中々埒が明かない.最後の切り札として「べき除リスト」というのを作ってみることにする.べき除リストはべき乗リストの逆リストで,x^k=yのとき,y→xのようにリスティングするものだ.y→x, z なら,yを登録解除するときには同時にxとzも削除される.x^2=e のときは,e→xとなるが,eを削除すると,連鎖してすべての要素が削除されるようになると考えられる.このリストはできればソートして,要素数が少ないものから逐次削除するようにするというのが作りとしては望ましい.これができると,「極大部分群」が文字通り最小コストで生成できる可能性がある.ともかく,やってみることにしよう.

ロジックは一応書いてみたが,どうもこれは反対ではないかという気がしてきた.必要なのは「べき除リスト」ではなく「べき乗リスト」ではないか?というか,構築すべきは,単位元eを根とする生成ツリーではないかと思う.つまり,「1」を根とする木構造だ.もし,このようなものができれば,部分木の生成は葉先から枝刈りしてゆく操作となる.葉を削除してもその上のノードをカットする訳ではないから,このリストは削除の順序を決めるためにのみ用いられるものになるだろう.つまり,優先削除リストだ.隣接リストの逆リストになるのではないか?

これはx^2=yのとき,x→yを記入するためのものであり,x→yは単射であるから,単純な一次元配列でよいのではないか?しかし,この表から読み取りたいのは,むしろ子ノードをいくつ持つかということなので,少なくともその情報が読み取れるようになっていなくてはならない.⇒生成してみた.これで見ると参照カウントがゼロとなっているノードには以下がある.1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22, 24の14個だ.これが優先的に削除してよいノードの候補と言える.

これはストレートに位数12の極大部分群の逆リストになっている.これが位数8の極大部分群になると,半数が葉ノードだ.これはとても正確なリストになっているので,最初に最大限の枝刈りを実行し,それから削除数を減らしてゆくという方法で達成できそうだ.まず,ともかくこれから位数12の極大部分群が取り出せることを確認してみよう.⇒そのものずばり,位数12の極大部分群が生成できた!

極大部分群分解:S4の極大部分群 →
1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22,
◎S4の極大部分群<再構成>は位数12の群である:{e,3,4,7,8,11,12,15,16,19,20,23}

群S4の極大部分群<再構成>の台集合 ={e,3,4,7,8,11,12,15,16,19,20,23}
e→     e, 3, 4, 7, 8, 11, 12, 15, 16, 19, 20, 23,
3→     3, 4, e, 11, 7, 8, 15, 16, 12, 23, 19, 20,
4→     4, e, 3, 8, 11, 7, 16, 12, 15, 20, 23, 19,
7→     7, 12, 19, e, 15, 20, 3, 8, 23, 4, 11, 16,
8→     8, 16, 20, 4, 12, 23, e, 11, 19, 3, 7, 15,
11→    11, 15, 23, 3, 16, 19, 4, 7, 20, e, 8, 12,
12→    12, 19, 7, 20, e, 15, 8, 23, 3, 16, 4, 11,
15→    15, 23, 11, 19, 3, 16, 7, 20, 4, 12, e, 8,
16→    16, 20, 8, 23, 4, 12, 11, 19, e, 15, 3, 7,
19→    19, 7, 12, 15, 20, e, 23, 3, 8, 11, 16, 4,
20→    20, 8, 16, 12, 23, 4, 19, e, 11, 7, 15, 3,
23→    23, 11, 15, 16, 19, 3, 20, 4, 7, 8, 12, e,

極大部分分解の反復テストができない.マウスイベントが取れていない.⇒リブートして動作するようになった.不良の原因は不明.⇒再発した.カーソルの移動はできるが,マウスイベントが入らない.開発環境だけでなく,エディタなどでも動作不良が起きている.タスクバーの上でのクリックは有効だが,それ以外では入らない.かなり具合が悪い.どう対処すればよいか?タスクマネージャだけは使える.アプリを強制終了したら動作するようになった.アリアドネの糸巻きはコンソールを開いているのでその辺りで動作不良が起きているのかもしれない.

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA