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