4.3-有向图 Euler路

《4.3-有向图 Euler路》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、init(e)=v}的元数；点v的输入

3、次数(入度)是集合{e

4、fin(e)=v}的元数；点v的度等于点v的输入次数加输出次数。今后，为简便计，有时也将有向图G中的点v、弧e，写成vG，eG。定义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）eiA(G),i=1,…,n2）v=init(e1),v’=fin(en)3）fin(ek)=init(ek+1),

5、1kn-1在不引起混乱的情况下，有时也将有向路(e1,…,en)写成(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)是有向图，vP(G)，从点v到自身的简单有向路(长度可以为1或2)称为有向回路。(e2),(e3,e4,e2),(e3,e5,e6,e10,e2),(e3,e5,e6,e7,e1)是从C到B的4个有向路。

6、这4条有向路只有第一条，第四条是简单的；ABCDEFe1e2e3e4e5e6e7e9e8e10(e3,e4),(e3,e5,e6,e10),(e8),(e9)是4条有向回路；有向图G中，从B到其它任意点都没有有向路。例：定义定义4.3.6设G=(P，A)是有向图，对G中任意两点v，v’(vv’)，如果都有从v到v’的有向路，则称G是强连通的。定义4.3.7设G=(P，A)是有向图，rP(G)。称r为G的根，如果对G中任一点v(vr)，都有从v到r的有向路。显然，强连通图的每一点都是根，反之，每一点都是根的有向图也必是强连通的。漠视图有向图G的漠视图G0：(1)

7、删去G中自身到自身的弧；(2)G中任意两点，若有弧，只保留一条；(3)删去弧的方向，即得G0。称有向图G是连通的，如果G的漠视图G0是连通的。显然，若有向图G是强连通的，则G必有根；若有向图G有根，则漠视图G0必连通。反之，不一定成立。亦即，若G0连通，则G不一定有根；若有根，则G未必强连通。例：ABCDEFe1e2e3e4e5e6e7e9e8e10不是强连通的，有根B强连通的r有根r定义4.3.8有向图G称为有向树（或有根树），如果G中有一点r，并且满足：(1)G中每一点v(vr)都恰是一条弧e的起点。(2)r不是任一条弧的起点。(3)r是根。从定义中我们

8、可推出有向树有如下性质：1)每一点v(vr)到r恰有一条有向路；2)没有有向回路；3)两点间最多有一条弧。有向树扩展应用案例例：ABCDEFe1e2e3e4e5e6e7e9e8e10有根B，但不是有向树不是有向树r有根r，是有向树定理4.3.1（转化定理）对有向树G，若无视各弧之方向，则得一树G0；反之，若G0是树，可选取任一点做根，并适当指定各边之方向，则得一有向树G。证明：1)首先证第一个命题。因有向树有根，所以G0是连通的，以下证G0无回路。用反证法。假设G0中有回路，设(v0,…,vn)是G0中一回路，其中v0=vn，n3。定理4.3.1（转化定理）(1

9、)若r在此路中，不妨假设v0=r，则在G中对应G0的边v0v1的弧一定是从v1到v0的，又因G中除根外每一点恰发一弧，所以G0中边v1v2必是G中从v2到v1的弧，…，G0中边vk-1vk必是G中vk到vk-1的弧，…，G0中边vn-1vn必是G中vn到vn-1的弧，而vn=v0=r，矛盾。……vn=v0=rv1v2vkvk-1vn-1定理4.3.1（转化定理）(2)若r不在此回路中，由有向树定义知，v0或v1恰发一弧，不妨设G0中的边v0v1是G中从v1到v0的弧，则v1已发弧，则G0中的边v1v2必是G中从v2到v1的弧，…，则G0中边vn-1vn是G中从v