[ 掲示板に戻る ]
記事No.86052に関するスレッドです
★ 同型 / 浜田
次の２つのグラフは同型ですか？
もしそうならなぜそうなるか説明してください。もし違うなら、どうするば同型になるか説明してください。
No.86052 - 2023/07/28(Fri) 11:29:50
☆ Re: 同型 / ポテトフライ
「グラフの同値の定義」を少し考えれば簡単にわかると思うが・・・。

とりあえず全単射を片っ端から考えてみて辺がどうなるか見ていけばよいでしょう。
（頂点が5程度なのでどうにかできるだろうし、さらに規則性などが見いだせれば同型かどうかはすぐわかると思う）
No.86058 - 2023/07/28(Fri) 21:46:48
☆ Re: 同型 / 浜田
1)それぞれのグラフの点の数、辺の数が同じかを確認。

2)それぞれのグラフの次数列が同じになるかを確認。
（次数列ではなくても、それぞれの次数が何個あるかを確認して,2つの次数で完全一致するかどうかを確認すればいい。）

3)同じ次数の点に対して、それぞれの点に隣接する点の次数を比べて一致するかを確認

上の３つを満たすことは確認しましたが、あくまでこれらは同型であるための必要条件ですよね？

なので、これらを満たしても同型であるかどうかはわからないので、どうすればいいかわかりません。
No.86063 - 2023/07/28(Fri) 23:18:20
☆ Re: 同型 / ポテトフライ
>あくまでこれらは同型であるための必要条件ですよね？

そうです。
なんか難しく考えすぎているような気がします。

もっと素直ににグラフの同型の定義
全単射f:V_1 → V＿2で、任意のx,y∈V_1に対してxy∈E＿1⇔f(x)f(y)∈E_2
となる写像fがあるかどうかを調べていけばよいです。
No.86064 - 2023/07/28(Fri) 23:59:10
☆ Re: 同型 / らすかる
3を四角形1245の内部に移動すればわかるのでは？
No.86066 - 2023/07/29(Sat) 00:34:19
☆ Re: 同型 / 浜田
ありがとうございます
No.86070 - 2023/07/29(Sat) 12:04:35