運籌學圖的基本概念名校講義課件

§1引言（1）

圖論是數(shù)學中廣泛應用的一個分支。早期圖論與“數(shù)學游戲”有著密切關系，所謂“哥尼斯堡七橋”問題就是其中之一。原東普魯士的哥尼斯堡城有一條普萊格爾河，河中有兩個小島，有7座橋把該河的兩個小島與河岸聯(lián)結起來，如圖5-1所示。圖5-1A

B

C

D

§1引言（1）圖論是數(shù)學中廣泛應用的一個分支。圖5§1引言（2）

有人提出這樣問題：從河岸或島上任一地方開始步行，能否通過每一座橋恰恰一次后又返回原地？瑞士數(shù)學家列昂納德歐拉（1707~1783）將這個問題簡化為一個如圖5-2所示的直觀數(shù)學模型，即用4個點表示兩岸和兩個小島，用兩點間聯(lián)線表示橋。于是問題轉化為：在該圖中，從任一點出發(fā)，能否通過每個線段一次且僅僅一次又回到原出發(fā)點。歐拉當時就證明出這是不可能實現(xiàn)的，并為此寫了被公認為世界第一篇有關圖論方面的論文，并于1736年由圣彼德堡科學院發(fā)表。

A

C

B

D

圖5-2

§1引言（2）有人提出這樣問題：從河岸或島上任一地方開§1引言（3）

圖論中的“四色猜想”是近代數(shù)學中沒有解決的最著名問題之一。即在一個平面或球面上的任何地圖只需用4種顏色來著色，便可使任何相鄰的兩個國家（具有公共的邊界線，不是僅一點相接）具有不同的顏色。該問題只需幾分鐘即可對不懂數(shù)學的人講清楚，然而數(shù)學家們化了一個多世紀時間也始終未徹底解決這個問題。雖然1976年美國的阿普爾、黑爾和考齊等三人依靠電子計算機用了1200個小時證明該猜想是正確的，然而并不理想，數(shù)學家們仍希望不依靠計算機給出證明。本書只準備介紹圖的基本概念以及圖論在諸如路徑問題、網(wǎng)絡流問題和匹配問題等領域中的應用。

§1引言（3）圖論中的“四色猜想”是近代數(shù)學中沒有解決§2圖的定義、分類及有關術語（1）

定義：一個圖是由一個表示具體事物的點（頂點）的集合和表示事物之間的聯(lián)系（邊）的集合所組成。分類：通常把圖分成兩類，圖邊不帶方向的無向圖及圖邊具有方向的方向圖。1．無向圖①定義及表示設V={v1，v2，，vn}是由一個由n個頂點組成的非空集合。E={e1，e2，，em}是一個由m條邊組成的集合，且知E中元素e是V中的一個無序元素對[u，v]。則稱V和E這兩個集合共同構成了一個無向圖G，記作G＝(V，E)?！?圖的定義、分類及有關術語（1）定義：一個圖是由一個表§2圖的定義、分類及有關術語（2）若e＝[u，v]＝[v，u]，則稱u與v為無向邊e之端點；邊e與頂點u、v相關聯(lián)；頂點u與v相鄰。

[例5-1]已知圖G＝（V，E）有5個頂點和8條邊，其點邊關系示于表5-1中

表5-1e

e1

e2

e3

e4

e5

e6

e7

e8

e＝[u,v][v1,v2][v2,v3][v3,v3][v3,v4][v2,v4][v4,v5][v2,v5][v2,v5]§2圖的定義、分類及有關術語（2）若e＝[u，v]＝[v§2圖的定義、分類及有關術語（3）其幾何圖形示于圖5-4中。②有關術語（在圖G(V，E)中）(i)平行邊（或多重邊，重復邊）：具有相同端點的邊。(ii)環(huán)：兩個端點落在一個頂點的邊。(iii)簡單圖：無平行邊和環(huán)的圖。(iv)完備圖：點點有通路，又無平行邊，這類圖又可稱完全圖或完美圖。

e3

v1

v2

v4

v3

v5

e1

e2

e4

e5

e6

e7

e8

圖5-4§2圖的定義、分類及有關術語（3）其幾何圖形示于圖5-4§2圖的定義、分類及有關術語（4）

2．有向圖①定義及表示E中元素e是V中一個有序元素對(u，v)，則稱V和E這兩個集合構成了一個有向圖G，記作G＝(V，E)。通常e=(u，v)表明u和v分別為邊e的起點和終點。

②有關術語

(i)平行邊（多重邊）：起終點全相同的邊。

(ii)環(huán)：起終點落為一個頂點的邊。

(iii)簡單圖：既無環(huán)又無平行邊的有向圖?！?圖的定義、分類及有關術語（4）2．有向圖§2圖的定義、分類及有關術語（5）

(iv)完備圖：圖中任意兩點u，v間有且僅有2條有向邊(u，v)及(v，u)的有向圖。(v)基本圖：將圖G中的有向邊全變?yōu)闊o向邊后所得的圖G’稱為G的基本圖。3．同構如果圖G=(V，E)和G’=(V’，E’)的各自頂點集合V與V’之間以及各自邊集合E與E’之間在保持關聯(lián)性質條件下一一對應，則稱圖G與G’同構，即同構圖的點邊關系一樣，而形狀和點邊符號可以不同。例如，圖5-6和圖5-7就是同構關系?！?圖的定義、分類及有關術語（5）(iv)完備圖：圖中任§2圖的定義、分類及有關術語（6）x

v

v3

w

h

e2

ae

c

d

f

圖5-7y

v2

v4

v3

v5

e1

e2

e4

e5

e6

e7

e8

圖5-6v1

e3

§2圖的定義、分類及有關術語（6）xvv3w§3圖的矩陣表示（1）

用矩陣表示無環(huán)圖中點與邊的聯(lián)接關系可使人們一目了然?？捎?種矩陣表示一個圖，是關聯(lián)矩陣、鄰接矩陣、回路矩陣、割集矩陣。我們只介紹最常用的前兩種矩陣。1．無向圖的矩陣表示①關聯(lián)矩陣A(G)，該矩陣是表示頂點與邊的聯(lián)接關系。令圖G=(V，E)，V={v1，v2，，vn}，E={e1，e2，，em}，則矩陣A(G)元素[aij]（A陣為n×m）定義為：

§3圖的矩陣表示（1）用矩陣表示無環(huán)圖中點與邊的聯(lián)接關系e6

v1

v2

v4

v3

v5

e1

e2

e4

e5

e7

圖5-8e3

e6

§3圖的矩陣表示（2）e6v1v2v4v3v5e1②鄰接矩陣B(G)，該陣表示頂點之間的鄰接關系。令圖G=(V，E)，V={v1，v2，，vn}，E={e1，e2，，em}，則矩陣B(G)元素[bij]（B陣為n×n）定義為：顯然，圖5-8的鄰接矩陣B(G)可表達為：§3圖的矩陣表示（3）②鄰接矩陣B(G)，該陣表示頂點之間的鄰接關系。令圖G=(V

2．有向圖的矩陣表示（與無向圖定義相似）①關聯(lián)矩陣A’(G)元素[a’ij]定義為：②鄰接矩陣B’(G)元素[b’ij]定義為以為vi起點和以vj為終點的邊數(shù)。針對有向圖5-9，可分別寫出相應的關聯(lián)矩陣A’(G)和鄰接矩陣B’(G)為：

§3圖的矩陣表示（4）2．有向圖的矩陣表示（與無向圖定義相似）§3圖的矩陣表示顯然，A’(G)中列元素和必為0。

B’(G)中，i行元素和為以vi為起點的有向邊數(shù)，j列元素和為以vj為終點的有向邊數(shù)。

v2

v1

e1

v4

v3

e2

e4

e5圖5-9e3

e6e7§3圖的矩陣表示（5）顯然，A’(G)中列元素和必為0。v2v1e1v§4子圖及其運算

1．子圖的有關定義：①設G1=(V1，E1)，G=(V，E)，若V1V，E1E，則稱G1為G的子圖，記為G1G。

②若G1G，且G1G時，稱G1為G的真子圖，記為G1G。③若G1G，且V1=V時，稱G1為G的生成子圖（即兩圖的頂點一樣）。2．子圖運算（略）

§4子圖及其運算1．子圖的有關定義：§5頂點的度(v)

在無向圖G=(V，E)中，與頂點v相聯(lián)的邊數(shù)，稱為v的度(v)。1．若(v)為偶數(shù)，稱為偶度頂點。若(v)為奇數(shù)，稱為奇度頂點。2．定理一：圖的頂點度之和為2m

（m為圖中總邊數(shù)）3．任一圖中，奇度頂點個數(shù)必為偶數(shù)。4．如果圖G=(V，E)中，所有頂點的度均相等，則稱G為正則的，頂點度均為的正則圖稱為度正則的。0度正則圖根本無邊，1度正則圖只有一條邊。

§5頂點的度(v)在無向圖G=(V，E)中，與頂點v§6圖的鏈、路及連通性

（1）

1．無向圖的有關術語設是無向圖G=(V，E)中的由頂點和邊交錯而成的非空有限有序列，且序列中邊的2個端點恰為序列中頂點與，則定義：①鏈：滿足上述條件的Q，即為G中的鏈。在簡單圖中，鏈可用頂點序列表示(因為無平行邊)，例如可寫為。②閉鏈和開鏈：在Q鏈中，在k＞0時，若，則稱Q為閉鏈，否則為開鏈。③初等鏈：開鏈Q中，頂點都不相同。

§6圖的鏈、路及連通性（1）1．無向圖的有關術語§6圖的鏈、路及連通性

（2）

④回路C：除起始點與終點重合外，其余頂點都不同的閉鏈稱為回路，記為C。⑤點連通：G中兩點u，v之間存在鏈，稱u，v是連通的。⑥連通圖：G中任兩點間都連通，則稱G為連通圖；否則稱為分離圖。G內頂點連通關系滿足等價關系。據(jù)此，可把G中頂點集合V分成幾個互不相交的子集V1，V2，，V，使得只有兩個頂點同屬一個子集時，才能連通。⑦分支：上述子集V1，V2，，V所對應的子圖G1，G2，，G稱為分支。圖G的分支個數(shù)記為(G)。⑧割邊：若eE(G)，且(E－e)>

(G)，則稱e為G的割邊。

§6圖的鏈、路及連通性（2）④回路C：除起始點與終點重§6圖的鏈、路及連通性

（3）

2．有向圖的有關術語①鏈（初等鏈）：若Q是有向圖G的基本圖中的一條鏈（初等鏈），則Q亦是G的鏈（初等鏈）。②路：若G的鏈中的每條邊恰以為起點，以為終點，則稱Q為從至的單向路，簡稱路。③路徑：G的路Q中每個頂點都不相同，稱Q為從至的單向路徑，簡稱路徑。

§6圖的鏈、路及連通性（3）2．有向圖的有關術語§6圖的鏈、路及連通性

（4）

④回路:起終點重合的單向路徑稱為單向回路，簡稱回路。⑤可達性：從u至v若存在路徑，稱u可達v。⑥連通圖：G中任意兩點間存在鏈的有向圖。⑦強連通圖：G中任意兩點間相互可達的有向圖。

§6圖的鏈、路及連通性（4）④回路:起終點重合的單向路§7樹及其性質（1）

1．樹的定義及術語①樹：無回路的連通無向圖稱為樹。②枝：樹中的邊稱為枝。③生成樹：若樹T是無向圖G的生成圖，則稱T是G的生成樹。④根：有向圖G中可以到達圖中任一頂點的頂點u稱為G的根。⑤根樹：若有向圖G有根u，且它的基本圖是一棵樹，則稱G

為以u為根的根樹或有向樹。§7樹及其性質（1）1．樹的定義及術語§7樹及其性質（2）

2．樹的性質①樹必連通，但無回路。②樹必有n－1條邊（設有n個頂點）。③樹無回路，但不相鄰頂點聯(lián)以一邊，恰得一回路。④樹連通，但去掉任一邊，必變?yōu)椴贿B通。⑤樹中任兩點間，恰有一條初等鏈。§7樹及其性質（2）2．樹的性質§1引言（1）

圖論是數(shù)學中廣泛應用的一個分支。早期圖論與“數(shù)學游戲”有著密切關系，所謂“哥尼斯堡七橋”問題就是其中之一。原東普魯士的哥尼斯堡城有一條普萊格爾河，河中有兩個小島，有7座橋把該河的兩個小島與河岸聯(lián)結起來，如圖5-1所示。圖5-1A

B

C

D

§1引言（1）圖論是數(shù)學中廣泛應用的一個分支。圖5§1引言（2）

有人提出這樣問題：從河岸或島上任一地方開始步行，能否通過每一座橋恰恰一次后又返回原地？瑞士數(shù)學家列昂納德歐拉（1707~1783）將這個問題簡化為一個如圖5-2所示的直觀數(shù)學模型，即用4個點表示兩岸和兩個小島，用兩點間聯(lián)線表示橋。于是問題轉化為：在該圖中，從任一點出發(fā)，能否通過每個線段一次且僅僅一次又回到原出發(fā)點。歐拉當時就證明出這是不可能實現(xiàn)的，并為此寫了被公認為世界第一篇有關圖論方面的論文，并于1736年由圣彼德堡科學院發(fā)表。

A

C

B

D

圖5-2

§1引言（2）有人提出這樣問題：從河岸或島上任一地方開§1引言（3）

圖論中的“四色猜想”是近代數(shù)學中沒有解決的最著名問題之一。即在一個平面或球面上的任何地圖只需用4種顏色來著色，便可使任何相鄰的兩個國家（具有公共的邊界線，不是僅一點相接）具有不同的顏色。該問題只需幾分鐘即可對不懂數(shù)學的人講清楚，然而數(shù)學家們化了一個多世紀時間也始終未徹底解決這個問題。雖然1976年美國的阿普爾、黑爾和考齊等三人依靠電子計算機用了1200個小時證明該猜想是正確的，然而并不理想，數(shù)學家們仍希望不依靠計算機給出證明。本書只準備介紹圖的基本概念以及圖論在諸如路徑問題、網(wǎng)絡流問題和匹配問題等領域中的應用。

§1引言（3）圖論中的“四色猜想”是近代數(shù)學中沒有解決§2圖的定義、分類及有關術語（1）

定義：一個圖是由一個表示具體事物的點（頂點）的集合和表示事物之間的聯(lián)系（邊）的集合所組成。分類：通常把圖分成兩類，圖邊不帶方向的無向圖及圖邊具有方向的方向圖。1．無向圖①定義及表示設V={v1，v2，，vn}是由一個由n個頂點組成的非空集合。E={e1，e2，，em}是一個由m條邊組成的集合，且知E中元素e是V中的一個無序元素對[u，v]。則稱V和E這兩個集合共同構成了一個無向圖G，記作G＝(V，E)。§2圖的定義、分類及有關術語（1）定義：一個圖是由一個表§2圖的定義、分類及有關術語（2）若e＝[u，v]＝[v，u]，則稱u與v為無向邊e之端點；邊e與頂點u、v相關聯(lián)；頂點u與v相鄰。

[例5-1]已知圖G＝（V，E）有5個頂點和8條邊，其點邊關系示于表5-1中

表5-1e

e1

e2

e3

e4

e5

e6

e7

e8

e＝[u,v][v1,v2][v2,v3][v3,v3][v3,v4][v2,v4][v4,v5][v2,v5][v2,v5]§2圖的定義、分類及有關術語（2）若e＝[u，v]＝[v§2圖的定義、分類及有關術語（3）其幾何圖形示于圖5-4中。②有關術語（在圖G(V，E)中）(i)平行邊（或多重邊，重復邊）：具有相同端點的邊。(ii)環(huán)：兩個端點落在一個頂點的邊。(iii)簡單圖：無平行邊和環(huán)的圖。(iv)完備圖：點點有通路，又無平行邊，這類圖又可稱完全圖或完美圖。

e3

v1

v2

v4

v3

v5

e1

e2

e4

e5

e6

e7

e8

圖5-4§2圖的定義、分類及有關術語（3）其幾何圖形示于圖5-4§2圖的定義、分類及有關術語（4）

2．有向圖①定義及表示E中元素e是V中一個有序元素對(u，v)，則稱V和E這兩個集合構成了一個有向圖G，記作G＝(V，E)。通常e=(u，v)表明u和v分別為邊e的起點和終點。

②有關術語

(i)平行邊（多重邊）：起終點全相同的邊。

(ii)環(huán)：起終點落為一個頂點的邊。

(iii)簡單圖：既無環(huán)又無平行邊的有向圖?！?圖的定義、分類及有關術語（4）2．有向圖§2圖的定義、分類及有關術語（5）

(iv)完備圖：圖中任意兩點u，v間有且僅有2條有向邊(u，v)及(v，u)的有向圖。(v)基本圖：將圖G中的有向邊全變?yōu)闊o向邊后所得的圖G’稱為G的基本圖。3．同構如果圖G=(V，E)和G’=(V’，E’)的各自頂點集合V與V’之間以及各自邊集合E與E’之間在保持關聯(lián)性質條件下一一對應，則稱圖G與G’同構，即同構圖的點邊關系一樣，而形狀和點邊符號可以不同。例如，圖5-6和圖5-7就是同構關系。§2圖的定義、分類及有關術語（5）(iv)完備圖：圖中任§2圖的定義、分類及有關術語（6）x

v

v3

w

h

e2

ae

c

d

f

圖5-7y

v2

v4

v3

v5

e1

e2

e4

e5

e6

e7

e8

圖5-6v1

e3

§2圖的定義、分類及有關術語（6）xvv3w§3圖的矩陣表示（1）

用矩陣表示無環(huán)圖中點與邊的聯(lián)接關系可使人們一目了然。可用4種矩陣表示一個圖，是關聯(lián)矩陣、鄰接矩陣、回路矩陣、割集矩陣。我們只介紹最常用的前兩種矩陣。1．無向圖的矩陣表示①關聯(lián)矩陣A(G)，該矩陣是表示頂點與邊的聯(lián)接關系。令圖G=(V，E)，V={v1，v2，，vn}，E={e1，e2，，em}，則矩陣A(G)元素[aij]（A陣為n×m）定義為：

§3圖的矩陣表示（1）用矩陣表示無環(huán)圖中點與邊的聯(lián)接關系e6

v1

v2

v4

v3

v5

e1

e2

e4

e5

e7

圖5-8e3

e6

§3圖的矩陣表示（2）e6v1v2v4v3v5e1②鄰接矩陣B(G)，該陣表示頂點之間的鄰接關系。令圖G=(V，E)，V={v1，v2，，vn}，E={e1，e2，，em}，則矩陣B(G)元素[bij]（B陣為n×n）定義為：顯然，圖5-8的鄰接矩陣B(G)可表達為：§3圖的矩陣表示（3）②鄰接矩陣B(G)，該陣表示頂點之間的鄰接關系。令圖G=(V

2．有向圖的矩陣表示（與無向圖定義相似）①關聯(lián)矩陣A’(G)元素[a’ij]定義為：②鄰接矩陣B’(G)元素[b’ij]定義為以為vi起點和以vj為終點的邊數(shù)。針對有向圖5-9，可分別寫出相應的關聯(lián)矩陣A’(G)和鄰接矩陣B’(G)為：

§3圖的矩陣表示（4）2．有向圖的矩陣表示（與無向圖定義相似）§3圖的矩陣表示顯然，A’(G)中列元素和必為0。

B’(G)中，i行元素和為以vi為起點的有向邊數(shù)，j列元素和為以vj為終點的有向邊數(shù)。

v2

v1

e1

v4

v3

e2

e4

e5圖5-9e3

e6e7§3圖的矩陣表示（5）顯然，A’(G)中列元素和必為0。v2v1e1v§4子圖及其運算

1．子圖的有關定義：①設G1=(V1，E1)，G=(V，E)，若V1V，E1E，則稱G1為G的子圖，記為G1G。

②若G1G，且G1G時，稱G1為G的真子圖，記為G1G。③若G1G，且V1=V時，稱G1為G的生成子圖（即兩圖的頂點一樣）。2．子圖運算（略）

§4子圖及其運算1．子圖的有關定義：§5頂點的度(v)

在無向圖G=(V，E)中，與頂點v相聯(lián)的邊數(shù)，稱為v的度(v)。1．若(v)為偶數(shù)，稱為偶度頂點。若(v)為奇數(shù)，稱為奇度頂點。2．定理一：圖的頂點度之和為2m

（m為圖中總邊數(shù)）3．任一圖中，奇度頂點個數(shù)必為偶數(shù)。4．如果圖G=(V，E)中，所有頂點的度均相等，則稱G為正則的，頂點度均為的正則圖稱為度正則的。0度正則圖根本無邊，1度正則圖只有一條邊。

§5頂點的度(v)在無向圖G=(V，E)中，與頂點v§6圖的鏈、路及連通性

（1）

1．無向圖的有關術語設是無向圖G=(V，E)中的由頂點和邊交錯而成的非空有限有序列，且序列中邊的2個端點恰為序列中頂點與，則定義：①鏈：滿足上述條件的Q，即為G中的鏈。在簡單圖中，鏈可用頂點序列表示(因為無平行邊)，例如可寫為。②閉鏈和開鏈：在Q鏈中，在k＞0時，若，則稱Q為閉鏈，否則為開鏈。③初等鏈：開鏈Q中，頂點都不相同。

§6圖的鏈、路及連通性（1）1．無向圖的有關術