グラフ

質問

3連結グラフの定義を分かりやすく教えてください
お願いします

回答No.4

tiezo- · ベストアンサー

NO.2の者ですが、例え話のほうが間違いです。
　定義は正しいです。すみません。

　ある国にいくつかの町があり道でつながっていたとします。
　その国が３連結であるとは、どの二つの町を除いても
　その国のその他の町はつながっているということです。
　除くのは、道ではなく点のほうでした。

　連結度とは、最小切断集合の点の個数のことです。
　いくつ点を除くと連結でなくなるかということです。

回答No.3

nyonta

すいません。NO1の者ですが
「３連結」という表現が有ることを知りませんでした。
しかし、tiezo-さんの町と橋の話から推測すると、

「グラフＧが　k-連結であるとは、Ｇからどんな（k-1）個の点を除去しても
　その結果得られるグラフは非連結でも単点でもない。」
は
「グラフＧが　k-連結であるとは、Ｇからどんな（k-1）個の道を除去しても
　その結果得られるグラフは非連結でも単点でもない。」

では、ないのでしょうか？
(僕の出しゃばりでしたらすいません。)

回答No.2

tiezo-

連結の定義は、
　グラフにおいて任意の二点に道が存在することである。
ｋ-連結の定義は
　グラフＧが　k-連結であるとは、Ｇからどんな（k-1）個の点を除去しても
　その結果得られるグラフは非連結でも単点でもない。

３連結グラフであれば、どんな２点を除去しても
非連結にも単点にもならないことです。
すなわち、連結であるということです。

たとえば、単なる連結であれば、一つの橋が壊れただけで
行けない所が出てくるかもわからないですが、
どの二つの橋が壊れても行けないところが
ないならば、その町は３連結の町であるということだと思います。

回答No.1

nyonta

こんばんわデス。
えっと、僕はまだ高校生のため、習ってないだけと言う可能性も有りますが、
これだけ待っても誰一人回答しないので、回答することにします。
「連結グラフ」なら分かりますが、「3連結グラフ」はやはり分かりません。
少し調べてみましたが、やはり分かりませんでした。
おそらく無いのでは無いでしょうか？どこで見かけたのでしょうか？
もしかしてこういう事は無いですか？

1○○グラフについて
　（うだうだうだ・・・）
2××グラフについて
　（うだうだうだ・・・）
3連結グラフについて
　（うだうだうだ・・・）

どうでしょうか？あと、「連結グラフ」の定義なら分かりますよね？
連結グラフの「位数が３」とか「３部グラフ」なら言うんですけどねぇ・・・
どうなんでしょう？
では、お役に立てませんでしたが、ずっと放置しておくよりかはマシかなと・・・