道路与回路2道路与回路.ppt

第二章 道路与回路2.1道路与回路,定义 有向图 中，若边序列，其中 满足是 的终点，是 的始点，就称 是 的一条有向道路。如果的终点也是 的始点，则称 是 的一条有向回路。,道路与回路,如果 中的边没有重复出现，则分别称为简单有向道路和简单有向回路。进而，如果 中结点也不重复出现，又分别称它们是初级有向道路和初级有向回路简称为路和回路。显然，初级有向道路(回路)一定是简单有向道路(回路)。,道路与回路,定义 无向图 中，若点边交替序列 满足 是的两个端点,则称 是 中的一条链或道路。如果，则称 是 中的一个圈，或回路。如果 中没有重复出现的边，称之为简单道路或简单回路，若其中结点也不重复，又称之为初级道路或初级回路。,道路与回路,定义 设 是无向图，若 的任意两结点之间都存在道路，就称 是连通图，否则称为非连通图。如果 是有向图，不考虑其边的方向，即视为无向图，若它是连通的，则称 是连通图。若连通子图 不是 的任何连通子图的真子图，则称 是 的极大连通子图，或称连通支。显然 的每个连通支都是它的导出子图。,道路与回路,定义 设 是简单图 中含结点数大于3的一个初级回路，如果结点 和 在 中不相邻，而边，则称 是 的一条弦。,道路与回路,证明：若对每一个，都有，则 中必含带弦的回路。证明：在 中构造一条初级道路，不妨设，。由于 是极长的初级道路，所以 和 的邻接电都在该道路 了。由已知条件，不妨设。其中，这时 是一条初级回路，而 就是该回路中的一条弦。,道路与回路,定义 设 是无向图，如果 可以划分为子集 和，使得对所有的，和 都分属于 和，则称 是二分图。,道路与回路,证明：如果二分图 中存在回路，则它们都是由偶数条边组成的。证明：设 是二分图 的任一条回路，不妨设 是 的始点，由于 是二分图，所以沿回路 必须经过偶数条边才能达到某结点，因而只有经过偶数条边才能回到。,道路与回路,证明：设 是简单图，当 时，是连通图。证明：假定 是非连通图，则它至少含有2个连通分支。设分别是。其中 由于 是简单图，因此,道路与回路,由于，所以 与已知条件矛盾，故 是连通图。,2.3 欧拉道路与回路,欧拉道路与回路,1736年瑞士著名数学家欧拉(Leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。成功地回答了，图中是否存在经过每条边一次且仅一次的回路。,欧拉道路与回路,欧拉道路与回路,定义 无向连通图 中的一条经过所有边的简单回路(道路)称为 的欧拉回路(道路)。定理 无向连通图 存在欧拉回路的充要条件是 中各结点的度都是偶数。,欧拉道路与回路,定理的证明：1.必要性：若 中有欧拉回路，则 过每条边一次且仅一次。对任一结点 来说，如果 经过进入，则一定通过另一条边从 离开。因此结点 的度是偶数。2.充分性：由于 是有穷图，因此可以断定，从 的任一结点出发一定存在 的一条简单回路。这是因为各结点的度都是偶数，所以这条简单道路不可能停留在以外的某个点，而不能再向前延伸以致构成回路。,欧拉道路与回路,推论 若无向连通图 中只有2个度为奇的结点。则 存在欧拉道路。证明：设和是两个度为奇数的结点。作，则中各点的度都是偶数。由定理，有欧拉回路，它含边，删去该边，得到一条从到的简单道路，它恰好经过了 的所有边，亦即是一条欧拉道路。,欧拉道路与回路,推论 若有向连通图 中各结点的正，负度相等，则 存在有向欧拉道路。其证明与定理的证明相仿。,欧拉道路与回路,例2.3.3 设连通图G=(V,E)有k个度为奇数的结点，那么E(G)可以划分成k/2条简单道路。证明：由性质，k是偶数。在这k个结点间增添k/2条边，使每个结点都与其中一条边关联，得到G，那么G中各结点的度都为偶数。由定理，G包含一个欧拉回路C。而新添的k/2条边再C上都不相邻。所以删去这些边后，我们就得到由E(G)划分成的k/2条简单道路。,2.4 哈密顿道路与回路,哈密顿道路与回路,哈密顿道路与回路,定义 无向图的一条过全部结点的初级回路(道路)称为G的哈密顿回路(道路)，简记为H回路(道路)。哈密顿回路是初级回路，是特殊的简单回路，因此它与欧拉回路不同。当然在特殊情况下，G的哈密顿回路恰好也是其欧拉回路。鉴于H回路是初级回路，所以如果G中含有重边或自环，删去它们后得到的简单图G，那么G和G关于H回路（道路）的存在性是等价的。因此，判定H回路存在性问题一般是针对简单图的。,哈密顿道路与回路,定理 如果简单图G的任意两结点 之间恒有，则G中存在哈密顿路。,哈密顿道路与回路,推论 若简单图 的任意两结点 和 之间恒有，则 中存在哈密顿回路。推论若简单图 中每个结点的度都大于等于，则 有 回路。,哈密顿道路与回路,引理设 是简单图，是不相邻结点，且满足，则 存在 回路的充要条件是 有 回路。定义若 和 是简单图 的不相邻结点，且满足，则令 对 重复上述过程，直至不再有这样的结点对为止。最终得到的图为 的闭合图，记作。,哈密顿道路与回路,引理简单图 的闭合图 是唯一的。定理 简单图 存在哈密顿回路的充要条件是其闭合图存在哈密顿回路。推论 设 是简单图，若 完全图，有 回路。,