查看“︁轮图”︁的源代码

{{infobox graph
 | name = 轮图
 | image = [[Image:Wheel graphs.svg|220px]]
 | image_caption = 轮图的一些例子
 | girth    = 3
 | diameter = 2，如果''n'' > 4<br>1，如果''n'' = 4
 | vertices = ''n''
 | edges = 2(''n'' − 1)
 | chromatic_number = 4，如果''n''是偶数<br/>3，如果''n''是奇数
 | chromatic_index =
 | spectrum = <math>\{2\cos(2k\pi / (n - 1))^1; </math><br><math>k = 1, \ldots, n - 2\}</math><math>\cup\{1 \pm \sqrt{n}\}</math>
 | properties = [[哈密顿路径问题|哈密顿图]]<br>[[平面图_(图论)#對偶圖|自对偶]]<br>[[平面圖 (圖論)|平面图]]
 | notation = ''W''<sub>''n''</sub>
}}

在[[图论]]这一[[数学]]分支中，'''轮图'''（{{lang|en|wheel graph}}）是指一个[[完全点]]连接到一个[[循环图]]上所有节点而形成的图。一些文献中<ref>{{cite mathworld| urlname = WheelGraph | title = Wheel Graph}}</ref>会使用记号''W''<sub>''n''</sub>来表示有''n''个节点（n ≥ 4）的轮图；另一些文献中<ref>{{cite book |last=Rosen |first=Kenneth H. |year=2011 |title=Discrete Mathematics and Its Applications |url=https://archive.org/details/discretemathemat00rose_408  |edition=7th |publisher=McGraw-Hill |page=[https://archive.org/details/discretemathemat00rose_408/page/n675 655] |isbn=978-0073383095}}</ref>则使用''W''<sub>''n''</sub>来表示有''n''+1个节点（n ≥ 3）的轮图，这里''n''是指形成轮图的循环图中节点的数量。在本条目中使用前一种记号。

==构造==
给定一个[[节点 (图论)|点集]]{1, 2, 3, …, v}，则若使用[[集合建构式符号]]，轮图的[[边 (图论)|边集]]可以表示为{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}。<ref>{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=56|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|accessdate=8 August 2012|archive-date=2019-05-05|archive-url=https://web.archive.org/web/20190505192352/http://store.doverpublications.com/0486678709.html|dead-url=no}}</ref>

==性质==
轮图是[[平面圖 (圖論)|平面图]]，因此有唯一的平面嵌入。更进一步，每个轮图都是{{tsl|en|Halin graph|哈林图}}。轮图是自对偶的：轮图的[[对偶图|平面对偶]]和其自身[[图同构|同构]]。除了''K''<sub>4</sub> = ''W''<sub>4</sub>之外，每个[[平面圖 (圖論)#极大平面图|极大平面图]]都有一个形如''W''<sub>5</sub>或''W''<sub>6</sub>的子图。

任意轮图中总有[[哈密顿路径问题|哈密顿环]]。''W''<sub>''n''</sub>中有<math>n^2-3n+3</math>个[[环 (图论)|环]]{{OEIS|id=A002061}}。

[[Image:CyclesW4.svg|320px|thumb|left|轮图''W''<sub>4</sub>中的7个环]]
当''n''为奇数时，''W''<sub>''n''</sub>是一个{{tsl|en|perfect graph|完美图}}，其[[图着色问题|色数]]为3：环上的节点可以用两种颜色染色，而中间的完全点使用第三种颜色。当''n''为偶数时，''W''<sub>''n''</sub>的[[色数]]为4，且当''n'' ≥ 6时不是完美图。''W''<sub>7</sub>是轮图中在欧几里得平面上的唯一一个{{tsl|en|unit distance graph|单位距离图}}<ref>
{{citation
  | last1 = Buckley | first1 = Fred | last2 = Harary | first2 = Frank 
  | title = On the euclidean dimension of a wheel
  | journal = Graphs and Combinatorics
  | volume = 4
  | issue = 1
  | year = 1988
  | doi = 10.1007/BF01864150
  | pages = 23–30
}}.</ref>。

轮图''W<sub>n</sub>''的[[色多项式]]为<math>P_{W_n}(x) = x((x - 2)^{(n - 1)} - (-1)^n(x - 2))</math>。

在[[拟阵]]论中，两类重要的拟阵'''轮拟阵'''（{{lang-en|wheel matroids}}）和'''旋拟阵'''（{{lang-en|whirl matroids}}）的概念都是轮图的推广。

轮图''W''<sub>6</sub>是[[埃尔德什·帕尔]]对[[拉姆齐理论]]一个猜想的反例：他猜想在色数相同的图中，完全图的拉姆齐数是最小的。但后来有研究发现''W''<sub>6</sub>的拉姆齐数是17，而与之色数相同的完全图''K''<sub>4</sub>的拉姆齐数则是18<ref>{{citation
  | last1 = Faudree
  | first1 = Ralph J.
  | last2 = McKay
  | first2 = Brendan D.
  | title = A conjecture of Erdős and the Ramsey number ''r''(''W''<sub>6</sub>)
  | url = http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz
  | journal = J. Combinatorial Math. and Combinatorial Comput.
  | volume = 13
  | year = 1993
  | pages = 23–31
  | accessdate = 2021-08-21
  | archive-date = 2012-02-05
  | archive-url = https://web.archive.org/web/20120205023737/http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz
  | dead-url = no
  }}.</ref>。也就是说，对于任意17节点的图''G''，''G''或它的补图一定有子图''W''<sub>6</sub>；而17节点的{{tsl|en|Paley graph|Paley图}}和它的补图都没有子图''K''<sub>4</sub>。

==参考资料==
{{Reflist}}

{{图论}}
[[Category:平面图]]
[[Category:图论]]