些定义 豪 定义144:在无向图中,任意点其作为边的端点次数 之和称为该点的度数,记为d 在有向图中,对于任何结点v,以v为始点的边的条 数,称为结点v的引出次数或出,记作d(v);以 v点为终点的边的条数称为v的引入折数或入度), 记作d-(y);结点的v的引入次数和引出次数之和称 为v的次数(度数),用d()表示。 由定义可见:度数d(v)=dt(y)+d(v)。 定义:最大度,最小度,最大出度,最大入度,最小 入度,最小出度,悬挂点,悬挂边 17
17 一些定义 定义14.4：在无向图中，任意点其作为边的端点次数 之和称为该点的度数，记为dG(v). 在有向图中，对于任何结点v，以v为始点的边的条 数，称为结点v的引出次数(或出度)，记作d + (v)；以 v点为终点的边的条数称为v的引入次数(或入度)， 记作d－(v)；结点的v的引入次数和引出次数之和称 为v的次数（度数），用d (v)表示。 由定义可见:度数d (v)＝d + (v)＋d－(v)。 定义：最大度，最小度，最大出度，最大入度，最小 入度，最小出度，悬挂点，悬挂边
例1 豪 例 ad(a)=3(引入)+2(引出=5 d(b)=4 d(c)=3 以后为了叙述方便, 我们将具有n个结点 和m条边的图简称为 (n,m)图 d(1)=3 d(2)=3 d(3)=2 18
18 例 1 例： d (a)＝３(引入)+２(引出)=5 d（b）＝４ d（c）＝３ d（1）＝３ d（2）＝３ d（3）＝２ 以后为了叙述方便， 我们将具有n个结点 和m条边的图简称为 （n,m）图
握手定理 定理14.1(握手定理):设G是(n,m)无向图,它的顶 点集合V={v1,V2y,n},于是有 ∑d(v)=2m 证明:∵在无向图中引入一条边,总的次数增2, ∴若有m条边,则总次数为2m (此定理也可推广到有向图和混合图) 定理14.1在有向图中,则为: ∑a(v)=2m,a(v)=∑a(v)=m i=1
19 握手定理 定理14.1（握手定理）：设G是（n, m）无向图，它的顶 点集合Ｖ＝｛v1 ,v2 ,…,vn｝，于是有 1 ( ) 2 n i i d v m = = 1 1 1 ( ) 2 , ( ) ( ) n n n i i i i i i d v m d v d v m + − = = = = = = 证明：∵在无向图中引入一条边，总的次数增２， ∴若有m条边，则总次数为2m。 （此定理也可推广到有向图和混合图） 定理14.1 在有向图中，则为：
例2 豪 d(a)=4, d(b)=3, d(c)=4, d(d)=3 m=7,2m=14=∑d ∑d=3+4+3+4 =14 20
20 例 2 d（a）＝４， d（b）＝３， d（c）＝４， d（d）＝３, m＝７，2m＝１４＝Σd Σd ＝３+４+３+４ ＝１４
例3 豪 例:若图G有n个顶点,(n+1)条边,则G中至 少有一个顶点的度数≥3。 证明:设G中有n个结点分别为v1,w2,…,vn,则 由握手定理: Ed(v1)=2(n+1) 而顶点的平均度数为: d(v;)=2(n+1)/n=2+1/n>2 ∴顶点中至少有一个顶点的度数≥3 21
21 例 3 例：若图Ｇ有n个顶点,（n+1）条边，则Ｇ中至 少有一个顶点的度数≥３。 证明：设Ｇ中有n个结点分别为v1,v2,…,vn，则 由握手定理： Σd（vi）＝２（n+1） 而顶点的平均度数为： d（vi）＝２(n+1)/n=2+1/n>2 ∴顶点中至少有一个顶点的度数≥３