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

Question

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

ありものがたり · Accepted Answer

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-閉路なら、それはハミルトン閉路です。
...てなことは、既に写真の解答の中に書いてあるんだがな。

ありものがたり · Answer

大事なところに誤字があったので、修正：
---------------------------------------------------------------------------------------------
問題の図のグラフを 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/circular_permutation.html

mtrajcp · Answer

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

ありものがたり · Answer

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

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

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

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

mtrajcp · Answer

画像の通り

Tacosan · Answer

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

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

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

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

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

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

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

画像の通り

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

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング