離散數(shù)學(xué)-圖論121張課件

第8章圖論(GraphTheory第八章圖論(GraphTheory)81圖的基本概念(Graph)82路與圖的連通性(waks&ConnectivityofGraphs83圖的矩陣表示(MatrixNotationofGraph)84最短鏈與關(guān)鍵路(Minimalpath)85歐拉圖與哈密爾頓圖(ulerianGraph&Hamilton-ianGraph8.6平面圖(PlanarGraph87樹(shù)與生成樹(shù)(TreesandSpanningTrees)8.8二部圖(bipartitegraph)第8章圖論(GraphTheory1第8章圖論(GraphTheory8.1圖的基本概念圖81.1哥尼斯堡七橋問(wèn)題第8章圖論(GraphTheory2第8章圖論(GraphTheory81圖的基本概念8.1.1圖1圖的定義現(xiàn)實(shí)世界中許多現(xiàn)象能用某種圖形表示這種圖形是由一些點(diǎn)和一些連接兩點(diǎn)間的連線(xiàn)所組成?！纠?11】a,b,c,d4個(gè)籃球隊(duì)進(jìn)行友誼比賽。為了表示4個(gè)隊(duì)之間比賽的情況,我們作出圖8,11的圖形在圖中4個(gè)小圓圈分別表示這4個(gè)籃球隊(duì),稱(chēng)之為結(jié)點(diǎn)如果兩隊(duì)進(jìn)行過(guò)比賽,則在表示該隊(duì)的兩個(gè)結(jié)點(diǎn)之間用條線(xiàn)連接起來(lái),稱(chēng)之為邊。這樣利用一個(gè)圖形使各隊(duì)之間的比賽情況一目了然。第8章圖論(GraphTheory3第8章圖論(GraphTheory81圖的基本概念如果圖811中的4個(gè)結(jié)點(diǎn)a,b,c,d分別表示4個(gè)人,當(dāng)某兩個(gè)人互相認(rèn)識(shí)時(shí),則將其對(duì)應(yīng)點(diǎn)之間用邊連接起來(lái)。這時(shí)的圖b又反映了這4個(gè)人之e間的認(rèn)識(shí)關(guān)系。圖811第8章圖論(GraphTheory4第8章圖論(GraphTheory81圖的基本概念定義811一個(gè)圖G是一個(gè)序偶〈VG),E(G)〉,記為G=〈V(G),E(G)。其中VG是非空結(jié)點(diǎn)集合,E(G)是邊集合,對(duì)E(G中的每條邊,有VG)中的結(jié)點(diǎn)的有序偶或無(wú)序偶與之對(duì)應(yīng)。若邊e所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)是有序偶(a,b〉,則稱(chēng)e是有向邊。a叫邊e的始點(diǎn)b叫邊e的終點(diǎn)統(tǒng)稱(chēng)為e的端點(diǎn)。若邊e所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)是無(wú)序偶ab),則稱(chēng)e是無(wú)向邊。這時(shí)統(tǒng)稱(chēng)e與兩個(gè)結(jié)點(diǎn)a和b互相關(guān)聯(lián)。第8章圖論(GraphTheory5第8章圖論(GraphTheory81圖的基本概念我們將結(jié)點(diǎn)a、b的無(wú)序結(jié)點(diǎn)對(duì)記為a,b),有序結(jié)點(diǎn)對(duì)記為(a,b)。一個(gè)圖G可用一個(gè)圖形來(lái)表示且表示是不唯一的【例81.2】設(shè)G=〈VG,E(G),其中V(G)={a,b升,EG)={e1y234P5627},e1=(a,b),e2=(anc),e3=(b,d,e4=(b,c),es=(d4),e6=(a,d)ey=(b,b)。則圖G可用圖8.12a)或(b表示。第8章圖論(GraphTheory6第8章圖論(GraphTheory8.1圖的基本概念ae?(a)圖812第8章圖論(GraphTheory7第8章圖論(GraphTheory81圖的基本概念2.圖G的結(jié)點(diǎn)與邊之間的關(guān)系鄰接點(diǎn):同一條邊的兩個(gè)端點(diǎn)。孤立點(diǎn):沒(méi)有邊與之關(guān)聯(lián)的結(jié)點(diǎn)鄰接邊:關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊。孤立邊:不與任何邊相鄰接的邊自回路(環(huán)):關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的一條邊((ν,ν)或(ν,p))平行邊(多重邊:關(guān)聯(lián)同一對(duì)結(jié)點(diǎn)的多條邊。第8章圖論(GraphTheory8第8章圖論(GraphTheory8.1圖的基本概念如例8.1.1中的圖,結(jié)點(diǎn)集V={a,b,c,d},邊集Ee1,e2,e3,e4,es},其中(a,b)(a,d)),es=(c,d)。d與a、d與c是鄰接的,但d與b不鄰接,邊e3與es是鄰接的。a第8章圖論(GraphTheory9第8章圖論(GraphTheory8.1圖的基本概念【例813】設(shè)圖G=〈V,E〉如圖10.1.3所示。這里V={v1,v2,v3},E={1e其中e1=(v1,p2),e2=(v1,v3De313圖8.1在這個(gè)圖中,e3是關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的一條邊即自回路;邊e4和e都與結(jié)點(diǎn)v2、v3關(guān)聯(lián),即它們是平行邊第8章圖論(GraphTheory10離散數(shù)學(xué)-圖論121張課件11離散數(shù)學(xué)-圖論121張課件12離散數(shù)學(xué)-圖論121張課件13離散數(shù)學(xué)-圖論121張課件14離散數(shù)學(xué)-圖論121張課件15離散數(shù)學(xué)-圖論121張課件16離散數(shù)學(xué)-圖論121張課件17離散數(shù)學(xué)-圖論121張課件18離散數(shù)學(xué)-圖論121張課件19離散數(shù)學(xué)-圖論121張課件20離散數(shù)學(xué)-圖論121張課件21離散數(shù)學(xué)-圖論121張課件22離散數(shù)學(xué)-圖論121張課件23離散數(shù)學(xué)-圖論121張課件24離散數(shù)學(xué)-圖論121張課件25離散數(shù)學(xué)-圖論121張課件26離散數(shù)學(xué)-圖論121張課件27離散數(shù)學(xué)-圖論121張課件28離散數(shù)學(xué)-圖論121張課件29離散數(shù)學(xué)-圖論121張課件30離散數(shù)學(xué)-圖論121張課件31離散數(shù)學(xué)-圖論121張課件32離散數(shù)學(xué)-圖論121張課件33離散數(shù)學(xué)-圖論121張課件34離散數(shù)學(xué)-圖論121張課件35離散數(shù)學(xué)-圖論121張課件36離散數(shù)學(xué)-圖論121張課件37離散數(shù)學(xué)-圖論121張課件38離散數(shù)學(xué)-圖論121張課件39離散數(shù)學(xué)-圖論121張課件40離散數(shù)學(xué)-圖論121張課件41離散數(shù)學(xué)-圖論121張課件42離散數(shù)學(xué)-圖論121張課件43離散數(shù)學(xué)-圖論121張課件44離散數(shù)學(xué)-圖論121張課件45離散數(shù)學(xué)-圖論121張課件46離散數(shù)學(xué)-圖論121張課件47離散數(shù)學(xué)-圖論121張課件48離散數(shù)學(xué)-圖論121張課件49離散數(shù)學(xué)-圖論121張課件50離散數(shù)學(xué)-圖論121張課件51離散數(shù)學(xué)-圖論121張課件52離散數(shù)學(xué)-圖論121張課件53離散數(shù)學(xué)-圖論121張課件54離散數(shù)學(xué)-圖論121張課件55離散數(shù)學(xué)-圖論121張課件56離散數(shù)學(xué)-圖論121張課件57離散數(shù)學(xué)-圖論121張課件58離散數(shù)學(xué)-圖論121張課件59離散數(shù)學(xué)-圖論121張課件60離散數(shù)學(xué)-圖論121張課件61離散數(shù)學(xué)-圖論121張課件62離散數(shù)學(xué)-圖論121張課件63離散數(shù)學(xué)-圖論121張課件64離散數(shù)學(xué)-圖論121張課件65離散數(shù)學(xué)-圖論121張課件66離散數(shù)學(xué)-圖論121張課件67離散數(shù)學(xué)-圖論121張課件68離散數(shù)學(xué)-圖論121張課件69離散數(shù)學(xué)-圖論121張課件70離散數(shù)學(xué)-圖論121張課件71離散數(shù)學(xué)-圖論121張課件72離散數(shù)學(xué)-圖論121張課件73離散數(shù)學(xué)-圖論121張課件74離散數(shù)學(xué)-圖論121張課件75離散數(shù)學(xué)-圖論121張課件76離散數(shù)學(xué)-圖論121張課件77離散數(shù)學(xué)-圖論121張課件78離散數(shù)學(xué)-圖論121張課件79離散數(shù)學(xué)-圖論121張課件80離散數(shù)學(xué)-圖論121張課件81離散數(shù)學(xué)-圖論121張課件82離散數(shù)學(xué)-圖論121張課件83離散數(shù)學(xué)-圖論121張課件84離散數(shù)學(xué)-圖論121張課件85離散數(shù)學(xué)-圖論121張課件86離散數(shù)學(xué)-圖論121張課件87離散數(shù)學(xué)-圖論121張課件88離散數(shù)學(xué)-圖論121張課件89離散數(shù)學(xué)-圖論121張課件90離散數(shù)學(xué)-圖論121張課件91離散數(shù)學(xué)-圖論121張課件92離散數(shù)學(xué)-圖論121張課件93離散數(shù)學(xué)-圖論121張課件94離散數(shù)學(xué)-圖論121張課件95離散數(shù)學(xué)-圖論121張課件96離散數(shù)學(xué)-圖論121張課件97離散數(shù)學(xué)-圖論121張課件98離散數(shù)學(xué)-圖論121張課件99離散數(shù)學(xué)-圖論121張課件100離散數(shù)學(xué)-圖論121張課件101離散數(shù)學(xué)-圖論121張課件102離散數(shù)學(xué)-圖論121張課件103離散數(shù)學(xué)-圖論121張課件104離散數(shù)學(xué)-圖論121張課件105離散數(shù)學(xué)-圖論121張課件106離散數(shù)學(xué)-圖論121張課件107離散數(shù)學(xué)-圖論121張課件108離散數(shù)學(xué)-圖論121張課件109離散數(shù)學(xué)-圖論121張課件110離散數(shù)學(xué)-圖論121張