定理5.17:任何一个强连通的竞赛图G 必是哈密顿有向图。 证明采用归纳法 (1)G包含长度为3的有向回路 对任意v∈VG,将顶点集分成两类,一类 是以v为起点的,另一类是以v为终点的 假设G中有包含长度为k的有向回路 (k<n), 下面证明G中必有包含长度为k+1的有向 回路
定理 5.17:任何一个强连通的竞赛图G 必是哈密顿有向图。 证明采用归纳法. (1)G包含长度为3的有向回路. 对任意vV(G),将顶点集分成两类,一类 是以v为起点的,另一类是以v为终点的. 假设G中有包含长度为k的有向回路 (k<n), 下面证明G中必有包含长度为k+1的有向 回路