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からスタートすれば描けるのですが、閉路にすることができない。ということかな。だとすると準ハミルトングラフか。
とか。
