この解法のグラフはどういった形なのでしょうか。グラフ理論初学者でありあまりよくわかりません。詳しくお

この解法のグラフはどういった形なのでしょうか。グラフ理論初学者でありあまりよくわかりません。詳しくおしえていただけると嬉しいです。

No.6 ベストアンサー 回答者： ありものがたり 回答日時： 2024/12/21 18:27

G0 に 5本の辺があり、それが G2 の 5個の頂点になる。

G0 の各辺は他の 4本の辺全てと(マークがあるとは限らない頂点で)交わっている
から、 G2 の各頂点は他の 4頂点との間に辺を持つ。
これは、G2 が 5-完全グラフであることを示しています。

G0 の頂点の中から 5個にマークをつけるというのは、
G2 の辺の中から 5本にマークをつけることに相当します。
G0 のどの辺にもマークがついた頂点が 2個あるということは、
G2 のどの頂点もマークのついた辺 2本と接続しているということです。

G2 からマークのついた辺だけを取り出したグラフが G です。
G は 5個の頂点を持ち、各頂点が 2本の辺と接続するグラフです。
そのようなグラフは、閉路のみからなりますが、
閉路が複数に分かれていたとすると、頂点 2個以下の閉路があることになります。
m≧3, n≧3 だと、m+n>5 になってしまいますからね。←[＊]
G0 の辺が自分自身と交わらないことから G2 に 1-閉路はなく、
G0 の辺の組が 2個以上交点を持たないことから G2 に 2-閉路はありません。
G2 になければ G にもないわけで、よって[＊]より G は 1つの閉路のみからなる、
すなわち 5-閉路であることが判ります。

以上で、この問題が、5-完全グラフ G2 の部分グラフに 5-閉路 G は何個あるか？
を数える問題だと解釈できることが判りました。
頂点が 5個のグラフの部分グラフが 5-閉路なら、それはハミルトン閉路です。
...てなことは、既に写真の解答の中に書いてあるんだがな。

No.5 回答者： ありものがたり 回答日時： 2024/12/16 19:02

大事なところに誤字があったので、修正：

---------------------------------------------------------------------------------------------
問題の図のグラフを G0 として、
解答のグラフ G とはまた別のグラフ G2 を以下のように定義する。
G0 の各辺を G2 の頂点とし、
G0 の辺と辺が(マークの有無に関わらず)交点を持つことを G2 の辺で表す。

こうして作った G2 は、G0 の頂点と辺を入れ替えたようなグラフになる。
G2 が 5-完全グラフ であることはすぐ判る。
G は G2 の部分グラフであり、解答の考えにより 5-閉路 である。

つまり、問題は 完全グラフにハミルトン閉路はいくつあるか？
と言い換えられたことになる。
それが 5-数珠順列であることは、解答の説明にあるとおり。

質問は、G0 と G2 の関係を何と言うか？ ということなんだろうが、
何て言うんだろうね？ 双対グラフとも違うし...
---------------------------------------------------------------------------------------------

Ｇ２ は、下図の K5 になる。
これの 5頂点全てを 1回づつ巡る閉路がハミルトン閉路。
G2 から取り出して閉路だけを眺めると、
輪っかの上に 5個の頂点が並んでいるものに見える。
その総数は？ というと、5-数珠順列だというわけ。

数珠順列については、参考↓
https://juken-mikata.net/how-to/mathematics/circ …

この回答へのお礼

問題は完全グラフにハミルトン閉路はいくつあるか？といいかえられる理由をもう少し詳しく説明していただけるとありがたいです

お礼日時：2024/12/21 16:07

No.4 回答者： mtrajcp 回答日時： 2024/12/16 17:12

5本の直線に v1,v2,v3,v4,v5 を対応させると

No.3 回答者： ありものがたり 回答日時： 2024/12/16 14:56

問題の図のグラフを G0 として、

解答のグラフ G とはまた別のグラフ G2 を以下のように定義する。
G の各辺を G2 の頂点とし、
G の辺と辺が(マークの有無に関わらず)交点を持つことを G2 の辺で表す。

こうして作った G2 は、G の頂点と辺を入れ替えたようなグラフになる。
G2 が 5-完全グラフ であることはすぐ判る。
G は G2 の部分グラフであり、解答の考えにより 5-閉路 である。

つまり、問題は 完全グラフにハミルトン閉路はいくつあるか？
と言い換えられたことになる。
それが 5-数珠順列であることは、解答の説明にあるとおり。

質問は、G と G2 の関係を何と言うか？ ということなんだろうが、
何て言うんだろうね？ 双対グラフとも違うし...

No.2 回答者： mtrajcp 回答日時： 2024/12/16 14:40

画像の通り

No.1 回答者： Tacosan 回答日時： 2024/12/16 03:06

「この解法のグラフ」が何をさしているのかわからんのだけど, 最終的に使っているのは「5-サイクル」って書いてあるよね.

「5頂点のグラフ」がどのようなものかわからない, ということではないよね?

この回答へのお礼

なぜ最終的にそうなるかがわかりません。どういった対応をなしているのでしょうか

お礼日時：2024/12/16 08:21