新聞中心
專業發展-加拿大一個大型學區聯繫了EFM,希望開展專業發展講座。如果您對EFM的專業發展講座有興趣,歡迎聯絡我們安排!一般來說,如果您願意支付差旅費用並對EFM的資料提供回饋,我非常樂意前往貴學區進行講座和工作坊。我已經準備好了兩個主題:一個是關於課堂和家庭中的趣味學習,另一個是關於課堂中的問題探索。
捐款-EFM的捐款金額和來源多種多樣。我們收到10美元到5000美元的捐款,也有員工透過雇主捐贈200美元或250美元。捐款支持EFM,幫助改善早期數學教育!
益智撲克牌-我們備有大量適合幼兒園至三年級和二年級至五年級學生的益智撲克牌,有英文和西班牙文兩種版本。每副售價僅3美元,我們也樂意與學校洽談資助事宜。如果您有興趣,請造訪我們的訂購頁面。
初級數學教師的應用程式——除了EFM面向家庭的行動應用程式外,EFM還希望開發一款針對教育工作者的免費行動應用程式。這款新應用程式的目標使用者是世界各地缺乏培訓和資源的初級數學教師。我們希望調整現有的大量教學材料,使其適用於此領域。然而,我們需要一些指導,了解這些材料在美國(或許包括一些啟蒙計劃地區)以及其他國家的使用情況。如果您有興趣參與此項目,請與我聯絡。
學前兒童圖論
在前兩期簡報中,我談到了您和您的孩子可以如何玩拓樸學。本月我想深入探討圖論。我這裡所說的圖並非用於數據分析的數據表示圖——我們將在下一期簡報中討論這些圖。
這些圖由點組成,稱為節點,某些節點對之間透過線連接,這些線稱為邊。節點的度是指連接到該節點的邊的數量。平面圖是指可以畫在一張紙上且所有邊都不交叉的圖。圖有時是抽象的概念,本身就很有趣;有時,圖可以幫助我們理解和分析物理情境,而不會被無用的資訊分散注意力。下面就是一個這樣的圖的例子。
圖論這個主題本身並不適合多人遊戲,只有一個例外——兩個月前,我在六月的簡報中介紹過一款名為「Sprouts」的雙人遊戲,它涉及平面圖。不過,圖論本身有很多有趣的謎題,今天我將介紹其中的許多。
第一個謎題最為著名,它常被認為是圖論和拓樸學的開端。分析這個謎題展現了將具體情境抽象化為圖的強大之處。
柯尼斯堡的七座橋
據說,柯尼斯堡人以他們的七座橋樑為傲,希望舉行一場遊行,隊伍能夠恰好依次經過每座橋樑一次。然而,沒有人能想到實現這個願望的方法。以下是EFM出品的一張謎題卡上所描述的這個難題。
我在2023年3月的簡報中也提到這個謎題。當時的重點是將數學問題融入精彩的故事中,使其引人入勝。萊昂哈德·歐拉在1735年就此謎題發表的演講,為圖論的創立做出了貢獻。
在這個問題中,物體的實際距離和形狀並不重要。問題的核心可以用一個簡單的圖來建模,其中每塊陸地都是一個節點,七座橋樑中的每一座都是一條邊。
是的,這個謎題看似不可能,但為什麼呢?探尋其中的奧秘才是樂趣所在。為了探討這一點,不妨運用一個最重要的解題策略:從問題的簡化版本入手,並多做一些例子。向孩子強調這種策略的實用性,看看他們能否自己舉出例子。這裡列舉幾個例子,但還有很多。試著為每個例子設計遊行路線,並觀察遊行的起點和終點,以及這些路線是否可行。你能發現什麼規律?又能做出哪些推測呢?
5室謎題——直線交叉問題
有很多關於直線交叉的謎題。這或許是其中最受歡迎的一個。挑戰在於畫一條連續的直線,使其恰好與圖中所有邊緣相交一次。下面的例子展示了一條不符合要求的路徑。
將此建模為一個圖,其中節點代表矩形的內部區域,外加一個代表整個外部區域的節點,邊則代表穿過圖中各個邊的路徑。雖然這張圖有點複雜(畫得不太好),但如果你運用從柯尼斯堡橋謎題中學到的知識來分析這個圖,你會發現它非常容易理解。
圖上的路徑
前兩個謎題展示了在圖上尋找路徑的挑戰。數學家喜歡定義事物並為它們命名,這也不例外。一條恰好遍歷圖上每條邊一次的路徑稱為歐拉路徑;如果這條路徑的起點和終點相同,則稱為歐拉迴路。
正如歐拉等人研究過的那樣,也正如你可能在前兩個謎題中分析過的那樣,找到歐拉路徑和迴路的關鍵在於計算具有奇數度的節點的數量。
你可以繪製漂亮的圖表,然後互相挑戰尋找歐拉路徑。知道路徑的起點和終點會很有幫助。不妨試試這個:
哈密頓路徑是指恰好訪問每個節點一次的路徑。如果路徑的起點和終點相同,則稱為哈密頓迴路。
一般來說,與歐拉路徑不同,對於給定的圖,很難判斷是否存在哈密頓路徑。
騎士巡遊問題就是一個典型的這類挑戰。假設你有一個國際象棋騎士,它位於一個 n×m 的棋盤上的一個方格內。騎士是否有可能恰好訪問棋盤上的每個方格一次?它最終能否回到起點?你可以將此問題轉換為哈密頓路徑問題:建立一個圖,其中節點代表棋盤上的方格,如果騎士可以移動經過兩個節點之間的任兩個節點,則這兩個節點之間有一條邊。
經典的哈密頓路徑問題之一是旅行商問題(TSP)。假設有人想造訪銷售路線上的所有城市,並且假設連接某些城市的邊表示城市之間的旅行時間(或距離或成本)。如何找到一條哈密頓迴路,使總旅行時間(或距離或成本)最小化?送貨卡車每天都在處理類似這個問題。
在這兩張圖中,每條邊都標示著沿著該邊行進的「成本」。旅行商問題 (TSP) 的目標是找到一條總成本最小的哈密頓迴路。您可以和孩子互相繪製地圖,然後挑戰對方在地圖上找到最佳迴路。請使用適合孩子技能等級的數字和地圖大小。
握手和熟人關係
假設聚會上有 8 個人,他們互相握手。 EFM 的每週謎題中有幾個就涉及到這種情況。用 8 個節點建模,每個節點代表一個人。如果兩個人握手,就在他們之間畫一條邊。你也可以用同樣的模型,讓邊代表彼此認識的人,或是代表有親屬關係的人。
在握手模型中,每個節點的度數(即其邊的數量)代表該節點與之握手的人數(包括未連接節點握手次數為0的情況)。我們的一個難題是:所有這些度是否可能各不相同?
關於度數可能的組合,我們可以提出很多問題。例如,所有度數是否可能都是偶數或都是奇數?所有圖表的一個有趣之處在於,圖中所有度數的總和是邊數的兩倍(為什麼?)。因此,在我們的握手問題中,必然存在偶數個人,他們握手的次數為奇數。還有哪些限制條件?
假設你有一個包含世界上所有人的圖,圖中如果兩個人互相認識,則他們之間有一條連接線。你能從這個圖中的任一個節點到達其他任一個節點嗎?還是說這張圖會分成幾個獨立的圖?對於這個圖的連通部分,要到達任兩個人之間,你最多需要經過多少邊?這有時被稱為兩個人之間的分離度。這個概念也被應用於合作過的電影演員,並為每位演員分配了一個「凱文貝肯數」。
家譜
在圖論中,樹是一種連通圖,其中不存在環路。等價地,任兩個節點之間都只有一條路徑。你可以透過連結兩個互為後代的人來建構家庭關係圖。這些圖通常被稱為家譜。
您可以和孩子一起探索,如果家譜真的是圖論意義上的樹,會發生什麼事。如果真是這樣,每一層會有多少人?注意,每一層人數都會翻倍(基於生物學關係)。從一個人開始,每一代的人數分別是 1、2、4、8、16,以此類推。追溯到十代,人數將是 1024 人。追溯到二十代,人數將是 1024 x 1024 人。到了四十代,人數將超過歷史上任何時期的人數。您的孩子能找出問題所在嗎?
圖著色
就像你可以研究地圖著色一樣,對於給定的圖,你可以問:要給圖的節點著色,使得沒有一條邊的兩端顏色相同,最少需要多少種顏色?這稱為該圖的色數。
平面圖和平面圖之間存在直接聯繫-假設圖的節點對應於地圖上的區域,並且當兩個區域共享邊界時,圖中就存在一條邊。四色定理指出,任何平面圖最多只需要四種顏色,這結論同樣適用於平面圖──任何平面圖的色數都小於等於四。不妨畫幾個平面圖,然後和孩子一起塗色,看看結果如何!
結束語
這次圖論入門主題和謎題之旅可謂是快速瀏覽。當然,我肯定還有很多內容沒有涵蓋。希望您和您的孩子能從這些謎題中找到一些有興趣的知識點。下個月,我將繼續帶領大家探索更高級的數學主題,並嘗試用簡單易懂、引人入勝的方式講解,讓孩子們樂在其中。