《离散数学》PPT课件

《《离散数学》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、图定义一个图是一个三元组,简记为G＝。7-1图的基本概念其中：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中的结点对（有序偶或无序偶）与之对应。例1离散数学图的术语图的术语若边e与结点无序偶(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；若边e与结点有偶相对应，则称

2、边e为有向边(或弧)，记为e＝，这时称u是边e的始点(或弧尾).v是边e的终点(或弧头)，统称为e的端点；在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；2离散数学续：续：关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为自回路(或环)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；含有n个结点、m条边的图称为(n，m)图；3离散数学续：续：每条边都是无向边的图称为无向图；每条

3、边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边，在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边，两结点vi，vj间相互平行的边的条数称为边(vi，vj)或的重数；含有平行边的图称为多重图。非多重图称为线图；无自回路的线图称为简单图。4离散数学(a)例：(b)(c)(d)例：5离散数学(e)(f)例：例：(g)6离散数学二、度数定义在无向图G＝中，与结点v(vV)关联的边的条

4、数，称为该结点的度数，记为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)为偶数，则称此结点为偶度数结点。7离

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；例：8离散数学定理定理1.在图G＝中，则所有结点的度数的总和等于边数的两倍，即：在有向图G＝中，则所有结点的出度之和等于所有结点的入度之和，即：3.定理在所有图中，度数为奇数的结点个数为偶数.9离散数学定

6、理。证明设V1＝{v

7、vV且deg(v)＝奇数}，V2＝{v

8、vV且deg(v)＝偶数}。显然，V1∩V2＝Φ，且V1∪V2＝V，于是有：由于上式中的2m和偶度数结点度数之和均为偶数，因而也为偶数。于是

9、V1

10、为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。■10离散数学三、完全图三、完全图定义在图G＝中，若所有结点的度数均有相同度数d，则称此图为d次正则图。定义一个(n，m)(n2)的简单无向图，若它为n-1次正则图，则称该(n，m)图为无向简单完全图，简称完全图,记为Kn。有向完

11、全图定理设无向完全图G有n个顶点，则G有条边。11离散数学四、子图和补图定义设有图G＝和图G1＝，若G和G1满足：若V1V，E1E，则称G1是G的子图，记为G1G；若G1G，且G1G(即V1V或E1E)，则称G1是G的真子图，记为G1G；定义若V1＝V，E1E，则称G1是G的生成子图，记为G1G；定义设有图G＝和图G2＝，若V2V，V2Φ，以V2为结点集，以两个端点均在V2中的边的全体为边集的G的子图称为V2导出的子图，简称G的导出子图。四、子图和补图12离散数学例：例

12、：它的真子图G’和生成子图G’’。13离散数学四、子图和补图定义设G＝为具有n个结点的简单图,从完全图Kn中删去G中的所有的边而得到的图称为G的补图(或G的补)，记为。