离散数学图论课件PPT课件

1、1图的术语1) 若边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) 仅含一个结点的零图称

2、为平凡图；第1页/共21页2续：9) 含有n个结点、m条边的图称为(n，m)图；10)每条边都是无向边的图称为无向图；11)每条边都是有向边的图称为有向图；12)有些边是无向边，而另一些是有向边的图称为混合图。13)在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边，在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边，两结点vi，vj间相互平行的边的条数称为边(vi，vj)或的重数；14)含有平行边的图称为多重图。非多重图称为线图；无自回路的线图称为简单图。15)赋权图G是一个三元组或四元组，其中，V是结点集合，E是边的集合，g是从E

3、到非负实数集合的函数。第2页/共21页3 (a)例：(b)(c)(c)(d)(d)例：第3页/共21页4 (e)(f)(f)(g)(g)(h)(h)例：例：第4页/共21页5 (i)(j)(j)(k)(k)(l)(l)例：例：第5页/共21页6 (m)(n)(n)(o)(o)(p)(p)例：例：第6页/共21页7定义 在无向图G中，与结点v(v V)关联的边的条数，称为该结点的度数，记为deg(v)；定义 在有向图G中，以结点v(v V)为始点引出的边的条数，称为该结点的引出度数,简称出度,记为deg+(v)；以结点v(v V)为终点引入的边的条数，称为该结点的引入度数，简称入度,记为deg-

4、(v)；而结点的出度和入度之和称为该结点的度数，记为deg(v)，即deg(v)deg+(v)+deg-(v)；(G)最小度，(G)最大度定义 在图G中，对任意结点v V，若度数deg(v)为奇数，则称此结点为奇度数结点，若度数deg(v)为偶数，则称此结点为偶度数结点。二、度数第7页/共21页8 例： deg(vdeg(v1 1) )3 3，degdeg+ +(v(v1 1) )2 2，degdeg- -(v(v1 1) )1 1； deg(vdeg(v2 2) )3 3，degdeg+ +(v(v2 2) )2 2，degdeg- -(v(v2 2) )1 1； deg(vdeg(v3 3

5、) )5 5，degdeg+ +(v(v3 3) )2 2，degdeg- -(v(v3 3) )3 3； deg(vdeg(v4 4) )degdeg+ +(v(v4 4) )degdeg- -(v(v4 4) )0 0； deg(vdeg(v5 5) )1 1，degdeg+ +(v(v5 5) )0 0，degdeg- -(v(v5 5) )1 1；例：第8页/共21页9定理1.在无向图G中，所有结点的度数的总和等于边数的两倍，即：；m2)vdeg(Vv ，m)v(deg)v(degVvVv 2. 在有向图G中，所有结点的出度之和等于所有结点的入度之和，所有结点的度数的总和等于边数的两倍

6、，即：。m2)v(deg)v(deg)vdeg(VvVvVv 第9页/共21页10定理 定理 在图G中，其Vv1,v2,v3,vn，Ee1，e2，em，度数为奇数的结点个数为偶数。证明设V1v|v V且deg(v)奇数，V2v|v V且deg(v)偶数。显然，V1V2，且V1V2V，于是有：。m2)vdeg()vdeg()vdeg(21VvVvVv 由于上式中的2m和偶度数结点度数之和均为偶数，因而奇数的结点个数也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。第10页/共21页11三、完全图定义 在图G中，若所有结点的度数均有相同度数d，则称

7、此图为d次正则图。定义 一个(n，m)(n 2)的简单无向图，若它为n-1次正则图，则称该(n，m)图为无向简单完全图，简称完全图,记为Kn。有向完全图定理 设无向完全图G有n个顶点，则G有n(n-1)/2条边。第11页/共21页12例：例：如图 (a)、(b)、(c)、(d)所示，它们分别是无向的简单完全图K3，K4，K5和有向的简单完全图K3。第12页/共21页13定义 设有图G和图G1，若G和G1满足：若V1 V，E1 E，则称G1是G的子图，记为G1 G；若G1 G，且G1 G(即V1 V或E1 E)，则称G1是G的真子图，记为G1 G；定义 若V1V，E1 E，则称G1是G的生成子图

8、；定义 若V2 V，V2 ，以V2为结点集，以两个端点均在V2中的边的全体为边集的G的子图称为V2导出的子图，简称G的导出子图。四、子图第13页/共21页14例：例：在下图中，给出了图G以及它的真子图G和生成子图G。G是结点集v1，v2，v4，v5，v6的导出子图。第14页/共21页15定义 设G为具有n个结点的简单图,从完全图Kn中删去G中的所有的边而得到的图称为G的补图(或G的补)，记为 。定义 是图，是的子图，”，” 是”中边所关联的所有顶点集合，则”称为关于的相对补图。关于完全图的子图的补图称为此子图的绝对补图。五、补图G第15页/共21页16例：例：在下图 (a)(a)、(b)(b)

9、、(c)(c)、(d)(d)中，(a)(a)与(b)(b)是互为补图；(c)(c)和(d)(d)是互为补图。第16页/共21页17六、图的同构例: :如下图所示，图(a)(a)、图(b)(b)、图(c)(c)和图(d)(d)所表示的图形实际上都是一样的。第17页/共21页18定义定义 设有图G和图G1,如果存在双射函数g:VV1,使得对于任意的边e(vi,vj) E(或 E)当且仅当e1(g(vi),g(vj) E1(或 E1) 则称G和G1同构，记为G G1。同构的充要条件：两个图的结点和边分别存在一一对应，且保持关联关系。第18页/共21页19例：例：如图(a)、(b)所示的两个图G和G1，证明G G1。解：定义函数g:VV1，满足g(vi)vi(i1，2，3，4，