[工學]圖論第01講(參考版)
2024-10-21 23:51本頁面
【正文】 但他關(guān)于 Ramsey數(shù)的遺產(chǎn)卻永澤數(shù)學界?？茖W界一致認為， Ramsey理論是離散數(shù)學中最漂亮的成就。凱恩斯的得意弟子。 是 20世紀最顯赫的兩大經(jīng)濟學家之一約翰 歐拉 Frank Ramsey 生平簡介 弗蘭克 小行星歐拉 2021是為了紀念歐拉而命名的。歐拉實際上支配了 18世紀的數(shù)學，對于當時新發(fā)明的微積分，他推導(dǎo)出了很多結(jié)果。他是把微積分應(yīng)用于物理學的先驅(qū)者之一。狄德羅：“ 先生， (a+b)n/n = x；所以上帝存在，這是回答！ ” 歐拉的離世也很特別：據(jù)說當時正是下午茶時間，正在逗孫兒玩的時候，被一塊蛋糕卡在喉頭窒息而死。然而，那個廣泛流傳的傳說卻不是真的。作為數(shù)學教授，他先后任教于圣彼得堡 (17271741)和柏林，爾后再返圣彼得堡 (1766)。歐拉出生于瑞士，在那里受教育。弗里德里克 歐拉 (Leonhard Euler， ~) 瑞士的數(shù)學家和物理學家。 練習思考題 試證明 9人中必有 3個人相互認識或 4個人相互不認識，兩者必居其一。 由此可見 圖論中蘊含著強有力的思想、漂亮的圖形和巧妙的理論，即使是非常困難尚未解決的問題，它的表述也可以是非常平易的。 Ramsey問題－ 2 而 5個人的人群，可能出現(xiàn)既沒有 3個人彼此不認識，也沒有 3個人相互認識，如下圖： v1 v3 v2 v5 v4 實線表示相互認識 虛線 表示相互不認識 所以 r(3,3)≥6 六、 Ramsey問題 自 Ramsey在 1928年提出了 Ramsey數(shù)與相關(guān)理論 70多年以來，至今求得的 Ramsey數(shù)僅僅 9個，它們是： r(3,3)=6, r(3,4)=9, r(3,5)=14, r(3,6)=18, r(3,7)=23, r(3,8)=28, r(3,9)=36, r(4,4)=18, r(4,5)=25. Ramsey問題－ 3 計算 Ramsey數(shù)是一個 NPC問題，匈牙利數(shù)學家厄爾多斯（ Erdos）曾用下面的話比喻計算 Ramsey數(shù)的艱巨性： 某年某月某日，一伙外星強盜入侵地球，并威脅到，若不能在一年內(nèi)計算出 r(5,5)，他們便滅絕人類！面對危機，人類最好的選擇是調(diào)動地球上所有的計算機、數(shù)學家、計算機專家，日以繼夜的計算 r(5,5)，以求人類免于滅頂之災(zāi)；如果外星人威脅說要求得 r(6,6)，那我們別無選擇，只能和外星人戰(zhàn)斗到底了！ 六、妖怪（ snark graph）
教學課件相關(guān)推薦
鄂ICP備17016276號-1