对于任意给定的正数 $\varepsilon$,试证明对于全部有限的正整数v,任意含有v个顶点并含有至少 $(1+\varepsilon)v$ 条边有两个等长的简单圈。
【难度】
【出处】
2019第十一届罗马尼亚大师赛
【标注】
【答案】
【解析】
固定一个正实数 $\varepsilon$,设 $G$ 是一个有 $v$ 个顶点的图,并且有至少 $(1+\varepsilon)v$ 条边。所有的简单圈都具有不同的对偶长度。
假设 $\varepsilon^{2}v\geqslant 1$,我们来针对 $G$ 中的简单图的个数来寻找一个和 $v$ 线性相关的上界和 $v^2$ 线性相关的下确界。
因为G中的简单图最多含有v个顶点,每个长度最多含有其中一种,所有G中至多含有v个不同的对偶简单圈。这就建立了我们想要的上界。
对于下界,我们针对G图中的各个元素来考虑他们的生成树。组合起来形成一个生成树林F。设集合A包括F中的所有边,集合B为G图中剩下的边。显然我们可以得到 $\arrowvert A \arrowvert \leqslant v-1$,所以 $\arrowvert B \arrowvert \geqslant (1+\varepsilon)v-\arrowvert A \arrowvert \geqslant (1+\varepsilon)v-(v-1)=\varepsilon v +1>\varepsilon v$ 。
对于B中的任意一条边b来说,和F组合即可得到一个特别的经过b的简单圈 $C_b$,设 $S_b$ 为A中经过Cb的集合。$$\sum \arrowvert S_{b} \arrowvert> \arrowvert B \arrowvert^{2} /2 > \varepsilon^{2}v^{2}/2$$得到了我们想要的下界。
答案 解析 备注
0.109637s