原创力文档- 1、本文档共12页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
握手定理
度：在图G=V,E中，与结点v(v?V)关联的边的数目(每个环计算两次)，记作：d(v)。在有向图D=V,E中，以结点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?V}1、结点的度
在图G=V,E中，度数为零的结点称为孤立点；度数为1的结点称为悬挂点；与悬挂点相关联的边称为悬挂边；度数为k的结点称为k度点；度数为奇/偶数的结点称为奇/偶度点；各结点的度数都相同的图为正则图；各结点的度均为k的图为k次正则图。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)=0d-(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是悬挂边。例：v1v4v3v2e1e2e3e4e5e8e6e7v5图D1、结点的度
图论基本定理：在任何图G=V,E中，结点度数的总和等于边数的两倍。(握手定理)图中每条边都有两个结点(环的两个结点相同)，所以一条边就会为两个结点各增加1度，共2度，因而得到握手定理。2、握手定理
例：已知图G中有10条边，4个3度结点，其余结点的度数均小于等于2，问G中至少有多少个结点？答：图G边数为10，由握手定理知，G中各结点度数之和为20，4个3度的结点共占12度，还剩下8度，若其余的结点都是2度，则需要4个结点来占用8度，所以图G至少有8个结点。2、握手定理
握手定理的推论：任何图中，奇度点的个数一定为偶数。证明：设图G=V,E，V1={v|v∈V且d(v)为奇数}，V2={v|v∈V且d(v)为偶数}。显然，V1∩V2=?，且V1∪V2=V，于是式中2|E|和(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数，即奇度点的个数为偶数。2、握手定理
握手定理的推论：有向图D=V,E中，各结点的出度之和等于各结点的入度之和等于边数。度数序列：设图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、握手定理
文档评论（0）