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