鸽子的等级秩序是什么？

Question

我正在阅读由埃里克松教授发布的关于图论的问题, 这是来自我的母校。其中有一道非常独特的问题涉及到鸽子和它们天生形成的啄食顺序。这个问题如下：

每当一群鸽子聚集在一起时，它们本能地建立了一个等级制度。对于任何一对鸽子，其中一只鸽子总是啄另一只鸽子，将其驱赶离开食物或潜在配偶。同一对鸽子总是选择相同的啄食顺序，即使分开多年，无论周围有什么其他鸽子。令人惊讶的是，整个啄食顺序可以包含循环-例如，鸽子A啄击鸽子B，鸽子B啄击鸽子C，鸽子C啄击鸽子A。

证明任何有限的鸽子集合都可以从左到右排列，以便每只鸽子都啄击其左边的鸽子。

由于这是关于图论的问题，我首先想到的是这是否只是要求关系图的拓扑排序（关系是啄食顺序）。使这个问题更加复杂的是事实上鸽子之间可能存在循环依赖关系。如果我们有一个循环依赖关系，如下所示：

A->B->C->A

其中A啄击B，B啄击C，C反过来啄击A

如果我们按照问题建议的方式表示它，我们会得到以下结果：C B A。

但是上述行排序没有考虑C和A之间的顺序。

我有另一种通过数学归纳解决它的想法，其中基本情况是将两只鸽子按其啄食顺序排列，假设n只鸽子的啄食顺序排列有效，然后证明它对n+1只鸽子也成立。

我不确定我是否走了错误的道路。关于如何分析这个问题的一些见解将会很有帮助。

谢谢。

- sc_ray

---

不是我的专业领域，但从我简单的逻辑来看，如果它是圆形或循环的，那么显然它们不能在一条直线上排列。相互连接的圆圈，类似于奥林匹克标志，但不是一行直线。 - MJB

如果你有四只鸽子，那么就会有6对鸽子。线性形式将涉及其中的三对。因此，你将不得不忽略一些配对。根据我理解的任务，要展示的是你总是可以选择配对来产生一个线性顺序，而不是存在一个代表所有配对的线性顺序。 - Pete Kirkham

3只鸽子的循环案例也让我疑惑不解，但是后来我再次检查了问题的措辞：

每只鸽子啄食它左边的鸽子。

这似乎并不要求C的左边有任何东西，只需要你能够排列鸽子在某一行中，以便每只有另一只在它左边的鸽子都啄食它。所以 C B A 是有效的，B A C 也是有效的，A C B 也是有效的。同样地，如果你有 A->B，A->C 和 B->C，排列鸽子在一排中无法同时传达 A->B 和 A->C。但是在这种情况下，C B A 是(唯一的)答案。有趣的问题！ - anton.burger

似乎有人之前研究过这个问题 :) “对于有限数量n个顶点的任何锦标赛都包含哈密顿路径，即所有n个顶点上的有向路径（Rédei 1934）。” http://en.wikipedia.org/wiki/Tournament_%28mathematics%29 - Dr. belisarius

@belisarius：没错，而且Vladimir所提供的就是证明！ - Aryabhatta

Answer 1

我将证明归纳法确实成立（a>b表示a比b高）：

1. 对于k=2，显然成立。
2. 假设对于k=n，总是存在所需的顺序，让我们证明它存在于n+1。从给定的n+1只鸽子中选择并排序任何n只鸽子（A1>A2...>An），并让C是第（n+1）只鸽子。
   如果C比A1高，则可以将其添加到“行”的开头，并证明该语句成立。如果A1比C高，则让我们将C与A2进行比较-如果C比A2高，则可以将其插入A1和A2之间，该语句成立。如果没有-请重复比较过程，直到最后一对-A（n-1）和An，随着过程进行，我们假设A（n-1）> C。如果C>An，则可以将C插入A（n-1）和An之间，如果不是，则可以将其插入“行”的末尾。

证毕

P.S. 请注意，“啄食周期”不一定存在-如果我们将鸽子编号从1到n并假设鸽子啄食另一个鸽子，如果他的编号更大，则显然可以将它们排列在一行中，但不能排成一个循环，以便每个鸽子啄食他的左邻居。

P.P.S. 该证明还提供了构建所需顺序的算法。

- Vladimir

---

很棒的答案。我也是这么想的。问题要求有限集是否可以排列，证明正好做到了这一点。谢谢！ - sc_ray

Answer 2

你有没有考虑构建一个有向图，然后寻找一条哈密顿路径，使得每个点（鸽子）只被访问一次？哈密顿路径应该揭示出这个序列 - 这不是一个证明，只是一个解决方案。

- Grembo