关于竞赛图如何证明至少有一个点能够一步或两步就能到达所有的点?
如题,这东西证明真难啊!大家来讨论一下!
[解决办法]
这个这个是不是老张的作业?
[解决办法]
数学归纳法,分情况讨论
假设n阶竞赛图满足条件,设为点A0--An
A0为满足条件的点,A0经过一步到达A1--Ak,经过两步到达A(k+1)--An
新点B
1) A0--Ak中,存在Ai-->B的有向线段
-----证明成功,A0依然为满足条件的点
2) A0--AK中,不存在Ai-->B的有向线段,即B->Ai(0<i<k)
-----证明成功,B为满足条件的点