圖論的起源和發(fā)展.pdf

《圖論的起源和發(fā)展.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、大眾文藝大理論研究圖論的起源和發(fā)展李冰（河北省唐山第五中學(xué)063000）摘要：圖論是數(shù)學(xué)領(lǐng)域中發(fā)展最快的分支之一，數(shù)學(xué)史上著名試求從圖中的任一點(diǎn)出發(fā)，通過每條邊一次，最后返回到該的七橋問題歐拉只用了一步就證明了不重復(fù)地通過7座橋的路線是根點(diǎn)，這樣的路徑是否存在？于是問題就變得簡潔明了多了，同時(shí)也本不存在的！這是拓?fù)鋵W(xué)研究的先聲。圖的染色問題一直是圖論研究更一般、更深刻。這樣一來，七橋問題就轉(zhuǎn)變?yōu)閳D論中的一個(gè)一筆的焦點(diǎn)問題。數(shù)學(xué)家赫伍德（Hedwood）成功地運(yùn)用肯普的方法證明畫問題。即能不能一筆不重復(fù)的畫出圖1．1(b)中的這個(gè)圖形。了五色定理，即一張地圖能夠用五種或者更少的顏色染色。美國

2、伊利原先人們是要求找出一條不重復(fù)的路線，歐拉想，成千上萬諾斯大學(xué)的黑肯（W.Haken）和阿佩爾（Appel），經(jīng)過四年的艱苦的人都失敗了，這樣的路線也許根本不存在。于是，歐拉接下來工作，終于完成了四色猜想的證明。正是上述那些似乎沒有多大意義著手判斷：這樣不重復(fù)的路線究竟存不存在？由于這么改變了一的游戲的抽象與論證的方法，開創(chuàng)了圖論科學(xué)的研究。下提問的角度，歐拉抓住了問題的實(shí)質(zhì)。最后，歐拉認(rèn)真考慮了關(guān)鍵詞：團(tuán)論；染色體；四色猜想一筆畫圖形的結(jié)構(gòu)特征。歐拉發(fā)現(xiàn)，凡是能用一筆畫成的圖形，都有這樣一個(gè)特點(diǎn)：圖論是組合數(shù)學(xué)的—個(gè)分支，與其他的數(shù)學(xué)分支，如群論、每當(dāng)用筆畫一條線進(jìn)入中間的一個(gè)點(diǎn)時(shí)，還

3、必須畫一條線離開這矩陣論、概率論、拓?fù)鋵W(xué)、數(shù)值分析等有著密切的聯(lián)系（參見文個(gè)點(diǎn)。否則，整個(gè)圖形就不可能用一筆畫出。也就是說，單獨(dú)考獻(xiàn)[1]）。圖論中以圖為研究對(duì)象，圖形中我們用點(diǎn)表示對(duì)象，察圖中的任何一點(diǎn)（起點(diǎn)和終點(diǎn)除外），這個(gè)點(diǎn)都應(yīng)該與偶數(shù)條兩點(diǎn)之間的連線表示對(duì)象之間的某種特定的關(guān)系。事實(shí)上，任何線相連；如果起點(diǎn)與終點(diǎn)重合，那么，連這個(gè)點(diǎn)也應(yīng)該與偶數(shù)條一個(gè)包含了某種二元關(guān)系的系統(tǒng)都可以用圖形來模擬，而且它具線相連。有形象直觀的特點(diǎn)。由于我們感興趣的是兩對(duì)象之間是否有某在七橋問題的幾何圖中，A、B、D三點(diǎn)分別與3條線相連，C種特定關(guān)系，所以圖形中兩點(diǎn)間連接與否尤為重要，而圖形的位點(diǎn)與5條線

4、相連。連線都是奇數(shù)條。因此，歐拉斷定：一筆畫出置、大小、形狀及連接線的曲直長短則無關(guān)緊要。這個(gè)圖形是不可能的。也就是說，不重復(fù)地通過7座橋的路線是20世紀(jì)后，圖論的應(yīng)用滲透到許多其他學(xué)科領(lǐng)域。從20世根本不存在的！天才的歐拉只用了一步就證明了這個(gè)難題，從這紀(jì)50年代以后，由于計(jì)算機(jī)的迅速發(fā)展，有力地推動(dòng)了圖論的發(fā)里我們也可以看到圖論的威力有多么的強(qiáng)大！展，使圖論成為數(shù)學(xué)領(lǐng)域中發(fā)展最快的分支之一。歐拉對(duì)七橋問題的研究，是拓?fù)鋵W(xué)研究的先聲。一、圖論的起源1750年，歐拉又發(fā)現(xiàn)了一個(gè)有趣的的現(xiàn)象。歐拉得到了后人圖論是一個(gè)古老的但又十分活躍的數(shù)學(xué)學(xué)科，也是一門很以他的名字命名的“多面體歐拉公式”。

5、正4面體有4個(gè)頂點(diǎn)、6有實(shí)用價(jià)值的學(xué)科，它在自然科學(xué)、社會(huì)科學(xué)等各領(lǐng)域均有很多條棱，它的面數(shù)加頂點(diǎn)數(shù)減去棱數(shù)等于2；正6面體有8個(gè)頂點(diǎn)、應(yīng)用。近年來它受計(jì)算機(jī)科學(xué)蓬勃發(fā)展的刺激，發(fā)展極其迅速。12條棱，它的面數(shù)加頂點(diǎn)數(shù)減去棱數(shù)也等于2。接著，歐拉又考應(yīng)用范圍不斷拓廣，已滲透到諸如語言學(xué)、邏輯學(xué)、物理學(xué)、化察了正12面體、正24面體，發(fā)現(xiàn)都有相同的結(jié)論。于是繼續(xù)深入學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。研究這個(gè)問題，終于發(fā)現(xiàn)了一個(gè)著名的定理：1736年是圖論的歷史元年。這一年，歐拉（L?Euler）研究了哥尼斯堡城（K?nigsberg）的七橋問題，發(fā)表了圖論的首篇論這個(gè)公式證明了多

6、面體只有正四面體、正六面體、正八面文。歐拉也因此被稱為圖論之父。體、正十二面體、正二十面體五種。這個(gè)定理成為拓?fù)鋵W(xué)的第一古老而美麗的哥尼斯堡城瀕臨藍(lán)色的波羅的海，是著名的個(gè)定理，這個(gè)公式被認(rèn)為開啟了數(shù)學(xué)史上新的一頁，促成了拓?fù)湔軐W(xué)家康德（ImmanuelKant）的出生地，城中有一條普萊格爾學(xué)的發(fā)展。（Pregel）河，河的兩條支流在這里匯合，然后橫穿全城，流入二、圖論的發(fā)展大海。河水把城市分成4塊，于是，人們建造了7座各具特色的從19世紀(jì)中葉開始，圖論進(jìn)入第二個(gè)發(fā)展階段。這一時(shí)期橋，把哥尼斯堡城連成一體，如圖1．1(a)所示。圖論問題大量出現(xiàn)，諸如關(guān)于地圖染色的四色問題、由“周游世早在1

7、8世紀(jì)，這些形態(tài)各異的小橋吸引了眾多的游客，游人界”游戲發(fā)展起來的哈密頓(W.Hamilton)問題等。在陶醉于美麗風(fēng)光的同時(shí)，不知不覺間，腳下的橋觸發(fā)了人們的圖的染色問題一直是圖論研究的焦點(diǎn)問題。最早記載染色問靈感，一個(gè)有趣的問題在居民中傳開。題的是英國倫敦大學(xué)（UniversityofLondon）的數(shù)學(xué)教授德?摩根（D.Morgan）。A1852年，一位剛從倫敦大學(xué)畢業(yè)的學(xué)生費(fèi)南西斯?古色利（F.Guthrie）在