补充资料：可平面图

可平面图
graph, planar

可平面图【脚户，户幽r;r，中n几oeK一‘」 可以正则地嵌人平面的图(见图的嵌入(g丑ph而加“ing)).换句话说，图G称为可平面的(p腼)，如果它可以表示在一个平面上，使得图的顶点对应于平面上不同的点，而且平面上对应于图的边的线不通过对应于顶点的点(端点除外)并互不相交.一些问题，如地图的着色、通讯设计、以及电子学中的一些牵涉到借助于平面印刷子电路来实现电路等问题，都可以化归到可平面图的研究.任何连通可平面图的正则嵌人(有不相交边)都牵涉到把平面剖分成若干区域(面).这样的平面剖分称为平率毕甲(phnartnaP).Euler公式(E枉ler forl妞日a) n一m+r=2，其中n是顶点数，m是边数，且r是地图的面数(包括在外部的一面)，可应用于任何平面地图.因此，图凡(。=5的完全图)与凡，，(每部都有3个顶点的完全二部图，亦见二部图(g卫ph，bipartite))都不是可平面的(图1).含酬冈 ks‘汀3，3 图l在某种意义下，这两种图是最小的不可平面图，根据no盯p用书卫一K切rato钻ki定理(Pon奶哪如一K切旧to枯kit坛泊~):一个图是可平面的，当且仅当它不包含一个同胚于凡或K3.，的子图(见图的同胚(g盈phho-~mo甲比m)). 还有别的可平面性(即一个图是否可平面)的判别准则.特别地，一个图是可平面的，当且仅当它的每个非平凡双连通分支有一个圈基21，…，Z，，与一个附加圈Z。，使得G的任一边恰好属于这m十1个圈中的2个圈的一部分(一个圈基(cyde hasis)是一给定图的所有圈的集合的一个子集，它在图的所有圈的集合中关于模2的加法运算是独立的和完全的，见图(g旧ph)). 任一可平面图可以在一平面上表示，使它的所有边都是直线段.任一3连通图(见图的连通度(graph，conn呱i访ty ofa))可以唯一地嵌人一个球面(在球面同胚的意义下).一个可平面图在平面上的每一个嵌人，因而每一个平面地图，可以与它的几何对偶图(dualg艺ph)构成一一对应关系，这种关系可以建立如下:在地图的每个面内取一点作为对偶图的顶点，如果两面有一公共边e，则将这两面所包含的两点用边e’相连，且e’仅与e相交一次(图2中嵌入的图用实线表示，而它的对偶图用虚线表示). <::，’’’’’’厂 、2 \、一__子，， 图2每个面都由三边围成的平面地图称为平面三角剖分(ph比虹曲 ng山tion).有n个顶点的平面三角剖分的边数是3n一6. 在图论中广泛研究的一个课题是可平面图的着色(见图的，色(g区ph colounng));对于不可平面图，研究了以反映它的不可平面性的程度的各种数值特征，这些数值特征包括亏格、图的厚度和糙度、交叉数等(见图的嵌入(脚phjn七司ding))，【补注】关于可平面图和著名四色猜想(four一田】。ur印叨民t切巴)的一个综述报导由0 .Ore给出【Al].所谓四色猜想是每一个可平面图可用四种颜色顶点着色.最近这个猜想已为K .APpel和w.Haken证明，见四色问题(four一colour pmbl曰n).他们的工作的一个好的摘要见【AZI.

说明：补充资料仅用于学习参考，请勿用于其它任何用途。