★阿修羅♪ 現在地 HOME > 掲示板 > 雑談専用6 > 314.html
 ★阿修羅♪
次へ 前へ
この部分の記述は(永久に)抹消してください.
http://www.asyura2.com/0311/idletalk6/msg/314.html
投稿者 きゃべ爺 日時 2003 年 11 月 18 日 18:14:22:jfzS9MOte8/0k

(回答先: カバラ神秘主義を離散数学で乗り越える 投稿者 きゃべ爺 日時 2003 年 11 月 18 日 09:13:42)

> グラフ理論的には木と
> サイクル(セット)は完全に双対な概念です.(※双対:それぞれについて完全に対称
> 的な定理が対応する名前を入れ替えただけで成立すること.)

上記の記述はグラフ理論的に初歩的に完全に誤っております.<(_ _)>
木とサイクルの対比を強調するあまり,つい筆が滑ってしまいました.
この部分の記述は(永久に)抹消してください.申し訳ありませんでした.
この部分を削除しても,記述の残りの部分に関してはなんら影響ありません.

木とサイクルの関係は本文に記した通り,以下に尽きます.

<木はサイクルを持たない極大なグラフである>

木とサイクルの補足: グラフのすべての点を通る木を全域木と言います.
連結なグラフ(つながっているグラフ)は少なくとも1個の全域木をもっています.
もちろん,サイクルについてはこのようなことは言えません.(木は連結でかつ,
サイクルを持っていない.全域サイクルの別名はハミルトンサイクルであり,
それを探す問題が,ハミルトン閉路問題⊂NP完全問題であるのだから当然.)

創世記で神はアダムのあばら骨を取って女を造ったとありますが,もし,
木が男性でサイクルが女性であるとすると,なんとなくうなずけます.

(いかに男性が単純であり,女性が複雑であるかを示しているようにも見える.
また,序列=全域木はあらゆる集団の中に存在しているのに,そこに和合=
全域サイクルを求めるのはとても難しいことを示しているようにも読める.)

グラフの双対性(duality)に関しては,やや専門的になりますが,以下が言えます.

連結なグラフから辺の集合を取り除いたとき,グラフが連結でなくなるような極大な
辺の集合をカットセットと言う.グラフに含まれるサイクルの族(部分集合の集合),
およびカットセットの族はマトロイドと呼ばれる共通の属性を持ち,マトロイド属性
から導かれる任意の定理について双対(dual)であると言える.

詳しくは類書をご覧ください.
(ネット上には適当な参考書がまだない.米国サイトにはある.まだまだ負けてるよ!)

 次へ  前へ

雑談専用6掲示板へ



フォローアップ:


 

 

 

 

  拍手はせず、拍手一覧を見る


★登録無しでコメント可能。今すぐ反映 通常 |動画・ツイッター等 |htmltag可(熟練者向)|(各説明

←ペンネーム新規登録ならチェック)
↓ペンネーム(なしでも可能。あったほうが良い)

↓パスワード(ペンネームに必須)

(ペンネームとパスワードは初回使用で記録、次回以降にチェック。パスワードはメモすべし。)
↓画像認証
( 上画像文字を入力)
ルール確認&失敗対策
画像の URL (任意):
投稿コメント全ログ  コメント即時配信  スレ建て依頼  削除コメント確認方法
★阿修羅♪ http://www.asyura2.com/  since 1995
 題名には必ず「阿修羅さんへ」と記述してください。
掲示板,MLを含むこのサイトすべての
一切の引用、転載、リンクを許可いたします。確認メールは不要です。
引用元リンクを表示してください。