图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
平面图 平面图的基本概念 欧拉公式 平面图的判断 平面图的对偶图
2 平面图 • 平面图的基本概念 • 欧拉公式 • 平面图的判断 • 平面图的对偶图
平面图的定义 定义1 若图G能以除顶点外无边相交的方式画在曲面上,则称G可嵌入 曲面.若G可嵌入平面,则称G是可平面图或平面图 画出的无边相交的图称为G的平面嵌入;无平面嵌入的图称为非 平面图
3 平面图的定义 定义1. 若图G能以除顶点外无边相交的方式画在曲面上, 则称G可嵌入 曲面. 若G可嵌入平面, 则称G是可平面图或平面图. 画出的无边相交的图称为G的平面嵌入; 无平面嵌入的图称为非 平面图
基本定理 定理1.若图G是平面图,则G的任何子图都是平面图。 定理2.若G是非平面图,则G的任何母图也都是非平面图。 定理3.设G是平面图,则在G中加平行边或环后所得图还是平面图 本定理说明平行边和环不影响图的平面性,因而在研究图是否 为平面图时,可不考虑平行边和环
4 基本定理 定理1. 若图G是平面图, 则G的任何子图都是平面图。 定理2. 若G是非平面图, 则G的任何母图也都是非平面图。 本定理说明平行边和环不影响图的平面性, 因而在研究图是否 为平面图时, 可不考虑平行边和环。 定理3. 设G是平面图, 则在G中加平行边或环后所得图还是平面图
平面嵌入 定义2. 设G是平面图且已是平面嵌入,由G的边将G所在的平面划分成若干个 区域,每个区域都称为G的一个面.其面积无限的面称为无限面或外部面; 面积有限的面称为有限面或内部面.包围每个面的所有边组成的回路组称 为该面的边界;边界的长度称为该面的次数 常记外部面为R,内部面为R1,R2…,R,面R的次数记为deg(R) 5
5 平面嵌入 定义2. 设G是平面图且已是平面嵌入, 由G的边将G所在的平面划分成若干个 区域, 每个区域都称为G的一个面. 其面积无限的面称为无限面或外部面; 面积有限的面称为有限面或内部面. 包围每个面的所有边组成的回路组称 为该面的边界; 边界的长度称为该面的次数。 常记外部面为R0, 内部面为R1, R2, …, Rk, 面R的次数记为deg(R)
平面嵌入 定理4.平面嵌入图G中所有面的次数之和等于边数m的两倍,即 ∑=.deg(R)=2m,其中r为G的面数 证明: 对于任意的e∈E(G),分以下情况考虑 若e为面R和R付≠的公共边界上的边时,在计算R和R的次 数时,e各被计算1次 当e只在某一个面的边界上出现时,则在计算该面的次数时,e 被计算2次; 所以,每条边在计算总次数时,都被计算2次 因此,∑=1.deg(R=2m
6 平面嵌入 定理4. 平面嵌入图G中所有面的次数之和等于边数m的两倍, 即 Σi=1..rdeg(Ri) = 2m, 其中r为G的面数. 证明: 对于任意的e∈E(G), 分以下情况考虑: 若e为面Ri和Rj(i ≠ j)的公共边界上的边时, 在计算Ri和Rj的次 数时, e各被计算1次; 当e只在某一个面的边界上出现时, 则在计算该面的次数时, e 被计算2次; 所以, 每条边在计算总次数时, 都被计算2次。 因此, Σi=1..rdeg(Ri) = 2m
极大平面图 定义3.设G为简单平面图,若在G的任意不相邻的顶点U,V之间加 边(uv),所得图为非平面图,则称G为极大平面图。 定理5.极大平面图是连通的 定理6.设G是n(n≥3)阶极大平面图,则G中不可能存在割点和桥
7 极大平面图 定义3. 设G为简单平面图, 若在G的任意不相邻的顶点u, v之间加 边(u, v), 所得图为非平面图, 则称G为极大平面图。 定理5. 极大平面图是连通的。 定理6. 设G是n(n ≥ 3)阶极大平面图, 则G中不可能存在割点和桥
极大平面图 定理7.设G为n(n≥3阶简单连通的平面图,G为极大平面图,当且仅当G 的每个面的次数均为3 证明:先证明该定理的必要性。其充分性在后续部分再证明 因为G为简单平面图,所以,G中无环和平行边。由定理5和定理6可知 G中无割点和桥。于是G中各面的次数大于或等于3,下面只需证明:G中各 面的次数不可能大于3 假设面R的次数deg(R)=s>3 在G中,若v1与v3不相邻,在R内加边1v3)不破坏平面性,这与G是极 大平面图矛盾,因此v1与v必相邻。由于R的存在,边(v1v3必在R外.类 似地,v2与v4也必相邻且边(2,V小必在R外这样,必产生(v1v)与(2,V 相交于R的外部,这与“G是平面图”相矛盾,故必有s=3,即G中不存在次 数大于3的面。 所以,G的每个面都由3条边所围,也就是说,各面的次数均为3
8 极大平面图 定理7. 设G为n(n ≥ 3)阶简单连通的平面图, G为极大平面图, 当且仅当G 的每个面的次数均为3。 证明: 先证明该定理的必要性。其充分性在后续部分再证明. 因为G为简单平面图, 所以, G中无环和平行边。由定理5和定理6可知, G中无割点和桥。于是G中各面的次数大于或等于3, 下面只需证明: G中各 面的次数不可能大于3。 假设面Ri的次数deg(Ri) = s > 3。 在G中, 若v1与v3不相邻, 在Ri内加边(v1, v3)不破坏平面性, 这与G是极 大平面图矛盾, 因此, v1与v3必相邻。由于Ri的存在,边(v1, v3)必在Ri外. 类 似地, v2与v4也必相邻, 且边(v2, v4)必在Ri外. 这样, 必产生(v1, v3)与(v2, v4) 相交于Ri的外部, 这与“G是平面图”相矛盾, 故必有s = 3, 即 G中不存在次 数大于3的面。 所以, G的每个面都由3条边所围, 也就是说, 各面的次数均为3
极小非平面图 定义4.若在非平面图G中任意删除一条边所得图为平面图,则称G 为极小非平面图
9 极小非平面图 定义4. 若在非平面图G中任意删除一条边, 所得图为平面图, 则称G 为极小非平面图
欧拉公式 定理8(欧拉公式)对于任意连通平面图G,有n-m+r=2.其中n,m 和分别为G的顶点数,边数和面数 证明:对边数m进行归纳 (1)m=0时,由于G为连通图,所以G只能是平凡图,结论显然 成立 (2)设m=k(k≥1)时,命题成立.当m=k+1时,分以下情况: 若G是树,则G是非平凡的,因此,G中至少有两个叶结点。设v 为叶结点,令G=GV,则G仍然是连通图,且G的边数m=m-1 k。由归纳假设可知n-m+r=2,其中n’,m,和r分别为G’的顶 点数,边数和面数.由n=n-1,r=r可得:nm+r=(n+1)-m+1)+r =n’-m’+r’=2 若G不是树,则G中含圈,设边e在G中某个圈上。令G”=G-e, 则G’仍连通,且m’=m-1=k。由归纳假设有n-m’+r=2。而n =n,r=r1,于是nm+r=n-(m+1)+(r+1)=n-m+r=2 10
10 欧拉公式 证明: 对边数m进行归纳。 定理8(欧拉公式) 对于任意连通平面图G, 有n-m+r = 2. 其中 n, m 和r分别为G的顶点数, 边数和面数。 (1) m = 0时, 由于G为连通图, 所以 G只能是平凡图, 结论显然 成立。 (2) 设m = k(k ≥ 1)时, 命题成立. 当m = k+1时, 分以下情况: 若G是树, 则G是非平凡的, 因此, G中至少有两个叶结点。设v 为叶结点, 令G’ = G-v, 则G’仍然是连通图, 且G’的边数m’ = m-1 = k。由归纳假设可知 n’ – m’ + r’ = 2, 其中n’, m’,和r’分别为G’的顶 点数, 边数和面数. 由n’ = n-1, r’ = r可得: 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’ - m’ + r’ = 2。而n’ = n, r’ = r-1,于是 n-m+r = n’-(m’+1)+(r’+1) = n’-m’+r’ = 2
