> 数学 >
3.设G为n阶有向简单图,每个点的入度大于等于3,证明G中存在长度大于等于4的圈.
人气:157 ℃ 时间:2020-06-25 13:50:04
解答
设AB为G的一条最长路径
设C、D、E为A的3个前驱结点,
则C一定在AB上(否则路径CAB比最长路径AB还长)
同理D、E也在AB上,
不失一般性,存在路径 A->C->D->E->B (E和B也可能是同一点,不过不影响结论)
故存在长度至少为4的环A->C->D->E->A
推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版