课件23.doc

Size: px

Start display at page:

Download "课件23.doc"

矶衷
5 years ago
Views:

1 6.3 平面图与图的着色一平面图 : 定义 3: 设无向图 G=<V,E>, 如果能把 G 的所有结点和边画在平面上, 使任何两边除公共结点外没有其它交叉点, 则称 G 为可嵌入平面图, 或称 G 是可平面图, 可平面图在平面上的一个嵌入称为平面图, 如果 G 不是可平面图, 则称 G 为非平面图例 : K 4 故 K 4 是可平面图例 : K 5 少一条边故 K 5 少一条边的图是可平面图例 : K 5, K 3, 3 不是平面图 V V V V5 V2 V3 V2 V3 V2 V3 V V5 点 V 5 放在外部,( V 5 V 4 ) 必要与回路相交, V 5 放在回路 V V 2 V 4 内部,

2 V2 则 (V 5 V 3 ) 必要与回路 V V 2 V 4 相交 V3 例 : K 3, 3 不是可平面图 x y z b x z c a b c a y xayc 构成了一个回路,z 放入内部 (z,a),(z,c) 有边构成了两个回路,b 点无论放在外部还是两个回路的某一个内部, 因 bx,by,bz 均有边, 必与一个回路要交叉 2 面的次数定义 4:G 是一个连通平面图, 由图的边所包围的并且其内部不包含图的结点和边的区域, 称 G 的一个面, 包围该面的各边所组成的回路称为这个面的边界, 面的边界的长度称为该面的次数, 记为 deg() 例 : 下列图中有 0 个点 3 条边, 把平面分成 5 个平面, 其中有且仅有一个无界面 0 V 4 V0 V2 V8 0 V7 2 V9 3 V3 V5 V6 由回路围成 deg()=5 2 由回路围成 deg(2)=6 3 由回路围成 deg(3)=3 4 由回路围成 deg(4)= 2

3 0 由回路围成 Deg(0)= 定义 6: 在平面图 G=<V,E> 中, V =, E =e, 所有面的度数之和等于边数的两倍, 即 deg(i)=2e 证明 : 如边是两个面的分界线, 该边在两个面的度数中各记次如边不是两个面的分界线 ( 称为割边 ) 则该边在该面的度数中重复记了两次, 故定理结论成立 3 Eule 公式定理 7: 连通平面图 G=<V,E> 中共有个结点,e 条边和个面, 则有 -e+=2, 该定理对于空间多面体仍然适用在刚才的图中,V=0, e=3,=5, 满足条件空间正六面体 :=8,e=2,=6 M B D C M C B D N N 空间正八面体 :=6,e=2,=8 定理 8: 设 G 有个结点,e 条边的简单连通平面图, 若 3, 则 e 3-6 证明 : 设 G 有个面, 因 G 是简单图, 则每个面至少由 3 条边围成 deg() i 3, 又 deg() i 2e 2e 3, 2 3 e, 代入欧拉公式 3

4 2=-e+ -e+ 2 3 e=- 3 e 2 - e, e 3-b 3 说明 : 这是简单图是可平面图的必要条件例如 : K 5 5 中 e=0,=5,3-6=9, 从而 e>3-6 K 5 5 不可能是平面图例 : 已知一个平面图中电数 =0, 每个面均由 4 条边围成, 求该平面图的边数和面数, 并画出该平面图解 : 因每个面的次数均为 4, 2e=4, e=2, 又 =0, 代入欧拉公式 -e+=2 0-2+=2 解得 =8, 则 e=2=6 点的毒序列为 : 度的序列为 : 4,4,4,4 6,6,3,3, 3,3,3,3 3,3,2,2, 2,2. 2,2 此两图均满足条件但不是同构的 4 库拉托夫斯基定理 fi fi 在图的一条边上插入一个二度的结点, 或者关联于一个二度结点的两边, 去掉该结点并将该两边合成一边, 这均 4

5 不影响一个图的平面性定义 5: 给两图 G 和 G2, 或者它们是同构的, 或者反复地插入或去掉二度结点后两图是同构, 则 G 和 G2 是二度结点内是同构的, 也称 G 和 G2 是同胚的定理 9:(Kuatowski 定理 ) 一个图是平面图的充要条件是它不含与 K 3,3 或 K 5, 在 2 点结点内同构的子图例 : 该图先将 e 去掉的一个子图 e, 再将 6, 7, 5 8 的二度 6 结点去掉两边合一边成 K 5, 故该图不是平面图 2 7 二平面的着色问题 3 4 问题的提出 : 该问题起源于地图的着色问题对点的着色就是对图 G 的每个结点指定一种颜色, 使的相邻结点的颜色不同, 对边着色就是, 给每条边指定一种颜色使得相邻的边的颜色不同, 给面着色就是给每个面指定一种颜色使得有公共边的两个面有不同的颜色如果给图 G 着色时, 至少要用 n 种颜色, 就称 G 为 n 一色的, 该 n 称为 G 的色数, 记为 X 对边着色和对面着色均可以转化为对结点着色问题 2 对点着色的鲍威尔方法 : 第一步 : 对每个结点按度数递减次序进行排列 ( 相同度数的结点次序可随意 ) 第二步 : 用第一种颜色对第一个结点着色, 并按次序对与第一个结点不相邻的结点着同样的颜色, 继续对后面与前面已着第一种颜色的这些点不相邻的结点, 着第一种颜色, 直到全部结点查完 8 (G) 5

6 第三步 : 对未着色的点, 用第二种颜色重复第二步, 再用第三种颜色重复第二步, 一直下去直到全部点均着了色为止例 : 对点着色 B C H G 按度数排列为 CBFGHDE, 用第一种颜色对 C,,G 着色用第二种颜色对 B,H,D,E 着色用第三种颜色对 F 着色 G 是三色图, X =3 (G) D F 定理 0: 对于完全图 K 有 χ( K )=n n 定理 : 连通平面图 G=<V,E> 至少有三个结点, 则必有一点 u V 使得 deg(u) 5 证明 : 设 V =, E =e, 若 G 的每个结点均有 deg(u) 6, 则有 2e= i= i n deg( ) 6 6 e 3>3-6 与定理 8 矛盾定理 2: 任意平面图的色数 5 四色定理 : 在实际中发现对面着色只要 4 色就够, 但始终没能证明, 后来用计算机证明了任何平面图均是 4 色图 6

7 6.3 平面图与图的着色一平面图 : 定义 3: 设无向图 G=<V,E>, 如果能把 G 的所有结点和边画在平面上, 使任何两边除公共结点外没有其它交叉点, 则称 G 为可嵌入平面图, 或称 G 是可平面图, 可平面图在平面上的一个嵌入称为平面图, 如果 G 不是可平面图, 则称 G 为非平面图例 : K 4 故 K 4 是可平面图例 : K 5 少一条边故 K 5 少一条边的图是可平面图例 : K 5, K 3, 3 不是平面图 V V V V5 V2 V3 V2 V3 V2 V3 V V5 点 V 5 放在外部,( V 5 V 4 ) 必要与回路相交, V 5 放在回路 V V 2 V 4 内部,

8 V2 则 (V 5 V 3 ) 必要与回路 V V 2 V 4 相交 V3 例 : K 3, 3 不是可平面图 x y z b x z c a b c a y xayc 构成了一个回路,z 放入内部 (z,a),(z,c) 有边构成了两个回路,b 点无论放在外部还是两个回路的某一个内部, 因 bx,by,bz 均有边, 必与一个回路要交叉 2 面的次数定义 4:G 是一个连通平面图, 由图的边所包围的并且其内部不包含图的结点和边的区域, 称 G 的一个面, 包围该面的各边所组成的回路称为这个面的边界, 面的边界的长度称为该面的次数, 记为 deg() 例 : 下列图中有 0 个点 3 条边, 把平面分成 5 个平面, 其中有且仅有一个无界面 0 V 4 V0 V2 V8 0 V7 2 V9 3 V3 V5 V6 由回路围成 deg()=5 2 由回路围成 deg(2)=6 3 由回路围成 deg(3)=3 4 由回路围成 deg(4)= 2

9 0 由回路围成 Deg(0)= 定义 6: 在平面图 G=<V,E> 中, V =, E =e, 所有面的度数之和等于边数的两倍, 即 deg(i)=2e 证明 : 如边是两个面的分界线, 该边在两个面的度数中各记次如边不是两个面的分界线 ( 称为割边 ) 则该边在该面的度数中重复记了两次, 故定理结论成立 3 Eule 公式定理 7: 连通平面图 G=<V,E> 中共有个结点,e 条边和个面, 则有 -e+=2, 该定理对于空间多面体仍然适用在刚才的图中,V=0, e=3,=5, 满足条件空间正六面体 :=8,e=2,=6 M B D C M C B D N N 空间正八面体 :=6,e=2,=8 定理 8: 设 G 有个结点,e 条边的简单连通平面图, 若 3, 则 e 3-6 证明 : 设 G 有个面, 因 G 是简单图, 则每个面至少由 3 条边围成 deg() i 3, 又 deg() i 2e 2e 3, 2 3 e, 代入欧拉公式 3

10 2=-e+ -e+ 2 3 e=- 3 e 2 - e, e 3-b 3 说明 : 这是简单图是可平面图的必要条件例如 : K 5 5 中 e=0,=5,3-6=9, 从而 e>3-6 K 5 5 不可能是平面图例 : 已知一个平面图中电数 =0, 每个面均由 4 条边围成, 求该平面图的边数和面数, 并画出该平面图解 : 因每个面的次数均为 4, 2e=4, e=2, 又 =0, 代入欧拉公式 -e+=2 0-2+=2 解得 =8, 则 e=2=6 点的毒序列为 : 度的序列为 : 4,4,4,4 6,6,3,3, 3,3,3,3 3,3,2,2, 2,2. 2,2 此两图均满足条件但不是同构的 4 库拉托夫斯基定理 fi fi 在图的一条边上插入一个二度的结点, 或者关联于一个二度结点的两边, 去掉该结点并将该两边合成一边, 这均 4

11 不影响一个图的平面性定义 5: 给两图 G 和 G2, 或者它们是同构的, 或者反复地插入或去掉二度结点后两图是同构, 则 G 和 G2 是二度结点内是同构的, 也称 G 和 G2 是同胚的定理 9:(Kuatowski 定理 ) 一个图是平面图的充要条件是它不含与 K 3,3 或 K 5, 在 2 点结点内同构的子图例 : 该图先将 e 去掉的一个子图 e, 再将 6, 7, 5 8 的二度 6 结点去掉两边合一边成 K 5, 故该图不是平面图 2 7 二平面的着色问题 3 4 问题的提出 : 该问题起源于地图的着色问题对点的着色就是对图 G 的每个结点指定一种颜色, 使的相邻结点的颜色不同, 对边着色就是, 给每条边指定一种颜色使得相邻的边的颜色不同, 给面着色就是给每个面指定一种颜色使得有公共边的两个面有不同的颜色如果给图 G 着色时, 至少要用 n 种颜色, 就称 G 为 n 一色的, 该 n 称为 G 的色数, 记为 X 对边着色和对面着色均可以转化为对结点着色问题 2 对点着色的鲍威尔方法 : 第一步 : 对每个结点按度数递减次序进行排列 ( 相同度数的结点次序可随意 ) 第二步 : 用第一种颜色对第一个结点着色, 并按次序对与第一个结点不相邻的结点着同样的颜色, 继续对后面与前面已着第一种颜色的这些点不相邻的结点, 着第一种颜色, 直到全部结点查完 8 (G) 5

12 第三步 : 对未着色的点, 用第二种颜色重复第二步, 再用第三种颜色重复第二步, 一直下去直到全部点均着了色为止例 : 对点着色 B C H G 按度数排列为 CBFGHDE, 用第一种颜色对 C,,G 着色用第二种颜色对 B,H,D,E 着色用第三种颜色对 F 着色 G 是三色图, X =3 (G) D F 定理 0: 对于完全图 K 有 χ( K )=n n 定理 : 连通平面图 G=<V,E> 至少有三个结点, 则必有一点 u V 使得 deg(u) 5 证明 : 设 V =, E =e, 若 G 的每个结点均有 deg(u) 6, 则有 2e= i= i n deg( ) 6 6 e 3>3-6 与定理 8 矛盾定理 2: 任意平面图的色数 5 四色定理 : 在实际中发现对面着色只要 4 色就够, 但始终没能证明, 后来用计算机证明了任何平面图均是 4 色图 6

一握手定理的应用二平面图欧拉公式的应用三图的基本概念与应用四欧拉图和哈密顿图五图的着色

一握手定理的应用二平面图欧拉公式的应用三图的基本概念与应用四欧拉图和哈密顿图五图的着色图论习题考研习题与经典习题 2004-5 一握手定理的应用二平面图欧拉公式的应用三图的基本概念与应用四欧拉图和哈密顿图五图的着色一握手定理的应用 1. 已知具有 n 个度数都为 3 的结点的简单图 G 有 e 条边, (1) 若 e=3n-6, 证明 G 在同构意义下唯一, 并求 e,n (2) 若 n=6, 证明 G 在同构意义下不唯一提示 : 握手定理 ( 北师大 2000