离散数学图论课件1第1页，共22页，星期日，2025年，2月5日
定义一个图是一个三元组V(G),E(G),φG,简记为G＝V,E，其中：V＝{v1,v2,v3,…,vn}是一个非空集合,vi(i＝1,2,3,…,n)称为结点,简称点,V为结点集；E＝{e1,e2,e3,…,em}是一个有限集，ei(i＝1,2,3,…,m)称为边,E为边集，E中的每个元素都有V中的结点对（有序偶或无序偶）与之对应。一、图的术语2第2页，共22页，星期日，2025年，2月5日
图的术语若边e与结点无序偶(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；若边e与结点有序偶u，v相对应，则称边e为有向边(或弧)，记为e＝u，v，这时称u是边e的始点(或弧尾)，v是边e的终点(或弧头)，统称为e的端点；在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vi和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为自回路(或环)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；3第3页，共22页，星期日，2025年，2月5日
续：含有n个结点、m条边的图称为(n，m)图；每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边，在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边，两结点vi，vj间相互平行的边的条数称为边(vi，vj)或vi，vj的重数；含有平行边的图称为多重图。非多重图称为线图；无自回路的线图称为简单图。赋权图G是一个三元组V,E,g或四元组V,E,f,g，其中，V是结点集合，E是边的集合，g是从E到非负实数集合的函数。4第4页，共22页，星期日，2025年，2月5日
(a)例：(b)(c)(d)例：5第5页，共22页，星期日，2025年，2月5日
(e)(f)(g)(h)例：例：6第6页，共22页，星期日，2025年，2月5日
(i)(j)(k)(l)例：例：7第7页，共22页，星期日，2025年，2月5日
(m)(n)(o)(p)例：例：8第8页，共22页，星期日，2025年，2月5日
定义在无向图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)；δ(G)最小度，Δ(G)最大度定义在图G＝V，E中，对任意结点v?V，若度数deg(v)为奇数，则称此结点为奇度数结点，若度数deg(v)为偶数，则称此结点为偶度数结点。二、度数9第9页，共22页，星期日，2025年，2月5日
例：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；例：10第10页，共22页，星期日，2025年，2月5日
定理1.在无向图G＝V，E中，所有结点的度数的总和等于边数的两倍，即：在有向图G＝V，E中，所有结点的出度之和等于所有结点的入度之和，所有结点的度数的总和等于边数的两倍，即：11第11页，共22页，星期日，2025年，2月5日
定理定理在图G＝V，E中，其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，于是有：由于上式中的2m和偶度数结点度数之和均为偶数，因而奇数的结点个数也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。12第12页，共22页，星期日，2025年，2月5日
三、完全图定义在图G＝V，E中，若所有结点的度数均有相
同度数d，则称此图为d次正则图。定义一个(n，m)(n?2)的简单无向图，若它
为n-1次正则图，则称该(n，m)图为无向简单
完全图，简