主题
Search

地图着色


给定一个亏格 g>0 的地图,希伍德在 1890 年证明,在无界曲面上为地图着色所需的最大颜色数(色数)是

N_u=|_1/2(7+sqrt(48g+1))_|
(1)
=|_1/2(7+sqrt(49-24chi))_|,
(2)

其中 |_x_|向下取整函数g亏格,而 chi欧拉示性数。这就是希伍德猜想。在 1968 年,对于除球面(或等价的平面)以外的任何无界可定向曲面,以及除克莱因瓶以外的任何不可定向曲面,N_u 被证明不仅是最大值,而且是实际需要的颜色数(Ringel 和 Youngs,1968 年)。

四色定理被证明后,希伍德公式也被证明适用于所有可定向和不可定向无界曲面,但克莱因瓶除外。对于克莱因瓶,实际需要的颜色数 N 是六种—— N_u=7少一种(Franklin 1934;Saaty 1986,第 45 页)。莫比乌斯带是一种有界曲面,也需要 6 种颜色,而盲目应用希伍德公式(在这种情况下不适用)则给出 7 种颜色。


另请参阅

色数, 四色定理, 希伍德猜想, 六色定理, 环面着色

使用 Wolfram|Alpha 探索

参考文献

Ball, W. W. R. 和 Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 237-238, 1987.Barnette, D. Map Coloring, Polyhedra, and the Four-Color Problem. Washington, DC: Math. Assoc. Amer., 1983.Franklin, P. "A Six Colour Problem." J. Math. Phys. 13, 363-369, 1934.Franklin, P. The Four-Color Problem. New York: Scripta Mathematica, Yeshiva College, 1941.Ore, Ø. The Four-Color Problem. New York: Academic Press, 1967.Ringel, G. 和 Youngs, J. W. T. "Solution of the Heawood Map-Coloring Problem." Proc. Nat. Acad. Sci. USA 60, 438-445, 1968.Saaty, T. L. 和 Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, 1986.

在 Wolfram|Alpha 上被引用

地图着色

引用为

Weisstein, Eric W. "地图着色。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/MapColoring.html

主题分类