尼基托夫城的道路均可双向行车，现决定在两年内全部翻修道路，为此在第一年中，有些道路线成为单行线；到了第二年，这些道路恢复双向行车，其余的道路则限制为单向行车线。现知，在翻修过程中任何时刻，都能从城市中的任何一个地点驱车前往另外任何地点。证明，可将基托夫城中的道路全部改为单行线，使得仍可由城中任一地点驱车前往另外任何地点。

证：首先将第一年修路时作为单行线的道路及其指定的单向行车方向确定下来；将这些道路染为红色，并标上原来的箭头。

我们再来分两个阶段解答问题。在第一阶段中，我们来增加红色道路的数目，并为它们标上箭头，使得在增加了它们以后，题目中的条件仍可满足，真到达到了如下程度时，我们就停止增加新的红色道路：即对任意两个用由A指向B的红色箭头直接连接的路口A和B，又都存在仅仅沿着红色箭头头即可由B到A的路径（即存在由红色箭头构成的环路）。在第二阶段中，我们来给出满足题目条件的道路走向，从而最终完成证明过程。具体作法如下：

第一阶段：设路口A和B已用红色箭头A→B连接，但由B至A却没有用红色道路。即在任何由B通向A的路径上，并不都具有红色箭头，亦即存在“空”路段。我们来任意取出一条由B至A的路段。在这条路径所包含的所有红色路段上，所标示的方向显然都与箭头A→B一致（因为由B至A有这条路径作为通道）；我们只要照此（即与箭头A→B一致的方向）将“空路段”标定方向并染为红色，就可使得由B能沿着红色箭头走到A了。由于城市道路的数量是有限的。所以在若干步以后，我们就得到了许多由红箭头构成的环路，亦即许多由红色环路围成的“小岛”。

第二阶段：我们再将未包含在红色环路中的路段都染上绿色；在这些路段上目前都还存在着两个方向。但由于它们都是第二年修路时的单行线，于是我们可为每一段绿色道路都标上一个箭头，使之与第二年修路时所标的方向一样，这样一来，全城的道路都已标定了行车方向。

下面就来证明，按着所引入的方向，都可以沿着道路由任意一个路口A到达任一另外一个路口B。事实上，如果取这样一条由A至B的路段，使它恰是第二年修路时所走过的，那么现在在它上面就可能会有红色箭头也有绿色箭头。沿着绿色箭头，我们总是去往应去的方向，但沿着红色箭头却未必总是如此。例如，在我们所取的路径A…XY…B中的路段XY上，所标的红色箭头是由Y指向X的（即不能沿着路段XY通行），那么我们就可以沿着那样一条补上箭头Y→X后就成为第一阶段所构造的的红色环路的路径由X走到Y，由此所得到的由A至B的路径即为所求。

Tags：方法, 策划, 统筹, 问题.
No Responses' | Add Comments
本文网址：http://www.logmath.com/article/2007/11/to-a-one-way-street.html