度 定义144 设无向图G=<VE>,Ⅴv∈V,称作为边的端点次数之和为v 的度数,简称度,记为dM∽。在有向图D=<VE>中,对于VV ∈∨,称v作为边的始点的次数之和为V的出度,记作d-); 无恐作为边的终点的次数之和为的入度,记作;称的 入度之和为v的度数,用d()表示 最大度△(G=maxa(v)v∈(G)} 最小度()=min{d(v)v∈(G)} 有向图中最大度△(G)=max{d(v)lve(G 最小度O(G)=mn{d(v)w∈V(G)} 最大出度△(G)=max{d(v)|we(G)} 最小出度δ(G)=min{d(v)|v∈V(G)} 最大入度Δ(G)=max{d(v)lv∈(G} 最小入度δ(G)=min{d(v)v∈(G)} 东南大学计算机科学与工程学院 同的出学 图论
定义14.4 设无向图G=<V,E>， v V，称v作为边的端点次数之和为v 的度数，简称度，记为d(v)。在有向图D=<V,E>中，对于v V，称v作为边的始点的次数之和为v的出度，记作d－(v) ； 以v点作为边的终点的次数之和为v的入度，记作d+(v)；称v的 出度与入度之和为v的度数，用d (v)表示。 ( ) min{ ( ) | ( )} ( ) max{ ( ) | ( )} G d v v V G G d v v V G = = 最大度 最小度 ( ) min{ ( ) | ( )} ( ) max{ ( ) | ( )} ( ) min{ ( ) | ( )} ( ) max{ ( ) | ( )} ( ) min{ ( ) | ( )} ( ) max{ ( ) | ( )} G d v v V G G d v v V G G d v v V G G d v v V G G d v v V G G d v v V G = = = = = = + + + + − − − − 最大度 最大出度 最小出度 最小度 最大入度 最小入度
例子 d=3 d=3 △(G)=6 d=3 6(G)=2 d=6 d=2 d=2 d=3 d=3 d=3 东南大学计算机科学与工程学院 同的出学 图论
( ) 2 ( ) 6 = = G G
握手定理 定理141在任何无向图中,所有顶点的度数之和等于边数的2倍。 在任何有向图中,所有顶点的度数之和等于边数的2倍。所 有顶点的入度之和等于所有顶点的出度之和,都等于边数。 d(a)=4,d(b)=3 d(c)=4,d(d)=3 边数m=7,2m=14 d Σd=3+4+3+4=14 东南大学计算机科学与工程学院 同的出学 图论
定理14.1 在任何无向图中，所有顶点的度数之和等于边数的2倍。 定理14.2 在任何有向图中，所有顶点的度数之和等于边数的2倍。所 有顶点的入度之和等于所有顶点的出度之和，都等于边数。 d（a）＝4，d（b）＝3， d（c）＝4，d（d）＝3 边数 m＝7，2m＝14 Σd ＝3+4+3+4＝14
例子 若图G有n个顶点,(n+1)条边,则G中至少有一个顶点的度数大于 等于3 季 的起 证明:设G中有n个顶点分别为V1,V 则由握手定理有Σd(v)=2(n+1 假设图中不存在度数大于等于3的节点,则根据顶点数量t 可知,图中度数d(G)为2n<2(n+1) 因此,图中存在度数大于等于3的顶点。 每个顶点的度数都是2时,n个顶点对应n条边 东南大学计算机科学与工程学院 同的出学 图论
证明：设Ｇ中有n个顶点分别为v1 ,v2 ,…,vn， 则由握手定理有 Σd（vi）＝２（n+1）; 假设图中不存在度数大于等于3的节点，则根据顶点数量n 可知，图中度数d(G)为2n<2（n+1）; 因此，图中存在度数大于等于3的顶点。 若图Ｇ有n个顶点,（n+1）条边，则Ｇ中至少有一个顶点的度数大于 等于３
推论 推论:在任何图(无向的或有向的)中,度数为奇数的顶点必定有 偶数个。 设图G=<V,E>,令 V1={v|v∈VAd(v)为奇数} 将顶点分成奇数度和偶数 度两个集合分开考虑 V2={|v∈V∧d()为偶数} 图的度如何表示 则有 ,∪V=F 2 结合握手定理一一图的度 V∩V2=p 必是偶数 根据握手定理有图的边数m和顶点的度满足 2m=∑(v)=∑(v)+∑(v) 表达式的左侧2m为偶数,表达式右侧第二项为偶数,因此表达式右侧第一项同 样为偶数。由于表达式右侧第一项中每一个d)均为奇数,可见|V1为偶数。 东南大学计算机科学与工程学院 同的出学 图论
推论：在任何图（无向的或有向的）中，度数为奇数的顶点必定有 偶数个。 设图 G = <V， E>，令 { | ( ) } { | ( ) } 2 1 为偶数 为奇数 V v v V d v V v v V d v = = 则有 = = 1 2 1 2 V V V V V 根据握手定理有图的边数m和顶点的度满足 = = + v V v V v V m d v d v d v 1 2 2 ( ) ( ) ( ) 表达式的左侧2m为偶数，表达式右侧第二项为偶数，因此表达式右侧第一项同 样为偶数。由于表达式右侧第一项中每一个d(v)均为奇数，可见|V1|为偶数