维基百科,自由的百科全书
在图论这一数学分支中,轮图(wheel graph)是指一个完全点连接到一个循环图上所有节点而形成的图。一些文献中[1]会使用记号Wn来表示有n个节点(n ≥ 4)的轮图;另一些文献中[2]则使用Wn来表示有n+1个节点(n ≥ 3)的轮图,这里n是指形成轮图的循环图中节点的数量。在本条目中使用前一种记号。
给定一个点集{1, 2, 3, …, v},则若使用集合建构式符号,轮图的边集可以表示为{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}。[3]
轮图是平面图,因此有唯一的平面嵌入。更进一步,每个轮图都是哈林图。轮图是自对偶的:轮图的平面对偶和其自身同构。除了K4 = W4之外,每个极大平面图都有一个形如W5或W6的子图。
任意轮图中总有哈密顿环。Wn中有
个环(OEIS數列A002061)。
轮图W4中的7个环
当n为奇数时,Wn是一个完美图,其色数为3:环上的节点可以用两种颜色染色,而中间的完全点使用第三种颜色。当n为偶数时,Wn的色数为4,且当n ≥ 6时不是完美图。W7是轮图中在欧几里得平面上的唯一一个单位距离图[4]。
轮图Wn的色多项式为
。
在拟阵论中,两类重要的拟阵轮拟阵(英語:wheel matroids)和旋拟阵(英語:whirl matroids)的概念都是轮图的推广。
轮图W6是埃尔德什·帕尔对拉姆齐理论一个猜想的反例:他猜想在色数相同的图中,完全图的拉姆齐数是最小的。但后来有研究发现W6的拉姆齐数是17,而与之色数相同的完全图K4的拉姆齐数则是18[5]。也就是说,对于任意17节点的图G,G或它的补图一定有子图W6;而17节点的Paley图和它的补图都没有子图K4。
- ^ Weisstein, Eric W. (编). Wheel Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语).
- ^ Rosen, Kenneth H. Discrete Mathematics and Its Applications 7th. McGraw-Hill. 2011: 655. ISBN 978-0073383095.
- ^ Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Pub. 1993: 56 [8 August 2012]. ISBN 978-0-486-67870-2. (原始内容存档于2019-05-05).
- ^
Buckley, Fred; Harary, Frank, On the euclidean dimension of a wheel, Graphs and Combinatorics, 1988, 4 (1): 23–30, doi:10.1007/BF01864150 .
- ^ Faudree, Ralph J.; McKay, Brendan D., A conjecture of Erdős and the Ramsey number r(W6), J. Combinatorial Math. and Combinatorial Comput., 1993, 13: 23–31 [2021-08-21], (原始内容存档于2012-02-05) .
|
---|
| 图 | 種類 | |
---|
| 結構 | |
---|
| 属性 | |
---|
| 二元運算 | |
---|
| 映射、關係 | |
---|
|
---|
| 定理 |
|
---|
|