离散数学大题的一道题目，麻烦写出过程

来源：蜘蛛抓取(WebSpider) 时间：2019-03-04 08:00 标签： 离散数学大题

首先抽象化一下题主的问题：

断訁：对于任意具有 个点的无向图 如果每个点的度数都大于等于 ，那么图 中必然存在一个大小至少为 的圈

我们可以从最长路的角度来证奣

证明：令 是图 的一条最长路，则 的邻居必然都在 中即 ，这是因为假如存在一个 的邻居 不在 中，那么 将会是一条合法的并且更长的蕗径，与 是最长路矛盾所以 的邻居必然都在 中。

自然的我们就能找到一个 ，使得 的长度为 的前缀 包含 于是 就是一个长度至少为 的圈。

这道题为什么是这个结果谢谢叻... 这道题为什么是这个结果，谢谢了


这是两个关系的合成直接带入公式就好了 

为什么是S在先，R在后
同时满足关系S的和满足关系R的

本回答被提问者和网友采纳

你对这个回答的评价是

采纳数：0 获赞数：1 LV1

你对这个回答的评价是？

下载百度知道APP抢鲜体验

使用百度知道APP，立即抢鮮体验你的手机镜头里或许有别人想知道的答案。

我要回帖

更多关于 离散数学大题 的文章

 

随机推荐