集合论与图论课件 第九章(旧)

29
2、图的色数的定义
定义9.4.2 图G的色数是使G为n—着色的数的最小值, 图G的色数记为(G),(G)n,则称G是n—可着色的，若 (G)=n,则称G是n色的。
若G是偶数个顶点圈C2n,则(C2n)=2, 若G是奇数个顶点圈C2n+1,则(C2n+1)=3。
30
2、图的色数的定义
定义9.4.2 图G的色数是使G为n—着色的数的最小 值,图G的色数记为(G),(G)n,则称G是n—可着色 的，若(G)=n,则称G是n色的。
定理9.4.5 每个可平面图是5—可着色的 [证]对可平面图的顶点数进行归纳证明； 当p≤5时,定理显然成立； 假设对一切有p个顶点的可平面图都是5—可着色 的,证明对一切有p+1个顶点的可平面图也是5—可 着色的； 设G是一个有p+1个顶点可平面图,由推论9.1.6知 G中有一个顶点v使degv≤5,于是,G-v是一个有p个 顶点的可平面图,由归纳假设,G-v是5可着色的；
34
9.4 图的顶点着色
定理9.4.3 如果G是一个连通图且不是完全图 也不是奇数长的圈,则G是(G)—可着色的。
35
9.4 图的顶点着色
定理9.4.4 每个平面图都是6可着色的 [证] 对平面图的顶点数p用归纳法; 如果顶点数小于7,显然是6—可着色的; 假设对p-1个顶点的平面图是6—可着色的,只需证对 有p个顶点的平面图也是6—可着色的即可; 设G是一个有p个顶点的平面图;
G-x有p个顶点，q-1条边，f-1个面 由归纳假设 p-(q-1)+(f-1)=2 p-q+f=2 因此面数是f时也成立。
f3
x
f1
f2 v
u
f4
f3
f2 v
f1
u
f4
9
2、平面图的面数、顶点数、边数之间的关系。
推论9.1.1 若平面连通图G有p个顶点q条边且每个面 都是由长为n的圈围成的，则
2、若G是2-连通的且没有三角形,则G中任意顶点 都在一个圈上, 已知没有三角形,所以圈的长都是4时边数最多,
所以q≤2p-4
16
4、最大(极大)平面图的性质
推论9.1.5 K5与K3,3都不是可平面图 证：
利用推论9.1.4,任意(p,q)平面图都满足
q≤3p-6,这里p≥3
对于k5来说： p=5, q=10;
*22
9.1 平面图及欧拉公式
定理9.1.1(欧拉公式) 如果一个平面连通图有p 个顶点、q条边、f个面，则：p-q+f=2
推论9.1.4 若G是任一有p个顶点q条边的可 平面图p≥3,则q≤3p-6,若G是2-连通的且没 有三角形,则q≤2p-4
推论9.1.6 每个平面图G中顶点度的最小值不超 过5,即(G)≤5
图1 推论9.1.4 若G是任一有p个顶点q条边的可平面图 p≥3,则q≤3p-6,若G是2-连通的且没有三角形,则 q≤2p-4
15
4、最大(极大)平面图的性质
推论9.1.4 若G是任一有p个顶点q条边的可平面图 p≥3,则q≤3p-6,若G是2-连通的且没有三角形,则 q≤2p-4
1、因为当平面图中每个面都是三角形时其边数最 多，由推论9.1.2,则q≤3p-6,
仍然用推论9.1.4,q≤3p-6 如果G的每个顶点的度大于5,也就是≥6 那么所有顶点的度数和大于或等于6p 由欧拉定理,2q≥6p,即q≥3p
不满足推论9.1.4,q≤3p-6
每个平面图G中顶点度的最小值不超过5, 即(G)≤5
19
4、最大(极大)平面图的性质
例题:顶点数p≥4的最大平面图,(G)≥3
V-E+F=2 定理9.1.1(欧拉公式) 如果一个平面连通图有p个 顶点、q条边、f个面，则：p-q+f=2
f3
f2 v
f1
u
f4
如图：顶点数4 边数6 面数4
7
2、平面图的面数、顶点数、边数之间的关系。
定理9.1.1(欧拉公式) 如果一个平面连通图有p个顶点、 q条边、f个面，则：p-q+f=2
第九章：平面图与图的着色
9.1 平面图及其欧拉公式
9.2 非哈密顿平面图
9.3 库拉托斯基定理、对偶图

9.4 图的顶点着色
9.5 图的边着色
v
u
平面图
1
第九章：平面图与图的着色
平面图的定义，性质，顶点着色和 边着色。
内容
除了顶点外，其他位 置边不相交的图
建模 电路图，地图，各种建筑平面图的建 模。本章对平面图的一般性质进行讨论。 图的顶点着色应用广泛。
证明
v
设G是最大平面图,其最小度顶点为v, 设G-v也是一个平面图,v在G-v的一个面内, 在这个面内,边界上至少有三个顶点, 由极大性,v必然与这些顶点都相连, 因此, (G)≥3。
20
4、最大(极大)平面图的性质
1(P281)、设G是一个有p个顶点的平面图,p≥4, 证明:G中有4个度不超过5的顶点 只要证明最大平面图有4个度不超过5的顶点即可 用反证法:若不成立,则至少有p-3个顶点≥6 顶点度数和≥(p-3)×6+9=6p-9 2q≥6p-9 q≥3p-4.5
38
9.4 图的顶点着色
1、如果degv≤4,则必有一种颜色,在G-v的一种 5-着色时,对与v邻接的顶点着色中未用此色,
于是,用此色对顶点v着色便得到G的5-着色； 2、degv=5且对G-v的5-着色中,与v邻接的5 个顶点v1,v2,v3,v4,v5分别着5种颜色 c1,c2,c3,c4,c5。
*24
4、最大(极大)平面图的性质
2(P281)、设G是一个有k个支的平面图，若G的 顶点数、边数、面数分别为p、q和f,试证：
p-q+f=k+1。
25
第九章：平面图与图的着色
9.1 平面图及其欧拉公式 9.2 非哈密顿平面图 9.3 库拉托斯基定理、对偶图 9.4 图的顶点着色 9.5 图的边着色
如果一个图可以嵌入平面，则称此图是可平面的。
4
2、平面图的面数、顶点数、边数之间的关系。
平面图的内部面与外部面
f3
f2 v
f1
u
f4
灰色环不是单连通区域
定义9.1.2 平面图把平面分成了若干个区域，这些区
域都是单连通的，称之为G的面，其中无界的那个连
通区域称为G的外部面，其余的单连通区域称为G的内
q=n(p-2)/(n-2)
f1
f2 f3
f4
图G
如图有4个长为4的面，边数为8，顶点数为6 8=4(6-2)/(4-2)
10
2、平面图的面数、顶点数、边数之间的关系。
推论9.1.1 若平面连通图G有p个顶点q条边且 每个面都是由长为n的圈围成的，则
q=n(p-2)/(n-2) 证： 因为G的每个面都是长为n的圈围成的 并且G的每条边都在G的两个面上 q=fn/2 f=2q/n p-q+2q/n=2 q=n(p-2)/(n-2)
(Kp)=p, (Kpc)=1, (Km,n)=2,
K6
K6c
K2,4
31
9.4 图的顶点着色
定理9.4.1 一个图是可双色的当且仅当它没 有奇数长的圈。
偶图
一个图是可双色的当且仅当是偶图。 偶图的充分必要条件是它的圈的长度都是偶数。
32
9.4 图的顶点着色
定理9.4.2 设=(G)为图G的顶点度的最大值,则 G是(+1)—可着色的.
部面。
单连通区域是指能够收缩到一个点的区域
5
2、平面图的面数、顶点数、边数之间的关系。
f3
f2 v
f1
u
f4
0
1
3
2
4
5
平面图的每个内部面都是G的某个圈围成的单连通区 域。
没有圈的图没有内部面，只有一个外部面。
6
2、平面图的面数、顶点数、边数之间的关系。
如果用V表示多面体的顶点,用E表示棱，用F表示 面数。
定理9.1.1(欧拉公式) 如果一个平面连通图 有p个顶点、q条边、f个面，则：p-q+f=2
11
3、最大(极大)可平面图
一个图称为最大可平面图，如果这个可平面图再 加入一条边，新图必然是不可平面的。
观察下面两个图，他们是不是最大可平面图
图1
图2
图1不是最大可平面图 图2是最大可平面图
12
4、最大(极大)平面图的性质
这与平面图满足q≤3p-6矛盾
因此,超过5的度数不可能有p-3个
21
4、最大(极大)平面图的性质
3(P281)、若G是顶点数p>11的平面图，试证 Gc不是平面图。 证明： 设G的顶点数是p 则G与Gc的边数是p(p-1)/2。 因为G与Gc都是平面图 应该：p(p-1)/26p-12 解不等式： p>11时上式不成立 所以：若G是顶点数p>11的平面 图，则Gc不是平面图。
证：对面数用归纳法
当f=1时，G没有内部面
所以G中无圈，G是树； p假如对q一+f切=1不+超1=过f-1个面 的平面连2 通图欧拉公式成立， 现证f个面时的情况。
0
1
3
2
4
5
只有一个面的平面 连通图（树）
8
2、平面图的面数、顶点数、边数之间的关系。
f≥2,G至少有一个内部面，从而G中有一个圈，
从这个圈上去掉一条边x， 则打通了两个面，
[证] 对顶点数p用归纳法 当p=1成立, 假设对顶点数为p-1的图定理成立,(+1)可着色 今设G是一个有p个顶点的图,
图G
33
9.4 图的顶点着色
图G
从G中任意去掉一个顶点v,则G-v有p-1个顶点, (G-v)≤(G) 由归纳假设G-v是(+1)—可着色的, 但在G中与v邻接的顶点最多有个,与v邻接的 顶点最多用去种颜色,剩下一种给顶点v着色即 可。