二章道路与回路2道路与回路.pptVIP

第二章 道路与回路2.1道路与回路 定义2.1.1 有向图 中，若边序列 　　　　　，其中 　　　　 满足　是 的终点，　是 　的始点，就称 是 的一条有向道路。如果　的终点也是 的始点，则称 是 的一条有向回路。 道路与回路 如果 中的边没有重复出现，则分别称为简单有向道路和简单有向回路。进而，如果 中结点也不重复出现，又分别称它们是初级有向道路和初级有向回路简称为路和回路。显然，初级有向道路(回路)一定是简单有向道路(回路)。 道路与回路 定义2.1.2 无向图 中，若点边交替序列 　　　　　　　　　满足　　 是　的两个端点,则称 是 中的一条链或道路。如果　　　，则称 是 中的一个圈，或回路。 如果 中没有重复出现的边，称之为简单道路或简单回路，若其中结点也不重复，又称之为初级道路或初级回路。 道路与回路 定义2.1.3 设 是无向图，若 的任意两结点之间都存在道路，就称 是连通图，否则称为非连通图。 如果 是有向图，不考虑其边的方向，即视为无向图，若它是连通的，则称 是连通图。 若连通子图 不是 的任何连通子图的真子图，则称 是 的极大连通子图，或称连通支。显然 的每个连通支都是它的导出子图。 道路与回路 定义2.1.4 设 是简单图 中含结点数大于3的一个初级回路，如果结点 和 在 中不相邻，而边 ，则称 是 的一条弦。 道路与回路 证明：若对每一个 ，都有 ，则 中必含带弦的回路。 证明：在 中构造一条初级道路 ，不妨设 ， 。由于 是极长的初级道路，所以 和 的邻接电都在该道路 了。由已知条件， ，不妨设 。其中 ，这时 是一条初级回路，而 就是该回路中的一条弦。 道路与回路 定义2.1.5 设 是无向图，如果 可以划分为子集 和 ，使得对所有的 ， 和 都分属于 和 ，则称 是二分图。 道路与回路 证明：如果二分图 中存在回路，则它们都是由偶数条边组成的。 证明：设 是二分图 的任一条回路，不妨设 是 的始点，由于 是二分图，所以沿回路 必须经过偶数条边才能达到某结点 ，因而只有经过偶数条边才能回到 。 道路与回路 证明：设 是简单图，当 时， 是连通图。 证明：假定 是非连通图，则它至少含有2个连通分支。设分别是 。其中 由于 是简单图，因此 道路与回路 由于 ， 所以 与已知条件矛盾，故 是连通图。 2.3 欧拉道路与回路 欧拉道路与回路 1736年瑞士著名数学家欧拉(Leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。成功地回答了，图中是否存在经过每条边一次且仅一次的回路。 欧拉道路与回路 欧拉道路与回路 定义2.3.1 无向连通图 中的一条经过所有边的简单回路(道路)称为 的欧拉回路(道路)。 定理2.3.1 无向连通图 存在欧拉回路的充要条件是 中各结点的度都是偶数。 欧拉道路与回路 定理2.3.1的证明： 1.　必要性：若 中有欧拉回路 ，则 过每条边一次且仅一次。对任一结点 来说，如果 经过　进入 ，则一定通过另一条边　从 离开。因此结点 的度是偶数。 2.　充分性：由于 是有穷图，因此可以断定，从 的任一结点　出发一定存在