4.3-有向图Euler路51263

1、4.3有向图 Euler路,定义4.3.1 G=(P, A)称为有向图，如果P是点集合，A是从一点引到一点(不要求一定是另一点)的弧集合。当P为有限集时，G称为有限有向图。 若e是一条从点v到点v的弧，则称v为e的起点，记为v=init(e)；v为e的终点，记为v=fin(e)。 把起点和终点都是点v的弧称为反身弧，有向图中两点(可以是相同的)间的弧可以有无穷条。显然，有限有向图中的集合A未必是有限集。即，有限有向图中的弧可以有无穷多条。,4.3.1 有向图与有向树,例：,有向图中点v的输出次数(出度)是集合e|init(e)=v的元数；点v的输入次数(入度)是集合e | fin(e)=v的元

2、数；点v的度等于点v的输入次数加输出次数。 今后，为简便计，有时也将有向图G中的点v、弧e，写成vG，eG。,定义4.3.2,设G，H是有向图。如果P(H) P(G)，A(H)A(G)，则称H为G的有向子图(简称子图)。G是H的母图。如果H是G的子图，并且P(H)=P(G)，则称H是G的支撑子图。,定义4.3.3,设G=(P, A)是有向图，弧序列(e1, ,en)称为G的从v到v其长度为n的有向路，如果1）eiA(G), i=1, ,n 2）v=init(e1), v=fin(en) 3）fin(ek)=init(ek+1), 1kn-1 在不引起混乱的情况下，有时也将有向路(e1, , e

3、n)写成(v1, , vn, vn+1)，其中 vi=init(ei) (i=1, , n)，vn+1=fin(en)。,定义4.3.4,有向图的有向路(e1,en)称为简单的，如果1）init(e1), , init(en)互不相同，2）fin(e1), , fin(en)互不相同。,定义4.3.5,设G=(P, A)是有向图，vP(G)，从点v到自身的简单有向路(长度可以为1或2)称为有向回路。,(e2),(e3, e4, e2),(e3, e5, e6, e10, e2),(e3, e5, e6, e7, e1)是从C到B的4个有向路。这4条有向路只有第一条，第四条是简单的；,(e3,

4、e4),(e3, e5, e6, e10),(e8),(e9)是4条有向回路；有向图G中，从B到其它任意点都没有有向路。,例：,定义,定义4.3.6 设G=(P，A)是有向图，对G中任意两点v，v (vv)，如果都有从v到v的有向路，则称G是强连通的。 定义4.3.7 设G=(P，A)是有向图，rP(G)。称r为G的根，如果对G中任一点v (vr)，都有从v到r的有向路。 显然，强连通图的每一点都是根，反之，每一点都是根的有向图也必是强连通的。,漠视图,有向图G的漠视图G0： (1)删去G中自身到自身的弧； (2)G中任意两点，若有弧，只保留一条； (3)删去弧的方向，即得G0。 称有向图G是

5、连通的，如果G的漠视图G0是连通的。 显然，若有向图G是强连通的，则G必有根； 若有向图G有根，则漠视图G0必连通。反之，不一定成立。亦即，若G0连通，则G不一定有根； 若有根，则G未必强连通。,例：,定义4.3.8,有向图G称为有向树（或有根树），如果G中有一点r，并且满足：(1) G中每一点v(vr)都恰是一条弧e的起点。(2) r不是任一条弧的起点。 (3) r是根。 从定义中我们可推出有向树有如下性质： 1) 每一点v(vr)到r恰有一条有向路； 2) 没有有向回路； 3) 两点间最多有一条弧。,例：,定理4.3.1（转化定理）,对有向树G，若无视各弧之方向，则得一树G0；反之，若G0

6、是树，可选取任一点做根，并适当指定各边之方向，则得一有向树G。 证明：1) 首先证第一个命题。 因有向树有根，所以G0是连通的，以下证G0无回路。 用反证法。假设G0中有回路，设(v0, , vn) 是G0中一回路，其中v0= vn，n3。,定理4.3.1（转化定理）,(1) 若r在此路中，不妨假设v0=r，则在G中对应G0的边v0v1的弧一定是从v1到v0的，又因G中除根外恰发一弧，所以G0中边v1v2必是G中从v2到v1的弧，G0中边vk-1 vk必是G中vk到vk-1的弧，G0中边vn-1vn必是G中vn到vn-1的弧，而vn= v0=r，矛盾。,vn = v0=r,v1,v2,vk,v

7、k-1,vn-1,定理4.3.1（转化定理）,(2)若r不在此回路中，由有向树定义知，v0或v1恰发一弧，不妨设G0中的边v0v1是G中从v1到v0的弧，则v1已发弧，则G0中的边v1v2必是G中从v2到v1的弧，则G0中边vn-1vn是G中从vn到vn-1的弧，又vn=v0, 于是，得G中一有向回路，矛盾。,vn = v0,v1,v2,vk,vk-1,vn-1,故假设不成立，此连通图G0无回路，故G0是树,定理4.3.1（转化定理）,2)再证第二个命题。 任选树中一点r作为根，规定：将G0中任意一边vv改成从v到v的弧当且仅当vr且从v到r的简单路通过v。即这条简单路形如：(v,v,r) 。

8、 (1)首先证明上述规定的无矛盾性：对树G0中任意一边vv，若v=r，则按规定，将边vv改成从v到r的弧；若vr，则往证：按规定，其方向或者从v到v，或者从v到v，二者必居其一。,定理4.3.1（转化定理）,因为从v,v各恰有一条到r的简单路，分别设为(v,v1,v2,r)、(v,v1,v2,r)， 若v v1，v1v，则由于vv，所以可设 vi，vj是这两条路中从左向右看第一对相同的点，亦即 vi= vj，但是v,v1,vi,vj-1,v1,v互不相同，所以(v,v1,vi,vj-1,v1,v,v)是从v到自身的简单路，当i=j=1时，此路为(v,v1,v,v)，长度为3，即此路是回路，矛盾

9、。,定理4.3.1（转化定理）,若v=v1且v1=v，则(v,v,v2, ,r)， (v,v2,r)是两条从v到r的简单路，由于v2 v，所以这是两条不同的从v到r的简单路。矛盾。 故由上面证明知，必有v=v1，或者v1=v，二者恰居其一。若v=v1，则按规定，边vv改成从v到v的弧；若v1=v，则按规定，边vv改成从v到v的弧。故按上述规定，树G0中任一边都能改成一个有确定方向的弧，即，将G0改成一个有向图G。,定理4.3.1（转化定理）,(2) 往证：G是以r为根的有向树。 每一点v (vr)恰是一弧的起点； 任取G中一点v，且vr。由于在G0中存在从v到r的简单路，故由上面的规定，在G中

10、，v必是某条弧的起点。若v是两条弧的起点，设这两条弧的终点分别为v1，v1，且v1 v1。于是，按着上面规定，在G0中，从v到r有两条简单路：(v,v1,r)， (v,v1,r)。矛盾。故点v恰是一条弧的起点。,定理4.3.1（转化定理）, r不是任意一条弧的起点； 由规定知，此结论显然成立。 r是根。 对G中任意一点v (vr) ，在G0中恰有一条从v到r的简单路。按规定此简单路上诸边的方向都指向r，故在G中，这是一条从v到r的有向路。 综上所述，G是一个有向树。,4.3.2 Euler路 Euler图,Konigsberg Seven Bridges Problem,4.3.2 Euler

11、路 Euler图,定义4.3.9 设G是有向图，G中一条Euler路，就是一条有向路(e1, , en)，其中fin(en)=init(e1)，而且G中每条弧在此有向路中恰出现一次。,Euler路是一有向图中周游诸弧的路线。一个有向图，如果存在着Euler路，就称为Euler图。,4.3.2 Euler路 Euler图,定义4.3.10 设G是有向图。G中点v说是孤立的，如果v的输入和输出次数全为0；G说是平衡的，如果G中每点v，都有有限的输入次数和输出次数，而且输入次数和输出次数相等。 于是，一有限平衡有向图，其弧数有限。显然，一有向图若存在Euler路，则必平衡。因为Euler路每经过一点

12、一次，该点就得到输入次数和输出次数各一次。这样，若一点共被经过k次（k=0时是孤立的），则该点在这有向图中的输入次数和输出次数就都是k。由此可见，Euler图中每个点所触及的弧必为偶数条（输入输出各半）。,例,下图是一有限平衡有向图，而（e00, e01, e12, e22, e21, e10, e01, e12, e20）是其中的一条Euler路。,一个Euler图G，如果没有孤立点，则必强连通。事实上，这时G的全部点皆出现在一条有向路(e1,e2,em)上，即出现在Euler路上。其中，init(e1)=fin(em)。沿着这条路线走两圈，总能够先到达任一给定的顶点v，然后再到达另一个任给

13、的顶点v。即对任意的v、v，都存在从v到v的有向路。 Euler路实际上是一条封闭的一笔画路线。,定理4.3.2,设G是无孤立点的有限有向图。于是，G有Euler路当且仅当G是平衡的，并且强连通。 证明：必要性显然。 充分性 由于G没有孤立点，且平衡，所以G的任一点至少发出一条弧。于是G中存在至少一条有向路，并且在该有向路中没有弧被重复使用。令 L=（e1, e2, , em） 是如此有向路中最长者。往证：L就是一条Euler路。,定理4.3.2,1) 证明 init(e1)=fin (em) 设v=fin (em)，设v的输出次数为k (0km)，则v的输入次数也为k 。 (1) 证明由v发

14、出的k条弧必然全部出现在L中。 反证法，若e不在L中，且init(e)=v，则(e1，em，e)就是一条比L更长的由无重复弧构成的有向路，矛盾。,定理4.3.2,(2) 证明由v发出的k条弧中，必有e1，即证： init(e1)=v。 反证法，若从v发出的k条弧中无e1，则设这k条弧是ei1,ei2,eik，其中2ijm，因为ei1,ei2,eik从v发出且都在有向路L中, 则必有ei1-1,ei2-1,eik-1发到v，且1ij-1m-1，即至少有k条弧发到v，这k条弧中不包括em，因em也发到v，于是至少有k+1条弧发到v，即v的输入次数至少是k+1，而输出次数是k，矛盾。 (3) 类似地

15、可证得：G中发到v的k条弧也都出现在L中，并且这k条弧中必有em。,2)最后证明：G的每条弧恰在L中出现一次。 因为已知L中的弧无重复，所以只需证：G的每条弧都在L中出现即可。 对于L，若顶点v在L中，则用1)中的方法可以证明，从v出发的所有弧都在L中。 任取eG，设u=init(e)，任取L中一点v，因为G强连通，v，u间有有向路(e1, e2, , ei)且init(e1)=v，fin(ei)=u，因v在L中，e1是由v发出的弧，所以e1在L中，因此fin(e1)= init(e2)=v1在L中，所以e2在L中，同理，ei的终点u在L中，所以e在L中。由e的任意性知，G中弧均出现在L中。

16、综上，L是一条Euler路。,推论,设G是无孤立点的有限有向图，于是，G有Euler路当且仅当G平衡，并且将G漠视为图G0时是连通的,定理4.3.3,设G是无孤立点的有限有向图，并且G有一条Euler路(e1 , , em)。令r=fin(em)=init(e1)，对每个点vr，令ev=ei，其中i=maxj | init(ej)=v。于是，G的全部点和全部弧ev | vr作成的有向图G，是一个以r为根的有向树。,(e00, e01, e12, e22, e21, e10, e01, e12, e20)是其中的一条Euler路。,所以，用点v0, v1, v2,以及弧e12, e20作成以r=

17、v0为根的有向树,证明：,由ev的定义知： (1) 对每个点vr，恰有一弧ev发出， (2) r不发出任何弧。 下面我们证明： (3) r是根。 先证：有向图G中无有向回路。 若不然，设有一个有向回路 (,ev,ev,)。其中fin(ev)=init(ev)=v。令ev=ej，ev=ek。因为弧ej发到点v。从而ej+1是由v发出的弧，但ek是由v发出的弧中下标最大者，所以jk。,证明：,而此有向回路又可写成： （ev, , ev） 与上面同样的推理，可得：kj 。矛盾。 再证：对G中任一点v，在G中，有一条从v到r的有向路。 在G中，从v出发可以这样走下去： v fin(ev) fin(e(

18、fin(ev) 显然，此有向路上的点没有重复(否则，将出现有向回路)，由于G有限，故最后必然停止在不发出弧的点r上，故G是一个有向树。,定理4.3.4,设G是有限平衡有向图，G是G的有向支撑树，设G的根为r，G中点v(r)发出的弧为ev。设e1是r在G中发出的任一条弧，如果从e1开始任一条有向路：L=(e1, e2, , em) 满足：(1)ej ek，当jk时。 (2)ej =ev当且仅当init(ej)=v并且G中由v发出的弧都出现在(e1, , ej)中。 (3)L终止在em当且仅当G中从em的终点发出的弧都已经在L中出现。 则有向路L是一条Euler路。,证明：,先证：fin(em)=

19、init(e1)=r。 由条件(3)知，由fin(em)发出的弧，都在L中。 仿照定理4.3.2的证明，不难得到结论：fin(em)发 出的弧中，有一条是e1，即fin(em)=init(e1)。 再证：G中每条弧恰在L中出现一次。 由条件(1)知，L中的弧无重复，所以只需证：G中每条弧都出现在L中。 若不然，设G中弧e不在L中，令fin(e)=v，由G和 L的平衡性知，G中有一条由v发出的弧e不在L 中，由于r发出的弧都在L中，故vr，由条件(2)知，ev不在L中。,证明：,同理，若fin(ev)r，efin(ev)不在L中， 于是，得一有向路：L=(e,ev,efin(ev),)， 并且L

20、中的弧不在L中，L中的弧都是G的弧 (除e以外)，L不能无限延长，最终必然沿着G 的一条有向路到达r，于是，根据上面的推理， 有一条从r发出的弧不在L中，与条件(3)矛盾。 所以G中弧均出现在L中。 综上，L是一条Euler路。,例,(e12,e20,e00,e01,e10,e01,e12,e22,e21) (e12,e20,e00,e01,e12,e22,e21,e10,e01) (e12,e20,e01,e10,e00,e01,e12,e22,e21) (e12,e20,e01,e12,e22,e21,e10,e00,e01) (e12,e22,e20,e00,e01,e10,e01,e1

21、2,e21) (e12,e22,e20,e00,e01,e12,e21,e10,e01) (e12,e22,e20,e01,e10,e00,e01,e12,e21) (e12,e22,e20,e01,e12,e21,e10,e00,e01),有向图G，命G是G中由顶点v0,v1,v2和e01,e21组成的有向支撑树(r=v1)。从弧e12出发，可按定理4.3.4的形成规则得出Euler路。,定义4.3.11 容许有平行边和反身边的图G=(P, L)称为无向图，其中P为(节)点集，L称为线集（包括平行边和反身边）。,4.3.3无向图 无向图中的Euler路,定义4.3.12,设G=(P, L)为

22、无向图，lG。如果W(G-l) W(G)，则称l为G的断线。 对于断线，下述结论是明显的。 (1) l是G的断线的充要条件是l不在G的回路上。 (2) 设P=S1S2，S1S2=，若T=l | lG, x S1, y S2, x, y为l的端点仅有一个元素l，则l是G的断线。 (3) 设G=(S, L)是无向图G=(P, L)的子图，若l是G的断线，且lL，则l是G的断线。 (4) 若有限无向图G的的每点的度都是偶数，则G中无断线。,定义4.3.12,在无向图G中讨论Euler路问题，是考虑能否对G中的线加上适当的方向，使之构成的有向图为Euler图。即若无向图G中存在无重复线的路L=(l1, , lm)，满足G中所有线都在L中，且l1的起点与lm的终点相同，则称无向图G为Euler图。反之，若L=(l1, , lm)是无