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

第8章圖論(GraphTheory第八章圖論(GraphTheory)81圖的基本概念(Graph)82路與圖的連通性(waks&ConnectivityofGraphs83圖的矩陣表示(MatrixNotationofGraph)84最短鏈與關(guān)鍵路(Minimalpath)85歐拉圖與哈密爾頓圖(ulerianGraph&Hamilton-ianGraph8.6平面圖(PlanarGraph87樹與生成樹(TreesandSpanningTrees)8.8二部圖(bipartitegraph)第8章圖論(GraphTheory1第8章圖論(GraphTheory8.1圖的基本概念圖81.1哥尼斯堡七橋問題第8章圖論(GraphTheory2第8章圖論(GraphTheory81圖的基本概念8.1.1圖1圖的定義現(xiàn)實世界中許多現(xiàn)象能用某種圖形表示這種圖形是由一些點和一些連接兩點間的連線所組成?！纠?11】a,b,c,d4個籃球隊進(jìn)行友誼比賽。為了表示4個隊之間比賽的情況,我們作出圖8,11的圖形在圖中4個小圓圈分別表示這4個籃球隊,稱之為結(jié)點如果兩隊進(jìn)行過比賽,則在表示該隊的兩個結(jié)點之間用條線連接起來,稱之為邊。這樣利用一個圖形使各隊之間的比賽情況一目了然。第8章圖論(GraphTheory3第8章圖論(GraphTheory81圖的基本概念如果圖811中的4個結(jié)點a,b,c,d分別表示4個人,當(dāng)某兩個人互相認(rèn)識時,則將其對應(yīng)點之間用邊連接起來。這時的圖b又反映了這4個人之e間的認(rèn)識關(guān)系。圖811第8章圖論(GraphTheory4第8章圖論(GraphTheory81圖的基本概念定義811一個圖G是一個序偶〈VG),E(G)〉,記為G=〈V(G),E(G)。其中VG是非空結(jié)點集合,E(G)是邊集合,對E(G中的每條邊,有VG)中的結(jié)點的有序偶或無序偶與之對應(yīng)。若邊e所對應(yīng)的結(jié)點對是有序偶(a,b〉,則稱e是有向邊。a叫邊e的始點b叫邊e的終點統(tǒng)稱為e的端點。若邊e所對應(yīng)的結(jié)點對是無序偶ab),則稱e是無向邊。這時統(tǒng)稱e與兩個結(jié)點a和b互相關(guān)聯(lián)。第8章圖論(GraphTheory5第8章圖論(GraphTheory81圖的基本概念我們將結(jié)點a、b的無序結(jié)點對記為a,b),有序結(jié)點對記為(a,b)。一個圖G可用一個圖形來表示且表示是不唯一的【例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é)點與邊之間的關(guān)系鄰接點:同一條邊的兩個端點。孤立點:沒有邊與之關(guān)聯(lián)的結(jié)點鄰接邊:關(guān)聯(lián)同一個結(jié)點的兩條邊。孤立邊:不與任何邊相鄰接的邊自回路(環(huán)):關(guān)聯(lián)同一個結(jié)點的一條邊((ν,ν)或(ν,p))平行邊(多重邊:關(guān)聯(lián)同一對結(jié)點的多條邊。第8章圖論(GraphTheory8第8章圖論(GraphTheory8.1圖的基本概念如例8.1.1中的圖,結(jié)點集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在這個圖中,e3是關(guān)聯(lián)同一個結(jié)點的一條邊即自回路;邊e4和e都與結(jié)點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張