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()

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

とか。

SageMathでグラフ理論

SageMathでグラフを描く描き方はいろいろあるみたいです。

空（カラ）のグラフを作って、頂点や辺を加えていく描き方。

g=Graph()
g.add_vertices(range(6))
g.add_edges([(0,3),(1,3),(2,3),(2,4),(2,5)])
show(g)

次のは頂点と隣接する辺をPythonの辞書にして描く方法です。

sage: g2={0:[3],1:[3],2:[3,4,5]}
sage: G2=Graph(g2)
sage: show(G2)

この他、行列をGraph()に与えても同じグラフが描けます。

で、今知りたいのは頂点と辺のリストとか、行列とかいろんなモデルの相互互換の関数があるかどうか。
グラフに図示したときの点の位置や順番を指定したいのだがどうしたらよいか。
頂点にa,b,cと名前をつける方法はわかったのですが、数字にしたり、順序を変えたりしたい。

とかね。