河北工业大学：《离散数学》课程PPT教学课件（讲稿）第七章 图

7-1图的基本概 定义一个图是一个三元组,简记为 G=, 其中 1)V={v1,v2,v3,…,vn}是一个非空集合,v1(i= 2,3,,n)称为结点,简称点,V为结点集; 2)E={e1,e2,e3,…,en}是一个有限的集合,e;(i 1,2,3,,m)称为边,E为边集,E中的每个元素都有V 中的结点对(有序偶或无序偶)与之对应 Guoyongfang.2006@yahoo.com.cn

Guoyongfang.2006@yahoo.com.cn 一、图 定义一个图是一个三元组,简记为 G＝， 7-1 图的基本概念 其中： 1) V＝{v1,v2,v3,…,vn}是一个非空集合,vi(i＝ 1,2,3,…,n)称为结点,简称点,V为结点集； 2) E＝{e1,e2,e3,…,em}是一个有限的集合，ei(i＝ 1,2,3,…,m)称为边,E为边集，E中的每个元素都有V 中的结点对（有序偶或无序偶）与之对应

图的术语 若边e与结点无序偶(u,v)相对应,则称边e为无向 边,记为e=(u,v),这时称u,v是边e的两个端点; 2)若边e与结点有偶u,v>相对应,则称边e为有向边 (或弧),记为e=,这时称u是边e的始点(或 弧尾).v是边e的终点(或弧头),统称为e的端点 3)在一个图中,关联结点v1和v的边e,无论是有向的 还是无向的,均称边e与结点v和v;相关联,而v1和 ⅴ;称为邻接点,否则称为不邻接的; Guoyongfang.2006@yahoo.com.cn

Guoyongfang.2006@yahoo.com.cn 图的术语 ▪ 若边e与结点无序偶(u，v)相对应，则称边e为无向 边,记为e＝(u，v)，这时称u，v是边e的两个端点； 2) 若边e与结点有偶相对应，则称边e为有向边 (或弧)，记为e＝，这时称u是边e的始点(或 弧尾).v是边e的终点(或弧头)，统称为e的端点； 3) 在一个图中，关联结点vi和vj的边e，无论是有向的 还是无向的，均称边e与结点vI和vj相关联，而vi和 vj称为邻接点，否则称为不邻接的；

续: 4)关联于同一个结点的两条边称为邻接边; 5)图中关联同一个结点的边称为自回路(或环); 6)图中不与任何结点相邻接的结点称为孤立结点 7)仅由孤立结点组成的图称为零图; 8)仅含一个结点的零图称为平凡图 9)含有n个结点、m条边的图称为(n,m)图; Guoyongfang.2006@yahoo.com.cn

Guoyongfang.2006@yahoo.com.cn 续： 续： 4) 关联于同一个结点的两条边称为邻接边； 5) 图中关联同一个结点的边称为自回路(或环)； 6) 图中不与任何结点相邻接的结点称为孤立结点； 7) 仅由孤立结点组成的图称为零图； 8) 仅含一个结点的零图称为平凡图； 9) 含有n个结点、m条边的图称为(n，m)图；

续: 续: 每条边都是无向边的图称为无向图; 每条边都是有向边的图称为有向图; 有些边是无向边,而另一些是有向边的图称为混合图。 在有向图中,两个结点间(包括结点自身间)若有同始点和 同终点的几条边,则这几条边称为平行边,在无向图中, 两个结点间(包括结点自身间)若有几条边,则这几条边称 为平行边,两结点v,v间相互平行的边的条数称为边(v v;)或的重数; Guoyongfang.2006@yahoo.com.cn

Guoyongfang.2006@yahoo.com.cn 续： 续： ▪ 每条边都是无向边的图称为无向图； ▪ 每条边都是有向边的图称为有向图； ▪ 有些边是无向边，而另一些是有向边的图称为混合图。 ▪ 在有向图中，两个结点间(包括结点自身间)若有同始点和 同终点的几条边，则这几条边称为平行边，在无向图中， 两个结点间(包括结点自身间)若有几条边，则这几条边称 为平行边，两结点vi，vj间相互平行的边的条数称为边(vi， vj)或的重数；

续: 14)含有平行边的图称为多重图。非多重图称为线 图;无环和平行边的图称为简单图。 Guoyongfang.2006@yahoo.com.cn

Guoyongfang.2006@yahoo.com.cn 续： 14)含有平行边的图称为多重图。非多重图称为线 图；无环和平行边的图称为简单图

例: b 2 Guoyongfang.2006@yahoo.com.cn

Guoyongfang.2006@yahoo.com.cn (a) 例： (b) (c) (d) 例：

度数 、度数 义在无向图G=中,与结点v(v∈V)关联的边的条数, 称为该结点的度数,记为deg(v) 定义在有向图G=中,以结点v(v∈V)为始点引出的边 的条数,称为该结点的引出度数,简称出度,记为deg+(v); 以结点v(v∈V)为终点引入的边的条数,称为该结点的引 入度数,简称入度,记为deg(v);而结点的出度和入度之 和称为该结点的度数,记为deg(v),即deg(v)= deg*(v)+deg"(v) 6(G最小度,△(O最大度 定义在图G=中,对任意结点veV,若度数deg(v)为奇 数,则称此结点为奇度数结点,若度数deg(v)为偶数,则 称此结点为偶度数结点。 Guoyongfang.2006@yahoo.com.cn

Guoyongfang.2006@yahoo.com.cn 二、度数 定义 在无向图G＝中，与结点v(vV)关联的边的条数， 称为该结点的度数，记为deg(v)； 二、度数 定义 在有向图G＝中，以结点v(vV)为始点引出的边 的条数，称为该结点的引出度数,简称出度,记为deg+(v)； 以结点v(vV)为终点引入的边的条数，称为该结点的引 入度数，简称入度,记为deg-(v)；而结点的出度和入度之 和 称 为 该 结 点 的 度 数 ， 记 为 deg(v) ， 即 deg(v) ＝ deg+(v)+deg-(v)； δ(G)最小度，Δ(G)最大度 定义 在图G＝中，对任意结点vV，若度数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=中,则所有结点的度数的总和等 于边数的两倍,即:∑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＝中，则所有结点的度数的总和等 于边数的两倍，即： deg(v) 2m； v V  =  deg (v) deg (v) m， v V v V  =  =  −  + 2. 在有向图G＝中，则所有结点的出度之和等于所 有结点的入度之和，所有结点的度数的总和等于边数 的两倍，即： deg(v) deg (v) deg (v) 2m。 v V v V v V  = +  =  −  + 

定理 定理在图G=中,其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＝{v1,v2,v3,…,vn}，E＝ {e1，e2，……，em}，度数为奇数的结点个数为偶数。 证明 V1＝{v|vV且deg(v)＝奇数}，V2＝{v|vV且 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) 都为奇数)，即奇度数的结点个数为偶数。■