为什么利用图很容易求得渡河问题有几解

有一则古老的智力游戏题，它是以童话的方式流传下来的，大意如下：有一个人带着一只狼、一只羊、一筐卷心莱来到河边。河边正好有一条空着的小船。那人想将狼、羊、卷心菜从河的东岸都带到西岸去。可是船很小，每次都只能让他带走一样东西，如果带两样东西上船，船就会沉没。另方面，如果无人照管，狼会吃掉羊，羊又很喜欢吃卷心菜，所以，狼与羊、羊与菜，在人不在的情况下，是不能放在一起的。怎么办呢？他应当采取什么样的渡河方案，才能把狼、羊、菜都安全地带到河西去呢？

这个问题称为渡河问题，也有人称为狼、羊、菜问题。对于多数人而言，要解决这个问题是不会有什么困难的，试上几次，就能给出一个符合要求的答案。但是如果要求回答：此题共有多少解？人将狼、羊、卷心菜都安全地带到河的西岸去，至少需要摆渡几次？回答起来，恐怕就比较困难了。

其实，这个问题应用欧拉解决七桥问题的思想方法，用图来解，是很容易求得答案的。

先想一想，可以允许出现的状态有几种。这里所说的“允许”，就是说不能出现狼吃羊、羊吃菜的现象。稍加分析可知，为保证安全渡河，可以允许出现的状态共有以下10种：

接下来，如图1所示，将10种允许出现的状态，每一种都用一个小圆圈表示。每个圆圈内标出这时河东岸有些什么，未标出的这时自然都在河的西岸。圆圈实际上就是图的顶点的夸张形式，它的作用与顶点一样。

图1

人划着船，每渡河一次，都会引起一次状态的转变。例如，当人、狼、菜在东岸，羊在西岸时，如果仅仅是人渡过河去，则河东岸剩下狼与菜，西岸出现了人与羊；如果人带着狼渡河，则河的东岸仅剩下菜，西岸出现人、狼、羊；又若人带菜过河，则河东岸剩下狼，河西岸出现人、羊、菜。在两种可以互相转变的状态之间（即在两个圆圈之间）都连条线（在图中称为“边”），就会得到图2所示的样子。这个图表明了渡河的所有各种情况，十分直观，使人一目了然。

从图2中可以看到，在渡河问题中，人想把狼、羊、菜都安全地带到河的西岸，就相当于从“人、狼、羊、菜”这个圆圈出发，找出一条到无物圈的路线。这是很容易做到的。图中每条边都代表摆了一次渡。

图2

在摆渡过程中，如果要求每种状态不重复出现，那么从图2中可以看出，渡河问题共有两解。还明显地可以看出，人把狼、羊、菜都安全地从河的东岸带到河的西岸，至少要摆渡7次。