2021年美国数学奥林匹克竞赛中的图论问题——到底难在哪里？

普拉纳国家公园由几条在交叉路口交汇的小径组成。。每条小路的两个端点都在两个不同的路口，而每个路口正好是三条小路的端点。小路只在路口相交。最后，没有小路在相同的两个路口开始和结束。下面是一个可能的公园布局的例子，其中有六个路口和九条小路。

一个游客在公园里的行走情况如下：她从一个路口开始，沿着一条小路行走。在第一条小路的尽头，她进入了一个路口并向左转。在下一个路口，她向右转，以此类推，在每个路口交替进行左转和右转。她这样做，直到她回到她开始的那个路口。在公园所有可能的布局中，她在行走过程中进入任何路口的最大可能次数是多少？

这个问题的陈述非常冗长，但是我们有简单图（Simple Graph）工具可以帮助理解（默认为平面图）。

简单图是指任意两个顶点之间没有超过一条边，也没有边的起点和终点在同一个顶点的图。换句话说，一个简单的图是一个没有循环和多条边的图。

下面这个简单图中，每个顶点的度数为3（顶点的度数是指和该节点相关联的边的条数）。 让我们看看根据题目要求的方式散步时，在每个顶点左右交替进行会发生什么。

我在每条路径上用字母 "L "和 "R "来表示散步者是左转还是右转。题目要求的是：进入任何路口的最大可能次数。在上面显示的第一条路径中，这个数字是1。

再选择几条路径，我们发现有可能进入一个路口两次。

为了考虑其他可能的行走方式，以更有规律的方向重新绘制图形是有帮助的，这样我们就可以看到对称性。

一旦我们认识到这种对称性，我们就可以看到，在这个公园里没有太多的 "不同 "路径。通过不断尝试，我们发现不可能进入任何路口两次以上。

但这个问题不仅仅是问所提供的公园的例子，而是问 "公园所有可能的布局"。

我认为有两个问题值得考虑。

1. 对公园的可能布局是否有限制，以帮助我们找到最大值？
2. 为什么会有一个最大值，也就是说，为什么不可能在一个无限循环中不断地进入同一个路口？

可能的公园布局

从考虑最简单的情况开始。给出的例子有6个路口（顶点），但是否有可能出现顶点更少的公园？我发现2个顶点是不可能的，因为 "没有小路在同一个路口开始和结束"，也就是说，这个图形是 "简单 "的。

我试着画一个有3个路口的公园，但没有成功，我意识到没有奇数个路口是可行的。因为对于n个路口，边的总数是3n÷2，（与每个顶点相连的3条边，除以2以避免重复计算）。如果n是奇数，这个总数就不是一个整数。

有一个可能有4个路口的公园，但不可能多次进入一个路口。

例子中给出的是一个有6个路口的公园，我没有找到具有6个路口的不同情况，所以我转到了8个路口。

这个图形是我熟悉的立方体的平面嵌入。它让我意识到，所有符合给定条件的公园都可以表示为多面体。这是一个切入点。8个路口的公园不允许任何路口进入一次以上。

对于10个路口，遵循类似的结构，有一个内部和外部的五边形。并尝试了一些不同的走法，我发现有可能进入一个路口3次！

一个路口进入3次的例子

想出这个结构后，我觉得3可能是最大的可能。

另外，这时我已经意识到，可能的公园有无限的变化，为了解决问题，我不能轻易地进行分类。

• 可能的公园布局情况

因此，我决定从我之前提出的关于无限循环的可能性的问题出发，重新审视这个问题。

排除无限循环的可能性

根据题意，散步者回到起点时将会停止。那么，有没有可能进入一个不包括起点的无限循环？这个无限循环会是什么样子呢？

在不失一般性的前提下，我们假设散步者进入了假设的无限循环，并向右转。

这意味着它必须以左转来结束这个循环，然后再右转来重复这个循环。但由于她是从另一个方向来的，右转会使她离开循环，如上面的动画所示。

因此，我们已经表明，无论任何路口的最大入口数是多少，它至少是有限的！这就是我们的观察。

关键是观察，路径是确定性的

一个重要的观察结果是，一旦我们知道散步者是在某条小路（边）上向左转还是向右转，接下来的每条小路就只有一种可能的选择。同样地，前一条小路也只有一种可能的选择，以此类推。所以她的整个路径是完全确定的。

我们也已经表明，不可能进入一个无限的循环，因为她回到起点后就停止了。所以不可能在一条特定的小路上左转两次，也不可能在一条特定的小路上右转两次。

这就把最大的可能上界减少到了6个（向左或向右转入3条小路的每个路口）。

但它实际上有可能实现吗？

当她进入一个路口左转时，她必须右转离开（反之亦然）。所以我应该在图中加入出口。它将有6个箭头进入，和6个箭头出来。

总之，有些地方不对。为了走完所有这些路径，她必须从她已经走过的路回来，但方向是相反的。

在下图中，只包括了4个箭头。橙色的箭头表示她左转进入路口，右转出来，蓝色的箭头表示她后面需要走的相反方向。

为什么这是不可能的？

正如我们之前所说，一旦我们知道路线和方向（左或右），整个路径就完全确定了。特别是，一旦我们知道她沿着橙色箭头左转进入路口，我们就知道她的整个路径形成了一个循环，从起点开始，在某个时间返回那里。

为了沿着蓝色箭头行走，她需要走这个完全相同的循环，但方向相反。这是不可能的。一旦开始走这条路，就真的没有回头路了！这限制了可能的最大数量。

这个限制将一个路口的最大可能进入次数限制为3次。下面显示了两种可能性，根据进入-退出顺序用颜色编码。

我们已经展示了一个实现最大3次的公园的例子（上面的五边形棱形结构）。

所以在公园所有可能的布局中，3是她在行走过程中进入任何路口的最大可能次数。

图论真了不起

图论是离散数学的一个迷人的领域，有很多实际应用。特别是世界网络和社交媒体的出现。