离散结构题,对边数用数学归纳法(p=1,2,3的时候不用考虑)
设结论在p=k(k>=3)时成立,即至少有k条边的k阶图必含圈,现考虑p=k+1情形,设G是至少有k+1条边的k+1阶图
求之后的解答步骤!谢谢!
后续肯定要用递归自顶向下思想,减去一个点什么的让问题规模缩小到k
数学归纳法不会,求解
离散结构题,对边数用数学归纳法(p=1,2,3的时候不用考虑)
设结论在p=k(k>=3)时成立,即至少有k条边的k阶图必含圈,现考虑p=k+1情形,设G是至少有k+1条边的k+1阶图
求之后的解答步骤!谢谢!
后续肯定要用递归自顶向下思想,减去一个点什么的让问题规模缩小到k
数学归纳法不会,求解
若G中存在一个点A,A只与一条边a关联,删掉A和a,剩下G'为k条边的k阶图,必含圈,故G含圈;否则,G中所有点关联边数大于等于2,必含圈(记不太清楚这个结论能不能直接用了,不能的话就说明一下构造就行)