運(yùn)籌學(xué)20圖論基本概念

1、HomeHomeOperational Research2Operational Research3哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題CBADBCAD從岸上某點(diǎn)出發(fā)，能否從岸上某點(diǎn)出發(fā)，能否恰好經(jīng)過(guò)每座橋一次又回到出發(fā)點(diǎn)？經(jīng)過(guò)每座橋一次又回到出發(fā)點(diǎn)？如果可以，路線如何？如果可以，路線如何？Operational Research4哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題CBADBCAD問(wèn)：從岸上某點(diǎn)出發(fā)，能否問(wèn)：從岸上某點(diǎn)出發(fā)，能否恰好經(jīng)過(guò)每座橋一次又回到出發(fā)點(diǎn)？如果可經(jīng)過(guò)每座橋一次又回到出發(fā)點(diǎn)？如果可以，路線如何？以，路線如何？答：歐拉（答：歐拉（17361736）認(rèn)為圖中每個(gè)點(diǎn)都是奇數(shù)連線，因此無(wú)法

2、完成）認(rèn)為圖中每個(gè)點(diǎn)都是奇數(shù)連線，因此無(wú)法完成Operational Research5 用點(diǎn)描述事物； 用連線表示事物與事物之間的聯(lián)系； 點(diǎn)和連線的集合稱為Operational Research6 無(wú)向連線稱“邊”（Edge），記為u,v 有向連線稱“弧”（Arc），記為(u,v)無(wú)向圖，GV,E有向圖，DV,Ax1x2y1y2v1v2v3BCADOperational Research7如果一個(gè)點(diǎn)是某條連線的端點(diǎn)，則稱這個(gè)點(diǎn)與這條連線關(guān)聯(lián)。若兩條連線有一個(gè)共同的端點(diǎn)，則這兩條線是相鄰的；若兩個(gè)頂點(diǎn)分別是一條線的兩個(gè)端點(diǎn)，則這兩個(gè)頂點(diǎn)也是相鄰的。請(qǐng)注意，線包括邊和弧BCADOperatio

3、nal Research8連接同一頂點(diǎn)的邊是環(huán)。兩點(diǎn)之間有多于一個(gè)的邊。無(wú)環(huán)且無(wú)平行邊的圖。BCADOperational Research9以點(diǎn)v為端點(diǎn)的邊或弧的個(gè)數(shù)稱為點(diǎn)v的度或次，記作d(v)。其中環(huán)計(jì)數(shù)兩次。奇點(diǎn)、偶點(diǎn)：奇數(shù)次的點(diǎn)稱奇點(diǎn)，偶數(shù)次的點(diǎn)稱偶點(diǎn)。一個(gè)圖如果邊集（或弧集）為空集，則稱該圖為空?qǐng)D。比如一些孤立點(diǎn)組成的圖。即：沒(méi)有邊的圖是空?qǐng)D。 孤立點(diǎn)：空?qǐng)D的點(diǎn)，或次為零的點(diǎn)，稱為孤立點(diǎn)。僅與一條邊或弧相關(guān)聯(lián)（即相連）的點(diǎn)，稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊 一個(gè)有向圖，如果某個(gè)頂點(diǎn)只做弧的起始點(diǎn)，則稱該點(diǎn)為發(fā)點(diǎn)或源點(diǎn)；如果某個(gè)頂點(diǎn)只做弧的終點(diǎn)，則稱該點(diǎn)為收點(diǎn)或沉點(diǎn)。 Opera

4、tional Research10設(shè)G1=V1 , E1，G2 =V2 ,E2。如果 V2 V1 , E2 E1，則稱 G2 是G1 的子圖。設(shè)G1=V1 , E1，G2 =V2 ,E2。如果 V2 V1 , E2 E1 稱 G2 是G1 的真子圖。 G1=V1 , E1，G2 =V2 ,E2。如果 V2V1 , E2 E1 稱 G2 是G1 的部分圖或支撐子圖、生成子圖。 Operational Research11v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)（真）子圖v1v2v3v4v5v6v7e1e6e7

5、e9e10e11(c)支撐子圖原圖Operational Research12在無(wú)向圖G=V, E中,由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。如：（v0，e1，v1，e2，v2，e3，v3 ,vn-1, en，vn），可簡(jiǎn)單記作（v0，v1，v2，v3 ,vn-1，vn）。其鏈長(zhǎng)為 n ，其中v0，vn分別稱為鏈的起點(diǎn)和終點(diǎn)。若鏈中所含的邊均不相同，即無(wú)重復(fù)邊，則稱此鏈為簡(jiǎn)單鏈；所含的點(diǎn)均不相同的鏈稱為初等鏈。初等鏈一定是簡(jiǎn)單鏈，但反之則不一定。即：無(wú)重復(fù)點(diǎn)一定無(wú)重復(fù)邊，反之不一定Operational Research13在一個(gè)有向圖中，從起點(diǎn)開(kāi)始沿著弧的正向前進(jìn)，經(jīng)過(guò)一系列的點(diǎn)、

6、弧交替到達(dá)終點(diǎn)，形成的這個(gè)序列稱為路。如：（v0，a1，v1，a2，v2，a3，v3 ,vn-1, an，vn），其中a1的起點(diǎn)是終點(diǎn)是，其它弧類似。路也可簡(jiǎn)單記作（v0，v1，v2，v3 ,vn-1，vn）。其中v0，vn分別稱為路的起點(diǎn)和終點(diǎn)。 非正向前進(jìn)的弧的序列也稱鏈和圈。Operational Research14任意兩點(diǎn)之間均至少有一條鏈或路，則稱此圖為連通圖，否則稱為不連通圖。以下哪些是連通圖？Operational Research15樹：無(wú)向圖，記為“T”生成樹： 若T=（V，E）是無(wú)向圖，是G=（V，E）的生成子圖，且T=（V，E）是一個(gè)樹，則稱T是G的生成樹。 v2v1v

7、3v4v5e1e6e5e7v2v1v3v4v5e1e6e5e7Operational Research16一個(gè)連通圖N（V,E），若在集合V中，指定了起點(diǎn)、終點(diǎn)和中間點(diǎn)；在邊的集合E中，任意一邊都賦予權(quán)bij，這樣的圖稱為網(wǎng)絡(luò)。V1V2V4V3432143210110101111010110,vvvvAvvvvGOperational Research17一個(gè)連通圖N（V,E），若在集合V中，指定了起點(diǎn)、終點(diǎn)和中間點(diǎn)；在邊的集合E中，任意一邊都賦予權(quán)bij，這樣的圖稱為網(wǎng)絡(luò)。V1V2V4V3432143210000100011000110,vvvvAvvvvDOperational Resea

8、rch18V1V2V3V443215432111000101100110100011,vvvvAeeeeeGe1e2e3e4e5Operational Research19V1V2V3V4e1e2e3e4e543215432111000101100110100011,vvvvAeeeeeGOperational Research20Operational Research21頂點(diǎn)已知，頂點(diǎn)間設(shè)置通道的長(zhǎng)度已知，如何才能使總長(zhǎng)度最小Operational Research22最短路問(wèn)題簡(jiǎn)單地說(shuō)就是找出圖或網(wǎng)絡(luò)中兩個(gè)頂點(diǎn)之間的最短距離，的提法較多，但實(shí)質(zhì)是一致的。一般提法為：設(shè)G為連通圖（有向或無(wú)向），已知圖中各邊的權(quán)值lij，要求找出這兩點(diǎn)之間權(quán)值之和最小的鏈（或路）。v1v2v3v4v6v5352242421Operational Research232v1v3v4v5v6v7v13 (5)9 (3)4 (1)5 (3)6(3)5