《图论课件平面图的判定与涉及平面性的不变量》由会员分享，可在线阅读，更多相关《图论课件平面图的判定与涉及平面性的不变量（32页珍藏版）》请在金锄头文库上搜索。
1、 图论及其应用应用数学学院1本次课主要内容(一)、平面图的判定(二)、涉及平面性的不变量平面图的判定与涉及平面性的不变量2这次课要解决的问题是：给出判定一个图是否是可 平面图的充分必要条件。(一)、平面图的判定在本章第一次课中，我们已经明确：对于3阶以上的 具有m条边的图G来说，如果G满足如下条件之一： (1)m3n-6; (2) K5是G的一个子图；(3) K3,3是G的一个子 图，那么，G是非可平面图。但上面的条件仅为G是非可平面图的充分条件。最早给出图的平面性判定充要条件的是波兰数学家 库拉托斯基(30年代给出)。后来，美国数学家惠特尼， 加拿大数学家托特，我国数学家吴文俊等都给出了不同
2、 的充要条件。3所以，我们称K5与K3,3为库拉托斯基图。我们主要介绍波兰数学家库拉托斯基的结果。库拉托斯基定理主要基于K5和K3,3是非可平面图这一 事实而提出的平面性判定方法。一个自然的猜测是：G是可平面图的充分必要条件是 G不含子图K5和K3,3。上面命题必要性显然成立！但充分性能成立吗？十分遗憾！下面例子给出了回答：NO!下面的图G是一个点数为5，边数为9的极大平面图。 考虑 F=GK34注：F由G的3个拷贝组成，分别是G1,G2,G3。三个拷 贝中的边没有画出。图中虚线不是对应的Gi中边。Gu5u4u3u2u1v5v4v3v2v1w5w4w3w2w1G3G2G15可以证明：F中不含K
3、5和K3,3，且F是非可平面图。尽管我们的直觉猜测错了，但库拉托斯基还是基于 K5与K3,3得到了图的平面性判据。1、相关概念定义1 在图G的边上插入一个2度顶点，使一条边分 成两条边，称将图在2度顶点内扩充；去掉一个图的2度 顶点，使关联它们的两条边合并成一条边，称将图G在 2度顶点内收缩。在2度顶点内收缩在2度顶点内扩充6定义2 两个图G1与G2说是同胚的，如果 ，或 者通过反复在2度顶点内扩充和收缩后能够变成一对同 构的图。G3G2G1上面的G1, G2, G3 是同胚的。注：图的平面性在同胚意义下不变。7定理1 (库拉托斯基定理) 图G是可平面的，当且仅当 它不含K5或K3,3同胚的子
4、图。例1 求证：下面两图均是非平面图。图 G1图 G2证明：对于G1来说，按G1在2度顶点内收缩后，可得 到K5。所以，由库拉托斯基定理知G1是非可平面图。8对于G2来说，先取如下子图G2的一个子图对上面子图，按2度顶点收缩得与之同胚子图K3,3:K3,3所以，G2是非可平面图。9例2 确定下图是否是可平面图。u1u2v1v2y1y2x1x2 w1w2分析：我们根据图的结构形式，怀疑该图是非可平 面图。但我们必须找到证据！当然我们可能考虑是否m3n-6。遗憾的是该图不满 足这个不等式！10u1u2v1v2y1y2x1x2 w1w2所以，我们要在该图中寻找一个与k5或K3,3同胚的子 图！由于该
5、图的最大度为4的顶点才4个，所以，不存在与K5 同胚的子图。因此，只有寻找与K3,3同胚的子图！解：取G中红色边的一个导出子图：也就是得到G的如下形式的一个子图：11上图显然和K3,3同胚。由库拉托斯基定理知，G是非可 平面的。u1u2v1v2y1y2x1x2w1w2注： (1) 库拉托斯基定理可以等价叙述为：库拉托斯基定理：图G是非可平面的，当且仅当它含有 K5或K3,3同胚的子图。12(2) 库拉托斯基 (1896-1980) 波兰数学家。1913年开始 在苏格兰格拉斯哥大学学习工程学，1915年回到波兰发沙 大学转学数学，主攻拓扑学。1921年获博士学位。1930年 在利沃夫大学作数学教
6、授期间，发现并证明了图论中的库 拉托斯基定理。1939年后到发沙大学做数学教授。他的一 生主要研究拓扑学与集合论。库拉托斯基定理：图G是非可平面的，当且仅当它含 有K5或K3,3同胚的子图。定义2 给定图G, 去掉G中的环，用单边代替平行边而 得到的图称为G的基础简单图。13定理2 (1) 图G是可平面的，当且仅当它的基础简单图 是可平面的；(2) 图G是可平面图当且仅当G的每个块是可平面图。证明： (1) 由平面图的定义，该命题显然成立。(2) 必要性显然。下面证明充分性。不失一般性，假设G连通。我们对G的块数n作数学归 纳证明。当n=1时，由条件，结论显然成立；设当nk 时，若G的每个块是
7、可平面的，有G是可平 面的。下面考虑n=k时的情形。14设点v是G的割点，则按照v，G可以分成两个边不重 子图G1与G2, 即G=G1G2,且G1G2=v。vG2G1按归纳假设，G1与G2都是可平面图。取G1与G2的平 面嵌入满足点v都在外部面边界上，则把它们在点v处对 接后，将得到G的平面嵌入。即证G是可平面图。关于图的可平面性刻画，数学家瓦格纳(Wangner)在 1937年得到了一个定理。15定义3 设uv是简单图G的一条边。去掉该边，重合其 端点，在删去由此产生的环和平行边。这一过程称为图G 的初等收缩或图的边收缩运算。称G可收缩到H,是指对G通过一系列边收缩后可得到 图H。定理2 (
8、瓦格纳定理)：简单图G是可平面图当且仅当它 不含有可收缩到K5或K3,3的子图。注：这是瓦格纳1937年在科隆大学博士毕业当年提出 并证明过的一个定理。16例3 求证彼得森图是非可平面图。证明：很明显，彼得森图通过一些列边收缩运算后得 到K5。由瓦格纳定理得证。定理3 至少有9个顶点的简单可平面图的补图是不可平 面的，而9是这个数目中的最小的一个。17注：该定理是由数学家巴特尔、哈拉里和科达马首先 得到。然后由托特(1963)给出了一个不太笨拙的证明，他 采用枚举法进行验证。还不知道有简洁证明，也没有得 到推理方法证明。例4 找出一个8个顶点的可平面图，使其补图也是可平 面的。765 4321
9、8G765 43218G的补补18例5 设G是一个简单图，若顶点数n11,则则G与G的补补 图图中，至少有一个是不可平面图图 (要求用推理方法).证明：设G是一个n阶可平面图，则：所以：考虑：19令:则：所以， 当n6.5时时，f(n)单调单调 上升。而当n=11时时：所以， 当n11时时，有：即证明了简单可平面图G的补图是非可平面图。20例6 设Gi是一个有ni个点，mi条边的图，i=1,2。证明： 若G1与G2同胚，则：证明：设G1经过p1次2度顶点扩充，p2次2度顶点收缩 得到H1, G2经过q1次2度顶点扩充，q2次2度顶点收缩得到 H2, 使得：又设H1与H2的顶点数分别为n1*和n
10、2*,边数分别为m1*与 m2*。那么：21所以：而由 得：所以：(二)、涉及平面性的不变量我们将要讨论的问题是：如何刻画一个非可平面图与平 面图之间的差距。只作简单介绍。1、图的亏格22环柄：边交叉处建立的“立交桥”。通过它，让一条边 经过 “桥下”，而另一条边经过“桥上”，从而把两条边在 交叉处分开。环柄示意图定义4 若通过加上k个环柄可将图G嵌入到球面，则k的 最小数目，称为G的亏格，记为：(G)。23定理4 对于一个亏格为，有n个顶点，m条边和个面 的多面体，有：因多面体对应一个连通图，所以上面恒等式称为一般 连通图的欧拉公式。推论：设G是一个有n个点m条边，亏格为的连通图， 则：24
11、证明 (3): 因为G的每个面是三角形，所以每条边是两 个面的公共边，得：3=2m。于是由定理4得：对于完全图的亏格曾经是一个长期的，有趣的，困难 的和成功的努力。1890年希伍德提出如下猜想：25希伍德由推论(1)证明了：同时希伍德也证明了(K7)=1.1891年，赫夫曼对n= 8-12 进行了证明；1952年，林格尔对n= 13 进行了证明；记阶数n=12s+r1954年，林格尔对r= 5 进行了证明；1961-65年，林格尔对r= 7、10、3 进行了证明；261961-65年，杨斯、台里等对r= 4、0、1、9、6 进行 了证明；1967-68年，林格尔、杨斯对r= 2、8、11进行了
12、证明 ；1968年后，法国蒙特派列尔大学文学教授杰恩对n=18 、20、23进行了证明.对于完全双图，结果由林格尔独立得到。定理5 设m, n是正整数，则：272、图的厚度定义5 若图G的k个可平面子图的并等于G，则称k的最 小值为G的厚度，记为 定理6 (1)若 ,则： (2)(3) 对任意的单图G=(n, m),有：3、图的糙度28定义6 图G中边不相交的不可平面子图的最多数目称为 G的糙度，记为： 定理7 完全图的糙度由下式给出：（3n+119并且3n+19r+7，其中r为面数）； 29定义8 将G画在平面上时相交的边对的最少数目称为G的 叉数，记为 定理9 30作业P143-146 习题5 ：6，7，8，11、12。31Thank You !32
