SageMathとグラフ理論（連結グラフ）

introduction to graph theory by wilsonのp.11のFig.2.9は頂点が5個までの連結グラフ(connected unlabelled graph)で、31個ある。

これを作る。

（なぜならテキストの練習問題で何度も使われるから。例えば、この内、ツリーはどれとどれか。とか。）

sage: len (filter (lambda G: G.is_connected(), list(graphs(1)) + list(graphs(2))
....: + list(graphs(3)) + list(graphs(4)) + list(graphs(5))))
31

数は合っているみたいなので、これからグラフを描いてみる。

sage: glist = filter (lambda G: G.is_connected(), list(graphs(1)) + list(graphs(
....: 2)) + list(graphs(3)) + list(graphs(4)) + list(graphs(5)))
sage: p0=plot(Graph(0))
sage: gplotlist = map (plot, glist)
sage: graphics_array( (gplotlist + [p0]*4), 7, 5)

こうしておけば、この内ツリーはどれとどれかというのは次のように解けます。

sage: len(filter (lambda G: G.is_tree(), glist))
8

sage: glist2=filter (lambda G: G.is_tree(), glist)
sage: gplotlist2= map(plot, glist2)
sage: graphics_array(gplotlist2, 2)

SageMathとグラフ理論（隣接行列、接続行列、ラプラシアン（キルヒホフ）行列）

まず、ひとつグラフを作ります。

V=['P','Q','R','S','T']
E=[['P','Q'],['Q','R'],['R','S'],['S','T'],['T','P'],['P','S'],['Q','T'],['Q','S']]
g=Graph([V,E])

隣接行列

sage: g.adjacency_matrix()
[0 1 0 1 1]
[1 0 1 1 1]
[0 1 0 1 0]
[1 1 1 0 1]
[1 1 0 1 0]

接続行列
sage: g.incidence_matrix()
[1 0 0 0 1 1 0 0]
[1 1 1 1 0 0 0 0]
[0 0 1 0 0 0 1 0]
[0 1 0 0 1 0 1 1]
[0 0 0 1 0 1 0 1]

ラプラシアン行列

sage: g.laplacian_matrix()
[ 3 -1 0 -1 -1]
[-1 4 -1 -1 -1]
[ 0 -1 2 -1 0]
[-1 -1 -1 4 -1]
[-1 -1 0 -1 3]

キルヒホフ行列

sage: g.kirchhoff_matrix()
[ 3 -1 0 -1 -1]
[-1 4 -1 -1 -1]
[ 0 -1 2 -1 0]
[-1 -1 -1 4 -1]
[-1 -1 0 -1 3]

ヘルプによると、ラプラシアン行列とキルヒホフ行列は同じものだそうです。

SageMathとグラフ理論（カノニカル行列）

Pythonのdictionaryの形で次のように指定すると、グラフが描けます。

g1=Graph({'P':['Q','S','T'],'Q':['R','S','T'],'R':['S'],'S':['T']})
show(g1)

これはうまい具合に横向きになったし、なによりも頂点がアルファベット順ですがいつも必ずしもそうではありません。

ただし、隣接行列の形は常に一緒です。

g1.adjacency_matrix()
[0 1 0 1 1]
[1 0 1 1 1]
[0 1 0 1 0]
[1 1 1 0 1]
[1 1 0 1 0]

たぶん人間には一番わかり易い頂点のリストと辺のリストを組み合わせた指定の仕方をしてみます。

V=['P','Q','R','S','T']
E=[['P','Q'],['Q','R'],['R','S'],['S','T'],['T','P'],['P','S'],['Q','T'],['Q','S']]
g2=Graph([V,E])
show(g2)

g2.adjacency_matrix()
[0 1 0 1 1]
[1 0 1 1 1]
[0 1 0 1 0]
[1 1 1 0 1]
[1 1 0 1 0]

行列の形が同じになりましたが、これは偶然かもしれない。

カノニカルラベルに振りなおしてみます。

(g1.canonical_label()).adjacency_matrix()
[0 0 0 1 1]
[0 0 1 1 1]
[0 1 0 1 1]
[1 1 1 0 1]
[1 1 1 1 0]

今度は行列の形は違いますが、同じもののはずです。

g3=Graph( (g1.canonical_label()).adjacency_matrix())
show(g3)

g1.is_isomorphic(g3)
True
g2.is_isomorphic(g3)
True

ほらね。

SageMathとグラフ理論（全域木）

下記のグラフのすべての全域木(spanning tree）を描け。

g=Graph([['a','b'],['b','c'],['c','d'],['d','a'],['a','c']])

[p1,p2,p3,p4,p5,p6,p7,p8]=map (plot, g.spanning_trees())

graphics_array((p1,p2,p3,p4,p5,p6,p7,p8),2,4)

同様に次のグラフのspaning treeを描け。

SageMathとグラフ理論（ツリー）

頂点が6個の単純グラフでツリーがいくつ作れるか。

6個のようです。

以下、図とSageMathのプログラムです。

pythonのfilterを使ってみました。

pythonでmapやfilterが使えるのを知らなかったし、lambdaにグラフを入れられるのも知らなかったし、is_treeで選択できるのも知りませんでした。うむ。便利。

1 # tree01.sage
2 #
3 # attach('tree01.sage')
4
5 gen=list(graphs(6))
6 gen1=filter(lambda G: G.is_tree(), gen)
7
8 print(len(gen1)) # -> 6
9 [p1,p2,p3,p4,p5,p6] = map (plot, gen1)
10 # graphics_array((p1,p2,p3,p4,p5,p6),2,3)

7頂点で同じことをやってみたら11個グラフができました。

SageMathとグラフ理論（プラトングラフ）

プラトングラフとは正四面体、正八面体、立方体、正十二面体グラフと正二十面体グラフのことだそうです。

とりあえずSageMathでグラフで表現することができたのでご紹介。

# platonic.sage
# plot five platonic graphs.
# attach('platonic.sage')

p1=plot(graphs.TetrahedralGraph())
p2=plot(graphs.OctahedralGraph())
p3=plot(graphs.HexahedralGraph())
p4=plot(graphs.IcosahedralGraph())
p5=plot(graphs.DodecahedralGraph())
p6=plot(Graph())

graphics_array(((p1,p2,p3),(p4,p5,p6)))

SageMathとグラフ理論(同型判定、カノニカルラベル)

グラフが同型である、ということの定義はこれこれ（要確認）、同型であることを判定する関数はG,Hをグラフとすると、

G.is_isomorphic(H)

とかであろう、と予想されます(未確認)。

ところでグラフが同型であることのアルゴリズムはカノニカル(canonical)型に変形して同じグラフになることらしい。計算量が半端ないようなことがグラフ理論の本に書いてある。

SageMathを検索すると、canonical_label()という関数があって、

G.canonical_label()

という風に使うらしい。

名前からみて、たぶん頂点の番号を振り直すのだろう。だとすると便利かもしれない。

G.canocnial_label().adjacent_matrix()

とすると、行列にしてくれるので、性質が研究できる。

とか。