離散數(shù)學王元元習題解答

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

第八章圖

圖的基本知識

內容提要

8.1.1圖的定義及有關術語

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

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

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

（3）函數(shù)Ψ

G

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

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

v），u，v為結點，它們未必別同。Ψ

G

(e)=(u,v)時稱邊e關聯(lián)端點u，v。當(u,v)用作序偶時(V(G)，V(G))=V(G)?V(G)，e稱為有向邊，e以u為起點,以v為終點,圖G稱為有向圖（directedgraph）；當(u,v)用作無序偶對時，(u,v)=(v,u)，稱e為無向邊（或邊），圖G稱為無向圖（或圖）。

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

定義8.2設圖G為。

（l）當V和E為有限集時，稱G為有限圖，否則稱G為無限圖。本書只討論有限圖。

（2）當Ψ

G為單射時，稱G為單圖；當Ψ

G

為非單射時，稱G為重圖，

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

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

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

徹底圖常記作K

n

。

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

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

此刻稱G為賦權圖，常用或或表示之。f(v)稱為結點v的

權，g(e)稱為邊e的權。

8.1.2結點的度

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

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

1，v

2

，…，v

n

}，這么

∑==

n

i

i

m

v

d

1

2

)

(

定理圖的奇數(shù)度頂點必為偶數(shù)個。

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

1,a

2

,…,a

n

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

頂點的度的序列。（a

1,a

2

,…,a

n

）為一度序列，當且僅當∑

=

n

i

i

a

1

為一偶數(shù)。

定義一度的頂點稱為懸掛點（pendantnodes）。

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

8.1.3圖運算及圖同構

由于圖由結點集、邊集及關聯(lián)映射組成，所以對圖可作種種與集合運算相類似的運算。

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

定義設圖G1＝，G2＝，且Ψ1與Ψ2是相容的，即對任一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對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為簡單圖，則可定義G的補，記為Gˉ，若?V(G)?=n，則Gˉ=K

－G

n

定義設圖G＝

（1）G－e表示對G作刪除邊e的運算，G－e=，其

。

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

E’

（2）G－v表示對G作刪除頂點v的運算，G－v=，

。

其中V’=V－{v}，E’＝E－{e?e以v為端點}，Ψ’＝Ψ?

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

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

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

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

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

）

當限于討論簡單圖時，能夠用頂點的偶對表示邊，即當Ψ(e)＝(u,v)

時，邊e用(u,v)來表示。這時兩圖同構的條件能夠簡化為

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

習題解答

練習

1、想一想，一只昆蟲是否也許從立方體的一具頂點動身，沿著棱爬行、

它爬行過每條梭一次且僅一次，同時最后回到原地為啥

解不會?？蓪⒘⒎襟w的一具頂點看作圖的一具頂點，把立方體的棱

看作圖的邊，這么該圖的四個頂點基本上三度的，所以不會從一具頂點

動身，遍歷所有的邊一次且僅一次，同時最后回到原頂點。

2、請設想一張圖，它的64個頂點表示國際象棋棋盤的64個方格，頂

點間的邊表示:在這兩個頂點表示的方格之間能夠舉行“馬步”的行

走。試指出其頂點有哪幾類（依其度分類），每類各有多少個頂點。

解其頂點有5類：二度頂點合計4個,三度頂點合計8個,四度頂點,

合計20個,六度頂點,合計16個頂點,八度頂點,合計16個頂點。

3、（l）證明：n個頂點的簡單圖中不可能有多于

2)1

(-

n

n

條邊。（2）n個頂點的有向徹底圖中恰有2n條邊。

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

2)1

(

1

2

)2

(

)1

(-

=

+

+

+

-

+

-

nn

n

n

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

2

n

n

n

n

n

n

n=

?

=

+

+

+

+

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

相同的度。

證假如G有兩個孤立頂點，這么它們便是具有相同的度的兩個頂點。

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

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

也許之一，所以必然有兩個頂點具有相同的度。

5、圖是一具迷宮,其中數(shù)字表示通道、和死胡同(包括目標)。請用一具圖來表示那個迷宮(用結點表示通道、和死胡同(包括目標)),用邊表示它們之間的可直截了當?shù)竭_關系。

圖解

6、在晚會上有n個人，他們各自與自個兒相識的人握一次手。已知每人

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

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

7、n個都市間有m條相互連接的直達公路。證明：當

2

)

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

2118

3

17

4

520211

615

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

)

1(-iinn(見練習之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是連通的。

（本題是定理的特例，固然也能夠應用這一定理和它的證明辦法來解題。）

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

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

iid1為偶數(shù)；

（b）對任一k，1≤k≤n,∑=k

iid1

≤k(k-1)+

∑+=n

kii

dk1

),min(。

證（1）由于7個頂點的簡單圖中不會有7度的頂點，所以序列（7，

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

證（2）∑=n

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

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

∑+=n

kii

dk1

),min(

所以我們有∑=k

iid1

≤k(k-1)+

∑+=n

kii

dk1

),min(。

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

圖

解補圖生成子圖

10、一具簡單圖，假如同構于它的補，則該圖稱為自補圖。（1）給出一具4個頂點的自補圖。（2）給出一具5個頂點的自補圖。（3）是否有3個頂點或6個頂點的自補圖

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

（3）沒有。

（4）證設G為自補圖，有n個頂點。我們已知n個頂點的徹底圖有

2)

1(-nn條邊，所以G應恰有4

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