次数(degree)の数列を与えられて単純グラフ（ループや多重辺がないグラフ）が描けるかどうか（グラフ的）かどうかを問う問題があります。
例えば[3,3,3,3,3,3]だと3点と3点の完全二部グラフが描けますのでグラフ的である、という解答が載っていたりする。
しかしこれはたまたま解けただけであって、完全二部グラフ以外に[3,3,3,3,3,3]のグラフがあるかどうかもわからないし、そもそも思いつかなかったら描けないことをどう証明するのか。
と思ったりして、次数を与えて、グラフが描けるかどうかを調べる関数を探してみたらありました。
G=graphs.DegreeSequence([3,3,3,3])
show(G)
G=graphs.DegreeSequence([3,3,3,4])
-> invalid degree sequence
[3,3,3,4]ではグラフが描けないので、エラーになります。つまり、[3,3,3,4]はグラフ的ではない。
次に[3,3,3,3,3,3]の場合。
G=graphs.DegreeSequence([3,3,3,3,3,3])
show(G)
で描けたのはいいのですが、完全二部グラフではない。完全二部グラフだと次のようになります。
G2=graphs.CompleteBipartiteGraph(3,3)
show(G2)
グラフ的かどうかは解けたけど、今度は別の問題が生じてしまいました。
いくつ書けるのか。同じものなのか。
G==G2
False
G.is_isomorphic(G2)
False
ちがうらしい。同型ではない。
G=graphs.DegreeSequence([3,3,3,3,3,3])
では描けるものを描くだけで、他にもグラフがあるかどうかは示してくれないようなので、他の方法を考える必要があります。
list(G.degree_iterator())
[3, 3, 3, 3, 3, 3]
とすると、次数の数列にしてくれるので、6頂点のグラフすべての次数の数列を作って、これと同じグラフがいくつあるかしらべるのがいいと思う。めんどくさそうだけど、ちょっと試行錯誤してみます。
Glist=filter (lambda G: G.is_connected(), graphs(6))
len(Glist)
112
うむ。連結グラフだけで112個もある。
しかし一応この112個は同型ではないはずなので、これを順々にフィルターにかけていく。
Glist2 = map (lambda G: G.degree_iterator(), Glist)
Glist3 = map (list , Glist2)
Glist4 = filter (lambda L: L == [3,3,3,3,3,3], Glist3)
len(Glist4)
2
Glist2で次数を数えて、Glist3でそれをリストにして、Glist4で[3,3,3,3,3,3]のものを抜いて、要素数を数えると2個だったので、[3,3,3,3,3,3]のラベル無しのグラフは2種類しかないことが確認できたと思います。
うむ。このやり方では数しかわからないけど、まあ、今日はここまで。
