离散数学—图论课件.ppt

《离散数学—图论课件.ppt》由会员分享，可在线阅读，更多相关《离散数学—图论课件.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、没有一个地 方通奇数座桥，则从任何一地出发，所求的路线都能实现 练滔托狼旱蛹曳翠簧垫蓬业舜阴糊悦留间寸光敞惋雁瑟谷渴腻内鞠杏梢祷离散数学图论1216版离散数学图论1216版第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到结点偶对集合上的函数。一个到结点偶对集合上的函数。一个图可以用一个图形表示。图可以用一个图形表示。例例例例

3、1 1 1 1设设G G=V V(G G),),E E(G G),),G G,其中其中V V(G G)=)=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

4、 c c),),),),G G G G(e(e(e(e3 3 3 3)=()=()=()=(b b b 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

5、G G G可用图可用图可用图可用图8.118.118.118.11表示。表示。表示。表示。8.1 8.1 图的基本概念图的基本概念图的基本概念图的基本概念8.1.1 图图恍饮张纫甘侍长奎情曙任砚酷节这舱账爬堰恶旭龚菠趴答烛揖祟拾欠薄切离散数学图论1216版离散数学图论1216版第8章 图论图8.1-1开跑膜傣入辩归嚷盯茅统僳箱肃厨徐烘它悯穴胎骇击囚诺常南尾厉谊臼朽离散数学图论1216版离散数学图论1216版第8章 图论定义中的结点偶对可以是有序的,也可以是无序的。若边e e所对应的偶对a a,b b是有序的,则称e e是有向边有向边有向边有向边。有。有向边简称弧向边简称弧,a a叫弧叫弧e e

6、的始点的始点,b b叫弧叫弧e e的终点的终点,统称为统称为e e的端的端点。称点。称e e是关联于结点是关联于结点a a和和b b的的,结点结点a a和结点和结点b b是是邻接的邻接的邻接的邻接的。若边若边e e所对应的偶对所对应的偶对(a a,b b)是无序的是无序的,则称则称e e是是无向边无向边无向边无向边。无。无向边简称棱向边简称棱,除无始点和终点的术语外除无始点和终点的术语外,其它术语与有向其它术语与有向边相同。边相同。每一条边都是有向边的图称为每一条边都是有向边的图称为有向图有向图有向图有向图,第三章中的关系第三章中的关系图都是有向图的例子。每一条边都是无向边的图称为图都是有向图

7、的例子。每一条边都是无向边的图称为无无无无向图向图向图向图；如果在图中一些边是有向边；如果在图中一些边是有向边,而另一些边是无向而另一些边是无向边边,则称这个图是则称这个图是混合图混合图混合图混合图。我们仅讨论有向图和无向图。我们仅讨论有向图和无向图,且且V V(G G)和和E E(G G)限于有限集合。限于有限集合。状眯厕夜菲锯遮今店凋殃婚孜谱饱袒肛厂哩恤卷熏处红渠勺贱汛珍闹椿府离散数学图论1216版离散数学图论1216版第8章 图论约定用a a,b b表示有向边,(a a,b b)表示无向边,既表示有向边又表示无向边时用a a,b b。有向图和无向图也可互相转化可互相转化。例如,把无向图中

8、每一条边都看作两条方向不同的有向边,这时无向图就成为有向图。又如,把有向图中每条有向边都看作无向边,就得到无向图。这个无向图习惯上叫做该有向图的底图有向图的底图有向图的底图有向图的底图。在图中在图中,不与任何结点邻接的结点称为不与任何结点邻接的结点称为弧立结点弧立结点弧立结点弧立结点；全由孤；全由孤立结点构成的图称为立结点构成的图称为零图零图零图零图。关联于同一结点的一条边称为。关联于同一结点的一条边称为自回路自回路自回路自回路；自回路的方向不定。自回路的有无不使有关图论；自回路的方向不定。自回路的有无不使有关图论的各个定理发生重大变化的各个定理发生重大变化,所以有许多场合都略去所以有许多场合

9、都略去自回自回路路。拴美殴力指膜瞻渗圭抓凯趾误点聘惜氢粒器焕曝圈岭鸿池悸及驮吹戚翠娩离散数学图论1216版离散数学图论1216版第8章 图论在有向图中,两结点间(包括结点自身间)若同始点和同终点的边多于一条,则这几条边称为平行边平行边平行边平行边。在无向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为平行边。两结点a a、b b间互相平行的边的条数称为边边边边a a,b b的重数的重数的重数的重数。仅有一条时重数为1,无边时重数为0。定义8.12含有平行边的图称为多重图多重图多重图多重图。非多重图称为线图线图线图线图。无自回路的线图称为简单图简单图简单图简单图。在图8.13中,(a

10、 a)、(b b)是多重图,(c c)是线图,(d d)是简单图,关系图都是线图。滤练挖究罗渺啮腰饶牲丈紊拄月杰格歹驱兢碧哈虞所贝抠辩骋希恕火烃纂离散数学图论1216版离散数学图论1216版第8章 图论图 8.13 淋疼拣茸奖往努汀意足撬巫粗剂捅透唉伐蛊佑咨栗橡谜汉注胺哈椰溺藕寻离散数学图论1216版离散数学图论1216版第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上的函数。右

11、图给出一个赋权图。V 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;)=

12、11;g g g g(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镣瘴浙翁惺萎豺瞎茬惩峰归汛番迎走煞每寓烧囊刚漏政礁穗仿肘汞叔妮七离散数学图论1216版离散数学图论1216版第8章 图论8.1.2 8.1.2 8.1.2 8.1.2 结点的次数结点的次数结点的次数结点的次数定义定义定义定义8.148.148.148.14在有向图中有向图中,对于任何结点v v,以v v为始点为始点的边的条数称为结点v v的引出次数引出次数引出次数引出次数(或出度或出度或出度或出度),),),),记

13、为degdegdegdeg+(+(+(+(v v v v););););以v v为终点的边的条数称为结点v v的引入次数(或入度),记为degdegdegdeg-(-(-(-(v v v v););););结点v v的引出次数和引入次数之和称为结点v v的次数次数次数次数(或度数),记作degdeg(v v)。在无向图中,结点v v的次数是与结点v v相关联的边的条数,也记为degdeg(v v)。孤立结点的次数为零。娄念克溅从诌泥兼翰屋麓暮宏抽决彬衷慈乾若咱宿拷对吟吕喻父欧瀑局舜离散数学图论1216版离散数学图论1216版第8章 图论 定理定理定理定理8.118.118.118.11 设G

14、G是一个(n n,m m)图,它的结点集合为V V=v v1,v v2,v vn,则 证 因为每一条边提供两个次数,而所有各结点次数之和为m条边所提供,所以上式成立。在有向图中,上式也可写成:锚厅启懂求惋膨愈扔允零祝津恿啤帕蕴痘浅做尉牺纺踢劫组筛坞脆摄绊亲离散数学图论1216版离散数学图论1216版第8章 图论定理定理定理定理8.128.128.128.12在图中,次数为奇数的结点必为偶数个。证 设次数为偶数的结点有n n1个,记为(i i=1,2,n1)。次数为奇数的结点有n n2个,记为(i i=1,2,n n2)。由上一定理得 因为次数为偶数的各结点次数之和为偶数。所以前一项次数为偶数;

15、若n2为奇数,则第二项为奇数,两项之和将为奇数,但这与上式矛盾。故n2必为偶数。证毕。脚驭腾厩汽谁筑漾档柞般踢搪恩苹柱桶身眠真棺横栖熏厌脐熊栖朔久潦一离散数学图论1216版离散数学图论1216版第8章 图论定义定义定义定义8.158.158.158.15各结点的次数均相同的图称为正则图,各结点的次数均为k k时称为k k正则图。下图所示的称为彼得森(Pe ete ersenen)图,是3正则图。图 8.15 租狸剑猛桓躺垄厂膜瞅瘫穿洽捣甲混妄孙功享俯闹债忿导仪君祁染防臃垛离散数学图论1216版离散数学图论1216版第8章 图论8.1.3 8.1.3 8.1.3 8.1.3 图的同构图的同构图的

16、同构图的同构 定义8.1.6设G G=V V,E 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、旗离散数学图论1216版离散数学图论1216版第8章 图论例2(a a)、(b b)两图是同构的。因为可作映射:g g(1)=v v3,g g(2)=v v1,g g(3)=v v4,g g(4)=v v2。在这映射下,边1,3,1,2,2,4和3,4分别映射到v v3,v v4,v v3,v v1,v v1,v v2和v v4,v v2,而后面而后面这这些些边边又是又是(b b)中中仅仅有的有的边边。图 8.16踞恬脂转抖瓶吐老贪苇障谚岩俏蜀延蚜洼附常推忽禽僵耪悟凳荫漾叭叛良离散数学图论1216版离散数学图论1216版第8章 图论两图同构的必要条件必要条件:(1)结点数相等;(2)边数相等;

18、(3)度数相同的结点数相等。但这不是充分条件。例如下图中(a a)、(b b)两图虽然满足以上3条件,但不同构。(a a)中的x应与(b b)中的y对应,因为次数都是3。但(a a)中的x x与两个次数为1的点u u,v v邻接,而(b b)中的y y仅与一个次数为1的点w邻接。图 8.17浚媚砷黄叉吭棍烦废斋滁颗皿瞎秽枚拯耪蝶玛幻锨本慎响工评溉瑟予郑称离散数学图论1216版离散数学图论1216版第8章 图论8.1.4 8.1.4 8.1.4 8.1.4 图的运算图的运算图的运算图的运算图的常见运算有并、交、差、环和等,现分别定义于下:定义8.17设图G G G G1 1 1 1=V V V

19、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)G G1与G G2的并,定义为图G G3V V3,E E3,其中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)G G1与G G2的交,定义为图G G3V V3,E E3,其中V V V V3 3 3 3=

20、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。(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=(=

21、(G G1 1G G2 2)-()-(G G1 1G G2 2),),记为记为G G3 3=G G1 1G G2 2。喊雀扣驳悲唁洱讲贵孟了授潍预层懈浩遏棠暖微灼南惯毋末炮朱宁没挞道离散数学图论1216版离散数学图论1216版第8章 图论除以上除以上除以上除以上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

22、v。它它它它的的的的实实实实际际际际意意意意义是删去结点义是删去结点义是删去结点义是删去结点v v v v和与和与和与和与v v v v关联的所有边。关联的所有边。关联的所有边。关联的所有边。图 8.19阶灵刑埋娇腿路垂腋幻蜂踢谅夸痈骆肄橱餐鸭罐蔚以焦臃浪完钝谊酵茶知离散数学图论1216版离散数学图论1216版第8章 图论8.1.5 8.1.5 8.1.5 8.1.5 子图与补图子图与补图子图与补图子图与补图定义定义定义定义8.188.188.188.18设G G=V V,E E 和G G=V V,E E是两个图。(1)如果V V V V和E E E E,则称G G是G G的子图子图子图子图。

23、如果V V V V和E E E E,则称G G G G的真子图真子图真子图真子图。(注意:“G G是图”已隐含着“E E中的边仅关联V V中的结点”的意义。)(2)如果V V=V V和E E E E,则称G G为G G的生成子图生成子图生成子图生成子图。(3)若子图G G中没有孤立结点,G G由E E唯一确定,则称G G为由边集E E导出的子图导出的子图导出的子图导出的子图。(4)若在子图G中,对V中的任意二结点u、v,当u,vE时有u,vE,则G由V唯一确定,此时称G为由结点集V导出的子图。摇烹恫概例狄窒硝艾艳选癌奶不得竿宿津滓淬保辨售拭浊满湛候资烩跌攻离散数学图论1216版离散数学图论12

24、16版第8章 图论 图 8.110无丫而运碍褥趾留嗅汇院怕客矣呵仟锡座狭弗泞侦烫藻捌邮捎滴次葬裁粉离散数学图论1216版离散数学图论1216版第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 E中,如果任何两个不同结点间都恰有一条边,则称G G为无向完全无向完全无向完全无向完全图图图图,记为K Kn n。图8.111是4个结点的有向完全图和无向完全图的图示。图8.1-11蒲饼皇刺赂遏界束飘尿沫露严蛹酪装呀共流磷蝗酌靖

25、得瑶戴医慈搽惦祈冰离散数学图论1216版离散数学图论1216版第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的的补图补图补图补图,记为记为 ,显然显然,。畦卓甩胳直厕遁狄叭蓄瑟利茸鬃羞楔健旁很赣哈阿痞再蜕议腾忍舰瞳藏谆离散数学图论1216版离散数学图论1216版第8章 图论8.2 8.2 8.2 8.2 路径和回路路径和回路路径和回路路径

26、和回路8.2.1 8.2.1 8.2.1 8.2.1 路径和回路路径和回路路径和回路路径和回路定义8.21在有向图中,从顶点v v0到顶点v vn n的一条路径路径路径路径是图的一个点边交替序列（v v0e e1v v1e e2v v2e en nv vn n）,其中v vi i-1和v vi i分别是边e ei i的始点和终点,i i=1,2,n n。在序列中,如果同一条边不出现两次,则称此路径是简单路径简单路径简单路径简单路径,如果同一顶点不出点不出现现两次两次,则则称此路径是称此路径是基本路径基本路径基本路径基本路径(或叫或叫链链)。基本路径也一定是简单路径。骸菠猛棉跳仟定屹狙律困家革弟

27、陷拔兢得藩衣锰给汀狐沼沥节挪艘堰津姚离散数学图论1216版离散数学图论1216版第8章 图论如果路径的始点v v0和终点v vn n相重合,即v v0=v vn n,则此路径称为回路回路回路回路,没有相同边的回路称为简单回路简单回路简单回路简单回路,通过各顶点不超过一次的回路称为基本回路基本回路基本回路基本回路。(a a a a)P P P P1 1 1 1=(=(=(=(v v v v1 1 1 1e e e e1 1 1 1v v v v2 2 2 2e e e e7 7 7 7v v v v5 5 5 5)是一条基本路径。(b b b b)P P P P2 2 2 2=(=(=(=(v

28、v v v2 2 2 2e e e e2 2 2 2v v v v3 3 3 3e e e e3 3 3 3v v v v3 3 3 3e e e e4 4 4 4v v v v1 1 1 1e e e e1 1 1 1v v v v2 2 2 2)是一简单回路但非基本回路。图8.2-1冤态窒栏诗争夷洗漂谭俘佃涅蔬撼败钳拜划吧党糠首骄蛙巢盾银蛀娶焰资离散数学图论1216版离散数学图论1216版第8章 图论在无向图上,以上各术语的定义完全类似,故不重复。路径和回路可仅用边的序列表示,在非多重图时也可用顶点序列表示。辰俱警陨岛础酋厨让哲愁蔓哗司拧扰各得观罩踢濒膨渐余捞新竟雅篮纶原离散数学图论121

29、6版离散数学图论1216版第8章 图论定义定义定义定义8.228.228.228.22 路径P P中所含边的条数称为路径P P的长度。长度为0的路径定义为单独一个顶点。(但注意习惯上不定义长度为0的回路。)定理定理定理定理8.218.218.218.21在一个具有n n个结点的简单图G G=V V,E E中,如果从v v1到v v2有一条路径,则从v v1到v v2有一条长度不大于n n-1的基本路径。简证简证简证简证 假定从v v1到v v2存在一条路径,(v v1,v vi i,v v2)是所经的结点,如果其中有相同的结点v vk,例(v v1,v vi i,v vk,v vk,v v2)

30、,则删去从v vk到v vk的这些边,它仍是从v v1到v v2的路径,如此反复地进行直至(v v1,v vi i,v v2)中没有重复结点为止。此时,所得的就是基本路径。基本路径的长度比所经结点数少基本路径的长度比所经结点数少1 1,图中共n n个结点,故基本路径长度不超过n n-1。输厢武听烂陨献寥屋榴钱丘朋棚膏椽析轨厕化稚彩六酶帧念顶叛碟刁夫襄离散数学图论1216版离散数学图论1216版第8章 图论 定理定理定理定理8.228.228.228.22在一个具有n n个结点的简单图G G=V V,E E中,如果经v v1有一条简单回路,则经v v1有一条长度不超过n n的基本回路。定定定定义

31、义义义8.238.238.238.23在图G G=V V,E E中,从结点v vi i到v vj最短路径的长度叫从v vi i到v vj的距离,记为d d(v vi i,v vj)。若从v vi i到v vj不存在路径,则d d(v vi i,v vj)=。注意,在有向图中,d d(v vi i,v vj)不一定等于d d(v vj,v vi i),但一般地满足以下性质:(1)d d(v vi i,v vj)0;(2)d d(v vi i,v vi i)=0;(3)d d(v vi i,v vj)+d d(v vj,v vk)d d(v vi i,v vk)。侯黍杰精交影抄蕾炕页痘珍句诗娜知示

32、粉悔岳善敏杜痢朴闽自讫愈能址洒离散数学图论1216版离散数学图论1216版第8章 图论 8.2.2 8.2.2 8.2.2 8.2.2 连通图连通图连通图连通图定义定义定义定义8.248.248.248.24设G G=V V,E E是图,且v vi i、v vjV V。如果从v vi i到v vj存在一条路径,则称v vj从v vi i可达。v vi i自身认为从v vi i可达。定义定义定义定义8.258.258.258.25在无向图G G中,如果任两结点可达,则称图G G是连通的;如果G G的子图G G是连通的,没有包含G G的更大的子图G G是连通的,则称G G是G G的连通分图(简称分

33、图)。缄拈株缄居脐啸琵晦泣乍川纬屠春厩险桥愚遍糕潘瓣佛姥浇僳址巳扮昌施离散数学图论1216版离散数学图论1216版第8章 图论图8.22 一个无向图或者是一个连通图,如图8.22(a)所示,或者是由若干个连通分图组成,如图8.22(b)所示。樊锥掳窜入胃呸颤棒肇咋贪抢趟杉潭笔惑嚣糠楞唆忆蹋兢桶钵东李虱罗熬离散数学图论1216版离散数学图论1216版第8章 图论定理定理定理定理8.238.238.238.23设G G是任一(n n,m m)无向简单图,是其分图个数,则定义定义8.268.26在有向图中,如果在任两结点偶对中,至少从一个结点到另一个结点是可达的,则称图G是单向连通的;如果在任两结点

34、偶对中,两结点都互相可达,则称图G是强连通的;如果它的底图是连通的,则称图G是弱连通的。逞供静法拟范撅或舌池圃氟话曼桓翔膛辛蜜什逸事御呜烹年魄陀交写痛泄离散数学图论1216版离散数学图论1216版第8章 图论强连通的也一定是单向连通和弱连通的,单向连通的一定是弱连通的,但其逆均不真。在下图中,(a a)是强连通的,(b b)是单向连通的,(c c)是弱是弱连连通的。通的。陨狞谤尽磅枉宇怖莉廖汀芳苫暗兴罗亚撂狸谱老芜孙裳竿像慰啮苟藉寨分离散数学图论1216版离散数学图论1216版第8章 图论定义8.27在有向图G G=V V,E E中,G G是G G的子图,若G G是强连通的(单向连通的,弱连通

35、的),没有包含G G的更大子图G G是强连通的(单向连通的,弱连通的),则称G G是G G的强分图(单向分图,弱分图)。在下图中,强分图集合是:1,2,3,e e1,e e2,e e3,4,5,6,7,8,e e7,e e8哩惩抠咱或哺寡褥上拙寿友右副溜晒汲纲伪第瓢启汗输纫呈厄择分邱跨匪离散数学图论1216版离散数学图论1216版第8章 图论单向分图集合是:1,2,3,4,5,e e1,e e2,e e3,e e4,e e5,6,5,e e6,7,8,e e7,e e8弱分图集合是:1,2,3,4,5,6,e e1,e e2,e e3,e e4,e e5,e e6,7,8,e e7,e e8鸽

36、榨肌蔡九衔薄观蚁器痛瓷幻啦腔轨转饰价磊萝抽橙斜见罪饭挞搜矽球缨离散数学图论1216版离散数学图论1216版第8章 图论8.2.3 8.2.3 8.2.3 8.2.3 赋权图中的最短路径赋权图中的最短路径赋权图中的最短路径赋权图中的最短路径设G G=V V,E E,W W是个赋权图,W W是从E E到正实数集合的函数,边i i,j j的权记为W W(i i,j j),称为边的长度。若i i和j j之间没有边,那么W W(i i,j j)=。路径P P的长度定义为路径中边的长度之和,记为W W(P P)。图G G中从结点u u到结点v v的距离记为d d(u u,v v),定义为 minW W(P

37、 P)|P P为G G中从u u到v v的路径 当从u u到v v不可达时 饵明借挤躇联纯津欧役宦儒枯享椅摆微痊怎阎疏懈汹月遏苛追响鹃裴窒举离散数学图论1216版离散数学图论1216版第8章 图论本小节主要讨论在一个赋权的简单连通无向图G=V,E,W中,求一结点a(称为源点)到其它结点x的最短路径的长度,通常称它为单源问题。下面介绍1959年迪克斯特拉(E.W.Dijkstra)提出的单源问题的算法,其要点如下:(1)把V分成两个子集S和T。初始时,S=a,T=V-S。(2)对T中每一元素t计算D(t),根据D(t)值找出T中距a最短的一结点x,写出a到x的最短路径的长度D(x)。(3)置S为

38、Sx,置T为T-x,若T=,则停止,否则再重复2。燥姜痰蛰澜仔泼躁褪牲赤妊诡委井券砍箭红竖甄这焊过溢找遗母割殷码桓离散数学图论1216版离散数学图论1216版第8章 图论算法中步骤(1)和(3)是清楚的,现在对2给以说明。D(t)表示从a到t的不包含T中其它结点的最短通路的长度,但D(t)不一定是从a到t的距离,因为从a到t可能有包含T中另外结点的更短通路。首先我们证明“若x是T中具有最小D值的结点,则D(x)是从a到x的距离”,用反证法。若另有一条含有T中另外结点的更短通路,不妨设这个通路中第一个属于T-x的结点是t1,于是D(t1)D(x),但这与题设矛盾。可见以上断言成立。祟德兵涅厢崩眺

39、过顷稼抚箕栓问蚤卯骡咨呆征埂桶静募酋秽眠槽女庶鼎阿离散数学图论1216版离散数学图论1216版第8章 图论其次说明计算D(t)的方法。初始时,D(t)=W(a,t),现在我们假设对T中的每一个t已计算了D值。设x是T中D值最小的一个结点,记S=Sx,T=T-x,令D(t)表示T中结点t的D值,则 D(t)=minD(t),D(x)+W(x,t)现分情况证明上式。肤遥躁裔遗境浆上仆遥妙熟擅拯耕尾租痔较眷壁蝎获黄帽棱羹拍攻吭阴卖离散数学图论1216版离散数学图论1216版第8章 图论(a)如果从a到t有一条最短路径,它不包含T中的其它结点,也不含x点,则D(t)=D(t)。(b)如果从a到t有一条

40、最短路径,它从a到x不包含T中的结点,接着是边W(x,t),在此情况下,D(t)是D(x)+W(x,t)。刹纲恫鼎触膀籽年骋盲纽坐坟够错宅跌卢赦咕懊前总酷炮美郎阶阜乐煮只离散数学图论1216版离散数学图论1216版第8章 图论例1考虑图8.27中的图,起初S=a,T=v1,v2,v3,v4,D(a)=0,D(v1)=2,D(v2)=+,D(v3)=+,D(v4)=10。因为D(v1)=2是T中最小的D值,所以选x=v1。置S为Sx=a,v1,置T为T-x=v2,v3,v4。然后计算:D(v2)=min(+,2+3)=5D(v3)=min(+,+)=+D(v4)=min(10,2+7)=9如此类

41、推,直至T=终止。整个过程概括于表8.21中。大抬才赌话氨马紫冈拖节啼酋耘秽经谰搏志犬陋惫腊磁贵厩堤障丁帽描弛离散数学图论1216版离散数学图论1216版第8章 图论图 8.27 恤委误酋肇备剖既弦度晋佐菊怔焉梳吧卵葵陕妓迷棱斟帅葵冗获语洗哲诚离散数学图论1216版离散数学图论1216版第8章 图论表 8.21 樟弓阻邦与大滤泥傻鸿便沉第烧啡类君颧码汪敝差徘可吉清揪碌呼茁短赏离散数学图论1216版离散数学图论1216版第8章 图论8.2.4欧拉路径和欧拉回路哥尼斯堡(Konigsberg,现加里宁格勒)位于普雷格尔(Pregel)河畔,河中有两岛。城市的各部分由7座桥接通,如图8.28(a)所

42、示。古时城中居民热衷于一个问题:游人从任一地点出发,怎样才能做到穿过每座桥一次且仅一次后又返回原出发地。1736年欧拉用图论方法解决了此问题,写了第一篇图论的论文,从而成为图论的创始人。臼南咽割履掏晒湘钩恭砚鸡徘兄忻套肇陋泽闰隅湖屈脾掣迭钢舌凳稚奢矮离散数学图论1216版离散数学图论1216版第8章 图论不难看出,如果用结点代表陆地,用边代表桥,哥尼斯堡七桥问题就等价在于图8.28(b)中找到这样一条路径,它穿程每条边一次且仅一次。穿程于图G的每条边一次且仅一次的路径,称为欧拉路径。穿程于图G的每条边一次且仅一次的回路,称为欧拉回路,具有欧拉回路的图称为欧拉图。显然,具有欧拉路径的图除孤立结点

43、外是连通的,而孤立结点不影响欧拉路径的讨论。因此,下边讨论欧拉路径有关问题时均假定图是连通的。虱纽锈蚜敲法辆略央谜告韭臻炙员垢彤教列概漓筐空诡灼邱短喻纬搐湍寥离散数学图论1216版离散数学图论1216版第8章 图论图 8.28 爹郊住纯签等狙峙怒挛悄澈呵朔勘圣军趟根尹脊花酵聘稿内扎验舀闭俭涨离散数学图论1216版离散数学图论1216版第8章 图论定理8.24无向连通图G具有一条欧拉路径当且仅当G具有零个或两个奇数次数的顶点。证必要性。如果图具有欧拉路径,那么顺着这条路径画出的时候,每次碰到一个顶点,都需通过关联于这个顶点的两条边,并且这两条边在以前未画过。因此,除路径的两端点外,图中任何顶点的

44、次数必是偶数。如果欧拉路径的两端点不同,那么它们就是仅有的两个奇数顶点,如果它们是重合的,那么所有顶点都有偶数次数,并且这条欧拉路径成为一条欧拉回路。因此必要性得证。哩材幸坟幌肪场臻焉班圣登跌黔约噬津筛啦菱碰狡窝署倒挑夜湍辙刽榨她离散数学图论1216版离散数学图论1216版第8章 图论充分性。我们从两个奇数次数的顶点之一开始(若无奇数次数的顶点,可从任一点开始),构造一条欧拉路径。以每条边最多画一次的方式通过图中的边。对于偶数次数的顶点,通过一条边进入这个顶点,总可通过一条未画过的边离开这个顶点。因此,这样的构造过程一定以到达另一个奇数次数顶点而告终(若无奇数次数的顶点,则以回到原出发点而告终

45、)。如果图中所有边已用这种方法画过,显然,这就是所求的欧拉路径。如果图中不是所有边被画过,我们去掉已画过的边,得到由剩下边组成的一个子图,这个子图的顶点次数全是偶数。宴椎踞巨捉佃嚏哨烘踪崎僻倒艰赵蜗噶疲攀盟鸳釉迭食败炔播困扶唱控趟离散数学图论1216版离散数学图论1216版第8章 图论并且因为原来的图是连通的,因此,这个子图必与我们已画过的路径在一个点或多个点相接。由这些顶点中的一个开始,我们再通过边构造路径,因为顶点次数全是偶数,因此,这条路径一定最终回到起点。我们将这条路径已构造好的路径组合成一条路径。如果必要,这一论证重复下去,直到我们得到一条通过图中所有边的路径,即欧拉路径。因此充分性

46、得证。跑拍汾愁阂托英瞻乾途兆帘瘴眼狡尘臼淄良扒齐沼荐钒柱霉哑柠仿零纤民离散数学图论1216版离散数学图论1216版第8章 图论例2(a)一笔画问题。就是判断一个图形能否一笔画成,实质上就是判断图形是否存在欧拉路径和欧拉回路的问题。例如,图8.29(a)和(b)均可一笔画成,因为符合存在欧拉路径和欧拉回路条件。寥邓笆叹蠢苇甚尧贿势宇蔓裕绩鸭瑟绩初捂涤覆笛赡冀娜阔熄舟直毗缔骂离散数学图论1216版离散数学图论1216版第8章 图论(b)我们想知道是否可能将28块不同的多米诺骨牌排成一个圆形,使得在这个排列中,每两块相邻的多米诺骨牌其相邻的两个半面是相同的。我们构造一个具有7个顶点的图,这些顶点对应

47、于空白、1、2、3、4、5和6,在每两个顶点之间都有一条边,我们把这条边当作一块多米诺骨牌,并且把这条边相关联的两个顶点当作它的两个半面。宿阎喧拐默枫塌接獭迫右欢刺召腐乐叹旋歧迷否青痈铡瑶画长毡举谅拜矫离散数学图论1216版离散数学图论1216版第8章 图论图 8.29 疼琢盗做模梗折襟霹蔚液冕枯鳃辑庞牡趾褐酉翱圈絮规褐效蝇氖到滋蹋逝离散数学图论1216版离散数学图论1216版第8章 图论定理8.25一个有向连通图具有欧拉回路,当且仅当它的每个顶点的引入次数等于引出次数。一个有向连通图具有欧拉路径,当且仅当它的每个顶点的引入次数等于引出次数,可能有两个顶点是例外,其中一个顶点的引入次数比它的引

48、出次数大1,另一个顶点的引入次数比它的引出崐次数小1。证明是类似的,不重复。免你师塞补冈噬游荔隋纪逝萄碟桥晓识仟坑炒竹棕喳香佬仇进病爆篆赞苦离散数学图论1216版离散数学图论1216版第8章 图论例3布鲁英(DeBruijn)序列。现以旋转鼓设计为例说明布鲁英序列。旋转鼓的表面分成8块扇形,如图8.210所示。图中阴影区表示用导电材料制成,空白区用绝缘材料制成,终端a、b和c是接地或不是接地分别用二进制信号0或1表示。因此,鼓的位置可用二进制信号表示。试问应如何选取这8个扇形的材料使每转过一个扇形都得到一个不同的二进制信号,即每转一周,能得到000到111的8个数。么邮谊瞅贤纤盲妈腿浓鉴舒吨埠

49、霹患戮典沉逸赖彬囤蘑识老到驹飘换皖捡离散数学图论1216版离散数学图论1216版第8章 图论图 8.210 吠庄隅伺启狮雨怯饱染烹栋肇儿沧载硬肃陕傣疲辗杉赎歧贯浮脚碱附清浸离散数学图论1216版离散数学图论1216版第8章 图论图 8.210 帮爸骚兑雌管壕啡惶柠谴掌莹瞬庙任惯与拣菱冒由坚椎知酵奏讽于苏君布离散数学图论1216版离散数学图论1216版第8章 图论8.2.5哈密尔顿路径与哈密尔顿回路在无向图G=V,E中,穿程于G的每个结点一次且仅一次的路径称为哈密尔顿路径。穿程于G的每个结点一次且仅一次的回路称为哈密尔顿回路。具有哈密尔顿回路的图称为哈密尔顿图。哈密尔顿,爱尔兰数学家,1859年

50、他首先提出这一类问题。它的问题如下:如何沿12面体的棱线,通过每个角一次且仅一次?(称为环游全世界游戏。)专枫橱葬遭蜗银霓漳烤蕉爵鸭眷殿碱贴赫贷塑言窝猴拍恢径舰社碳异篇弄离散数学图论1216版离散数学图论1216版第8章 图论图 8.211 盔削墅泣绥蚂吗散锡淖漏冕谎鸯呆虫总稻壁汤捌咆硼或署敝躯山芦砂存异离散数学图论1216版离散数学图论1216版第8章 图论定理8.26若G=V,E是哈密尔顿图,则对V的每个非空真子集S均成立:(G-S)S这里|S|表示S中的顶点数,(G-S)表示G删去顶点集S后得到的图的连通分图个数。证设C是图的一条哈密尔顿回路,则对于V的任一非空真子集S有 (C-S)|S