题目

理解并叙述图论的握手定理

提问时间：2021-03-13

答案

握手定理：有n个人握手,握手次数的总和S,必有S≤ 2(n+1).顶点的度数与握手定理 -------------------------------------------------------------------------------- 1．顶点的度数 定义14.4 设G=为一无向图,v∈V,称v作为边的端点次数之和为v的度数,简称为度,记做 dG(v),在不发生混淆时,简记为d(v).设D=为有向图,v∈V,称v作为边的始点次数之和为v的出度,记做(v),简记作d+(v).称v作为边的终点次数之和为v的入度,记做(v),简记作d-(v),称d+(v)+d-(v)为v的度数,记做d(v).-------------------------------------------------------------------------------- 2．握手定理 定理14.1(握手定理) 设G=为任意无向图,V={v1,v2,…,vn},|E|=m,则 度数和=2m 证 G中每条边(包括环)均有两个端点,所以在计算G中各顶点度数之和时,每条边均提供2度,当然,m条边,共提供2m度.定理14.2(握手定理) 设D=为任意有向图,V={v1,v2,…,vn},|E|=m,则 度数和=2m,且出度=入度=m.本定理的证明类似于定理14.1 握手定理的推论 任何图(无向的或有向的)中,奇度顶点的个数是偶数.证 设G=为任意一图,令 V1={v|v∈V∧d(v)为奇数} V2={v|v∈V∧d(v)为偶数} 则V1∪V2=V,V1∩V2=,由握手定理可知 2m==+ 由于2m,均为偶数,所以为偶数,但因V1中顶点数为奇数,所以|V1|必为偶数.握手定理也称为图论的基本定理,图中顶点的度数是图论中最为基本的概念之一.