離散數(shù)學(xué)王元元習(xí)題解答

千里之行，始于足下。第2頁(yè)/共2頁(yè)精品文檔推薦離散數(shù)學(xué)王元元習(xí)題解答第三篇圖論

第八章圖

圖的基本知識(shí)

內(nèi)容提要

8.1.1圖的定義及有關(guān)術(shù)語(yǔ)

定義圖（graph）G由三個(gè)部分所組成：

（1）非空集合V(G)，稱為圖G的結(jié)點(diǎn)集，其成員稱為結(jié)點(diǎn)或頂點(diǎn)（nodesorvertices）。

（2）集合E(G)，稱為圖G的邊集，其成員稱為邊(edges)。I

（3）函數(shù)Ψ

G

：E(G)→(V(G)，V(G))，稱為邊與頂點(diǎn)的關(guān)聯(lián)映射（associatvemapping）。

這個(gè)地方（V(G)，V(G)）稱為VG的偶對(duì)集，其成員偶對(duì)（pair）形如（u，

v），u，v為結(jié)點(diǎn)，它們未必別同。Ψ

G

(e)=(u,v)時(shí)稱邊e關(guān)聯(lián)端點(diǎn)u，v。當(dāng)(u,v)用作序偶時(shí)(V(G)，V(G))=V(G)?V(G)，e稱為有向邊，e以u(píng)為起點(diǎn),以v為終點(diǎn),圖G稱為有向圖（directedgraph）；當(dāng)(u,v)用作無(wú)序偶對(duì)時(shí)，(u,v)=(v,u)，稱e為無(wú)向邊（或邊），圖G稱為無(wú)向圖（或圖）。

圖G常用三元序組,或來(lái)表示。顯然，圖是一種數(shù)學(xué)結(jié)構(gòu)，由兩個(gè)集合及其間的一具映射所組成。

定義8.2設(shè)圖G為。

（l）當(dāng)V和E為有限集時(shí)，稱G為有限圖，否則稱G為無(wú)限圖。本書只討論有限圖。

（2）當(dāng)Ψ

G為單射時(shí)，稱G為單圖；當(dāng)Ψ

G

為非單射時(shí)，稱G為重圖，

又稱滿腳Ψ(e1)=Ψ(e2)的別同邊e1,e2,為重邊,或平行邊。

（3）當(dāng)Ψ(e)＝(v,v)（或）時(shí)，稱e為環(huán)（loops）。無(wú)環(huán)和重邊的無(wú)向單圖稱為簡(jiǎn)單圖。當(dāng)G為有限簡(jiǎn)單圖時(shí)，也常用（n，m）表示圖G，其中n=?V?，m=?E?。

（4）Ψ為雙射的有向圖稱為有向徹底圖；對(duì)每一(u，v)，u?v，均有e使Ψ(e)＝(u,v)的簡(jiǎn)單圖稱為無(wú)向徹底圖，簡(jiǎn)稱徹底圖，n個(gè)頂點(diǎn)的

徹底圖常記作K

n

。

（5）在單圖G中，Ψ(e)＝(u,v)（或）時(shí)，也用(u,v)(或)表示邊e，這時(shí)稱u，v鄰接e,u,v是e的端點(diǎn)（或稱u為e的起點(diǎn)，v為e的終點(diǎn)）;也稱e關(guān)聯(lián)結(jié)點(diǎn)u,v。別是任何邊的端點(diǎn)的結(jié)點(diǎn)都稱為孤立結(jié)點(diǎn)，僅由孤立結(jié)點(diǎn)構(gòu)成的圖（E=?）稱為零圖。

（6）當(dāng)給G給予映射f：V→W，或g：E→W，W為任意集合，常用實(shí)數(shù)集及其子集,

此刻稱G為賦權(quán)圖，常用或或表示之。f(v)稱為結(jié)點(diǎn)v的

權(quán)，g(e)稱為邊e的權(quán)。

8.1.2結(jié)點(diǎn)的度

定義在無(wú)向圖中，結(jié)點(diǎn)v的度（degree）d(v)是v作為邊的端點(diǎn)的數(shù)目。在有向圖中，結(jié)點(diǎn)的度d(v)是v的出度d+(v)（out-degree）與入度d-(v)（in-degree）的和；v的出度是v作為有向邊起點(diǎn)的數(shù)目，v的入度是v作為有向邊終點(diǎn)的數(shù)目。

定理對(duì)任意圖G，設(shè)其邊數(shù)為m,頂點(diǎn)集為{v

1，v

2

，…，v

n

}，這么

∑==

n

i

i

m

v

d

1

2

)

(

定理圖的奇數(shù)度頂點(diǎn)必為偶數(shù)個(gè)。

定理自然數(shù)序列（a

1,a

2

,…,a

n

）稱為一具度序列，假如它是一具圖的

頂點(diǎn)的度的序列。（a

1,a

2

,…,a

n

）為一度序列，當(dāng)且僅當(dāng)∑

=

n

i

i

a

1

為一偶數(shù)。

定義一度的頂點(diǎn)稱為懸掛點(diǎn)（pendantnodes）。

定義各頂點(diǎn)的度均相同的圖稱為正則圖（regulargraph）。各頂點(diǎn)度均為k的正則圖稱為k-正則圖。

8.1.3圖運(yùn)算及圖同構(gòu)

由于圖由結(jié)點(diǎn)集、邊集及關(guān)聯(lián)映射組成，所以對(duì)圖可作種種與集合運(yùn)算相類似的運(yùn)算。

定義設(shè)圖G1＝，G2＝，稱G1為G2的子圖（subgraph），假如V1?V2，E1?E2，Ψ1?Ψ2。稱G1為G2的真子圖，假如G1是G2的子圖，且G1?G2。稱G1為G2的生成子圖（spanningsubgraph），假如G1是G2的子圖，且V1=V2。

定義設(shè)圖G1＝，G2＝，且Ψ1與Ψ2是相容的，即對(duì)任一x，若Ψ1(x)=y1,Ψ2(x)=y2，則y1=y2，從而Ψ1?Ψ2為一函數(shù)。

（1）G1與G2的并，記為G1?G2＝G3＝，其中V3=V1?V2，E3=E1?E2，Ψ3=Ψ1?Ψ2。

（2）G1與G2的交,記為G1?G2=G3=，其中V3=V1?V2，E3=E1?E2，Ψ3=Ψ1?Ψ2。

（3）若G1為G2的子圖，則可定義G2對(duì)G1的差，記為G2－G1＝G3＝，其中E3=E2–E1，V3＝V2，Ψ3=Ψ2?

。

E3（4）G1與G2的環(huán)和，記為G1?G2，

G1?G2＝(G1?G2)－(G1?G2)

（5）若G為簡(jiǎn)單圖，則可定義G的補(bǔ)，記為Gˉ，若?V(G)?=n，則Gˉ=K

－G

n

定義設(shè)圖G＝

（1）G－e表示對(duì)G作刪除邊e的運(yùn)算，G－e=，其

。

中E’＝E－{e}，Ψ’=Ψ?

E’

（2）G－v表示對(duì)G作刪除頂點(diǎn)v的運(yùn)算，G－v=，

。

其中V’=V－{v}，E’＝E－{e?e以v為端點(diǎn)}，Ψ’＝Ψ?

E’（3）邊e切割運(yùn)算。設(shè)G中Ψ(e)=(u,v),對(duì)G作邊e切割得G’＝，其中，V’＝V?{v’}，E’=(E－{e})?{e1,e2},Ψ’=(Ψ－{})?{，}

（4）頂點(diǎn)v貫穿運(yùn)算。設(shè)G中頂點(diǎn)v恰為邊e1,e2的端點(diǎn)，且Ψ(e1)=(u,v)，Ψ(e2)=(w,v)。對(duì)G作頂點(diǎn)v貫穿得G’＝，其中V’=V－{v},E’=(E－{e1,e2})?{e},Ψ’=(Ψ－{,})?{}。

切割與貫穿是互逆的，兩者常被稱為同胚運(yùn)算。

定義設(shè)G1＝，G2＝為兩個(gè)圖，稱G1與G2同構(gòu)（isomorphic），假如存在雙射f：V1→V2，雙射g：E1→E2，使得對(duì)每一邊e?E1，

Ψ1(e)＝(u,v)（或）當(dāng)且僅當(dāng)Ψ2(g(e))=(f(u),f(v))（或

）

當(dāng)限于討論簡(jiǎn)單圖時(shí)，能夠用頂點(diǎn)的偶對(duì)表示邊，即當(dāng)Ψ(e)＝(u,v)

時(shí)，邊e用(u,v)來(lái)表示。這時(shí)兩圖同構(gòu)的條件能夠簡(jiǎn)化為

(u,v)?E1當(dāng)且僅當(dāng)(f(u),f(v))?E2

習(xí)題解答

練習(xí)

1、想一想，一只昆蟲是否也許從立方體的一具頂點(diǎn)動(dòng)身，沿著棱爬行、

它爬行過(guò)每條梭一次且僅一次，同時(shí)最后回到原地為啥

解不會(huì)。可將立方體的一具頂點(diǎn)看作圖的一具頂點(diǎn)，把立方體的棱

看作圖的邊，這么該圖的四個(gè)頂點(diǎn)基本上三度的，所以不會(huì)從一具頂點(diǎn)

動(dòng)身，遍歷所有的邊一次且僅一次，同時(shí)最后回到原頂點(diǎn)。

2、請(qǐng)?jiān)O(shè)想一張圖，它的64個(gè)頂點(diǎn)表示國(guó)際象棋棋盤的64個(gè)方格，頂

點(diǎn)間的邊表示:在這兩個(gè)頂點(diǎn)表示的方格之間能夠舉行“馬步”的行

走。試指出其頂點(diǎn)有哪幾類（依其度分類），每類各有多少個(gè)頂點(diǎn)。

解其頂點(diǎn)有5類：二度頂點(diǎn)合計(jì)4個(gè),三度頂點(diǎn)合計(jì)8個(gè),四度頂點(diǎn),

合計(jì)20個(gè),六度頂點(diǎn),合計(jì)16個(gè)頂點(diǎn),八度頂點(diǎn),合計(jì)16個(gè)頂點(diǎn)。

3、（l）證明：n個(gè)頂點(diǎn)的簡(jiǎn)單圖中不可能有多于

2)1

(-

n

n

條邊。（2）n個(gè)頂點(diǎn)的有向徹底圖中恰有2n條邊。

證（l）n個(gè)頂點(diǎn)的簡(jiǎn)單徹底圖的邊數(shù)總和為

2)1

(

1

2

)2

(

)1

(-

=

+

+

+

-

+

-

nn

n

n

（2）n個(gè)頂點(diǎn)的有向徹底圖的邊數(shù)總和為

2

n

n

n

n

n

n

n=

?

=

+

+

+

+

4、證明:在任何n(n≥2)個(gè)頂點(diǎn)的簡(jiǎn)單圖G中，至少有兩個(gè)頂點(diǎn)具有

相同的度。

證假如G有兩個(gè)孤立頂點(diǎn)，這么它們便是具有相同的度的兩個(gè)頂點(diǎn)。

假如G恰有一具孤立頂點(diǎn)，這么我們可對(duì)有n–1個(gè)頂點(diǎn)但沒有孤立頂點(diǎn)的G’（它由G刪除孤立頂點(diǎn)后得到）作下列討論。

別妨設(shè)G沒有孤立頂點(diǎn)，這么G的n個(gè)頂點(diǎn)的度數(shù)應(yīng)是：1，2，3，…，n–1這n–1種

也許之一，所以必然有兩個(gè)頂點(diǎn)具有相同的度。

5、圖是一具迷宮,其中數(shù)字表示通道、和死胡同(包括目標(biāo))。請(qǐng)用一具圖來(lái)表示那個(gè)迷宮(用結(jié)點(diǎn)表示通道、和死胡同(包括目標(biāo))),用邊表示它們之間的可直截了當(dāng)?shù)竭_(dá)關(guān)系。

圖解

6、在晚會(huì)上有n個(gè)人，他們各自與自個(gè)兒相識(shí)的人握一次手。已知每人

與不人握手的次數(shù)基本上奇數(shù)，咨詢n是奇數(shù)依然偶數(shù)。為啥

解n是偶數(shù)。用n個(gè)頂點(diǎn)表示n個(gè)人，頂點(diǎn)間的一條邊表示一次握手，可構(gòu)成一具無(wú)向圖。若n是奇數(shù)，這么該圖的頂點(diǎn)度數(shù)之和為奇數(shù)（奇數(shù)個(gè)奇數(shù)的和），這是不會(huì)的，所以n是偶數(shù)。

7、n個(gè)都市間有m條相互連接的直達(dá)公路。證明：當(dāng)

2

)

2)(1(-->nnm時(shí)，人們便能經(jīng)過(guò)這些公路在任何兩個(gè)都市間旅行。

2118

3

17

4

520211

615

證用n個(gè)頂點(diǎn)表示n個(gè)都市，頂點(diǎn)間的邊表示直達(dá)公路，據(jù)題意需證這n個(gè)都市的公路網(wǎng)絡(luò)所構(gòu)成的圖G是連通的。反設(shè)G別連通，這么可設(shè)G由兩個(gè)別相關(guān)的子圖（沒有任何邊關(guān)聯(lián)分不在兩個(gè)子圖中的頂點(diǎn)）G1，G2組成，分不有n1，n2個(gè)頂點(diǎn)，從而，n=n1+n2，n1≥1，n2≥1。由于各子圖的邊數(shù)別超過(guò)2

)

1(-iinn(見練習(xí)之3)，所以G的邊數(shù)m滿腳：

))1()1((2

1

)1(2122111-+-=-≤∑=nnnnnnmkiii

))1)(1()1)(1((2

1

21--+--=

nnnn)2)(1(2

1

)2)(1(2

1

21--=-+-=

nnnnn

與已知2

)

2)(1(-->

nnm矛盾，故圖G是連通的。

（本題是定理的特例，固然也能夠應(yīng)用這一定理和它的證明辦法來(lái)解題。）

*8、（1）證明：序列（7，6，5，4，3，3,2），（6，5，5，4，3，2，2）以及（6，6，5，4，3，3，1）都別是簡(jiǎn)單圖的度序列。

（2）若自然數(shù)序列（d1,d2,…,dn）滿腳d1>d2>…>dn，這么當(dāng)它為一簡(jiǎn)單圖的度序列時(shí)必有（a）∑=n

iid1為偶數(shù)；

（b）對(duì)任一k，1≤k≤n,∑=k

iid1

≤k(k-1)+

∑+=n

kii

dk1

),min(。

證（1）由于7個(gè)頂點(diǎn)的簡(jiǎn)單圖中不會(huì)有7度的頂點(diǎn)，所以序列（7，

6，5，4，3，3,2）別是簡(jiǎn)單圖的度序列。序列（6，5，5，4，3，2，2）中有三個(gè)奇數(shù)，所以它別是簡(jiǎn)單圖的度序列。序列（6，6，5，4，3，3，1）中有兩個(gè)6，若它是簡(jiǎn)單圖的度序列，這么應(yīng)有兩個(gè)頂點(diǎn)是6度頂點(diǎn)，于是它們都要與其它所有頂點(diǎn)鄰接，該圖就不可能有一度的頂點(diǎn)，與序列中末尾的1沖突。故（6，6，5，4，3，3，1）也別是簡(jiǎn)單圖的度序列。

證（2）∑=n

iid1為偶數(shù)是顯然的。

思考圖中的k個(gè)頂點(diǎn)（k=1,2,…,n）,這k個(gè)頂點(diǎn)的生成子圖的度數(shù)總和≤k(k-1)，而其余n–k個(gè)頂點(diǎn)vk+1,vk+2,…,vn,可使v1,v2,…,vk增加的度數(shù)不可能超過(guò)

∑+=n

kii

dk1

),min(

所以我們有∑=k

iid1

≤k(k-1)+

∑+=n

kii

dk1

),min(。

9、畫出圖中圖的補(bǔ)圖及它的一具生成子圖。

圖

解補(bǔ)圖生成子圖

10、一具簡(jiǎn)單圖，假如同構(gòu)于它的補(bǔ)，則該圖稱為自補(bǔ)圖。（1）給出一具4個(gè)頂點(diǎn)的自補(bǔ)圖。（2）給出一具5個(gè)頂點(diǎn)的自補(bǔ)圖。（3）是否有3個(gè)頂點(diǎn)或6個(gè)頂點(diǎn)的自補(bǔ)圖

（4）證明一具自補(bǔ)圖一定有4k或4k＋1個(gè)頂點(diǎn)（k為正整數(shù)）。解（1）4個(gè)頂點(diǎn)的自補(bǔ)圖：（2）5個(gè)頂點(diǎn)的自補(bǔ)圖：

（3）沒有。

（4）證設(shè)G為自補(bǔ)圖，有n個(gè)頂點(diǎn)。我們已知n個(gè)頂點(diǎn)的徹底圖有

2)

1(-nn條邊，所以G應(yīng)恰有4

)1(-nn條邊。故或者n是4的整數(shù)倍，或者n–1是4的整數(shù)倍，即圖G一定有4k或4k＋1個(gè)頂點(diǎn)（k為正整數(shù)）。