离散数学图论课件.ppt

离散数学图论课件1现在学习的是第1页，共22页定义定义 一个一个图图是一个三元组是一个三元组,简记为简记为G，其，其中：中：Vv1,v2,v3,vn是一个非空集合是一个非空集合,vi(i1,2,3,n)称为称为结点结点,简称简称点点,V为为结点集结点集；2)Ee1,e2,e3,em是一个有限集，是一个有限集，ei(i1,2,3,m)称为称为边边,E为为边边集集，E中的每个元素都有中的每个元素都有V中的结点对（有序偶或无序偶）与之对中的结点对（有序偶或无序偶）与之对应。应。一、图的术语一、图的术语2现在学习的是第2页，共22页图的术语图的术语若边若边e与结点无序偶与结点无序偶(u，v)相对应，则称边相对应，则称边e为为无向边无向边,记为记为e(u，v)，这时称，这时称u，v是边是边e的两个的两个端点端点；若边若边e与结点有序偶与结点有序偶相对应，则称边相对应，则称边e为为有向边有向边(或或弧弧)，记，记为为e，这时称，这时称u是边是边e的的始点始点(或或弧尾弧尾)，v是边是边e的的终点终点(或或弧头弧头)，统称为，统称为e的的端点端点；在一个图中，关联结点在一个图中，关联结点vi和和vj的边的边e，无论是有向的还是无向的，无论是有向的还是无向的，均称边均称边e与结点与结点vi和和vj相关联相关联，而，而vi和和vj称为称为邻接点邻接点，否则称为，否则称为不邻不邻接的接的；关联于同一个结点的两条边称为关联于同一个结点的两条边称为邻接边邻接边；图中关联同一个结点的边称为图中关联同一个结点的边称为自回路自回路(或或环环)；图中不与任何结点相邻接的结点称为图中不与任何结点相邻接的结点称为孤立结点孤立结点；仅由孤立结点组成的图称为仅由孤立结点组成的图称为零图零图；仅含一个结点的零图称为仅含一个结点的零图称为平凡图平凡图；3现在学习的是第3页，共22页续：续：含有含有n个结点、个结点、m条边的图称为条边的图称为(n，m)图图；每条边都是无向边的图称为每条边都是无向边的图称为无向图无向图；每条边都是有向边的图称为每条边都是有向边的图称为有向图有向图；有些边是无向边，而另一些是有向边的图称为有些边是无向边，而另一些是有向边的图称为混合图混合图。在有向图中，两个结点间在有向图中，两个结点间(包括结点自身间包括结点自身间)若有同始点和同终点的几若有同始点和同终点的几条边，则这几条边称为条边，则这几条边称为平行边平行边，在无向图中，两个结点间，在无向图中，两个结点间(包括结包括结点自身间点自身间)若有几条边，则这几条边称为若有几条边，则这几条边称为平行边平行边，两结点，两结点vi，vj间间相互平行的边的条数称为边相互平行的边的条数称为边(vi，vj)或或的的重数重数；含有平行边的图称为含有平行边的图称为多重图多重图。非多重图称为。非多重图称为线图线图；无自回路的线图称；无自回路的线图称为为简单图简单图。赋权图赋权图G是一个三元组是一个三元组或四元组或四元组，其中，其中，V是结点是结点集合，集合，E是边的集合，是边的集合，g是从是从E到非负实数集合的函数。到非负实数集合的函数。4现在学习的是第4页，共22页(a)例：(b)(c)(c)(d)(d)例：5现在学习的是第5页，共22页(e)(f)(f)(g)(g)(h)(h)例：例：6现在学习的是第6页，共22页(i)(j)(j)(k)(k)(l)(l)例：例：7现在学习的是第7页，共22页(m)(n(n)(o(o)(p(p)例：例：8现在学习的是第8页，共22页定义定义 在无向图在无向图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)为偶数，则称此结点为为偶数，则称此结点为偶偶度数结点度数结点。二、度数9现在学习的是第9页，共22页例：例：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，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；例：10现在学习的是第10页，共22页定理定理1.在无向图在无向图G中，所有结点的度数的总和等于边数中，所有结点的度数的总和等于边数的两倍，即：的两倍，即：；m2)vdeg(Vv ，m)v(deg)v(degVvVv 在有向图在有向图G中，所有结点的出度之和等于所有结中，所有结点的出度之和等于所有结点的入度之和，所有结点的度数的总和等于边数的两倍，即点的入度之和，所有结点的度数的总和等于边数的两倍，即：。m2)v(deg)v(deg)vdeg(VvVvVv 11现在学习的是第11页，共22页定理定理定理定理 在图在图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)都为奇数都为奇数)，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。12现在学习的是第12页，共22页三、完全图定 义定 义 在 图在 图 G 中，若 所 有 结 点 的 度 数 均 有 相中，若 所 有 结 点 的 度 数 均 有 相同度数同度数d，则称此图为，则称此图为d次正则图。次正则图。定 义定 义 一 个一 个(n，m)(n 2)的 简 单 无 向 图，若 它的 简 单 无 向 图，若 它为为n-1次正则图，则称该次正则图，则称该(n，m)图为图为无向简单无向简单完全图完全图，简称，简称完全图完全图,记为记为Kn。有向完全图有向完全图定理定理 设无向完全图设无向完全图G有有n个顶点，则个顶点，则G有有n(n-1)/2条边。条边。13现在学习的是第13页，共22页例：例：例：如图如图(a)、(b)、(c)、(d)所示，它们分别是无向的简单完所示，它们分别是无向的简单完全图全图K3，K4，K5和有向的简单完全图和有向的简单完全图K3。14现在学习的是第14页，共22页定义定义 设有图设有图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的的生成子图生成子图；定义定义 若若V2 V，V2，以，以V2为结点集，以两个端点均在为结点集，以两个端点均在V2中的边的中的边的全体全体为边集的为边集的G的子图称为的子图称为V2导出的子图导出的子图，简，简称称G的导出子图的导出子图。四、子图15现在学习的是第15页，共22页例：例：例：在下图中，给出了图在下图中，给出了图G以及它的真子图以及它的真子图G和生成子图和生成子图G。G是结点集是结点集v1，v2，v4，v5，v6的导出子图。的导出子图。16现在学习的是第16页，共22页定义定义 设设G为具有为具有n个结点的简单图个结点的简单图,从完全图从完全图Kn中删去中删去G中的所有的边而得到的图称为中的所有的边而得到的图称为G的的补图补图(或或G的的补补)，记为，记为 。定义定义 是图，是图，是的是的子图，子图，”，”是是”中边所关联的所中边所关联的所有顶点集合，则有顶点集合，则”称为称为关于关于的的相对补图相对补图。关于完全图的子图的补图称为此子图的关于完全图的子图的补图称为此子图的绝对补图绝对补图。五、补图五、补图G17现在学习的是第17页，共22页例：例：例：在下图在下图 (a)(a)、(b)(b)、(c)(c)、(d)(d)中，中，(a)(a)与与(b)(b)是互是互为补图；为补图；(c)(c)和和(d)(d)是互为补图。是互为补图。18现在学习的是第18页，共22页六、图的同构例例:如下图所示，图如下图所示，图(a)(a)、图、图(b)(b)、图、图(c)(c)和图和图(d)(d)所表示所表示的图形实际上都是一样的。的图形实际上都是一样的。19现在学习的是第19页，共22页定义定义定义定义 设有图设有图G和图和图G1,如果存在双射函数如果存在双射函数g:VV1,使得对于任意的边使得对于任意的边e(vi,vj)E(或或 E)当且仅当当且仅当e1(g(vi),g(vj)E1(或或 E1)则称则称G和和G1同构同构，记为，记为G G1。同构的充要条件：同构的充要条件：两个图的结点和边分别存在一一对应，且保持两个图的结点和边分别存在一一对应，且保持关联关系。关联关系。20现在学习的是第20页，共22页例：例：例：如图如图(a)、(b)所示的两个图所示的两个图G和和G1，证明，证明G G1。解解：定义函数：定义函数g:VV1，满足，满足g(vi)vi(i1，2，3，4，5)，可以验，可以验证证g是一个满足定义的双射，所以是一个满足定义的双射，所以G G1。21现在学习的是第21页，共22页必要条件两个图同构的必要条件：结点数目相同；边数相同；度数相同的结点数相同。注意注意：这三个条件并不是充分条件。例如下面两个图满足这：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。三个条件，但它们不同构。22现在学习的是第22页，共22页