2019RMM第三题完整版解答

作者 | Peter 编辑 | 罗数君

文 3210字  阅读时间约 8分钟

本答案是RMM官方答案中，署名罗教授版本的翻译版。由罗教授提供思路，RMM官方委员会进行推理论证，罗博深数学实习生Peter进行翻译、注释。

题目：Given any positive real number ε, prove that, for all but finitely many positive

integers v, any graph on v vertices with at least(1 + ε)v edges has two distinct simple cycles of equal lengths.

给定任意正实数ε，请证明，除了有限个反例之外，所有正整数v都满足：所有由v个顶点和至少(1 +ε)v 条边构成的图，都存在一对等长的不同简单圈（注意，简单圈不允许重复出现相同的顶点）。

注：本证明旨在帮助大家理解题目背后的思想，因此省略了很多严谨的细节。如果你不满足于这篇概要，欢迎访问RMM官网（http://rmms.lbi.ro/rmm2019/index.php?id=problems_math）查看完整的证明。如果有其他疑问，欢迎在文章下留言，我们会尽全力解答的哦~

在开始证明之前，我们先来介绍几个图论中基本的概念：

顶点（vertex）：图论中图（graph）的基本组成部分是顶点（vertex）和连接顶点的边（edge）

边（edge）：连接两个顶点的线叫边（edge）

相邻（adjacent）：如果两个顶点之间存在一条边，我们说它们是相邻的。

度数（degree）：对于任何一个顶点v，与它相临的所有顶点的总数叫做这个顶点的度数, 用deg(v)表示。

邻域（neighborhood）：对于任何一个顶点v，与它相临的所有顶点组成的集合叫做v的邻域，用N(v)表示。

路径（path）：图论中，路径的本质是一个顶点序列，它的每个顶点有一条边连接该序列中下一顶点。一条路径可能是无穷的，但有限路径有一个最先顶点，称为起点，和最后顶点，称为末点，这两个顶点都叫做端点。

圈（cycle）：图论中，圈从一个顶点起步，沿着不重复的边，不重复的顶点为途径，回到起点的闭合路径。

连通性（connectedness）：如果对于图中的任何两个顶点，我们都能找到一条路径以它们为两个端点，那我们说这个图是联通的。

树（tree）：如果图符合以下标准：

1．边的数量是顶点数量减一  2．图是联通的3．图中不存在圈

我们说这幅图是树。

环（loop）：一条连接顶点本身的边

围长（girth）：图中最短圈包含的边数，比如一个正方形的围长就是4

Little o: 我们说 f(n) = o(g(n)) 当且仅当 ：存在c > 0 ，k > 0 使得0 ≤ f(n) < cg(n) 对于任何n ≥ k。k 的取值与n相关, 但是与c无关。

引理：任意固定的正实数δ，都满足：在v个顶点上，且围长至少为δv的图，最多有v+ o(v)条边。

证明：

喜欢这篇文章吗？欢迎给我们留言，探讨有趣的数学问题，如果你还想看其他的相关内容，也可以向我们提出来哦！ 

相关推荐