圖論千言萬語不及一張圖哥尼斯堡七橋問題:可否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點?ABDC七橋問題模型圖歐拉(1736):如果每塊陸地所連接的橋都是偶數(shù)座,那么可;否那么,不可.引言環(huán)球旅行問題([英]哈密頓.1859):十二面體的20個頂點代表世界上20個城市,能否從某個城市出發(fā)沿著十二面體的棱經(jīng)過每個城市恰好一次,最后回到出發(fā)點?十二面體骨架圖十二面體(?25)四色問題對任何一張地圖進行著色,兩個有共同邊界的國家染不同的顏色,那么只需要四種顏色就夠了.ABCFED同位素問題:圖論中的“圖〞(graph)這個術(shù)語最早用來表示化學(xué)結(jié)構(gòu):點表示原子,邊表示化學(xué)鍵.C3H7OH的兩個同位素的結(jié)構(gòu)圖(樹):碳(C),氫(H),氧(O)各有4個,1個,2個價電子.碳60分子球:碳同位素C60(1985.諾貝爾獎1996,另兩種為金剛石和石墨).目前,對Fullerene的分子結(jié)構(gòu)的研究在國際圖論界,化學(xué)界很熱門.C60的分子模型:20個正六邊形和12個正五邊形相互連接C60的分子模型:20個正六邊形和12個正五邊形相互連接現(xiàn)實中有大量問題適合用“點—邊〞圖形來描述.這種圖形叫做“圖〞.ABDC圖論的首篇論文:[瑞士]歐拉/Euler.哥尼斯堡七橋問題無解.1736.圖論的第一部專著:[匈]寇尼格/Konig.有限圖與無限圖理論.1936年.

標(biāo)志著圖論開始突飛猛進.近40年來,圖論開展速度驚人,活潑非凡.主要原因是:①計算機為圖論提供了計算工具;②現(xiàn)代科技在圖論中找到描述和解決問題的犀利手段.目前,圖論在計算機科學(xué)、物理學(xué)、化學(xué)、運籌學(xué)、信息論、控制論、網(wǎng)絡(luò)通訊、社會科學(xué)以及經(jīng)濟管理等諸多領(lǐng)域有著廣泛的應(yīng)用.

預(yù)備知識：1.有序積:AB={a,b|aAbB}.有序?qū),

b

b,

a.2.無序積:A&B={(a,

b)|aA

bB}.無序?qū)?a,

b)=(b,

a).3.多重集

{a,

a,

b,

b,

b,

c,

d}

=

{2a,

3b,

1c,

1d}

{a,

b,

c,

d}.a,b,c,d的重復(fù)度分別為2,3,1,1.?無序?qū)?/p>

(a,

b)

就是多重集

{a,

b},允許

a

=

b.??

A&B

=

B&A.無序積與多重集主要內(nèi)容：圖通路與回路圖的連通性圖的矩陣表示圖的運算第14章圖的根本概念圖的定義:圖是一種數(shù)學(xué)結(jié)構(gòu)，是一個數(shù)學(xué)概念,它的圖形表示叫做圖解.1.無向圖G=V,E,φG,其中V,多重集EV&V.例如G=V,E,φG,其中V={a,b,e,d,e},E={(a,a),(a,b),(b,c),(b,c),(b,e),(a,e),(d,e).2.把&改為,那么為有向圖.?相關(guān)概念:頂點集,頂點,邊集,

無向邊,有向邊.?有向圖表示二元關(guān)系,無向圖表示對稱的二元關(guān)系.ae1e2e3e4e5e6e7bcde一.圖的定義及相關(guān)概念圖例有向圖

D

=

V,

E,φG

,其中

V

=

{a,

b,

c,

d},

E

=

{a,

a,

a,

b,

a,

b,

a,

d,

c,

d,

d,

c,

c,

b}

VV,可圖解為ae1e2e3e6e7e4e5bcd有序?qū)?orderedpair,多重集/multiset,重復(fù)度/multiplicity.圖/graph,無向圖/undirectedgraph,頂點/vertex(pl.vertices),邊/edge,有向圖/directedgraph,digraph,有向邊/directededge,圖解/diagram圖例設(shè)圖

G

的圖解如下.求

G

(集合表示).e3e2e1uwv

G

=

V,

E =

{u,

v,

w},

{e1,

e2,

e3} ={u,

v,

w},

{(u,

u),

(u,

v),

(v,

w)}.G

=

V,

E

或

D

=

V,

E.V(G)

=

V.E(G)

=

E.?本課程中只討論有限圖.??空圖不是圖!但在圖的運算中可能產(chǎn)生頂點集為空集的運算結(jié)果.

n

階圖:|V|

=

n.

有限圖:|V|

<

,|E|

<

.

n

階零圖

Nn:E

=

.

平凡圖:N1.

空圖:?

=

V,

E

=

,

N4N1?標(biāo)定圖,非標(biāo)定圖,基圖(1)標(biāo)定圖e3ve2e1uw(2)非標(biāo)定圖(3)標(biāo)定圖e3ve2e1uw?(1)是(3)的基圖.n階圖/graphofordern,有限圖/finitegraph,零圖/nullgraph,平凡圖/trivialgraph,空圖/emptygraph,標(biāo)定圖/labelledgraph,非標(biāo)定圖/unlabelledgraph,基圖/basegraph端點,關(guān)聯(lián):點與邊關(guān)聯(lián)次數(shù):環(huán):孤立點:相鄰:點與點,邊與邊鄰接到(于):點與點,邊與邊始點,終點11112?end-vertex,incident,loop,isolatedvertex,adjacent,adjacent

to,adjacent

from,initialvertex,terminatingvertexe1e2uve鄰域

NG(v).閉鄰域NG(v).關(guān)聯(lián)集

IG(v).(閉)鄰域/(closed)neighborhood,關(guān)聯(lián)集/incidencyset,后繼/successor,先驅(qū)/predecessorv后繼元集:+(v).先驅(qū)元集:

(v).鄰域:N(v)=

+(v)

(v).閉鄰域:N(v)=N(v){v}.v一個圖會有不同的圖解.圖形

1,

2都是圖

G

的圖解.abcd1cdab2G

=

{a,

b,

c,

d},

{(a,

b),

(a,

c),

(a,

d),

(b,

c),

(b,

d),

(c,

d)}.二.簡單圖與多重圖

平行邊:關(guān)聯(lián)于同一對頂點的多條邊(在有向圖中它們方向相同).重數(shù):平行邊的條數(shù).多重圖:含平行邊的圖.簡單圖:既不含平行邊也不含環(huán)的圖.(1)3重平行邊(2)2重平行邊(3)簡單圖(4)簡單圖平行邊/paralleledge,重數(shù)/multiplicity,多重圖/multiplegraph,簡單圖/simplegraph圖論中,無向簡單圖被研究得較多.在一些圖論書籍中,“圖〞(graph)這個術(shù)語專指無向簡單圖.例2右邊哪幾個圖準確表示左邊的陸地－橋梁地圖?答Graph1和Graph3.三.頂點的度數(shù)及相關(guān)定理度數(shù)：

d(v).有向圖

D

中,出度

d+(v);入度

d

(v).顯然,d(v)

=

d+(v)

+

d

(v).d+(v)

=

3

+

1

=

4,d(v)

=

2

+

1

=

3,d(v)

=

4

+

3

=

7.度/degree,出度/outdegree,入度/indegree定理7-1.1〔握手定理〕無向圖G=V,E中所有頂點度數(shù)之和等于邊數(shù)的兩倍:證

圖中每條邊(包括環(huán))均有兩個端點,在計算

各頂點度數(shù)之和時,每條邊均提供

2

度.圖例注意到

d(v3)

=

6

5,

d(v)

=

3

+

3

+

6

+

2

=

14,|E|

=

7,

d(v)

=

2|E|.每條環(huán)與點關(guān)聯(lián)次數(shù)為2!v1v2v3v4握手定理(有向圖)

有向圖

D

=

V,

E

中頂點入數(shù)之和與出度之和相等,都等于邊數(shù),即證

圖中每條邊(包括環(huán))都有一個始點和一個終點,在計算圖中頂點度數(shù)之和時,每條邊均提供

1

個出度和

1

個入度.圖例

|E|

=

7,d+(v)

=

2

+

1

+

4

+

0

=

7

=

|E|,d(v)

=

1

+

2

+

2

+

2

=

7

=

|E|.v1v2v3v4推論:任何圖(無向或有向)中,奇度頂點的個數(shù)是偶數(shù).證設(shè)V1

和V2分別是G中奇頂點集和偶頂點集.由握手定理最大度

(G),最小度

(G).有向圖D中,最大出度

+(D),最大入度

(D),

最小出度

+(D),最小入度－(D),.懸掛頂點,懸掛邊.偶度頂點(偶點),奇度頂點(奇點).v4是懸掛頂點,e2是懸掛邊.奇點:v1,

v4.偶點:v2,

v3.

=

4,

=

1e5v1v2v3e3e1e4v4e2懸掛頂點/pendantvertex,懸掛邊/pendantedge,奇度頂點/oddvertex,偶度頂點/evenvertex圖例(1)度數(shù)列4,

4,

2,

1,

3.(2)度數(shù)列5,

3,

3,

3;出度列

4,

0,

2,

1;入度列

1,

3,

1,

2.v1v2v3v4v5abcd(1)(2)度數(shù)列:

d(v1),d(v2),…,d(vn).對于有向圖,

出度列,入度列.證明的說明1G33739246構(gòu)圖思路先把

2k

個奇度頂點配對連邊.去掉這些邊后度數(shù)列僅含偶數(shù),用環(huán)來實現(xiàn).d'

=

(0,

2,

2,

6,

2,

8,

2,

4,

6).

可圖化的與可簡單圖化的非負整數(shù)列d

=

(d1,

d2,

d3,

d4,

d5,

d6,

d7,

d8,

d9)

=

(1,

3,

3,

7,

3,

9,

2,

4,

6)定理

(可圖化的充要條件)

非負整數(shù)列

d

=

(d1,

d2,

…

,

dn)

是可圖化的是偶數(shù).證由握手定理知必要性.下面證明充分性.因di是偶數(shù),d中有2k(0kn/2)個奇數(shù),不妨設(shè)為d1,d2,…,dk,dk+1,dk+2,…,d2k.可按如下兩步做出度數(shù)列為d的圖G=V,E,V={v1,v2,…,vn}:①在頂點vr與vr+k之間連邊,r=1,2,…,k.假設(shè)di為偶數(shù),令d'i=di,假設(shè)di為奇數(shù),令d'i=di1,得d'=(d'1,d'2,…,d'n),其中d'i均為偶數(shù).②在vi處做出d'i/2條環(huán),i=1,2,…,n.將①,②所得各邊組成邊集E,那么G的度數(shù)列為d:當(dāng)di為偶數(shù)時,d(vi)=2·d'i/2=d'i=di;當(dāng)di為奇數(shù)時,d(vi)=1+2·d'i/2=1+d'i=1+(di1)=di.這就證明了d是可圖化的.QED證由握手定理可知必要性顯然.下面證明充分性.因di是偶數(shù),d中有2k(0kn/2)個奇數(shù),不妨設(shè)為d1,d2,…,dk,dk+1,dk+2,…,d2k.可按如下兩步做出度數(shù)列為d的圖G=V,E,V={v1,v2,…,vn}:①在頂點vr與vr+k之間連邊,r=1,2,…,k.假設(shè)di為偶數(shù),令d'i=di,假設(shè)di為奇數(shù),令d'i=di1,得d'=(d'1,d'2,…,d'n),其中d'i均為偶數(shù).②再在vi處做出d'i/2條環(huán),i=1,2,…,n.將①,②所得各邊組成邊集E,那么G的度數(shù)列為d:當(dāng)di為偶數(shù)時,d(vi)=2·d'i/2=d'i=di;當(dāng)di為奇數(shù)時,d(vi)=1+2·d'i/2=1+d'i=1+(di1)=di.這就證明了d是可圖化的.QED可簡單圖化的必要條件:定理對任意

n

階無向簡單圖

G,有

(G)

n

1.證

G

既無平行邊也無環(huán),所以

G

中任何頂點

v

至多與其余的

n

1

個頂點以

1

條邊相鄰.QED例3可圖化?可簡單圖化?(1)(5,

5,

4,

4,

2,

1)(2)(5,

4,

3,

2,

2)(3)(3,

3,

3,

1)(4)(d1,

d2,

…

,

dn),d1>

d2>

…

>

dn

1且為偶數(shù)(5)(4,

4,

3,

3,

2,

2)可圖化原因可簡單圖化原因(1)奇?zhèn)€奇點不可圖化(2)和是偶數(shù)>n1(3)和是偶數(shù)去掉懸掛點(4)和是偶數(shù)>n1(5)和是偶數(shù)見后(5)(4,

4,

3,

3,

2,

2)

可簡單圖化?(0,

3,

2,

2,

1,

2)

可簡單圖化?(0,

0,

1,

1,

1,

1)

可簡單圖化?(0,

0,

1,

1,

1,

1)(0,

3,

2,

2,

1,

2)(4,

4,

3,

3,

2,

2)上例(5)的構(gòu)圖思路可用來導(dǎo)出可簡單圖化的充要條件.是可簡單圖化的.?對非負整數(shù)列,其中的

0

可用孤立點來實現(xiàn).剔除孤立點后得正整數(shù)列.??定理是構(gòu)造性的:通過降低度的數(shù)目來構(gòu)圖.定理(V.Havel,1955):正整數(shù)列d=(d1,d2,…,dn),n1

d1

d2…

dn是可簡單圖化的經(jīng)修正過的非負整數(shù)列例4可否簡單圖化?(1)(5,5,4,4,2,2), (2)(4,4,3,3,2,2)解:(1)(5,5,4,4,2,2)

(4,3,3,1,1)

(2,2,0,0)

(1,1,0),不可簡單圖化.(2)(4,4,3,3,2,2)(3,2,2,1,2)(3,2,2,2,1)(1,1,1,1)(0,1,1)(1,1),可簡單圖化.QEI??例5構(gòu)圖問題畫出

4

個

3

度頂點,4

個

2

度頂點的簡單圖.解anymore?What'sthedifference?G

=

V,

E

=

{a,

b,

c,

d},

{(a,

b),

(a,

d),

(b,

c),

(b,

d),

(c,

d)}.G'

=

V',

E'

=

{a',

b',

c',

d'},

{(a',

b'),

(a',

d'),

(b',

c'),

(b',

d'),

(c',

d')}.G'f

:

V

V'a

a'b

b'c

c'd

d'Gdabcc'd'a'b'G

G'.同構(gòu)是在兩個圖的頂點之間建立的一一對應(yīng),使得頂點的鄰接情況是相同的，圖G1、G2同構(gòu)記為

G1

G2.四、圖的同構(gòu)〔重要〕圖的同構(gòu)定義定義14.5設(shè)G1=<V1,E1>,G2=<V2,E2>為兩個無向圖(有向圖)，假設(shè)存在雙射函數(shù)f:V1V2,對于vi,vjV1,(vi,vj)E1當(dāng)且僅當(dāng)(f(vi),f(vj))E2〔<vi,vj>E1當(dāng)且僅當(dāng)<(f(vi),f(vj)>E2〕并且,(vi,vj)與(f(vi),f(vj))〔<vi,vj>與<f(vi),f(vj)>〕〕的重相同，那么稱G1與G2是同構(gòu)的，記作G1G2.圖之間的同構(gòu)關(guān)系具有自反性、對稱性和傳遞性.能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件：①邊數(shù)相同，頂點數(shù)相同;②度數(shù)列相同;③對應(yīng)頂點的關(guān)聯(lián)集及鄰域的元素個數(shù)相同，等等假設(shè)破壞必要條件，那么兩圖不同構(gòu)判斷兩個圖同構(gòu)是個難題圖例以下各圖彼此同構(gòu),叫做彼得松圖.(1)(2)(3)彼得松圖/Petersen'sgraph圖例以下各圖彼此都不同構(gòu).(4)(5)(6)容易看出它們同構(gòu)嗎?這兩個呢?圖同構(gòu)的判別方法尚未找到判斷圖同構(gòu)的好算法.圖同構(gòu)的必要條件:

階數(shù)相同,邊數(shù)相同,度數(shù)列相同,….例6(1)畫出

4

階

3

條邊的所有非同構(gòu)的無向簡單圖.(2)畫出

3

階

2

條邊的所有非同構(gòu)的有向簡單圖.解(1)d(v)

=

23

=

6,

4

1

=

3,度數(shù)列滿足d1+

d2+

d3+

d4=

6,0

di

3,di中有偶數(shù)個奇數(shù).可能的情況:(a)

3,

1,

1,

1;(b)

2,

2,

1,

1;(c)

2,

2,

2,

0(2)3,1,1,1(1)2,2,1,1(3)2,2,2,0K4(2)畫出

3

階2條邊的所有非同構(gòu)的有向簡單圖.d(v)=22=4,+,41=3.度數(shù)列1,2,12,

2,

0入度列0,

1,

10,

2,

01,

0,

11,

1,

0出度列1,

1,

01,

0,

10,

2,

01,

1,

0①②③④①②③④?給定

n,

m+,構(gòu)造出

n

階

m

條邊的所有非同構(gòu)的簡單圖,這問題目前還沒解決.無向完全圖/completegraphK1K2K3K4K5K6有向完全圖/completedigraph1階2階3階4階五、完全圖〔重要〕易知,n

階無向完全圖,n

階有向完全圖的邊數(shù)分別為

n(n

1)/2,n(n

1).

Kn

有n(n1)/2條邊,

因為(n

1)

+

(n

2)

+

…

+

2

+

1

=

n(n

1)/2,

也因為Cn2

=

n(n

1)/2.

還因為

Kn

每個頂點的度數(shù)是

n

1,度數(shù)之和為

n(n

1).根據(jù)握手定理,邊數(shù)是

n(n

1)/2.K5例如,|E(K5)|

=

4

+

3

+

2

+

1

=

C52=

n(n

1)/2

=

10.n階完全圖與競賽圖定義14.6(1)n(n1)階無向完全圖——每個頂點與其余頂點均相鄰的無向簡單圖，記作Kn.簡單性質(zhì)：邊數(shù)(2)n(n1)階有向完全圖——每對頂點之間均有兩條方向相反的有向邊的有向簡單圖.簡單性質(zhì)：(3)n(n1)階競賽圖——基圖為Kn的有向簡單圖.簡單性質(zhì)：邊數(shù)

頂點度數(shù)都是k的無向簡單圖叫做k-正那么圖.?3-正那么圖特別有研究價值.N1=

K1K2K3K40-正那么1-正那么2-正那么3-正那么k-正那么圖/k-regulargraph六、正那么圖

1、r

部圖:頂點集劃分成

r

類,同類頂點不相鄰.4

部圖2

部圖r部圖/r-partitegraph,二部圖/bipartitegraph七、二部圖和r部圖2、完全

r

部圖:頂點集劃分成

r

類,同類頂點不相鄰;不同類的頂點都相鄰.完全

4

部圖

K1,2,2,3完全

2

部圖

K3,4完全

r

部圖/completer-partitegraph,完全二部圖/completer-partitegraph.星圖/stars:星形圖

S6=

K1,5輪圖/wheels:W2W3W4W5八、其他四種圖〔了解〕路徑圖/paths:P1P2P3P4圈圖/cycles:C1C2C3C4設(shè)圖

G

=

V,

E,

G'

=

V',

E',子圖G'

G

(母圖):

V'

V

且

E'

E.真子圖:

V'

V

或

E'

E.生成子圖:

G'

G

且V'

=

V.子圖/subgraph,母圖/supgraph,真子圖/propersub-graph,生成子圖/spanningsubgraph九、子圖v1e1e2e3e4e5e7v2v3v5圖例(2)是(1)的子圖,(3),(4)是(1)的生成子圖.v1e1e2e3e4e5e6e7v2v3v4v5(1)(2)v1e1e2e3e4e5e6v2v3v4v5v1e2e3e4e5e6v2v3v4v5(3)(4)圖例點集

V1=

{v1,

v2,

v4,

v5}

和邊集

E1=

{e2,

e3,

e4,

e5}

導(dǎo)出的子圖.v1e1e2e3e4e5e6e7v2v3v4v5(1)e6v3v1