离散数学—图论1216版.ppt
《离散数学—图论1216版.ppt》由会员分享,可在线阅读,更多相关《离散数学—图论1216版.ppt(82页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第8章 图论第8章图论8.1 8.1 图的基本概念图的基本概念 8.2 8.2 路径和回路路径和回路8.8.图的矩阵表示图的矩阵表示8.8.二部图二部图8.5 8.5 平面图平面图8.68.6 树树8.78.7 有向树有向树8.8 8.8 运输网络运输网络问题是要从这四块陆问题是要从这四块陆地中任何一块开始,地中任何一块开始,通过每一座桥正好一通过每一座桥正好一次,再回到起点。次,再回到起点。欧拉在欧拉在17361736年解决了年解决了这个问题这个问题 。判定法则:如果通奇数座桥的地方不止两个,那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥,则可从其中任何一地出发找到所要求的路线。若
2、没有一个地 方通奇数座桥,则从任何一地出发,所求的路线都能实现 第8章 图论定义定义定义定义8.118.118.118.11 一个一个图图图图G G是一个三重组是一个三重组V V(G G),),E E(G G),),G G,其中其中V V(G G)是一个非空的是一个非空的结点结点结点结点(或叫顶点或叫顶点)集合集合,E E(G G)是是边边边边的集合的集合,G G是从边集是从边集E E到结点偶对集合上的函数。一个到结点偶对集合上的函数。一个图可以用一个图形表示。图可以用一个图形表示。例例例例1 1 1 1设设G G=V V(G G),),E E(G G),),G G,其中其中V V(G G)=
3、)=a a,b b,c c,d d ,E E E E(G G G G)=)=)=)=e e e e1 1 1 1,e e e e2 2 2 2,e e e e3 3 3 3,e e e e4 4 4 4,e e e e5 5 5 5,e e e e6 6 6 6,e e e e7 7 7 7,G G G G(e(e(e(e1 1 1 1)=()=()=()=(a a a a,b b b b),),),),G G G G(e e e e2 2 2 2)=()=()=()=(a a a a,c c c c),),),),G G G G(e(e(e(e3 3 3 3)=()=()=()=(b b b
4、 b,d d d d),),),),G G G G(e(e(e(e4 4 4 4)=()=()=()=(b b b b,c c c c),),),),G G G G(e e e e5 5 5 5)=()=()=()=(d d d d,c c c c),),),),G G G G(e(e(e(e6 6 6 6)=()=()=()=(a a a a,d d d d),),),),G G G G(e e e e7 7 7 7)=()=()=()=(b b b b,b b b b)则图则图则图则图G G G G可用图可用图可用图可用图8.118.118.118.11表示。表示。表示。表示。8.1 8.
5、1 图的基本概念图的基本概念图的基本概念图的基本概念8.1.1 图图第8章 图论图8.1-1第8章 图论定义中的结点偶对可以是有序的定义中的结点偶对可以是有序的,也可以是无序的。若也可以是无序的。若边边e e所对应的偶对所对应的偶对a a,b b是有序的是有序的,则称则称e e是是有向边有向边有向边有向边。有。有向边简称弧向边简称弧,a a叫弧叫弧e e的始点的始点,b b叫弧叫弧e e的终点的终点,统称为统称为e e的端的端点。称点。称e e是关联于结点是关联于结点a a和和b b的的,结点结点a a和结点和结点b b是是邻接的邻接的邻接的邻接的。若边若边e e所对应的偶对所对应的偶对(a
6、a,b b)是无序的是无序的,则称则称e e是是无向边无向边无向边无向边。无。无向边简称棱向边简称棱,除无始点和终点的术语外除无始点和终点的术语外,其它术语与有向其它术语与有向边相同。边相同。每一条边都是有向边的图称为每一条边都是有向边的图称为有向图有向图有向图有向图,第三章中的关系第三章中的关系图都是有向图的例子。每一条边都是无向边的图称为图都是有向图的例子。每一条边都是无向边的图称为无无无无向图向图向图向图;如果在图中一些边是有向边;如果在图中一些边是有向边,而另一些边是无向而另一些边是无向边边,则称这个图是则称这个图是混合图混合图混合图混合图。我们仅讨论有向图和无向图。我们仅讨论有向图和
7、无向图,且且V V(G G)和和E E(G G)限于有限集合。限于有限集合。第8章 图论约定用约定用a a,b b表示有向边表示有向边,(,(a a,b b)表示无向边表示无向边,既表示有向既表示有向边又表示无向边时用边又表示无向边时用a a,b b。有向图和无向图也有向图和无向图也可互相转化可互相转化。例如。例如,把无向图中每一条把无向图中每一条边都看作两条方向不同的有向边边都看作两条方向不同的有向边,这时无向图就成为有向这时无向图就成为有向图。又如图。又如,把有向图中每条有向边都看作无向边把有向图中每条有向边都看作无向边,就得到无就得到无向图。这个无向图习惯上叫做该向图。这个无向图习惯上叫
8、做该有向图的底图有向图的底图有向图的底图有向图的底图。在图中在图中,不与任何结点邻接的结点称为不与任何结点邻接的结点称为弧立结点弧立结点弧立结点弧立结点;全由孤;全由孤立结点构成的图称为立结点构成的图称为零图零图零图零图。关联于同一结点的一条边称为。关联于同一结点的一条边称为自回路自回路自回路自回路;自回路的方向不定。自回路的有无不使有关图论;自回路的方向不定。自回路的有无不使有关图论的各个定理发生重大变化的各个定理发生重大变化,所以有许多场合都略去所以有许多场合都略去自回自回路路。第8章 图论在有向图中在有向图中,两结点间两结点间(包括结点自身间包括结点自身间)若同始点和同若同始点和同终点的
9、边多于一条终点的边多于一条,则这几条边称为则这几条边称为平行边平行边平行边平行边。在无向图。在无向图中中,两结点间两结点间(包括结点自身间包括结点自身间)若多于一条边若多于一条边,则称这则称这几条边为平行边。两结点几条边为平行边。两结点a a、b b间互相平行的边的条数间互相平行的边的条数称为称为边边边边a a,b b的重数的重数的重数的重数。仅有一条时重数为。仅有一条时重数为1,1,无边时重无边时重数为数为0 0。定义定义8.128.12含有平行边的图称为含有平行边的图称为多重图多重图多重图多重图。非多重图称为非多重图称为线图线图线图线图。无自回路的线图称为。无自回路的线图称为简单图简单图简
10、单图简单图。在图在图8.138.13中中,(,(a a)、(b b)是多重图是多重图,(,(c c)是线图是线图,(,(d d)是简是简单图单图,关系图都是线图。关系图都是线图。第8章 图论图 8.13 第8章 图论定义定义定义定义 8.13 8.13 8.13 8.13 赋权图赋权图赋权图赋权图G G是一个三重组是一个三重组V V,E E,g g或四重或四重组组V V,E E,f f,g g,其中其中V V是结点集合是结点集合,E E是边的集合是边的集合,f f是定义在是定义在V V上的函数上的函数,g g是定义在是定义在E E上的函数。上的函数。右图给出一个赋权图。右图给出一个赋权图。V
11、V V V=v v v v1 1 1 1,v v v v2 2 2 2,v v v v3 3 3 3;E E E E=e e e e1 1 1 1,e e e e2 2 2 2=(=(=(=(v v v v1 1 1 1,v v v v2 2 2 2),(),(),(),(v v v v2 2 2 2,v v v v3 3 3 3););););f f f f(v v v v1 1 1 1)=5,)=5,)=5,)=5,f f f f(v v v v2 2 2 2)=8,)=8,)=8,)=8,f f f f(v v v v3 3 3 3)=11;)=11;)=11;)=11;g g g g(
12、e e e e1 1 1 1)=4.6,)=4.6,)=4.6,)=4.6,g g g g(e e e e2 2 2 2)=7.5)=7.5)=7.5)=7.5第8章 图论8.1.2 8.1.2 8.1.2 8.1.2 结点的次数结点的次数结点的次数结点的次数定义定义定义定义8.148.148.148.14在在有向图中有向图中,对于任何结点对于任何结点v v,以以v v为始点为始点的的边的条数称为结点边的条数称为结点v v的的引出次数引出次数引出次数引出次数(或出度或出度或出度或出度),),),),记为记为degdegdegdeg+(+(+(+(v v v v););););以以v v为终点的
13、边的条数称为结点为终点的边的条数称为结点v v的引入次数的引入次数(或入度或入度),),记为记为degdegdegdeg-(-(-(-(v v v v););););结点结点v v的引出次数和引入次数之和称为的引出次数和引入次数之和称为结点结点v v的的次数次数次数次数(或度数或度数),),记作记作degdeg(v v)。在无向图中在无向图中,结点结点v v的次数是与结点的次数是与结点v v相关联的边的条数相关联的边的条数,也记为也记为degdeg(v v)。孤立结点的次数为零。孤立结点的次数为零。第8章 图论 定理定理定理定理8.118.118.118.11 设设G G是一个是一个(n n,
14、m m)图图,它的结点集合为它的结点集合为V V=v v1 1,v v2 2,v vn n,则则 证 因为每一条边提供两个次数,而所有各结点次数之和为m条边所提供,所以上式成立。在有向图中,上式也可写成:第8章 图论定理定理定理定理8.128.128.128.12在图中在图中,次数为奇数的结点必为偶数个。次数为奇数的结点必为偶数个。证证 设次数为偶数的结点有设次数为偶数的结点有n n1 1个个,记为记为(i i=1,2,=1,2,n1),n1)。次数为奇数的结点有次数为奇数的结点有n n2 2个个,记为记为(i i=1,2,=1,2,n n2 2)。由上一定理得由上一定理得 因为次数为偶数的各
15、结点次数之和为偶数。所以前一项次数为偶数;若n2为奇数,则第二项为奇数,两项之和将为奇数,但这与上式矛盾。故n2必为偶数。证毕。第8章 图论定义定义定义定义8.158.158.158.15各结点的次数均相同的图称为正则图各结点的次数均相同的图称为正则图,各各结点的次数均为结点的次数均为k k时称为时称为k k正则图。正则图。下图所示的称为彼得森下图所示的称为彼得森(P(Pe et te ersrsenen)图图,是是33正则图。正则图。图 8.15 第8章 图论8.1.3 8.1.3 8.1.3 8.1.3 图的同构图的同构图的同构图的同构 定义定义8.1.68.1.6设设G G=V V,E
16、E和和G G=V V,E E是两个图是两个图,若存在从若存在从V V到到V V的双射函数的双射函数,使对任意使对任意a a、b bV V,a a,b b E E当且仅当当且仅当(a a),),(b b)E E,并且并且a a,b b和和(a a),),(b b)有相同的重数有相同的重数,则称则称G G和和G G是是同构的同构的同构的同构的。上述定义说明上述定义说明,两个图的各结点之间两个图的各结点之间,如果存在一一对如果存在一一对应关系应关系,而且这种对应关系保持了结点间的邻接关系而且这种对应关系保持了结点间的邻接关系(在有向图时还保持边的方向在有向图时还保持边的方向)和边的重数和边的重数,则
17、这两个图则这两个图是同构的是同构的,两个同构的图除了顶点和边的名称不同外实两个同构的图除了顶点和边的名称不同外实际上代表同样的际上代表同样的组组合合结结构。构。第8章 图论例例2(2(a a)、(b b)两图是同构的。因为可作映射两图是同构的。因为可作映射:g g(1)=(1)=v v3 3,g g(2)=(2)=v v1 1,g g(3)=(3)=v v4 4,g g(4)=(4)=v v2 2。在这映射下在这映射下,边边1,31,3,1,21,2,2,42,4和和3,43,4分别映射到分别映射到v v3 3,v v4 4,v v3 3,v v1 1,v v1 1,v v2 2和和v v4
18、4,v v2 2,而后面而后面这这些些边边又是又是(b b)中中仅仅有的有的边边。图 8.16第8章 图论两图同构的两图同构的必要条件必要条件:(1):(1)结点数相等结点数相等;(2);(2)边数相等边数相等;(3);(3)度度数相同的结点数相等。数相同的结点数相等。但这不是充分条件。例如下图中但这不是充分条件。例如下图中(a a)、(b b)两图虽然满足以两图虽然满足以上上3 3条件条件,但不同构。但不同构。(a a)中的中的x x应与应与(b b)中的中的y y对应对应,因为次因为次数都是数都是3 3。但。但(a a)中的中的x x与两个次数为与两个次数为1 1的点的点u u,v v邻接
19、邻接,而而(b b)中的中的y y仅与一个次数为仅与一个次数为1 1的点的点w w邻接。邻接。图 8.17第8章 图论8.1.4 8.1.4 8.1.4 8.1.4 图的运算图的运算图的运算图的运算图的常见运算有并、交、差、环和等图的常见运算有并、交、差、环和等,现分别定义于下现分别定义于下:定义定义8.178.17设图设图G G G G1 1 1 1=V V V V1 1 1 1,E E E E1 1 1 1和图和图和图和图G G G G2 2 2 2=V V V V2 2 2 2,E E E E2 2 2 2(1)(1)G G1 1与与G G2 2的并的并,定义为图定义为图G G3 3V
20、V3 3,E E3 3,其中其中V V V V3 3 3 3=V V V V1 1 1 1V V V V2 2 2 2,E E E E3 3 3 3=E E E E1 1 1 1E E E E2 2 2 2,记为记为记为记为G G G G3 3 3 3=G G G G1 1 1 1G G G G2 2 2 2。(2)(2)G G1 1与与G G2 2的交的交,定义为图定义为图G G3 3V V3 3,E E3 3,其中其中V V V V3 3 3 3=V V V V1 1 1 1V V V V2 2 2 2,E E E E3 3 3 3=E E E E1 1 1 1E E E E2 2 2 2
21、,记为记为记为记为G G G G3 3 3 3=G G G G1 1 1 1G G G G2 2 2 2。(3)G1与G2的差,定义为图G G3 3V V3 3,E E3 3,记为记为G G3 3=G G1 1-G G2 2。其中E E3 3=E E1 1-E E2 2,V V3 3=(=(V V1 1-V V2 2)E3中边所关联的顶点。(4)(4)G G1 1与与G G2 2的环和,定义为图G G3 3V V3 3,E E3 3,G G3 3=(=(G G1 1G G2 2)-()-(G G1 1G G2 2),),记为记为G G3 3=G G1 1G G2 2。第8章 图论除以上除以上除
22、以上除以上4 4 4 4种运算外种运算外种运算外种运算外,还有以下两种操作还有以下两种操作还有以下两种操作还有以下两种操作:(1)(1)(1)(1)删删删删去去去去图图图图G G G G的的的的一一一一条条条条边边边边e e e e;(2)(2)(2)(2)删删删删去去去去图图图图G G G G的的的的一一一一个个个个结结结结点点点点v v v v。它它它它的的的的实实实实际际际际意意意意义是删去结点义是删去结点义是删去结点义是删去结点v v v v和与和与和与和与v v v v关联的所有边。关联的所有边。关联的所有边。关联的所有边。图 8.19第8章 图论8.1.5 8.1.5 8.1.5
23、8.1.5 子图与补图子图与补图子图与补图子图与补图定义定义定义定义8.188.188.188.18设设G G=V V,E E 和和G G=V V,E E是两个图。是两个图。(1)(1)如果如果V V V V和和E E E E,则称则称G G是是G G的的子图子图子图子图。如果。如果V V V V和和E E E E,则称则称G G G G的的真子图真子图真子图真子图。(注意注意:“G G是图是图”已隐含着已隐含着“E E中的边仅关联中的边仅关联V V中的结点中的结点”的的意义。意义。)(2)(2)如果如果V V=V V和和E E E E,则称则称G G为为G G的的生成子图生成子图生成子图生成
24、子图。(3)(3)若子图若子图G G中没有孤立结点中没有孤立结点,G G由由E E唯一确定唯一确定,则则称称G G为由边集为由边集E E导出的子图导出的子图导出的子图导出的子图。(4)若在子图G中,对V中的任意二结点u、v,当u,vE时有u,vE,则G由V唯一确定,此时称G为由结点集V导出的子图。第8章 图论 图 8.110第8章 图论定义定义定义定义8.198.198.198.19在在n n个结点的有向图个结点的有向图G G=V V,E E中中,如果如果E E=V VV V,则称则称G G为为有向完全图有向完全图有向完全图有向完全图;在在n n个结点的无向图个结点的无向图G G=V V,E
25、E中中,如如果任何两个不同结点间都恰有一条边果任何两个不同结点间都恰有一条边,则称则称G G为为无向完全无向完全无向完全无向完全图图图图,记为记为K Kn n。图图8.1118.111是是4 4个结点的有向完全图和无向完全图的图示。个结点的有向完全图和无向完全图的图示。图8.1-11第8章 图论定义定义定义定义8.1108.1108.1108.110 设线图设线图G G=V V,E E有有n n个顶点个顶点,线图线图H=H=V V,E E也有同样的顶点也有同样的顶点,而而E E是由是由n n个顶点的完全个顶点的完全图的边删去图的边删去E E 所得所得,则图则图H H称为图称为图G G的的补图补
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 图论 1216
限制150内