問題12.1(i) 頂点数5の車輪Wheel、が平面グラフであることをグラフで示せ。(ii) octahedron(八面体)が平面グラフであることをグラフで示せ。 すなおに描くと平面グラフになってしまう。 問題の意図としては必ずしも平面グラフでないものを平面グラフ的(plana…

THEOREM 12.2(Kuratowski, 1930). A graph is planar if and only if it contains no subgraph homeomorphic to or . グラフが平面グラフであるための必要十分条件はが またはと位相同型な部分グラフを含まないことである。 THEOREM 12.3 A graph is planar …

次数(degree)の数列を与えられて単純グラフ（ループや多重辺がないグラフ）が描けるかどうか（グラフ的）かどうかを問う問題があります。 例えば[3,3,3,3,3,3]だと3点と3点の完全二部グラフが描けますのでグラフ的である、という解答が載っていたりする。 し…

接続行列からでもグラフがかけるか実験します。 接続行列Mで与えられるグラフを描け。 M=matrix(5,8,[[0,0,1,1,1,1,1,0],[0,1,0,1,0,0,0,1],[0,0,0,0,0,0,0,1],[1,0,1,0,1,0,1,0],[1,1,0,0,0,1,0,0]]) G=Graph(M)show(G) 描けました。 ということは、接続行…

introduction to graph theory by wilsonのp.11のFig.2.9は頂点が5個までの連結グラフ(connected unlabelled graph)で、31個ある。 これを作る。 （なぜならテキストの練習問題で何度も使われるから。例えば、この内、ツリーはどれとどれか。とか。） sage: …

まず、ひとつグラフを作ります。 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…

Pythonのdictionaryの形で次のように指定すると、グラフが描けます。 g1=Graph({'P':['Q','S','T'],'Q':['R','S','T'],'R':['S'],'S':['T']})show(g1) これはうまい具合に横向きになったし、なによりも頂点がアルファベット順ですがいつも必ずしもそうではあ…

下記のグラフのすべての全域木(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) 同様に次のグラフのspan…

頂点が6個の単純グラフでツリーがいくつ作れるか。 6個のようです。 以下、図とSageMathのプログラムです。 pythonのfilterを使ってみました。 pythonでmapやfilterが使えるのを知らなかったし、lambdaにグラフを入れられるのも知らなかったし、is_treeで選…

プラトングラフとは正四面体、正八面体、立方体、正十二面体グラフと正二十面体グラフのことだそうです。 とりあえずSageMathでグラフで表現することができたのでご紹介。 # platonic.sage# plot five platonic graphs.# attach('platonic.sage') p1=plot(gr…

グラフが同型である、ということの定義はこれこれ（要確認）、同型であることを判定する関数はG,Hをグラフとすると、 G.is_isomorphic(H) とかであろう、と予想されます(未確認)。 ところでグラフが同型であることのアルゴリズムはカノニカル(canonical)型に…

SageMathでグラフを描く描き方はいろいろあるみたいです。 空（カラ）のグラフを作って、頂点や辺を加えていく描き方。 g=Graph()g.add_vertices(range(6))g.add_edges([(0,3),(1,3),(2,3),(2,4),(2,5)])show(g) 次のは頂点と隣接する辺をPythonの辞書にして…

WilsonのIntroduction to Graph Theoryに、図のGrötzschグラフがハミルトングラフであることを示せ、という練習問題がありました。 SageMathでこういった名前がついたグラフを描くのはとても簡単です。 sage: g=graphs.GrotzschGraph()sage: show(g) graphs…