作业帮 > 数学 > 作业

3.设G为n阶有向简单图,每个点的入度大于等于3,证明G中存在长度大于等于4的圈.

来源:学生作业帮 编辑:灵鹊做题网作业帮 分类:数学作业 时间:2024/05/03 07:54:05
3.设G为n阶有向简单图,每个点的入度大于等于3,证明G中存在长度大于等于4的圈.
3.设G为n阶有向简单图,每个点的入度大于等于3,证明G中存在长度大于等于4的圈.
设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