文｜冷丝

栏目｜丝说中小学教育

不管你是小朋友还是大朋友，或者是成年人，一定在很小的时候就听哥哥姐姐说过《渡河》的数学题：一个人挑着白菜，牵着一条狗、一只羊要渡河，但是船太小，一次只能允许这个人带3样中的一样过河，而且，羊或者狗不能单独同白菜呆在一起，因为菜会被吃掉。你该怎么过河呢？

数学学霸们的开学典礼

我们在当年就知道了最终的答案——2种渡河方式，但为什么会是这个答案？这个答案是通过什么计算方法得来的？

冷丝今天想说的是，这个难题困扰了我们整个少儿时代，因为涉及的知识只能在大学里的应用数学中解决。

1000多年前的数学游戏难题不断演化，最终成功地被“图论”方法解决。

这道难题其实是在1000多年前就被提出来，英国著名学者Alcuin提出过一个古老的渡河问题，即狼、羊和卷心菜的渡河问题。随着时代的发展，狼被替换成了狗，卷心菜成了大白菜，羊还是那只羊。

所谓应用数学“图论”中的图，就是数据结构和算法学中最强大的框架之一，现在是计算机科学的重要课程之一，几乎可以用来表现所有类型的结构或系统，从交通网络到通信网络，从下棋游戏到最优流程，从任务分配到人际交互网络，图都有广阔的用武之地。

数学课堂

说简单一点，你就要学会用“图”的概念，运用形象的思维方式来解决现实中碰到的难题。

下面，冷丝就带着你解决《渡河》难题，解释其中的数学道理，你可以顺便看看自己的智商如何。

由于需要渡河的成员是固定不变的，所以，不管是什么情况，岸两边的情况也是一样的，为了让问题简单化，冷丝在这里只讨论左岸的情况。用“l”表示狗，“m”表示羊，“n”表示白菜，“r”表示人和人的状态，“l”同时表示在左岸，o表示在右岸，每渡一次河为一步。

好了，把这些设定以后，我们可以用“穷举法”推论得出下面这样的图形：

从这个图形中，我们可以得出2种渡河的方法，即（1）和（2）：

我们还可以对前面的“穷举法”推出的图形进行简化，还可以得出这样的一个环形图：

用公式表达这两种渡河办法：

归纳起来就是下面的渡河采用方式：

你能看懂渡河的2种办法吗？你如果没有看懂，这只能说明的你的智商很让人“捉急”啊！你还要继续努力学习！

那么，“图论”到底是什么呢？我们该懂得那一点点常识？

关于图论的概念很多，面最核心最重要的就这么几点：

顶点和边的概念

所谓的“图”，并不是指图形图像或地图，通常来说，我们会把图视为一种由“顶点”组成的抽象网络，网络中的各顶点可以通过“边”实现彼此的连接，表示两顶点有关联。

冷丝提醒注意定义中的两个关键字，由此得到我们最基础最基本的2个概念，顶点和边。

在图上任取两顶点，分别作为起点和终点，我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线，就是一条“路径”。两点之间存在路径，则称这2个顶点是连通的。

冷丝提出一个简单问题：我们常常走的京广线路，北京到广州怎样走，距离最短？

这样有多种走法：

从北京到广州该怎么走？

北京->上海->广州，是一条路径；北京->武汉->广州，是另一条路径；北京—>武汉->上海->广州，也是一条路径。

而北京->武汉->广州这条路径最短，称为最短路径。

路径是有权重的，路径经过的每一条边，沿路加权重，权重总和就是路径的权重（通常只加边的权重，而不考虑顶点的权重）。在路网中，路径的权重，可以想象成路径的总长度。在有向图中，路径还必须跟随边的方向。

数学专业的学生

值得注意的是，一条路径包含了顶点和边，因此路径本身也构成了图结构，只不过是一种特殊的图结构。

冷丝总结，《渡河》难题采用的就是“图论”方法，既简单也容易理解。看来，我们还是要多读书，多学习，要继续深造，懂的道理才会多，我们才会不断地解决一个又一个难题。