离散数学图论课件.ppt

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

1、图的术语度数完全图子图补图图的同构7-1图的基本概念定义一个图是一个三元组,简记为G＝，其中：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中的结点对（有序偶或无序偶）与之对应。一、图的术语图的术语若边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称为邻接点，否则称为不邻接的；关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为自回路(或环)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；续：含有n个结点、m条边的图称为(n，m)图；每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图

3、；有些边是无向边，而另一些是有向边的图称为混合图。在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边，在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边，两结点vi，vj间相互平行的边的条数称为边(vi，vj)或的重数；含有平行边的图称为多重图。非多重图称为线图；无自回路的线图称为简单图。赋权图G是一个三元组或四元组，其中，V是结点集合，E是边的集合，g是从E到非负实数集合的函数。(a)例：(b)(c)(d)例：(e)(f)(g)(h)例：例

4、：(i)(j)(k)(l)例：例：(m)(n)(o)(p)例：例：定义在无向图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＝中，对任意结点

5、vV，若度数deg(v)为奇数，则称此结点为奇度数结点，若度数deg(v)为偶数，则称此结点为偶度数结点。二、度数例：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＝中，所有结点的度数的总和等于边数的两倍，即：在有向图G＝中，所有结点的出度之

6、和等于所有结点的入度之和，所有结点的度数的总和等于边数的两倍，即：定理定理在图G＝中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度数为奇数的结点个数为偶数。证明设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)都为奇数)，即奇度数的结点个数为偶数。三、完全图定义在图G＝中，若所有结点的度

11、数均有相同度数d，则称此图为d次正则图。定义一个(n，m)(n2)的简单无向图，若它为n-1次正则图，则称该(n，m)图为无向简单完全图，简称完全图,记为Kn。有向完全图定理设无向完全图G有n个顶点，则G有n(n-1)/2条边。例：例：如图(a)、(b)、(c)、(d)所示，它们分别是无向的简单完全图K3，K4，K5和有向的简单完全图K3。定义设有图G＝和图G1＝，若G和G1满足：若V1V，E1E，则称G1是G的子图，记为G1G；若G1G，且G1G(即V1V或E1E)，则称G1是G的真子图，记为G1

12、G；定义若V1＝V，E1E，则称G1是G的生成子图；定义若V2V，V2Φ，以V2为结点集，以两个端点均在V2中的边的全体为边集的G