离散数学平面图课件.pptVIP

17.2 欧拉公式 一、欧拉公式相关定理 1、 欧拉公式 定理17.6 对于任意的连通的平面图G，有 n-m+r=2其中，n、m、r分别为G的顶点数、边数和面数。 证明 对边数m作归纳法。 (1) m＝0时，由于G为连通图，所以G只能是由一个孤立顶点组成的平凡图，即n=1，m=0，r=1，结论显然成立。 (2) m＝1时，由于G为连通图，所以n=2，m=1，r=1，结论显然成立。 (3)设m＝k(k≥1)时成立，当m＝k+1时，对G进行如下讨论。 若G是树，则G是非平凡的，因而G中至少有两片树叶。 设v为树叶，令G=G-v，则G仍然是连通图，且G的边数m=m-1=k，n=n-1，r=r。 由假设可知 n-m+r=2，式中n，m，r分别为G的顶点数，边数和面数。 于是n-m+r=(n+1)-(m+1)+r=n-m+r=2 若G不是树，则G中含圈。 设边e在G中某个圈上，令G=G-e，则G仍连通且m=m-1=k， n=n，r=r-1。 由假设有 n-m+r=2。 于是 n-m+r=n-(m+1)-(r+1)=n-m+r=2 定理17.7 对于具有k(k≥2)个连通分支的平面图G，有 n-m+r = k+1其中n，m，r分别为G的顶点数，边数和面数。 证明 设G的连通分支分别为G1、G2、…、Gk，并设Gi的顶点数、边数、面数分别为ni、mi、ri、i=1，2，…，k。 由欧拉公式可知: ni-mi+ri = 2，i=1，2，…，k (17.1) 易知， 由于每个Gi 有一个外部面，而G只有一个外部面，所以G的面数 于是，对(17.1)的两边同时求和得 经整理得 n-m+r = k+1。 2、 与欧拉公式有关的定理 定理17.8 设G为连通的平面图，且每个面的次数至少为l(l?3)，则 G的边数与顶点数有如下关系： 由定理17.3（面的次数之和等于边数的2倍）及欧拉公式得 证明 解得 推论 K5, K3,3不是平面图。 证明 若K5是平面图，由于K5中无环和平行边，所以每个面的次数均大于或等于l≥3，由定理17.8可知边数10应满足 10≤(3/(3-2))(5-2) = 9 这是个矛盾，所以K5不是平面图。 若K3,3是平面图，由于K3,3中最短圈的长度为l≥4，于是边数9应满足 9≤ (4/(4-2))(6-2) = 8 这又是矛盾的，所以K3,3也不是平面图。 定理17.9 设G是有k(k≥2)个连通分支的平面图，各面的次数至少为l(l≥3)，则边数m与顶点数n应有如下关系： 定理17.10 设G为n(n?3)阶m条边的简单平面图，则m?3n?6。 设G有k(k?1)个连通分支， 若G为树或森林，当n?3时，m=n-k?3n?6为真。 若G不是树也不是森林，则G中必含圈，又因为G是简单图，所以，每个面至少由l（l?3）条边围成，又在l=3达到最大值，由定理17.9可知 证明 定理17.11 设G为n(n?3)阶m条边的极大平面图，则m=3n?6。 证明 由于极大平面图是连通图，由欧拉公式得: r=2+m-n　 (17.4) 又因为G是极大平面图，由定理17.7的必要性可知，G的每个面的次数均为3，所以： 将(17.4)代入(17.5)，整理后得 m = 3n-6。 二、一个意义重大的定理 定理17.12 设G为简单平面图，则G的最小度?(G)?5。 若阶数 n?6，结论显然成立。 若阶数n?7时，用反证法。 假设?(G) ?6，由握手定理可知： 证明 因而m ?3n，这与定理17.10矛盾。 所以，假设不成立，即G的最小度?(G)?5。 本定理在图着色理论中占重要地位。 说明 一、为判断定理做准备 1、 插入2度顶点和消去2度顶点 定义17.5 设e=(u,v)为图G的一条边，在G中删除e，增加新的顶点w，使u、v均与w相邻，称为在G中插入2度顶点w。 设w为G中一个2度顶点，w与u、v相邻，删除w，增加新边(u,v)，称为在G中消去2度顶点w。 17.3 平面图的判断 2、图之间的同胚 若两个图G1与G2同构，或通过反复插入或消去2度顶点后是同构的，则称G1与G2是同胚的。 上面两个图分别与K3,3, K5同胚 。 二、两个判断定理 定理17.13(库拉图斯基定理1) 图G是平面图当且仅当G中既不含与K5同胚子图，也不含与K3,3同胚子图。 定理17.14(库拉图斯基定理2) 图G是平面图当且仅