運籌學20圖論基本概念

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

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

3、nal Research8連接同一頂點的邊是環(huán)。兩點之間有多于一個的邊。無環(huán)且無平行邊的圖。BCADOperational Research9以點v為端點的邊或弧的個數(shù)稱為點v的度或次，記作d(v)。其中環(huán)計數(shù)兩次。奇點、偶點：奇數(shù)次的點稱奇點，偶數(shù)次的點稱偶點。一個圖如果邊集（或弧集）為空集，則稱該圖為空圖。比如一些孤立點組成的圖。即：沒有邊的圖是空圖。 孤立點：空圖的點，或次為零的點，稱為孤立點。僅與一條邊或弧相關(guān)聯(lián)（即相連）的點，稱為懸掛點。懸掛點的關(guān)聯(lián)邊稱為懸掛邊 一個有向圖，如果某個頂點只做弧的起始點，則稱該點為發(fā)點或源點；如果某個頂點只做弧的終點，則稱該點為收點或沉點。 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在無向圖G=V, E中,由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列稱為鏈。如：（v0，e1，v1，e2，v2，e3，v3 ,vn-1, en，vn），可簡單記作（v0，v1，v2，v3 ,vn-1，vn）。其鏈長為 n ，其中v0，vn分別稱為鏈的起點和終點。若鏈中所含的邊均不相同，即無重復(fù)邊，則稱此鏈為簡單鏈；所含的點均不相同的鏈稱為初等鏈。初等鏈一定是簡單鏈，但反之則不一定。即：無重復(fù)點一定無重復(fù)邊，反之不一定Operational Research13在一個有向圖中，從起點開始沿著弧的正向前進，經(jīng)過一系列的點、

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

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

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