鸡；因此，必须先带鸡过河，而后空船返回。

第二次渡河，既可带狗，亦可带米。不妨先带狗，过河后，若将狗放下，空船返回，狗要吃鸡，因此，必须把鸡带回。第三次渡河，把米带过河，而后空船返回。第四次渡河，再把鸡带过河即可。

第二次渡河，若先带米，过河后.再把鸡带回。第三次渡河，带狗过河，空船返回。第四次渡河，将鸡带过河即可。

用图论解法：假设人、狗.鸡、米未过河时.均用1描述，过河后, 用0描述。按照(人、狗、鸡、米)的顺序，将可能的10种状态用如下1 个图来表示，其连线是可转移的状态。

已过河

(1/ 1 > 1 >1)A\^F(0 ,0,0,0)

(1> 1 , 1 ,> 0 / 0 , 1)

(1/ 1 P0 >> 0 > 1 > 0)

(1,0 , 1 ,-^•1(0 , 1 > 0 > 0)

(1，0 ,1，0)E^

在图上找1条从顶点(1, 1f 1f 1)到(0, 0, 0, 0)的路就是问题的解。易见有2条路(如图所示)：

A T J T C T G T D T H T E T F；

A T J T C T I T

B T H T E T F。

我们把上图改画成下图就更潸楚了。

I B

14. 3对夫妇过河

为了叙述方便，设3位丈夫为A. B. C,他们的妻子分别为a、b、Co 首次过河，可以某对夫妇先过，然后丈夫返回；亦可以2位妻子先过，返回1位妻子。不妨让a、b先过.b返回。