1、第二章 道路与回路2.1道路与回路l 定义 2.1.1有向图 中，若边序列 ，其中满足 是 的终点， 是 的始点，就称 是 的一条有向道路。如果 的终点也是的始点，则称 是 的一条有向回路。道路与回路l 如果 中的边没有重复出现，则分别称为简单有向道路和简单有向回路。进而，如果 中结点也不重复出现，又分别称它们是初级有向道路和初级有向回路简称为路和回路。显然，初级有向道路 (回路 )一定是简单有向道路 (回路 )。道路与回路l 定义 2.1.2无向图 中，若点边交替序列 满足 是 的两个端点 ,则称 是 中的一条链或道路。如果 ，则称 是 中的一个圈，或回路。如果 中没有重复出现的边，称之为简
2、单道路或简单回路，若其中结点也不重复，又称之为初级道路或初级回路。道路与回路l 定义 2.1.3设 是无向图，若 的任意两结点之间都存在道路，就称 是连通图，否则称为非连通图。如果 是有向图，不考虑其边的方向，即视为无向图，若它是连通的，则称 是连通图。若连通子图 不是 的任何连通子图的真子图，则称 是 的极大连通子图，或称连通支。显然 的每个连通支都是它的导出子图。道路与回路l 定义 2.1.4设 是简单图 中含结点数大于 3的一个初级回路，如果结点 和 在 中不相邻，而边，则称 是 的一条弦。道路与回路l 证明：若对每一个 ，都有 ，则 中必含带弦的回路。证明：在 中构造一条初级道路 ，不
3、妨设 ， 。由于 是极长的初级道路，所以 和 的邻接电都在该道路 了。由已知条件， ，不妨设 。其中 ，这时 是一条初级回路，而 就是该回路中的一条弦。道路与回路l 定义 2.1.5设 是无向图，如果 可以划分为子集 和 ，使得对所有的 ， 和 都分属于 和 ，则称 是二分图。道路与回路l 证明：如果二分图 中存在回路，则它们都是由偶数条边组成的。证明：设 是二分图 的任一条回路，不妨设 是 的始点，由于 是二分图，所以沿回路 必须经过偶数条边才能达到某结点 ，因而只有经过偶数条边才能回到 。道路与回路l 证明：设 是简单图，当 时，是连通图。 证明：假定 是非连通图，则它至少含有 2个连通分支。设分别是 。其中由于 是简单图，因此 道路与回路由于 ， 所以 与已知条件矛盾，故 是连通图。
