复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)21/30
团购合买资源类别:文库,文档格式:PPT,文档页数:1,文件大小:39.5KB
定理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的有向 回路
点击进入文档下载页(PPT格式)
已到末页,全文结束