证明：无向完全图转为有向图后必有H路径证明：无向完全图转为有向图后必有哈密顿路径.不知如何证明,rchlch:非常感谢你的回答,我想应该是正确的.可是我没看懂这句否则就存在边(v,vk),(v1,

Question

证明：无向完全图转为有向图后必有H路径
证明：无向完全图转为有向图后必有哈密顿路径.不知如何证明,
rchlch:非常感谢你的回答,我想应该是正确的.可是我没看懂这句
否则就存在边(v,v_k),(v_1,v).那么就一定有一个i(1≤i≤k-1),使得(v_i,v)与(v,v_i+1)同时存在.此时v_1,v_2,……,v_i,v,v_i+1,……,v_k就是一条Hamiltonian路.
我想你的意思是不是由于出度和入度相等,所以有(v_i,v)与(v,v_i+1).可是我不能理解为什么一定是v_i,v_i+1两个连续的值呢?有没可能不是那条H路上连续两个点的出度和入度?

Answer 1

对顶点数n使用数学归纳法.设命题对不超过k个顶点的有向完全图成立,那么当n=k+1时,从k+1个顶点中任取一个v,在完全图K_(k+1)中去掉v以及与之相邻的边.根据归纳假设,在去掉v之后的图中存在Hamiltonian路,设为v_1,v_2,…...