タットグラフのソースを表示

{{infobox graph|name=タットグラフ|image=[[Image:Tutte graph.svg|240px]]|image_caption=タットグラフ|namesake={{仮リンク|ウィリアム・トーマス・タット|en|William Thomas Tutte}}|vertices=46|edges=69|automorphisms=3 ('''Z'''/3'''Z''')|girth=4|radius=5|diameter=8|chromatic_number=3|chromatic_index=3|properties=[[立方体グラフ]]<br>[[平面グラフ]]<br>[[多面体グラフ]]}}

'''タットグラフ'''は、46頂点、69辺からなる3-[[正則グラフ]]であり、W・T・タットにちなんで名付けられた<ref>[[:en:Eric_W._Weisstein|Weisstein, Eric W.]] [http://mathworld.wolfram.com/TuttesGraph.html "Tutte's Graph"]. ''[[MathWorld]]''.</ref>。頂点は3色で[[グラフ彩色|彩色]]可能、3-辺彩色可能であり、内周は4、半径は8である。

タットグラフは[[立方体グラフ]]であり[[多面体グラフ]]であるが、[[ハミルトン路]]を持たない。したがって、[[テイトの予想|テイト予想]]の反例である<ref>{{Citation|title=Listing's ''Topologie''|year=1884|last=Tait|first=P. G.|author-link=P. G. Tait|authorlink=P. G. Tait|series=5th Series|journal=[[Philosophical Magazine]]|work=[[Philosophical Magazine]]|volume=17|pages=30–46}}. Reprinted in ''Scientific Papers'', Vol. II, pp. 85–98.</ref>。

1946年にタットはこのテイト予想の反例としてこのグラフを公開した<ref>{{Citation|title=On Hamiltonian circuits|year=1946|last=Tutte|first=W. T.|author-link=W. T. Tutte|authorlink=W. T. Tutte|url=http://jlms.oxfordjournals.org/cgi/reprint/s1-21/2/98.pdf|journal=Journal of the London Mathematical Society|work=Journal of the London Mathematical Society|volume=21|issue=2|pages=98–101|doi=10.1112/jlms/s1-21.2.98|DOI=10.1112/jlms/s1-21.2.98}}.</ref>。そして後に、グリンベルクの定理などにより、他の反例も見つかった。

== 構成 ==
[[ファイル:Tutte_fragment.svg|左|サムネイル|165x165ピクセル|タットの小片]]
タットは、'''タットの小片'''（Tutte fragment）と呼ばれるより小さな構成要素を3つ組み合わせることで、ハミルトン路を持たない多面体グラフを構成した。この小片の飛び出たような辺は「強制的な」辺（＝ハミルトン路の一部に使わなければならない辺）であり、この辺を中心の頂点で3つ連結すると、ハミルトン路はその3つの辺の内2つしか通る事ができない。したがって、タットグラフはハミルトン路を持たない。

組み合わせたグラフは3-正則グラフであり、平面グラフである。したがって、シュタイニッツの定理より、対応する多面体が存在し、その多面体は25個の面を持つ。

この多面体は、四面体から3つの頂点を切り落とすことで幾何学的に実現することができる。4つの大きな面を含む9面からなり、4面のそのうち3つは小片の間に対応し、4つ目は外周に対応する。

== 代数的な性質 ==
タットグラフの[[自己同型群]]は '''Z'''/3'''Z '''であり、3つの元を持つ[[巡回群]]である。

タットグラフの[[固有多項式]]は
: <math>(x-3)(x^{15}-22x^{13}+x^{12}+184x^{11}-26x^{10}-731x^9+199x^8+1383x^7-576x^6-1061x^5+561x^4+233x^3-151x^2+4x+4)^2</math>
: <math>(x^{15}+3x^{14}-16x^{13}-50x^{12}+94x^{11}+310x^{10}-257x^9-893x^8+366x^7+1218x^6-347x^5-717x^4+236x^3+128x^2-56x+4).</math>
である。

== 関連するグラフ ==
タットグラフは1946年に発見された3-正則グラフであり、最初にハミルトン路が存在しないことが知られたグラフであるが、そのような性質を持つグラフの中で最小のグラフではない。

1965年にレーダーバーグは38頂点の Barnette–Bosák–Lederberg グラフを発見した<ref>Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. [http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf].</ref><ref>[[:en:Eric_W._Weisstein|Weisstein, Eric W.]] [http://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html "Barnette-Bosák-Lederberg Graph"]. ''[[MathWorld]]''.</ref>。1968年には、グリンベルクがテイト予想の反例として42、44、46頂点のグリンベルクグラフを追加した<ref>Grinberg, E. J. "Plane Homogeneous Graphs of Degree Three without Hamiltonian Circuits." Latvian Math. Yearbook, Izdat. Zinatne, Riga 4, 51–58, 1968.</ref>。1974年には、フォークナーとヤンガーは42頂点と44頂点の反例を発見した<ref>Faulkner, G. B. and Younger, D. H. "Non-Hamiltonian Cubic Planar Maps." ''[[:en:Discrete_Mathematics_(journal)|Discrete Math.]]'' 7, 67–74, 1974.</ref>。

そして1988年に、ホルトンとマッケイは6種類の38頂点からなるハミルトン路を持たない多面体を見つけた。それらは五角柱の2つの頂点をタットの小片に置き換えたものからなる<ref>{{Citation|title=The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices|year=1988|last=Holton|last1=Holton|last2=McKay|first1=D. A.|first=D. A.|first2=B. D.|author2-link=Brendan McKay|authorlink2=Brendan McKay|journal=Journal of Combinatorial Theory, Series B|work=Journal of Combinatorial Theory, Series B|volume=45|issue=3|pages=305–319|doi=10.1016/0095-8956(88)90075-5|DOI=10.1016/0095-8956(88)90075-5}}.</ref>。

== 出展 ==
{{reflist}}

{{DEFAULTSORT:たつとくらふ}}
[[Category:数学に関する記事]]