西安电子科技大学：《图论》课程教学课件（研讨课）第五讲 欧拉公式与权转移方法

2016图论讨论班（五) 欧拉公式与牧转移方法

2016图论讨论班（五） 欧拉公式与权转移方法

欧拉公式：设G是一个有v个顶点，e条边和f个面的连通平面图，则 v-e+f=2 点度d(W):与点v关联的边的条数（环算两条边） 面度d(⑤：与面关联的边的条数（割边算两条边） d(v1)=4 -6 d(v2)=2 d(f1)=3 d(v3)=4 d(f2)=3 d(v4)=3 d(f3)=3 19 d(v5)=2 d(f4)=3 d(v6)=4 d(fs)=3 Is d(v,)=4 d(f6)=1 d(vs)=3 d(f7)=2 d(fg)=12 V8 d(vo)=4 V=9,e=15,f=8 点度和=面度和=30=2e

欧拉公式：设G是一个有v个顶点，e条边和f个面的连通平面图，则 v-e+f=2 点度d(v)：与点v关联的边的条数（环算两条边） 面度d(f)：与面f关联的边的条数（割边算两条边） ( ) 4 ( ) 3 ( ) 4 ( ) 4 ( ) 2 ( ) 3 ( ) 4 ( ) 2 ( ) 4 9 8 7 6 5 4 3 2 1          d v d v d v d v d v d v d v d v d v ( ) 12 ( ) 2 ( ) 1 ( ) 3 ( ) 3 ( ) 3 ( ) 3 ( ) 3 8 7 6 5 4 3 2 1         d f d f d f d f d f d f d f d f v=9， e=15, f=8 点度和=面度和=30=2e

定理：设G是一个连通平面图，则对于任何实数k,>0,恒有： ∑(kd(v)-2k+10)+∑(ld(f)-2k+10)=-4k+1) v∈V(G) f∈F(G) 推论： ∑(d()-4)+∑(d(f)-4)=-8 vEV(G) f∈F(G) ∑(dy)-6)+∑(2d(f)-6)=-12 vEV(G) f∈F(G) 0●年布事●

定理：设G是一个连通平面图，则对于任何实数k,l>0，恒有：             ( ) ( ) ( ( ) 2( )) ( ( ) 2( )) 4( ) v V G f F G kd v k l ld f k l k l 推论：          ( ) ( ) ( ( ) 4) ( ( ) 4) 8 v V G f F G d v d f          ( ) ( ) ( ( ) 6) (2 ( ) 6) 12 v V G f F G d v d f …………

四色定理的证明概述（每个平面图都是4-顶点可染的) 第一部分：（权转移方法） 证明每个平面图都含有若干种构型中的其中一个！ 此部分使用的是理论性的数学证明！ 第二部分：（可约性验证） 假设四色定理不正确，则其必然存在反例，即一个不是4-顶点可 染的平面图G,接下来证明图G不含有上述提及的任何一个构型！ 此部分使用的是计算机证明，耗时1200小时！

四色定理的证明概述（每个平面图都是4-顶点可染的） 第一部分：（权转移方法） 证明每个平面图都含有若干种构型中的其中一个！ 此部分使用的是理论性的数学证明！ 第二部分：（可约性验证） 假设四色定理不正确，则其必然存在反例，即一个不是4-顶点可 染的平面图G，接下来证明图G不含有上述提及的任何一个构型！ 此部分使用的是计算机证明，耗时1200小时！

权转移方法：一个例子 每个最小度为5的平面简单图，都含有以下两种构型之一： (1)一条边uv,其中d(u=5,d(W=5; (2)一条边uv,其中d(u)=5,d()=6. 证明：假设该命题的结论不对！即存在一个最小度为5的平面简单图G, 其不含有上述两种构型。 由于G的最小度为5，因此G必定含有一条边uv,其中d(u)=5。 由于G不含有构型(1)与(2)，d()≥7

权转移方法：一个例子 每个最小度为5的平面简单图，都含有以下两种构型之一： (1) 一条边uv，其中d(u)=5，d(v)=5; (2) 一条边uv，其中d(u)=5，d(v)=6. 证明：假设该命题的结论不对！即存在一个最小度为5的平面简单图G， 其不含有上述两种构型。 由于Ｇ的最小度为５，因此Ｇ必定含有一条边uv，其中d(u)=5。 由于G不含有构型(1)与(2), d(v)≥7

根据欧拉公式，有 ∑(d(m-6)+∑(2d(f)-6)=-12 vEV(G) f∈F(G) 从而给图G的每一个点V,定义权值 c()=d()-6 给图G的每一个面f,定义权值 c(⑤=2d(f⑤-6 于是图中所有点与面的权值总和为-12

根据欧拉公式，有          ( ) ( ) ( ( ) 6) (2 ( ) 6) 12 v V G f F G d v d f 从而给图G的每一个点v，定义权值 c(v)=d(v)-６ 给图G的每一个面f，定义权值 c(f)=2d(f)-６ 于是图中所有点与面的权值总和为-12

由于图G是平面简单图，其不含有【环】与【重边】，因此G中 每个面的度数至少为3· 接下来，我们定义权转移规则，使得图中每个点或者面的权值可 以向其他点或者面进行转移（传递)。 对于图中的点V,其初始的权值为c(),在进行权转移后，其最终 的权值设为c(V) 对于图中的点f,其初始的权值为c(⑤，在进行权转移后，其最终 的权值设为c*(f)

由于图Ｇ是平面简单图，其不含有【环】与【重边】，因此Ｇ中 每个面的度数至少为３！ 接下来，我们定义权转移规则，使得图中每个点或者面的权值可 以向其他点或者面进行转移（传递）。 对于图中的点v，其初始的权值为c(v)，在进行权转移后，其最终 的权值设为c *(v) 对于图中的点f，其初始的权值为c(f)，在进行权转移后，其最终 的权值设为c *(f)

由于权值仅仅在所有的点与所有的面所构成的一个“集体”的“内 部成员”之间进行转移，权值总和必定保持不变，即 ∑c()=∑c()=-12<0 vEV(G)UF(G) vEV(G)UF(G)

由于权值仅仅在所有的点与所有的面所构成的一个“集体”的“内 部成员”之间进行转移，权值总和必定保持不变，即 ( ) ( ) 12 0 ( ) ( ) ( ) ( ) *       vV G F G vV G F G c v c v

本例的权转移规则定义如下： R1.每个度数为5的点从它的每个邻点得到权值1/5 R2.每个度数至少为4的面向其关联的每个点转移权值1/2 下面计算图中每个点和面的最终的权值！ 5-度点：其有5个邻点，它从这5个邻点分别得到1/5，因此 c*(W)2c()+5*1/5=5-6+1=0 6-度点：其与5-度点不相邻，因此其不向外转移权值，因此 c*(W)≥c()）=6-6=0

本例的权转移规则定义如下： R1. 每个度数为5的点从它的每个邻点得到权值1/5 R2. 每个度数至少为4的面向其关联的每个点转移权值1/2 下面计算图中每个点和面的最终的权值！ ------------------------------------------------------------------- 5-度点：其有5个邻点，它从这5个邻点分别得到1/5，因此 c*(v)≥c(v)+5*1/5=5-6+1=0 6-度点：其与5-度点不相邻，因此其不向外转移权值，因此 c*(v)≥c(v)=6-6=0

本例的权转移规则定义如下： R1.每个度数为5的点从它的每个邻点得到权值1/5 R2.每个度数至少为4的面向其关联的每个点转移权值1/2 下面计算图中每个点和面的最终的权值！ k-度点(k≥8)：其可能是5-度点的邻点，并且它最多可以是k个5- 度点的邻点，因此根据权转移规则，有 c*()≥c()-k*1/5=k-6-k*1/5≥8-6-1.6>0 7-度点（如果它最多是5个5-度点的邻点) c*(N)2c(W)-5*1/5=7-6-5*1/5=0

本例的权转移规则定义如下： R1. 每个度数为5的点从它的每个邻点得到权值1/5 R2. 每个度数至少为4的面向其关联的每个点转移权值1/2 下面计算图中每个点和面的最终的权值！ ------------------------------------------------------------------- k-度点（k≥8）：其可能是5-度点的邻点，并且它最多可以是k个5- ~~~~~~~~~~..度点的邻点，因此根据权转移规则，有 c*(v)≥c(v)-k*1/5=k-6-k*1/5≥8-6-1.6>0 7-度点（如果它最多是5个5-度点的邻点） c*(v)≥c(v)-5*1/5=7-6-5*1/5=0