現在地 HOME > 掲示板
> 雑談専用６ > 314.html
★阿修羅♪
|
現在地 HOME > 掲示板
> 雑談専用６ > 314.html
★阿修羅♪
|
|
(回答先: カバラ神秘主義を離散数学で乗り越える 投稿者 きゃべ爺 日時 2003 年 11 月 18 日 09:13:42)
> グラフ理論的には木と
> サイクル（セット）は完全に双対な概念です．（※双対：それぞれについて完全に対称
> 的な定理が対応する名前を入れ替えただけで成立すること．）
上記の記述はグラフ理論的に初歩的に完全に誤っております．<(_ _)>
木とサイクルの対比を強調するあまり，つい筆が滑ってしまいました．
この部分の記述は（永久に）抹消してください．申し訳ありませんでした．
この部分を削除しても，記述の残りの部分に関してはなんら影響ありません．
木とサイクルの関係は本文に記した通り，以下に尽きます．
＜木はサイクルを持たない極大なグラフである＞
木とサイクルの補足： グラフのすべての点を通る木を全域木と言います．
連結なグラフ（つながっているグラフ）は少なくとも１個の全域木をもっています．
もちろん，サイクルについてはこのようなことは言えません．（木は連結でかつ，
サイクルを持っていない．全域サイクルの別名はハミルトンサイクルであり，
それを探す問題が，ハミルトン閉路問題⊂NP完全問題であるのだから当然．）
創世記で神はアダムのあばら骨を取って女を造ったとありますが，もし，
木が男性でサイクルが女性であるとすると，なんとなくうなずけます．
（いかに男性が単純であり，女性が複雑であるかを示しているようにも見える．
また，序列＝全域木はあらゆる集団の中に存在しているのに，そこに和合＝
全域サイクルを求めるのはとても難しいことを示しているようにも読める．）
グラフの双対性(duality)に関しては，やや専門的になりますが，以下が言えます．
連結なグラフから辺の集合を取り除いたとき，グラフが連結でなくなるような極大な
辺の集合をカットセットと言う．グラフに含まれるサイクルの族（部分集合の集合），
およびカットセットの族はマトロイドと呼ばれる共通の属性を持ち，マトロイド属性
から導かれる任意の定理について双対(dual)であると言える．
詳しくは類書をご覧ください．
（ネット上には適当な参考書がまだない．米国サイトにはある．まだまだ負けてるよ！）
題名には必ず「阿修羅さんへ」と記述してください。