(48)--5.4 握手定理离散数学离散数学.ppt

《(48)--5.4 握手定理离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(48)--5.4 握手定理离散数学离散数学.ppt（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、握手定理度：在图G=中，与结点v(v V)关联的边的数目(每个环计算两次)，记作：d(v)。在有向图D=中，以结点v(v V)作为始点的边的数目，称为该结点的出度，记作：d+(v)；以结点v作为终点的边的数目，称为该结点的入度，记作：d(v)。结点v的度：d(v)=d+(v)+d(v)最大度：(G)=max d(v)|v V；最小度：(G)=min d(v)|v V1、结点的度在图 G=中，度数为零的结点称为孤立点；度数为1的结点称为悬挂点；与悬挂点相关联的边称为悬挂边；度数为 k 的结点称为k度点；度数为奇/偶数的结点称为奇/偶度点；各结点的度数都相同的图为正则图；各结点的度均为k的图为k次

2、正则图。1、结点的度例：e1e2e3e4e5e6v1v2v3v5v4v6图Gd(v1)=3，d(v2)=3，d(v3)=4，d(v4)=1，d(v5)=1，d(v6)=0，(G)=4，(G)=0v6是孤立点；v4、v5是悬挂点；e2、e6是悬挂边。1、结点的度d+(v1)=0，d+(v2)=2，d+(v3)=4，d+(v4)=2，d+(v5)=0 d-(v1)=1，d-(v2)=2，d-(v3)=1，d-(v4)=4，d-(v5)=0d(v1)=1，d(v2)=4，d(v3)=5，d(v4)=6，d(v5)=0v5是孤立点；v1是悬挂点；e1是悬挂边。例：v1v4v3v2e1e2e3e4e5e

3、8e6e7v5图D1、结点的度图论基本定理：在任何图G=中，结点度数的总和等于边数的两倍。(握手定理)图中每条边都有两个结点(环的两个结点相同)，所以一条边就会为两个结点各增加 1 度，共 2 度，因而得到握手定理。2、握手定理例：已知图G中有10条边，4个3度结点，其余结点的度数均小于等于2，问G 中至少有多少个结点？答：图G边数为10，由握手定理知，G 中各结点度数之和为20，4个3度的结点共占12度，还剩下8度，若其余的结点都是2度，则需要4个结点来占用8度，所以图G至少有8个结点。2、握手定理握手定理的推论：任何图中，奇度点的个数一定为偶数。证明：设图 G=，V1=v|vV 且 d(v

4、)为奇数，V2=v|vV 且 d(v)为偶数。显 然，V1 V2=，且 V1 V2=V，于是 式中 2|E|和 (偶数之和为偶数)均为偶数，因而 也为偶数。于是|V1|为偶 数，即奇度点 的个数为偶数。2、握手定理握手定理的推论：有向图D=中，各结点的出度之和等于各结点的入度之和等于边数。度数序列：设图G的结点集V=v1,v2,vn，称(d(v1),d(v2),d(vn)为G的度数序列。由握手定理可知，度数序列之和必为偶数。2、握手定理例：(3,3,2,3)，(1,3,3,3)能成为无向图的度数序列吗？能成为无向简单图的度数序列吗？答：(3,3,2,3)中，奇度点个数为3，所以不是无向图的度数序列，也不能成为无向简单图的度数序列。(1,3,3,3)中，奇度点个数为4，所以是无向图的度数序列，且由该序列可知，图中4个结点，且每个结点度数最大为3，(1,3,3,3)能成为无向简单图的度数序列。2、握手定理例：有向简单图的度数序列(3,3,3,3)，它的入度序列能为(1,1,1,1)吗？答：不能，因为该入度序列不能使得入度之和等于出度 之和等于边数。2、握手定理THANKYOU