《图论》第5章平面图ppt课件.ppt

1 可平面性可平面性 一个图一个图 G=(V,E) ，若能将其画在平面上，若能将其画在平面上，且任意两条边的交点只能是且任意两条边的交点只能是G的顶点，则称的顶点，则称G可嵌可嵌入平面，或称入平面，或称G是可平面的。可平面图在平面上是可平面的。可平面图在平面上的一个嵌入称为一个平面图。的一个嵌入称为一个平面图。树是一类重要的平面图。树是一类重要的平面图。应用举例：印刷电路版、集成电路设计。应用举例：印刷电路版、集成电路设计。5.1 5.1 平面图及其性质平面图及其性质2 区域区域 由平面图的边包围而成，其中不含图的顶点。由平面图的边包围而成，其中不含图的顶点。也称为面。包围域也称为面。包围域R的所有边组成的回路称为该的所有边组成的回路称为该域的边界，回路长度称为该域的度，记为域的边界，回路长度称为该域的度，记为deg(R)。5.1 5.1 平面图及其性质平面图及其性质v2R1R2R0v1v3v4v5v6v7各域的边界：各域的边界：R0: v1 v2 v4 v5 v7 v7 v4 v3 v1R1: v1 v2 v4 v3 v1R2: v4 v5 v7 v4 v6 v4R3: v7 v7 例例deg(R0)=8, deg(R1)=4, deg(R2)=5, deg(R3)=1R33 内部面和外部面内部面和外部面 由平面图的边包围且无穷大的域称由平面图的边包围且无穷大的域称为外部面。（如上例的域为外部面。（如上例的域R0为外部面）为外部面）一个平面图有且只有一个外部面。一个平面图有且只有一个外部面。 曲面嵌入曲面嵌入 一个图可嵌入平面当且仅当它可嵌入曲面一个图可嵌入平面当且仅当它可嵌入曲面.5.1 5.1 平面图及其性质平面图及其性质1deg()2riiRm 定理定理5-1-15-1-1 平面图平面图G的所有域的度之和等于其边数的所有域的度之和等于其边数m的的2倍，即：倍，即：4 定理定理5-1-2 5-1-2 欧拉公式欧拉公式 设平面连通图设平面连通图G有有n个顶点，个顶点，m条边，条边，d个域，则有个域，则有 n- -m+d = 2。证明证明1 对对m作归纳。作归纳。证明证明2 对对d作归纳。作归纳。欧拉公式对非简单图仍然成立。欧拉公式对非简单图仍然成立。 推论推论 设平面图设平面图G的连通分支数为的连通分支数为k，并有，并有n个顶点，个顶点，m条边，条边，d个域，则有个域，则有 n- -m+d = k+1。5.1 5.1 平面图及其性质平面图及其性质5 极大平面图极大平面图 设设G=(V,E)为简单平面图，为简单平面图，|V| 3，若对，若对任意任意vi ,vj V，且，且 (vi ,vj) E，有，有G =(V, E (vi ,vj)为非平面图，则称为非平面图，则称G为一个极大平面图。为一个极大平面图。“极大性极大性”乃针对固定顶点数的图的边的数目而乃针对固定顶点数的图的边的数目而言。言。5.1 5.1 平面图及其性质平面图及其性质6 极大平面图的性质极大平面图的性质 1.极大平面图是连通图。极大平面图是连通图。2.极大平面图的每个面都由极大平面图的每个面都由3条边组成。条边组成。3.极大平面图有极大平面图有3d=2m（d为面数目，为面数目，m 为边数目）。为边数目）。4.极大平面图极大平面图G=(V, E)，若，若|V| 4，则，则 vi V，有，有 deg(vi ) 3。证明证明5.1 5.1 平面图及其性质平面图及其性质7 定理定理5-1-35-1-3 设极大平面图设极大平面图G有有n个顶点，个顶点，m条边，条边，d个域，则有个域，则有m=3n- -6，d=2n- -4。证明证明 将将3d=2m代入欧拉公式。代入欧拉公式。 推论推论 简单平面图简单平面图G有有 m 3n- -6，d 2n- -4。 定理定理5-1-45-1-4 简单平面图至少有一个顶点的度小于简单平面图至少有一个顶点的度小于6。 证明证明 设任一点的度设任一点的度 6，得，得 m 3n，矛盾。，矛盾。5.1 5.1 平面图及其性质平面图及其性质8 二部图二部图 图图G=(V, E)，若，若V可划分成可划分成V1和和V2 两部分，两部分，使得：使得： v1 V1，若，若( v1, v2 ) E ，则必，则必v2 V2 ; v2 V2，若，若( v1, v2 ) E ，则必，则必v1 V1 。 则称则称G为一个二部图。为一个二部图。5.1 5.1 平面图及其性质平面图及其性质例例9 完全二部图完全二部图 设设G=(V, E)为一个二部图，为一个二部图， V1和和V2 如如上所述，若上所述，若 ( v1 ) ( v2 )(v1 V1 , v2 V2 ( v1, v2 ) E)， 则称则称G为一个完全二部图，记为为一个完全二部图，记为 Kn1, n2。 ( n1 =|V1| ，n2 =| V2 |)5.1 5.1 平面图及其性质平面图及其性质例例 K3,310 定理定理5-1-55-1-5 K5 和和K3,3 是不可平面的。是不可平面的。 证明证明 反证法并由欧拉公式导出矛盾反证法并由欧拉公式导出矛盾.K5 和和K3,3 称为基本的不可平面图，或称为基本的不可平面图，或 Kuratowski 图。图。K5K3,35.1 5.1 平面图及其性质平面图及其性质11 串联边串联边 图图 G=(V,E) ，若，若e1=(u1 , u2)， e2=(u2 , u3)，且且deg(u2)=2，则称，则称e1与与e2串联。串联。e1e2u1u2u35.2 5.2 Kuratowski 定理定理例例12 串联边置换串联边置换 将上述将上述e1, e2 置换成置换成 e3=(u1 , u3) ，并消去，并消去可能的多重边的过程，称为串联边置换。可能的多重边的过程，称为串联边置换。e1e2u1u2u3e3u1u3u1u3e3e1e2u1u2u3e3u1u3e35.2 5.2 Kuratowski 定理定理13 同胚同胚 设无向图设无向图 G和和G ，若存在，若存在G ，使得，使得G和和G 分别分别经若干串联边置换后与经若干串联边置换后与G 同构，则称同构，则称G和和G 同胚同胚.与与K5同胚的图，称为同胚的图，称为K(1)型图；与型图；与K3,3同胚的图，同胚的图，称为称为K(2)型图；型图；K(1)型图和型图和K(2)型图统称型图统称K型图。型图。 定理定理5-2-15-2-1(Kuratowski) 图图 G=(V,E) 可平面当且仅当可平面当且仅当G中不存在任何中不存在任何K型子图。型子图。( 证略证略)Kuratowski 定理的实际应用较为困难。定理的实际应用较为困难。5.2 5.2 Kuratowski 定理定理14例例 Petersen 图不是平面图。图不是平面图。5.2 5.2 Kuratowski 定理定理AAABBBK3,315 平面性等价图平面性等价图 图图G=(V,E)，满足下列条件之一的图，满足下列条件之一的图G*= (V*,E*) 称为图称为图G的平面性等价图：的平面性等价图：1. G是不连通图，在是不连通图，在G的两个连通分支之间增加的两个连通分支之间增加一条边得到一条边得到G*;2. 对对G中存在中存在割点割点v，将，将G从从v处分割得到由若干处分割得到由若干连通分支构成的连通分支构成的G*；3. 对对G作串联边置换得到作串联边置换得到G*;4. 从从G中移去自环得到中移去自环得到G*；5. 从从G中移去多重边得到中移去多重边得到G*。5.3 5.3 图的平面性检测图的平面性检测16 平面性的不完全判定平面性的不完全判定 图图G*=(V*,E*)，n=|V|，m=|E|，则当，则当n=5且且m3n-6，G是不可平面的；是不可平面的； 平面性检测的平面性检测的DMPDMP算法算法 戴书戴书P755.3 5.3 图的平面性检测图的平面性检测17 对偶图对偶图 图图G=(V,E)，满足下列条件的图，满足下列条件的图G*= (V*,E*) 称为图称为图G的对偶图：的对偶图：1. G的任一的任一域域 fi 内有且仅有一点内有且仅有一点vi*;2. 对对G的域的域 fi , fj 的共同边界的共同边界ek，画一条，画一条ek*=(vi* , vj* ) 且只与且只与ek交于一点；交于一点；3. 若若ek完全处于完全处于fi中，则中，则vi*有一自环有一自环ek* 且与且与ek相相交与一点。交与一点。上述过程称为求对偶图的上述过程称为求对偶图的D过程，得到的对偶图过程，得到的对偶图称为原图的拓扑对偶。称为原图的拓扑对偶。5.4 5.4 对偶图对偶图18对平面图对平面图G，D过程构造的过程构造的G*是唯一的；对于非是唯一的；对于非平面图，平面图， D过程可能不成立；过程可能不成立；对平面图对平面图G， D过程构造的过程构造的G*也是平面图；也是平面图；不论图不论图G是否连通，是否连通，D过程得到的过程得到的G*是连通的；是连通的；若图若图G连通，且存在连通，且存在G*，则，则 (G*)*=G；对图对图G，若存在，若存在G*，则，则 G中回路相对应于中回路相对应于G*中割中割集，集，G中割集相对应于中割集相对应于G*中回路；中回路；若若G G*，称，称G为一个自对偶图。为一个自对偶图。5.4 5.4 对偶图对偶图19 定理定理5-4-15-4-1(Whitney) 图图G有对偶图当且仅当有对偶图当且仅当G是平面是平面图。图。证明证明 在平面图上施行在平面图上施行D过程即得。过程即得。 反证：设反证：设G有对偶有对偶G*且且G不是平图。不是平图。 由由 Kuratowski 定理，此时定理，此时G中含有中含有K型型子图。只需子图。只需证明证明K(1)型图和型图和K(2)型图，或型图，或K5 和和K3,3都没有对偶都没有对偶即引起矛盾。即引起矛盾。5.4 5.4 对偶图对偶图20 定理定理5-4-25-4-2 对图对图G施行施行D过程得到过程得到G*，设，设 n, m, d 和和 n*,m*,d* 分别表示分别表示G和和G*的结点数、边数及域数，的结点数、边数及域数，则有：则有： m*=m , n*=d , deg(vi*)=deg(fi)证明证明由由D过程直接得到。过程直接得到。5.4 5.4 对偶图对偶图21 定理定理5-4-35-4-3 设设G为平面图，施行为平面图，施行D过程得到过程得到G*，设，设 n, m, d 和和 n*,m*,d* 如上所述，如上所述，k为为G的连通分支数，的连通分支数，则有：则有：d* = n k+1证明证明 G*是平面连通图是平面连通图 : n* m*+ d* = 2 G 是平面图是平面图 : n m+ d = k+1 由由 定理定理5-3-2:5-3-2: m*=m , n*=d 综上可得：综上可得：d* = n k+15.4 5.4 对偶图对偶图