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
推荐
猜你喜欢
- 一根2米长的绳子,第一次用去4/1米,第二次用去全长的25%,剩下( )米?
- 关于高原和盆地特点正确叙述是
- 如图是一个形状为平行四边形的花圃,经测量,他的周长为48米,两条高de,df,分别为5米,7米,求这个平行四边
- If you want to have a good ______with your ______,you should be ____to them.(friend)
- 悄悄这个词第二个悄读不读轻声?
- 仿写《草虫的村落》
- 直角三角形斜边上的中线等于斜边的一半这个定理可以逆推吗?
- 单词T结尾的现在分词的话双写不双写?