CH1圖的基本概念

圖論在現(xiàn)代科學(xué)技術(shù)中有著廣泛的應(yīng)用，如：網(wǎng)絡(luò)設(shè)計(jì)、計(jì)算機(jī)科學(xué)、信息科學(xué)、密碼學(xué)、DNA的基因譜的確定和計(jì)數(shù)、工業(yè)生產(chǎn)和企業(yè)管理中的優(yōu)化方法等都廣泛的應(yīng)用了圖論及其算法。

首先我們通過圖的發(fā)展過程來了解一下圖論所研究的內(nèi)容。圖論起源于1736年的一個(gè)游戲----哥尼斯城堡七橋問題。

返回結(jié)束§1圖論發(fā)展史1精品ABDC轉(zhuǎn)化

Euler1736年

BDCA圖論中討論的圖

問題：是否能從四塊陸地中的任一塊開始，通過每座橋恰好一次再回到起點(diǎn)？是否能從任意一個(gè)頂點(diǎn)開始，通過每條邊恰好一次再回到起點(diǎn)？轉(zhuǎn)化返回結(jié)束包含兩個(gè)要素：對(duì)象（陸地）及對(duì)象間的二元關(guān)系（是否有橋連接）七橋問題2精品

四色問題是世界近代三大數(shù)學(xué)難題之一。

四色問題的內(nèi)容是：任何一張地圖只用四種顏色就能使具有共同邊界的國(guó)家著上不同的顏色。它的提出來自英國(guó)。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯·格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家都被著上不同的顏色。”這個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？問題一：四色問題3精品

1872年，英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題。

1878～1880年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了。

1890年，在牛津大學(xué)就讀的年僅29歲的赫伍德以自己的精確計(jì)算指出了肯普在證明上的漏洞。不久，泰勒的證明也被人們否定了。后來，人們開始認(rèn)識(shí)到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題。4精品

進(jìn)入20世紀(jì)以來，科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在進(jìn)行。后來美國(guó)數(shù)學(xué)家富蘭克林于1939年證明了22國(guó)以下的地圖都可以用四色著色。1950年，有人從22國(guó)推進(jìn)到35國(guó)。1960年，有人又證明了39國(guó)以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到了50國(guó)。

1976年6月，美國(guó)伊利諾大學(xué)哈肯與阿佩爾在兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明，轟動(dòng)了世界。然而，真正數(shù)學(xué)上的嚴(yán)格證明仍然沒有得到！數(shù)學(xué)家仍為此努力，并由此產(chǎn)生了多個(gè)不同的圖論分支。5精品

Hamilton問題源于1856年，英國(guó)數(shù)學(xué)家Hamilton設(shè)計(jì)了一個(gè)名為周游世界的游戲：他用一個(gè)正十二面體的二十個(gè)端點(diǎn)表示世界上的二十座大城市（見圖），提出的問題是要求游戲者找一條沿著十二面體的棱通過每個(gè)端點(diǎn)恰好一次的行走路線。反映到圖論上就是判斷一個(gè)給定的圖是否存在一條含所有頂點(diǎn)的回路。問題二：Hamilton問題6精品幾個(gè)事實(shí)：任意的6個(gè)人中，總有3個(gè)人互相認(rèn)識(shí)或有3個(gè)人互不認(rèn)識(shí)。任意的9個(gè)人中，總有3個(gè)人互相認(rèn)識(shí)或有4個(gè)人互不認(rèn)識(shí)。問題：對(duì)任意的自然數(shù)k和t，是否存在一個(gè)最小的正整數(shù)r(k,t)，使得每個(gè)至少有r(k,t)個(gè)人的團(tuán)體，總有k個(gè)人互相認(rèn)識(shí)或有t個(gè)人互不認(rèn)識(shí)。拉姆瑟（F.P.Ramsey）在1930年證明了這個(gè)數(shù)

r(k,t)是存在的，人們稱之為Ramsey數(shù)。

問題三：Ramsey問題7精品

1847年基爾霍夫運(yùn)用圖論解決了電路理論中求解聯(lián)立方程的問題，引進(jìn)了“樹”概念。

1857年Cayley非常自然在有機(jī)化學(xué)領(lǐng)域發(fā)現(xiàn)了一種重要的圖，稱為“樹”，解決了計(jì)算飽和氫化物同分異構(gòu)體的數(shù)目。

1936年,哥尼格的第一本圖論專著問世,才使得圖論成為一門獨(dú)立的數(shù)學(xué)學(xué)科.1946年,隨著世界上第一臺(tái)計(jì)算機(jī)的問世,使圖論的發(fā)展突飛猛進(jìn).8精品圖論相關(guān)的交叉研究

代數(shù)圖論

拓?fù)鋱D論

化學(xué)圖論

算法圖論