离散数学22_第8章图__握手定理

在图这一章，  要识记的限定、知识点很多

一  握手定理

图G = (V,  E) 为无向图或有向图，  G有n个结点，  e条边，  则所有结点的度数之和等于2倍e.

 

推论：  任何图(无向或有向)，  度数为奇数的结点个数为偶数。

这个推论很重要， 经常用到。

 

二. 光说不练假把式， 看几个例题

例1：  图G中结点数n与边数m  相等，  2度与3度结点各2个，  其余结点均为悬挂结点，  求图G的边数。

解：  所谓悬挂结点，是指只有一条边连结的 结点。

       2x2 + 3x2 + (n-4)   = 2m

     又因为根据题意，结点数是等于边数，   n = m

  联立两方程，可解得，m=6.

所以, 图G有6条边。

例2：  无向图G有 8条边，  1个1度结点，  2个2度结点，  1个5度结点，  其余结点数均为3，  求3度结点个数。

解：  根据握手定理，  结点数 = 2倍的边数

         2x8 = 1 + 2x2 + 1x5 + a x 3

解得 a = 2

所以 3度结点有2个。

例3：  自然数序列 (3,3, 2, 2, 1) 和 (4, 2 ,2, 1, 1)能作为图的结点的度数序列吗？ 

解：根据推论，  度数为奇数的结点个数为偶数