图论与代数结构.ppt

《图论与代数结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章道路与回路2.1道路与回路定义2.1.1有向图中，若边序列　　　　　，其中满足　是的终点，　是　的始点，就称是的一条有向道路。如果　的终点也是的始点，则称是的一条有向回路。道路与回路如果中的边没有重复出现，则分别称为简单有向道路和简单有向回路。进而，如果中结点也不重复出现，又分别称它们是初级有向道路和初级有向回路简称为路和回路。显然，初级有向道路(回路)一定是简单有向道路(回路)。道路与回路定义2.1.2无向图中，若点边交替序列满足　　是　的两个端点,则称是中的一条链或道路。如果　　　，则称是中的一个圈，或回路。如果中没有重复出现的边，称之为简单道路或简单回路，若其中结点也不重复

2、，又称之为初级道路或初级回路。道路与回路定义2.1.3设是无向图，若的任意两结点之间都存在道路，就称是连通图，否则称为非连通图。如果是有向图，不考虑其边的方向，即视为无向图，若它是连通的，则称是连通图。若连通子图不是的任何连通子图的真子图，则称是的极大连通子图，或称连通支。显然的每个连通支都是它的导出子图。道路与回路定义2.1.4设是简单图中含结点数大于3的一个初级回路，如果结点和在中不相邻，而边，则称是的一条弦。道路与回路证明：若对每一个，都有，则中必含带弦的回路。证明：在中构造一条初级道路，不妨设，。由于是极长的初级道路，所以和的邻接电都在该道路了。由已知条件，，不妨设。其中，这时

3、是一条初级回路，而就是该回路中的一条弦。道路与回路定义2.1.5设是无向图，如果可以划分为子集和，使得对所有的，和都分属于和，则称是二分图。道路与回路证明：如果二分图中存在回路，则它们都是由偶数条边组成的。证明：设是二分图的任一条回路，不妨设是的始点，由于是二分图，所以沿回路必须经过偶数条边才能达到某结点，因而只有经过偶数条边才能回到。道路与回路证明：设是简单图，当时，是连通图。证明：假定是非连通图，则它至少含有2个连通分支。设分别是。其中由于是简单图，因此道路与回路由于，所以与已知条件矛盾，故是连通图。2.3欧拉道路与回路欧拉道路与回路1736年瑞士著名数学家欧拉(LeonhardE

4、uler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。成功地回答了，图中是否存在经过每条边一次且仅一次的回路。欧拉道路与回路欧拉道路与回路定义2.3.1无向连通图中的一条经过所有边的简单回路(道路)称为的欧拉回路(道路)。定理2.3.1无向连通图存在欧拉回路的充要条件是中各结点的度都是偶数。欧拉道路与回路定理2.3.1的证明：1.必要性：若中有欧拉回路，则过每条边一次且仅一次。对任一结点来说，如果经过　进入，则一定通过另一条边　从离开。因此结点的度是偶数。2.充分性：由于是有穷图，因此可以断定，从的任一结点　出发一定存在的一条简单回路。这是因为各结点的度都是偶数，所以这条简单道路不可能

5、停留在　以外的某个点，而不能再向前延伸以致构成回路。欧拉道路与回路推论2.3.1若无向连通图中只有2个度为奇的结点。则存在欧拉道路。证明：设　和　是两个度为奇数的结点。作，则　中各点的度都是偶数。由定理2.3.1，　有欧拉回路，它含边　　　，删去该边，得到一条从　到　的简单道路，它恰好经过了的所有边，亦即是一条欧拉道路。欧拉道路与回路推论2.3.2若有向连通图中各结点的正，负度相等，则存在有向欧拉道路。其证明与定理2.3.1的证明相仿。欧拉道路与回路例2.3.3设连通图G=(V,E)有k个度为奇数的结点，那么E(G)可以划分成k/2条简单道路。证明：由性质1.1.2，k是偶数。在这k个

6、结点间增添k/2条边，使每个结点都与其中一条边关联，得到G’，那么G’中各结点的度都为偶数。由定理2.3.1，G’包含一个欧拉回路C。而新添的k/2条边再C上都不相邻。所以删去这些边后，我们就得到由E(G)划分成的k/2条简单道路。2.4哈密顿道路与回路哈密顿道路与回路哈密顿道路与回路定义2.4.1无向图的一条过全部结点的初级回路(道路)称为G的哈密顿回路(道路)，简记为H回路(道路)。哈密顿回路是初级回路，是特殊的简单回路，因此它与欧拉回路不同。当然在特殊情况下，G的哈密顿回路恰好也是其欧拉回路。鉴于H回路是初级回路，所以如果G中含有重边或自环，删去它们后得到的简单图G’，那么G和G

7、’关于H回路（道路）的存在性是等价的。因此，判定H回路存在性问题一般是针对简单图的。哈密顿道路与回路定理2.4.1如果简单图G的任意两结点之间恒有，则G中存在哈密顿路。哈密顿道路与回路推论2.4.1若简单图的任意两结点和之间恒有，则中存在哈密顿回路。推论2.4.2若简单图中每个结点的度都大于等于，则有回路。哈密顿道路与回路引理2.4.1设是简单图，是不相邻结点，且满足，则存在回路的充要条件是有回路。定义2.4.2若和是简单图的不相邻结点，且满足