定理6.10（五色定理）任何平面图G是5-可着色的。证明.ppt

定理 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. (1)d(v0)5, (2)d(v0)=5 定理 6.11(二色定理)：地图G是2-面可着色的当且仅当它是一个欧拉图。 证明：(1) G是2-面可着色的，则它是一个欧拉图 (2) G是欧拉图，则G是2-面可着色的 第七章 树 7.1树及其性质 定义 7.1：一个连通无回路的图称为树,记为T。树中度数为1的顶点称为树叶(或称悬挂点)。度数大于1的顶点称为分枝点或内点。不相交的树的全体称为森林。平凡图也可称为平凡树。(平凡图即只有一个点) 除了定义 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的每一对不同的顶点之间有唯一的一条路。 证明：(1)→(2): T是无回路的连通图要证明T是无回路图,且e=n-1，即证明e=n-1 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图，显然只能是下图所示： (2)→(3): T是无回路图,且e=n-1,要证明T是连通图,且e=n-1。即证明T是连通图,用反证法, (3)→(4):在T是连通图,且e=n-1的条件下,证明T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通, 只能是下图 假设n=k-1时结论成立,考察n=k时,由于T是连通的,所以,每个顶点度数?1(e=k-1)。可以证明,至少存在一个顶点u,使 d(u)=1。Why? 2)再证明如果在连通图T的任两个不相邻顶点之间添加一边,记为{vi,vj},则该边与T中从vi到vj的一条路 (vi,vi1,…, vis,vj) 构成一条回路(vi,vi1,…, vis,vj,vi)。 若这条回路不唯一，由于T无回路，而T∪{vi,vj}得到了回路，因此另一条回路C也含有边{vi,vj}， (4)→(5): 在T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路的条件下证明T是连通图,但删去任一边后,便不连通。 若T不连通, 则存在顶点vi和vj,在vi与vj之间没有路。显然,若加一边{vi,vj},不会产生回路,与假设矛盾。 又由于T无回路,则删去任一边,便不连通 (5)→(6): 在T是连通图,但删去任一边后,便不连通的条件下证明T的每一对不同的顶点之间有唯一的一条路。 由于T是连通的,任两点之间有一条路。如果某两个顶点之间多于一条路,则T中必含有回路,(Why?) 删去该回路上任一边,图仍连通,与假设矛盾。 (6)→(1): 在T的每一对不同的顶点之间有唯一的一条路的条件下，证明T是无回路的连通图。显然图是连通的。若有回路, 则回路上任两点之间有两条路, 从而导致矛盾。 推论：若G是n个顶点?个分支的森林, 则G有n-?条边。 定理7.2:在任一棵非平凡树T中, 至少有两片树叶。 证明:由于T是连通的,对T的任一顶点vi,d(vi)?1,并且e=n-1,即所有顶点度数之和=2(n-1). 下面证明T中至少有两个顶点的度数为 1 。 7.2生成树与割集 例如下图中给定图G,粗线表示G的生成树T,它的边集是{e1,e4,e5,e6},的边集是{e2,e3,e7,e8}。 定理7.3：G是连通图当且仅当G有生成树。 证明：1) G有生成树证明G是连通图。因为生成树是连通图,生成子图连通，则原图一定连通。 2) G是连通图证明G有生成树 设G是连通图,若G没有回路,则G本身就是生成树； 若G只有一条回路,从这条回路中删去一条边, 仍保持连通, 得到一棵生成树； 若G中有多条回路, 则重复上述过程, 直到得到一棵生成树为止。 设连通图G有n个顶点, e条边, 那么G的任一棵生成树有n-1条枝, e-n+1条连枝。 设图G有n个顶点,e条边, ?个分支, n,e,?之间有两个简单的关系式: n-??0; e-n+??0。 定义 7.3:设图G