在你的下一次聚會中繪製連接圖。 unclibraries_commons
假設你正在計劃你的下一個派對，並對客人名單感到痛苦。 你應該向誰發送邀請？ 朋友和陌生人的哪種組合是正確的組合？
事實證明，近一個世紀以來，數學家們一直在研究這個問題的一個版本。 根據您的需求，答案可能會很複雜。
我們的書， “圖論的迷人世界，”探討了諸如此類的難題，並展示瞭如何通過圖表來解決它們。 像這樣的問題可能看起來很小，但它很好地演示瞭如何使用圖表來解決科學、傳播和社會等不同領域的數學問題。
一個謎題誕生了
眾所周知，哈佛大學是美國頂尖的學術大學之一，但您可能會驚訝地發現，哈佛大學曾經擁有全美最好的橄欖球隊之一。 但到了 1931 年，在 全美四分衛巴里·伍德，情況就是如此。
那個賽季哈佛隊打的是陸軍隊。 半場結束時，陸軍出人意料地以 13-0 領先哈佛。 哈佛大學校長顯然很沮喪，他告訴陸軍學員指揮官，雖然陸軍在橄欖球方面可能比哈佛更好，但哈佛在學術性更強的競賽中更勝一籌。
儘管哈佛以 14-13 擊敗了陸軍，但指揮官接受了挑戰，在更學術的領域與哈佛競爭。 雙方商定，兩人將進行數學競賽。 這導致陸軍和哈佛大學選擇了數學團隊； 這場對決發生在 1933 年的西點軍校。令哈佛驚訝的是，陸軍獲勝了。
哈佛-陸軍競賽最終於 1938 年舉辦了一年一度的本科生數學競賽，稱為 普特南考試，以哈佛大學校長的親戚威廉·洛厄爾·帕特南的名字命名。 該考試旨在促進美國和加拿大數學領域的健康競爭。 多年來，直到今天，這項考試包含了許多有趣且往往具有挑戰性的問題 - 包括我們上面描述的問題。
紅線和藍線
1953 年的考試包含以下問題（稍作修改）：平面上有六個點。 每個點都通過藍色或紅色的線與其他點連接。 證明存在三個這樣的點，在這三個點之間僅繪製相同顏色的線。
在數學中，如果存在一些點的集合，並且在一些點對之間繪製了線，則該結構稱為圖。 對這些圖的研究稱為圖論。 然而，在圖論中，點稱為頂點，線稱為邊。
圖表可以用來表示各種各樣的情況。 例如，在普特南問題中，一個點可以代表一個人，紅線可以表示這些人是朋友，藍線表示他們是陌生人。
表明有三個點由相同顏色的線連接。 加里·查特蘭德
例如，我們將點稱為 A、B、C、D、E、F，並選擇其中之一，例如 A。從 A 到其他五個點繪製的 XNUMX 條線中，必須有 XNUMX 條線顏色相同。
假設從 A 到 B、C、D 的線都是紅色的。 如果 B、C、D 中任意兩個之間的線是紅色，則存在三個點，它們之間只有紅線。 如果 B、C、D 中的任何兩個之間沒有一條線是紅色的，那麼它們都是藍色的。
如果只有五分怎麼辦？ 可能不存在三個點，它們之間的所有線的顏色都相同。 例如，線 A-B、B-C、C-D、D-E、E-A 可能是紅色，其他線可能是藍色。
根據我們的觀察，可以邀請參加聚會（每兩個人要么是朋友，要么是陌生人），並且有 XNUMX 個共同的朋友或 XNUMX 個共同的陌生人的最少人數是 XNUMX 人。
如果我們希望四個人成為共同的朋友或共同的陌生人怎麼辦？ 為了確定這一點，我們必須邀請最少多少人參加聚會？ 這個問題已經得到解答。 18 了。
如果我們希望五個人成為共同的朋友或共同的陌生人怎麼辦？ 在這種情況下，要保證這一點，邀請參加聚會的最少人數是未知的。 沒人知道。 雖然這個問題很容易描述，而且聽起來可能相當簡單，但它卻是出了名的困難。
拉姆齊數
我們一直在討論的是圖論中的一種數字，稱為拉姆齊數。 這些數字以英國哲學家、經濟學家和數學家的名字命名 弗蘭克·普蘭普頓·拉姆齊.
拉姆齊 26 歲時去世，但他很小的時候就得到了一個非常奇怪的數學定理，這引起了我們這裡的問題。 假設我們有另一個充滿由紅線和藍線連接的點的平面。 我們選擇兩個正整數，命名為 r 和 s。 我們希望恰好有 r 個點，其中它們之間的所有線都是紅色，或者有 s 個點，其中它們之間的所有線都是藍色。 我們可以用最少的點數來做到這一點？ 這就是所謂的拉姆齊數。
例如，假設我們希望平面至少具有由所有紅線連接的三個點和由所有藍線連接的三個點。 拉姆齊數（實現這一目標所需的最小點數）是 XNUMX。
當數學家研究一個問題時，他們經常問自己：這是否暗示了另一個問題？ 這就是拉姆齊數字和政黨問題所發生的情況。
例如，這是一個：五個女孩正在計劃一個聚會。 他們決定邀請一些男孩參加聚會，無論他們是否認識這些男孩。 他們需要邀請多少個男孩才能確定其中總是有三個男孩，這樣五個女孩中的三個要么是所有三個男孩的朋友，要么與所有三個男孩都不認識？ 想要很好地猜測答案可能並不容易。 41了！
已知的拉姆齊數很少。 然而，這並不能阻止數學家嘗試解決此類問題。 通常，未能解決一個問題可能會導致一個更有趣的問題。 這就是數學家的生活。
關於作者
加里·查特蘭德 (Gary Chartrand)，數學名譽教授， 西密西根大學; 阿瑟·本傑明，數學教授， 哈維穆德學院和張平，數學教授， 西密西根大學
相關書籍：
at InnerSelf 市場和亞馬遜
