例: b 2 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn (a) 例： (b) (c) (d) 例：
度数 、度数 义在无向图G=<V,E>中,与结点v(v∈V)关联的边的条数, 称为该结点的度数,记为deg(v) 定义在有向图G=<V,E>中,以结点v(v∈V)为始点引出的边 的条数,称为该结点的引出度数,简称出度,记为deg+(v); 以结点v(v∈V)为终点引入的边的条数,称为该结点的引 入度数,简称入度,记为deg(v);而结点的出度和入度之 和称为该结点的度数,记为deg(v),即deg(v)= deg*(v)+deg"(v) 6(G最小度,△(O最大度 定义在图G=<V,E>中,对任意结点veV,若度数deg(v)为奇 数,则称此结点为奇度数结点,若度数deg(v)为偶数,则 称此结点为偶度数结点。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 二、度数 定义 在无向图G＝<V，E>中，与结点v(vV)关联的边的条数， 称为该结点的度数，记为deg(v)； 二、度数 定义 在有向图G＝<V，E>中，以结点v(vV)为始点引出的边 的条数，称为该结点的引出度数,简称出度,记为deg+(v)； 以结点v(vV)为终点引入的边的条数，称为该结点的引 入度数，简称入度,记为deg-(v)；而结点的出度和入度之 和 称 为 该 结 点 的 度 数 ， 记 为 deg(v) ， 即 deg(v) ＝ deg+(v)+deg-(v)； δ(G)最小度，Δ(G)最大度 定义 在图G＝<V，E>中，对任意结点vV，若度数deg(v)为奇 数，则称此结点为奇度数结点，若度数deg(v)为偶数，则 称此结点为偶度数结点
例 例 deg(v1)=3,deg+(v1)=2,deg(v1)=1; o4 deg(v)=3, degt(v,)=2, deg (v)=1; ⅴ5 deg(v3)=5, deg(v3)=2, deg"(v3)=3; deg(v)=deg*( v4)=deg (V4)=0 deg(v5)=1,deg+(v5)=0,deg(v5)=1 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 例： deg(v1 )＝3，deg+(v1 )＝2，deg-(v1 )＝1； deg(v2 )＝3，deg+(v2 )＝2，deg-(v2 )＝1； deg(v3 )＝5，deg+(v3 )＝2，deg-(v3 )＝3； deg(v4 )＝deg+(v4 )＝deg-(v4 )＝0； deg(v5 )＝1，deg+(v5 )＝0，deg-(v5 )＝1； 例：
定理 定理 1.在无向图G=<V,E>中,则所有结点的度数的总和等 于边数的两倍,即:∑deg()=2m; 2.在有向图G=<,E》中,则所有结点的出度之和等于所 有结点的入度之和,所有结点的度数的总和等于边数 的两倍,即: ∑degt(v)=∑deg(v) ∑deg(v)=∑dgt(v)+∑deg()=2m Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定理 定理 1.在无向图G＝<V，E>中，则所有结点的度数的总和等 于边数的两倍，即： deg(v) 2m； v V = deg (v) deg (v) m， v V v V = = − + 2. 在有向图G＝<V，E>中，则所有结点的出度之和等于所 有结点的入度之和，所有结点的度数的总和等于边数 的两倍，即： deg(v) deg (v) deg (v) 2m。 v V v V v V = + = − +
定理 定理在图G=<V,E>中,其V={v1,V2V3,…,Vn},E= e 2 ,en},度数为奇数的结点个数为偶数 证明设V1={vveV且deg(v)=奇数},V2={vvEⅤ且 deg(v)=偶数}。显然,V1∩V2=①,且V1∪V2=V,于是 有: ∑eg(v)=∑deg)+∑deg(v)=2m v∈V 由于上式中的2m和偶度数结点度数之和均为偶数,因而 也为偶数。于是V1为偶数(因为V1中的结点v之deg(v) 都为奇数),即奇度数的结点个数为偶数 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定理 定理 在图G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝ {e1，e2，……，em}，度数为奇数的结点个数为偶数。 证明 V1＝{v|vV且deg(v)＝奇数}，V2＝{v|vV且 deg(v)＝偶数}。显然，V1∩V2＝Φ，且V1∪V2＝V，于是 有： deg(v) deg(v) deg(v) 2m。 v V v V1 v V2 = + = 由于上式中的2m和偶度数结点度数之和均为偶数，因而 也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v) 都为奇数)，即奇度数的结点个数为偶数。■