ヒーウッドグラフのソースを表示

{{infobox graph
 | name = ヒーウッドグラフ
 | image = [[Image:Heawood_Graph.svg|180px]]
 | image_caption = 
 | namesake = {{仮リンク|パーシー・ジョン・ヒーウッド|en|Percy John Heawood}}
 | vertices = 14
 | edges = 21
 | girth = 6
 | diameter = 3
 | radius = 3
 | automorphisms = 336 ([[射影線型群|PGL<sub>2</sub>(7)]])
 | chromatic_number = 2 
 | chromatic_index = 3
 | properties = [[2部グラフ|2部]]<br>[[立方体グラフ|立方体]]<br>[[ケージ (グラフ理論)|ケージ]]<br>[[距離推移グラフ|距離推移的]]<br>{{仮リンク|距離正則グラフ|label=距離正則|en|Distance-regular graph}}<br>{{仮リンク|トロイダルグラフ|label=トロイダル|en|Toroidal graph}}<br>[[ハミルトングラフ|ハミルトン]]<br>[[対称グラフ|対称]]<br>向き付け可能・単純
}}

[[数学]]の[[グラフ理論]]の分野における'''ヒーウッドグラフ'''（{{Lang-en-short|Heawood graph}}）は、{{仮リンク|パーシー・ジョン・ヒーウッド|en|Percy John Heawood}}の名にちなむ、14の頂点と21の辺を含むある[[無向グラフ]]である<ref>{{MathWorld | urlname=HeawoodGraph | title=Heawood Graph}}</ref>。

== 組合せの性質 ==
ヒーウッドグラフは[[立方体グラフ|立方体]]であり、それに含まれるすべての閉路には六つ以上の辺がある。これよりも小さいすべての立方体グラフにはより短い閉路しか含まれないため、ヒーウッドグラフは 6-[[ケージ (グラフ理論)|ケージ]]の、[[内周 (グラフ理論)|内周]] 6 の最小の立方体グラフである。また、[[距離推移グラフ]]（[[対称グラフ|フォスター調査]]を参照）でもあり、したがって{{仮リンク|距離正則グラフ|label=距離正則|en|Distance-regular graph}}である<ref name="brouwer">{{cite web | author=Brouwer, Andries E. | authorlink = :en:Andries Brouwer | title = Heawood graph | url = http://www.win.tue.nl/~aeb/drg/graphs/Heawood.html | work = [http://www.win.tue.nl/~aeb/drg/index.html Additions and Corrections to the book ''Distance-Regular Graphs''] (Brouwer, Cohen, Neumaier; Springer; 1989)|accessdate=2012-10-19}}</ref>。

ヒーウッドグラフには 24 の[[マッチング (グラフ理論)|完全マッチング]]が存在する;各マッチングに対し、それに含まれない辺の集合は[[ハミルトン閉路]]を形成する。例えば、ページ右上の図は、マッチングを形成する閉路からなる内部対角（internal diagonal）を備える閉路上の頂点を示しているグラフである。その閉路を二つのマッチングに分けることで、ヒーウッドグラフを三つの完全マッチング（すなわち、[[グラフ彩色|3辺彩色]]）に分ける方法が八通りある<ref name="brouwer"/>。どの二つの完全マッチングと、どの二つのハミルトン閉路も、グラフの対称性によってお互い交換することが出来る<ref>{{citation
 | last1 = Abreu | first1 = M.
 | last2 = Aldred | first2 = R. E. L.
 | last3 = Funk | first3 = M.
 | last4 = Jackson | first4 = Bill
 | last5 = Labbate | first5 = D.
 | last6 = Sheehan | first6 = J.
 | doi = 10.1016/j.jctb.2004.09.004
 | mr = 2099150
 | issue = 2
 | journal = [[:en:Journal of Combinatorial Theory|Journal of Combinatorial Theory]] | series = Series B
 | pages = 395–404
 | title = Graphs and digraphs with all 2-factors isomorphic
 | volume = 92
 | year = 2004}}.</ref>。

ヒーウッドグラフには 6-頂点の閉路が 28 含まれる。そのような 6-閉路は、必ず三つの他の 6-閉路と互いに素になっている;そのような三つの 6-閉路において、どの一つも必ず他の二つの対称差（symmetric difference）になっている。6-閉路に対して一つの頂点と、6-閉路の互いに素な各ペアに対して一つの辺を備えるグラフは、{{仮リンク|コクセターグラフ|en|Coxeter graph}}である<ref>{{citation|first=Italo J.|last=Dejter|title=From the Coxeter graph to the Klein graph|journal=Journal of Graph Theory|year=2011|doi=10.1002/jgt.20597|arxiv=1002.1960}}.</ref>。

== 幾何および位相的性質 ==
ヒーウッドグラフは{{仮リンク|トロイダルグラフ|en|toroidal graph}}である; すなわち、ヒーウッドグラフは[[トーラス]]上で交叉することなく埋め込まれる。このタイプの一つの埋め込みは、その頂点と辺を三次元[[ユークリッド空間]]へ、あるトーラスの位相を備える非凸多面体（{{仮リンク|シラッシの環状多面体|en|Szilassi polyhedron}}）の頂点と辺の集合として配置する。

グラフの名の由来である{{仮リンク|パーシー・ジョン・ヒーウッド|en|Percy John Heawood}}は1890年、トーラスの多角形への全ての細分割において、その多角形領域は高々七色の色で彩色されることを証明した<ref>{{cite journal | doi=10.2307/3219140 | author=Brown, Ezra | title = The many names of (7,3,1) | journal = [[:en:Mathematics Magazine|Mathematics Magazine]] | volume=75 | issue=2 | year=2002 | pages=83–94 | url=http://www.math.vt.edu/people/brown/doc/731.pdf | jstor=3219140}}</ref><ref>{{cite journal | author=Heawood, P. J. | authorlink=:en:Percy John Heawood | title=Map colouring theorems | journal = Quarterly J. Math. Oxford Ser. | year=1890 | volume=24 | pages=322–339}}</ref>。ヒーウッドグラフは、境界が tight であるような、七つの互いに近接した領域を備えるトーラスの細分割を形成する。

ヒーウッドグラフはまた{{仮リンク|ファノ平面|en|Fano plane}}の{{仮リンク|レヴィグラフ|en|Levi graph}}でもあり、幾何における点と距離の間の incidences を表すグラフである。この解釈によると、ヒーウッドグラフに含まれる 6-閉路は、ファノ平面における[[三角形]]に対応する。

ヒーウッドグラフの{{仮リンク|交差数 (グラフ理論)|label=交叉数|en|Crossing number (graph theory)}}は 3 であり、そのような交叉数を持つ立方体グラフの中では最小である。ヒーウッドグラフを含む、交叉数 3 で位数 14 のグラフは 8 つある。

ヒーウッドグラフは[[単位距離グラフ]]である: 隣接する頂点はちょうど距離が 1 だけ離れており、同じ点に埋め込まれている頂点はなく、また、辺に含まれるある点に埋め込まれる頂点もないような平面に、そのグラフは埋め込まれる。しかしながら、そのグラフに備わっている対称性は、このタイプの知られている埋め込みにおいては欠落している<ref>{{Cite journal | last = Gerbracht | first = Eberhard H.-A. | title = Eleven unit distance embeddings of the Heawood graph | year = 2009 | arxiv = 0912.5395}}</ref>。

== 代数的性質 ==
ヒーウッドグラフの[[自己同型|自己同型群]]は、位数 336 の[[射影線型群]] PGL<sub>2</sub>(7) と同型である<ref>{{cite book|last1=Bondy|first1=J. A.|author1-link=:en:John Adrian Bondy|last2=Murty|first2=U. S. R.|author2-link=:en:U. S. R. Murty|title=Graph Theory with Applications|location=New York|publisher=North Holland|year=1976|page=237|isbn=0-444-19451-7|url=http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html|archiveurl=https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html|archivedate=2010年4月13日|deadurldate=2017年9月}}</ref>。それは、グラフの頂点、辺および弧の上で推移的に作用する。したがって、ヒーウッドグラフは[[対称グラフ]]である。任意の頂点や辺を、任意の別の頂点や辺へと写す自己同型が存在する。[[対称グラフ|フォスター調査]]によれば、F014A と番号付けられるヒーウッドグラフは、頂点が14個であるような唯一つの立方体対称グラフである<ref>Royle, G. [http://www.cs.uwa.edu.au/~gordon/remote/foster/#census "Cubic Symmetric Graphs (The Foster Census)."]</ref><ref>Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.</ref>。

ヒーウッドグラフの[[固有多項式]]は <math>(x-3) (x+3) (x^2-2)^6</math> である。ヒーウッドグラフはこの固有多項式を持つ唯一つのグラフであり、これによってヒーウッドグラフはそのスペクトルによって決定付けられるグラフとなっている。

== ギャラリー ==
<gallery>
Image:Szilassi polyhedron.svg|{{仮リンク|シラッシの環状多面体|en|Szilassi polyhedron}}
File:3-crossing Heawood graph.svg|ヒーウッドグラフの{{仮リンク|交差数 (グラフ理論)|label=交叉数|en|Crossing number (graph theory)}}は 3 である。
File:Heawood graph 3color edge.svg|ヒーウッドグラフの[[グラフ彩色|彩色指数]]は 3 である。
File:Heawood graph 2COL.svg|ヒーウッドグラフの[[グラフ彩色|彩色数]]は 2 である。
File:7x-torus.svg|ヒーウッドグラフのトーラス（図では[[周期境界条件]]の下で正方形として描かれている）への埋め込みは、それを七つの互いに隣接した領域に区分する。
</gallery>

== 参考文献 ==
{{reflist}}

{{DEFAULTSORT:ひいうつとくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]