下記のグラフのすべての全域木(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と名前をつける方法はわかったのですが、数字にしたり、順序を変えたりしたい。
とかね。
SageMathでグラフ理論
WilsonのIntroduction to Graph Theoryに、図のGrötzschグラフがハミルトングラフであることを示せ、という練習問題がありました。
SageMathでこういった名前がついたグラフを描くのはとても簡単です。
sage: g=graphs.GrotzschGraph()
sage: show(g)
graphsのあとにピリオドを売って、Tabキーを押すと候補が出ますので、その中からGrotzschGraphを選びます。
次にこれがハミルトングラフかどうか判定します。
sage: g.is_hamiltonian()
True
便利ですねー。
完全二分木がハミルトングラフかどうか、という問題もありました。
これは、
sage: g=graphs.CompleteBipartiteGraph(2,3)
sage: show(g)
で描いたもので、
sage: g.is_hamiltonian()
False
となるのでハミルトングラフではないらしい。全部の頂点を1回だけ通る経路は3からスタートすれば描けるのですが、閉路にすることができない。ということかな。だとすると準ハミルトングラフか。
とか。
SageMath LaTeX Error: File `preview.sty' not found.
数学ソフトのSageMathのドキュメントでConstructionsというのの最初の方に、次のような例があって、
sage: var('x k w')
sage: f = x^3 * e^(k*x) * sin(w*x)
sage: f.diff(x)
sage: latex(f.diff(x))
sage: view(f.diff(x))
最後の一行で、LaTexに画像変換されたウィンドウが開きます。
LaTeX Error: File `preview.sty' not found.
というエラーが出たので、次のようにパッケージをインストールして解決しました。
sudo apt-get install preview-latex-style
環境はubuntu16.04、SageMathは7.5.1です。
以上
