定理 6.10(五色定理)：任何平面图G是5-可着色的。

Presentation on theme: "定理 6.10(五色定理)：任何平面图G是5-可着色的。"— Presentation transcript:

1 定理 6.10(五色定理)：任何平面图G是5-可着色的。
证明：不妨设G是平面简单图。下面对G的顶点数采用归纳法证明。 当n5时结论显然成立 假设对n-1个顶点的所有平面简单图G是5-可着色的。 考虑n个顶点的平面简单图G, 由定理 6.2知, G中存在顶点v0,使d(v0)5。 删去v0及其关联边得到G'=G-v0 由归纳假设, G- v0是5-可着色的, 在给定G- v0的一种着色后, 将v0及其关联边加回到原图中, 得到G.

2 (1)d(v0)<5, (2)d(v0)=5 定理 6.11(二色定理)：地图G是2-面可着色的当且仅当它是一个欧拉图。 证明：(1) G是2-面可着色的，则它是一个欧拉图 (2) G是欧拉图，则G是2-面可着色的

3 第七章 树 7.1树及其性质 定义 7.1：一个连通无回路的图称为树,记为T。树中度数为1的顶点称为树叶(或称悬挂点)。度数大于1的顶点称为分枝点或内点。不相交的树的全体称为森林。平凡图也可称为平凡树。(平凡图即只有一个点)

4 图 (a)是一棵树；(b)是森林,也就是无回路的图,它的每个分支是一棵树。

5 除了定义 7.1 给出树的定义外还有几个树的等价定义, 即下面的定理。
定理7.1：设图T有n个顶点,有下列6条T是树的等价定义: (1)T是无回路的连通图; (2)T是无回路图,且e=n-1,其中e是边数; (3)T是连通图,且e=n-1; (4)T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路(称T为最大无回路图); (5)T是连通图,但删去任一边后,便不连通(称T为最小连通图); (6)T的每一对不同的顶点之间有唯一的一条路。

6 证明：(1)→(2): T是无回路的连通图要证明T是无回路图,且e=n-1，即证明e=n-1
对顶点数n采用归纳法,n=2时,因为T是无回路的连通图，显然只能是下图所示： 故结论成立。 假设n=k时结论成立,现考察n=k+1时,由于连通无回路以及定理 5.4 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为1的点u,它的关联边为 {u,v}。

7 (2)→(3): T是无回路图,且e=n-1,要证明T是连通图,且e=n-1。即证明T是连通图,用反证法,

8 (3)→(4):在T是连通图,且e=n-1的条件下,证明T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路。
n=2时e=1,且连通, 只能是下图 显然T是无回路的。

9 假设n=k-1时结论成立,考察n=k时,由于T是连通的,所以,每个顶点度数1(e=k-1)。可以证明,至少存在一个顶点u,使 d(u)=1。Why?

10 2)再证明如果在连通图T的任两个不相邻顶点之间添加一边,记为{vi,vj},则该边与T中从vi到vj的一条路
(vi,vi1,…, vis,vj) 构成一条回路(vi,vi1,…, vis,vj,vi)。 若这条回路不唯一，由于T无回路，而T∪{vi,vj}得到了回路，因此另一条回路C'也含有边{vi,vj}，

11 (4)→(5): 在T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路的条件下证明T是连通图,但删去任一边后,便不连通。
若T不连通, 则存在顶点vi和vj,在vi与vj之间没有路。显然,若加一边{vi,vj},不会产生回路,与假设矛盾。 又由于T无回路,则删去任一边,便不连通

12 (5)→(6): 在T是连通图,但删去任一边后,便不连通的条件下证明T的每一对不同的顶点之间有唯一的一条路。
由于T是连通的,任两点之间有一条路。如果某两个顶点之间多于一条路,则T中必含有回路,(Why?) 删去该回路上任一边,图仍连通,与假设矛盾。 (6)→(1): 在T的每一对不同的顶点之间有唯一的一条路的条件下，证明T是无回路的连通图。显然图是连通的。若有回路, 则回路上任两点之间有两条路, 从而导致矛盾。

13 推论：若G是n个顶点个分支的森林, 则G有n-条边。
定理7.2:在任一棵非平凡树T中, 至少有两片树叶。 证明:由于T是连通的,对T的任一顶点vi,d(vi)1,并且e=n-1,即所有顶点度数之和=2(n-1). 下面证明T中至少有两个顶点的度数为 1 。

14 7.2生成树与割集

15 例如下图中给定图G,粗线表示G的生成树T,它的边集是{e1,e4,e5,e6},的边集是{e2,e3,e7,e8}。

16 定理7.3：G是连通图当且仅当G有生成树。 证明：1) G有生成树证明G是连通图。因为生成树是连通图,生成子图连通，则原图一定连通。 2) G是连通图证明G有生成树 设G是连通图,若G没有回路,则G本身就是生成树； 若G只有一条回路,从这条回路中删去一条边, 仍保持连通, 得到一棵生成树； 若G中有多条回路, 则重复上述过程, 直到得到一棵生成树为止。

17 设连通图G有n个顶点, e条边, 那么G的任一棵生成树有n-1条枝, e-n+1条连枝。
设图G有n个顶点,e条边, 个分支, n,e,之间有两个简单的关系式: n-0; e-n+0。 定义 7.3:设图G有n个顶点, e条边, 个分支, 称n-为G的秩, 称e-n+为图G的零度。 显然G的秩是G的各分支中生成树的枝数之和, G的零度是G的各分支中生成树的连枝数之和。 对于连通图G来说, 它的秩为n-1, 零度为e-n+1。

18 定义7.4：设D是图G的一个边集, 若在G中删去D的全部边后所得图的秩减少 1 , 而删去D的任何真子集均无此性质, 称D为G的割集。
二、割集与断集 定义7.4：设D是图G的一个边集, 若在G中删去D的全部边后所得图的秩减少 1 , 而删去D的任何真子集均无此性质, 称D为G的割集。 图 (a) 中边集{e1, e3,e5,e6,e8}是割集，但删去任何真子集不具有此性质

19 图(b)中边集{e1, e2} 是割集 边集{ e1,e2,e3,e4} 不是割集,

20 定义7.5:设图G的顶点非空真子集为V1V, 在G中一个端点在V1中, 另一端点在V(G)-V1中的所有边组成的集合称为G的一个断集或称边割,记为 E(V1(V(G)-V1)), 简记为(V1, V(G)-V1)。 当|(V1, V(G)-V1)|=1时, (V1, V(G)-V1)中的那条边称为割边或 桥。 图 7.2(b) 中边集{e1,e2}和{e1,e2,e3,e4}都是断集(边割)。 割集是断集, 反之不一定。

21 作业: P ,15,16 P152 1,2,3,4,5,6,7,8