首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

关于竞赛图怎么证明至少有一个点能够一步或两步就能到达所有的点

2012-02-28 
关于竞赛图如何证明至少有一个点能够一步或两步就能到达所有的点?如题,这东西证明真难啊!大家来讨论一下![

关于竞赛图如何证明至少有一个点能够一步或两步就能到达所有的点?
如题,这东西证明真难啊!大家来讨论一下!

[解决办法]
这个这个是不是老张的作业?
[解决办法]
数学归纳法,分情况讨论

假设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为满足条件的点

热点排行