資源描述：
《無(wú)向圖及有向圖》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、離散數(shù)學(xué)CH7圖的基本概念1無(wú)向圖及有向圖1圖論的起源圖論是組合數(shù)學(xué)的一個(gè)分支,它起源于1736年歐拉的第一篇關(guān)于圖論的論文，這篇論文解決了著名的“哥尼斯堡七橋問(wèn)題”，從而使歐拉成為圖論的創(chuàng)始人。1.哥尼斯堡七橋問(wèn)題哥尼斯堡位于前蘇聯(lián)的加里寧格勒，歷史上曾經(jīng)是德國(guó)東普魯士省的省會(huì)，普雷格爾河橫穿城堡，河中有兩個(gè)小島，共有七座橋連接兩岸和小島。問(wèn)題：在所有橋都只能走一遍的前提下，如何才能把這個(gè)地方所有的橋都走遍？哥尼斯堡七橋問(wèn)題解決方式萊昂哈德·歐拉（LeonhardEuler）在1735年圓滿(mǎn)地解決了這一問(wèn)題，證明這種方法并不存在，也順帶解決了一筆畫(huà)問(wèn)題。他在圣彼得堡科學(xué)院發(fā)表了圖論史上
2、第一篇重要文獻(xiàn)。歐拉把實(shí)際的抽象問(wèn)題簡(jiǎn)化為平面上的點(diǎn)與線(xiàn)組合，每一座橋視為一條線(xiàn)，橋所連接的地區(qū)視為點(diǎn)。這樣若從某點(diǎn)出發(fā)后最后再回到這點(diǎn)，則這一點(diǎn)的線(xiàn)數(shù)必須是偶數(shù)?！鷪D論的起源歐拉最后給出任意一種河──橋圖能否全部走一次的判定法則。如果通奇數(shù)座橋的地方不止兩個(gè)，那么滿(mǎn)足要求的路線(xiàn)便不存在了。如果只有兩個(gè)地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線(xiàn)。若沒(méi)有一個(gè)地方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線(xiàn)都能實(shí)現(xiàn)，他還說(shuō)明了怎樣快速找到所要求的路線(xiàn)。不少數(shù)學(xué)家都嘗試去解析這個(gè)事例。而這些解析，最后發(fā)展成為了數(shù)學(xué)中的圖論。5歐拉圖定義一個(gè)圖,如果能夠從一點(diǎn)出發(fā),經(jīng)過(guò)每條邊一次且僅一
3、次再回到起點(diǎn),則稱(chēng)為歐拉圖歐拉在論文中給出并證明了判斷歐拉圖的充分必要條件定理,并證明了七橋圖不是歐拉圖。從這個(gè)問(wèn)題可以看出：圖：圖用點(diǎn)代表各個(gè)事物,用邊代表各個(gè)事物間的二元關(guān)系。所以，圖是研究集合上的二元關(guān)系的工具，是建立數(shù)學(xué)模型的一個(gè)重要手段。2、一百多年以后“七橋”問(wèn)題以后，圖論的研究停滯了一百多年，直到1847年，基爾霍夫用“樹(shù)”圖解決了電路理論中的求解聯(lián)立方程的問(wèn)題，十年后凱萊用“樹(shù)”圖計(jì)算有機(jī)化學(xué)中的問(wèn)題。在這一時(shí)期流行著兩個(gè)著名的圖論問(wèn)題：哈密爾頓回路問(wèn)題和“四色猜想”問(wèn)題。3.哈密爾頓回路問(wèn)題1856年,英國(guó)數(shù)學(xué)家哈密爾頓設(shè)計(jì)了一個(gè)周游世界的游戲，他在一個(gè)正十二面體的二十
4、個(gè)頂點(diǎn)上標(biāo)上二十個(gè)著名城市的名字，要求游戲者從一個(gè)城市出發(fā)，經(jīng)過(guò)每一個(gè)城市一次且僅一次，然后回到出發(fā)點(diǎn)。哈密爾頓回路圖此路線(xiàn)稱(chēng)為：哈密爾頓回路，而此圖稱(chēng)為：哈密爾頓圖。4、“四色猜想”問(wèn)題人們?cè)陂L(zhǎng)期為地圖(平面圖)上色時(shí)發(fā)現(xiàn)，最少只要四種顏色，就能使得有相鄰國(guó)界的國(guó)家涂上不同的顏色四色猜想的證明一直沒(méi)有解決，直到一百多年后，在計(jì)算機(jī)出現(xiàn)以后，于1976年用計(jì)算機(jī)算了1200多小時(shí)，才證明了四色猜想問(wèn)題。5、又過(guò)了半個(gè)世紀(jì)四色猜想問(wèn)題出現(xiàn)后，圖論的研究又停滯了半個(gè)世紀(jì)，直到1920年科尼格寫(xiě)了許多關(guān)于圖論方面的論文，并于1936年發(fā)表了第一本關(guān)于圖論的書(shū)。此后圖論從理論上到應(yīng)用上都有了很大
5、發(fā)展。特別是計(jì)算機(jī)的出現(xiàn)使圖論得到飛躍的發(fā)展。學(xué)好圖論十分重要圖論是組合數(shù)學(xué)的一個(gè)分支，與其它數(shù)學(xué)分支如群論、矩陣論、集合論、概率論、拓?fù)鋵W(xué)、數(shù)值分析等有著密切的聯(lián)系。圖論給含有二元關(guān)系的系統(tǒng)提供了數(shù)學(xué)模型，因而在許多領(lǐng)域里都具有越來(lái)越重要的地位，并且在物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)等各方面都取得了豐碩的成果。從二十世際50年代以來(lái)，由于計(jì)算機(jī)的迅速發(fā)展，有力地推動(dòng)了圖論的發(fā)展，使得圖論成為數(shù)學(xué)領(lǐng)域里發(fā)展最快的分支之一。第7章圖的概念本章學(xué)習(xí)：1.無(wú)向圖及有向圖2.通路、回路、圖的連通性3.圖的矩陣表示4.最短路徑及關(guān)鍵路徑14今日內(nèi)容無(wú)向圖及有向圖圖的一些相關(guān)概念度握手定理子圖相關(guān)概念圖同
6、構(gòu)15預(yù)備知識(shí)有序積:A×B={
7、x∈A∧y∈B}有序?qū)?≠無(wú)序積:A&B={(x,y)
8、x∈A∧y∈B}無(wú)序?qū)?(x,y)=(y,x)多重集:{a,a,a,b,b,c}≠{a,b,c}重復(fù)度:a的重復(fù)度為3,b的為2,c的為1161、無(wú)序積：A&B設(shè)A、B為兩集合，稱(chēng){{a,b}
9、a∈A∧b∈B}為A與B的無(wú)序積，記作A&B。為方便起見(jiàn)，將無(wú)序?qū)a,b}記作(a,b)。(a,b)＝(b,a)例：設(shè)A={a,b},B={c,d},則A&B＝？A&A＝？A&B={(a,c),(a,d),(b,c),(b,d)}A&A={(a,a),(a,b),(b,b)}1
10、72、無(wú)向圖一個(gè)無(wú)向圖G是一個(gè)二元組,即G=,其中:①.V是一個(gè)非空集合,稱(chēng)為G的頂點(diǎn)集,V中元素稱(chēng)為頂點(diǎn)或結(jié)點(diǎn);②.E是無(wú)序積V&V的一個(gè)多重子集,稱(chēng)E為G的邊集,E中元素稱(chēng)為無(wú)向邊或簡(jiǎn)稱(chēng)邊。?用小圓圈表示V中頂點(diǎn),若(a,b)∈E,就在a,b之間連線(xiàn)段表示邊(a,b),其中頂點(diǎn)的位置、連線(xiàn)的曲直及是否相交都無(wú)關(guān)緊要。18無(wú)向圖示例給定無(wú)向圖G＝，其中V＝{v1,v2,v3,v4,v5}， E={(v
