兒時的一道數學智力題，難倒我們10多年，上大學終於揭開了謎底
文｜冷絲
欄目｜絲說中小學教育
不管你是小朋友還是大朋友，或者是成年人，一定在很小的時候就聽哥哥姐姐說過《渡河》的數學題：一個人挑著白菜，牽著一條狗、一隻羊要渡河，但是船太小，一次只能允許這個人帶3樣中的一樣過河，而且，羊或者狗不能單獨同白菜呆在一起，因為菜會被吃掉。你該怎麼過河呢？
數學學霸們的開學典禮
我們在當年就知道了最終的答案——2種渡河方式，但為什麼會是這個答案？這個答案是通過什麼計算方法得來的？
冷絲今天想說的是，這個難題困擾了我們整個少兒時代，因為涉及的知識只能在大學裡的應用數學中解決。
1000多年前的數學遊戲難題不斷演化，最終成功地被「圖論」方法解決。
這道難題其實是在1000多年前就被提出來，英國著名學者Alcuin提出過一個古老的渡河問題，即狼、羊和捲心菜的渡河問題。隨著時代的發展，狼被替換成了狗，捲心菜成了大白菜，羊還是那隻羊。
所謂應用數學「圖論」中的圖，就是數據結構和演算法學中最強大的框架之一，現在是計算機科學的重要課程之一，幾乎可以用來表現所有類型的結構或系統，從交通網路到通信網路，從下棋遊戲到最優流程，從任務分配到人際交互網路，圖都有廣闊的用武之地。
數學課堂
說簡單一點，你就要學會用「圖」的概念，運用形象的思維方式來解決現實中碰到的難題。
下面，冷絲就帶著你解決《渡河》難題，解釋其中的數學道理，你可以順便看看自己的智商如何。
由於需要渡河的成員是固定不變的，所以，不管是什麼情況，岸兩邊的情況也是一樣的，為了讓問題簡單化，冷絲在這裡只討論左岸的情況。用「l」表示狗，「m」表示羊，「n」表示白菜，「r」表示人和人的狀態，「l」同時表示在左岸，o表示在右岸，每渡一次河為一步。
好了，把這些設定以後，我們可以用「窮舉法」推論得出下面這樣的圖形：
從這個圖形中，我們可以得出2種渡河的方法，即（1）和（2）：
我們還可以對前面的「窮舉法」推出的圖形進行簡化，還可以得出這樣的一個環形圖：
用公式表達這兩種渡河辦法：
歸納起來就是下面的渡河採用方式：
你能看懂渡河的2種辦法嗎？你如果沒有看懂，這隻能說明的你的智商很讓人「捉急」啊！你還要繼續努力學習！
那麼，「圖論」到底是什麼呢？我們該懂得那一點點常識？
關於圖論的概念很多，面最核心最重要的就這麼幾點：
頂點和邊的概念
所謂的「圖」，並不是指圖形圖像或地圖，通常來說，我們會把圖視為一種由「頂點」組成的抽象網路，網路中的各頂點可以通過「邊」實現彼此的連接，表示兩頂點有關聯。
冷絲提醒注意定義中的兩個關鍵字，由此得到我們最基礎最基本的2個概念，頂點和邊。
在圖上任取兩頂點，分別作為起點和終點，我們可以規劃許多條由起點到終點的路線。不會來來回迴繞圈子、不會重複經過同一個點和同一條邊的路線，就是一條「路徑」。兩點之間存在路徑，則稱這2個頂點是連通的。
冷絲提出一個簡單問題：我們常常走的京廣線路，北京到廣州怎樣走，距離最短？
這樣有多種走法：
從北京到廣州該怎麼走？
北京->上海->廣州，是一條路徑；北京->武漢->廣州，是另一條路徑；北京—>武漢->上海->廣州，也是一條路徑。
而北京->武漢->廣州這條路徑最短，稱為最短路徑。
路徑是有權重的，路徑經過的每一條邊，沿路加權重，權重總和就是路徑的權重（通常只加邊的權重，而不考慮頂點的權重）。在路網中，路徑的權重，可以想像成路徑的總長度。在有向圖中，路徑還必須跟隨邊的方向。
數學專業的學生
值得注意的是，一條路徑包含了頂點和邊，因此路徑本身也構成了圖結構，只不過是一種特殊的圖結構。
冷絲總結，《渡河》難題採用的就是「圖論」方法，既簡單也容易理解。看來，我們還是要多讀書，多學習，要繼續深造，懂的道理才會多，我們才會不斷地解決一個又一個難題。
