graph12.txt

Euler公式来源及其应用

平面图小结： 

一、平面图的研究起源于四色猜想。 

1852 年, 英国青年学生 Francis Guthrie 在给英国地图染色时发现 
4 种颜色就足够了。地图可以看成平图, 行政区域就是这个平图的面。 
给地图上的每个行政区域染色, 就是给这个平图的每个面染色。于 
是，形成四色猜想 
(Highlight)
：任何平图的面是 4 色可染的。 

平面图是拓扑图论的重要研究内容。L. Euler 于 1753 年发现了 
Euler 公式而成为拓扑图论的奠基人。接着中断了 170 多年。1930 年, 
当波兰数学家 C. Kuratowski 和美国数学家 O. Frink & P. A. Smith 发现 
了平面图判定准则(定理 3.2)后，这方面的研究才开始复苏。 

上世纪 50 年代, 我国著名数学 
(Highlight)
家吴文俊(1955) 基于代数拓扑学 
中的上同调理论发现了图的平面性判定准则。W. Tutte(1970)基于实域 
上链群的理论也发现一个判定准则。我国 
(Highlight)
刘彦佩(1988)证明这两个判 
定准则从二元域 GF(2)上的空间理论来看是同一的。 

二、掌握平面图与平图的概念和基本结果。 

Euler公式，面数是平面图不变量，最大边数为 6 - 3ν ，最小度不 
超过5。平面图的判断（Kuratowski定理）。 

三、平面图判断算法。 

平面图用于大规模集成电路板的设计激发了对平面图的研究。值得 
指出的是, 
(Highlight)
吴文俊(1973，1974)利用代数拓扑的方法把平面性判定问 
题转化成模 2 代数方程组的求解问题, 得到判定平面性的 算 
法。 
(Highlight)
刘彦佩(1978, 1979, 1988)把判定图的平面性问题转化为在辅助图 
上求支撑树问题，改进了吴文俊的结果, 也得到一个线性算法。由吴 
文俊和刘彦佩所创立的方法, 被欧洲组合学杂志三主编之一的 P. 
Rorenstiehl(1980)称为 
(Highlight)
“吴--刘判别准则”和“吴--刘定理”。 
Ｏ（ｖ） ６ 

非平面图和图的曲面嵌入是拓扑图论研究的重要内容之一. 本 
章没有涉及它, 有兴趣的读者可参阅刘彦佩的专著《图的可嵌入性理 
论》(1995)和《Topological Theory on Graphs》（2008）。