離散數(shù)學及其應用-第2版第10章部分習題解答

習題設無向圖G=（V，E），V={v1，v2，v3，v4，v5}，E={（v1，v2），（v2，v2），（v2，v4），（v4，v5），（v3，v4），（v1，v3），（v3，v1）}。畫出G的圖形；求出G中各結(jié)點的度及奇數(shù)度結(jié)點的個數(shù)。解答：a)b)d(v1)=3，d(v2)=4，d(v3)=3，d(v4)=3，d(v5)=1下列序列中，哪些是可構(gòu)成無向簡單圖的結(jié)點度數(shù)序列？1）（1，1，2，2，3）2）（1，1，2，2，2）3）（0，1，3，3，3）4）（1，3，4，4，5）5）（0，1，1，2，3，3）解答：1)N2)Y3)N4)N5)Y(當刪去一個3度結(jié)點的度數(shù)序列為(0,0,1,1,2,0)時)，N（當刪去一個3度結(jié)點的度數(shù)序列為(0,0,0,1,3,0)時)設無向圖G有16條邊，3個4度結(jié)點，4個3度結(jié)點，其余結(jié)點的度數(shù)均小于3，問：G中至少有幾個結(jié)點。解：設度數(shù)小于3的結(jié)點有x個，則有3×4＋4×3＋2x≥2×16解得：x≥4所以度數(shù)小于3的結(jié)點至少有4個所以G至少有11個結(jié)點證明：若有n個人，每個人恰恰有三個朋友，則n必為偶數(shù)。證明：n個人對應n個結(jié)點，每個人恰恰有三個朋友，即為每個結(jié)點有3度，根據(jù)握手定理的推論，n必為偶數(shù)。設圖G有n個結(jié)點，n+1條邊，證明：G中至少有一個結(jié)點度數(shù)≥3。證明：用反證法.若G的最大度(G)則按握手定理2m其中m是邊數(shù).從而mn,證明：無向簡單圖G=(V,E),e=|E|,v=|V|則有ev(v-1)/2.證明：無向簡單圖是完全圖時邊數(shù)最多，完全圖的邊數(shù)為v(v-1)/2，所以無向簡單圖有ev(v-1)/2.設圖G=(V,E),e=|E|,v=|V|,d(v)min為G中結(jié)點的最小度數(shù),d(v)max為G中結(jié)點的最大度數(shù).證明:d(v)min2e/vd(v)max.證明：根據(jù)握手定理：將式（1）代入式（2），整理得：d(v)min2e/vd(v)max.有n個抽屜，若每兩個抽屜里有一種相同的物品，每種物品恰好放在兩個抽屜中，問共有多少種物品？解：每個抽屜用一個結(jié)點表示；每兩個抽屜放相同的物品，在每兩個抽屜對應的結(jié)點間連接一條邊，則構(gòu)成一個n個結(jié)點的完全圖，每條邊是一個物品。n個結(jié)點的完全圖有n(n-1)/2條邊，所以共有n(n-1)/2種物品。證明：無向簡單圖的最大度小于結(jié)點數(shù)。證明：由定義可知，無向簡單圖是無環(huán)無多重邊的圖，因此n個節(jié)點的無向簡單圖，每個結(jié)點最多和其它結(jié)點都有邊相連接時有n-1條邊。因此，簡單圖的最大度為n-1，小于結(jié)點個數(shù)n。下列各圖有多少個結(jié)點和多少條邊？1）Kn2）Cn3）Wn4）Km，n5）Qn解：1）n個結(jié)點，n(n-1)/2條邊2）n個結(jié)點，n條邊3)n+1個結(jié)點，2n條邊4)m+n個結(jié)點，mn條邊5）2n個結(jié)點，n*2n-1條邊當n為何值時，下列各圖是正則圖？1）Kn2）Cn3）Wn4）Qn解：(1)對所有n1(2)對所有n>=3(3)4(4)對所有n1證明：3正則圖必有偶數(shù)個結(jié)點。試證明下圖中兩個圖不同構(gòu)。(b)證明：同構(gòu)的充要條件是兩圖的結(jié)點和邊分別存在一一對應且保持關聯(lián)關系。我們可以看出，(a)圖和(b)圖中都有一個三度結(jié)點，(a)圖中三度結(jié)點的某條邊關聯(lián)著兩個一度結(jié)點和一個二度結(jié)點，而(b)圖中三度結(jié)點關聯(lián)著兩個二度結(jié)點和一個一度結(jié)點，因此可斷定二圖不是同構(gòu)的。證明：下圖中的圖是同構(gòu)的。證明：下面兩圖是同構(gòu)的。證明：簡單圖的同構(gòu)關系是等價關系。提示：簡單圖的同構(gòu)關系是自反、對稱和傳遞的。連通圖G有n個結(jié)點，e條邊，則en-1。證明：用歸納法證明。當n=2時，連通圖G至少有一條邊，e1，所以en-1成立。設n￡k時，結(jié)論成立，即ek-1。當n=k+1時，=1\*GB3①若刪去一個度數(shù)為d(v)的結(jié)點得到圖G’，而且圖G’仍是連通的，圖G’的結(jié)點數(shù)和邊數(shù)分別為k和e’，則e’k-1，e’=e-d(v)，所以e-d(v)k-1，則ek-1+d(v),因為G是連通圖，d(v)1,因而ek,所以en-1.=2\*GB3②若刪去一個度數(shù)為d(v)的結(jié)點得到圖G’，而且圖G’不連通的，假設圖G’有兩個連通分支G1’、G2’,結(jié)點數(shù)和邊數(shù)分別為k1’和e1’，k2’和e2’，則e1’k1’-1，e2’k2’-1,e1’+e2’=e-d(v)，所以e-d(v)k-2，則ek-2+d(v),因為G是連通圖，d(v)2,因而ek,所以en-1.給定圖G，如下圖所示，求出G中從v1到v6的所有基本通路。給定圖G，如下圖所示，找到G中從v2出發(fā)的所有基本回路。設G為無向連通圖，有n個結(jié)點，那么G中至少有幾條邊？為什么？對有向圖如何？解答：根據(jù)定理7.2.3，無向連通圖，有n個結(jié)點，至少有n-1條邊。有向連通圖，有n個結(jié)點，至少有n-1條邊。圖G如下圖所示，以下說法正確的是()．

A．{(a,d)}是割邊N

B．{(a,b),(b，f)}是邊割集Y

C．{(d,e)}是割邊Y

D．d9j7dxt是割點YE.{b,c}是點割集NF.{a,f}是點割集Y設V'和E'分別為無向連通圖G的點割集和邊割集，G-E'的連通分支數(shù)一定是多少？G-V'的連通分支數(shù)也是定數(shù)嗎?解答：G-E'的連通分支數(shù)一定是2，G-V'的連通分支數(shù)不是一個確定的數(shù)。一個有向圖是強連通的，當且僅當G中有一個回路，它至少包含每個結(jié)點一次。證明：必要性：如果圖中的任何一個回路都不能包含所有結(jié)點，則可知未被包含在回路內(nèi)的結(jié)點不能與其他結(jié)點中的某一結(jié)點連通。這與本圖是強連通的相矛盾。因此必有這樣一個回路它至少包含每個結(jié)點一次。充分性：當G中有一個回路，它至少包含每個結(jié)點一次時，可以知道，任一結(jié)點可達其他所有結(jié)點，因此它是強連通的若有簡單圖至多有2n個結(jié)點，每個結(jié)點度數(shù)至少為n，G是連通圖。又若簡單圖G至多有2n個結(jié)點，每個結(jié)點度數(shù)至少為n-1，那么G是連通圖嗎？為什么？證明：假設G是不連通的，有兩個連通分支，若簡單圖至多有2n個結(jié)點，則至少有一個連通分支的結(jié)點數(shù)n，這個連通分支的結(jié)點最大度數(shù)n-1，和每個結(jié)點度數(shù)至少為n矛盾，所以G是連通圖。若簡單圖G至多有2n個結(jié)點，每個結(jié)點度數(shù)至少為n-1，那么G不一定是連通圖。因為由2個n個結(jié)點的完全圖組成的圖有2n個結(jié)點，每個結(jié)點度數(shù)為n-1，是不連通的圖。簡單圖G有n個結(jié)點，e條邊，設e>0.5(n-1)(n-2),證明：G是連通的。證明：用反證法。假若簡單無向圖G不是連通圖，那么G必可成K（≥2）個連通分支G1，G2，…，Gk，每個連通分支Gi（1≤i≤k）都是一個簡單無向圖，因此它們的結(jié)點數(shù)分別為n1，n2，m2，…nk，邊數(shù)分別為e1，e2，…，ek，顯然有n=n1+n2+…nk，e=e1+e2+…ek，且ni≤n-1（1≤i≤k）于是有e=e1+e2+…ek=(n-1)··((n1-1)+(n2-1)+…+(nk-1))=(n-1)((n1+n2+…+nk)-k)=(n-1)(n-k)≤(n-1)(n-2)(k≥2)這與已知e＞0.5（n-1）(n-2)矛盾。因此假設錯誤，G是連通圖。設圖G=<V,E>,V={v1,v2,v3,v4}的鄰接矩陣則v1的入度是多少？v4的出度是多少？從v1到v4長度為2的通路有幾條？有向圖G如圖所示，求G中長度為4的路徑總數(shù)，并指出其中有多少條是回路。v3到v4的簡單通路有幾條。26題圖27題圖給定圖G，求：a)給出G的鄰接矩陣，b)求各結(jié)點的出、入度，c)求從結(jié)點V3出發(fā)長度為3的所有回路(1).給出G的鄰接矩陣按結(jié)點順序v1,v2,v3,v4給出鄰接矩陣如下: [0110]A=[1000] [0101] [0001](2).各結(jié)點的出入度 v1 v2 v3 v4出度:2 1 2 1入度:1 2 1 2(3).從結(jié)點V3出發(fā)長度為3的所有回路 由A3=[1111]可知,長度為3的回路有1條 [1101] [0111] [0001]它是:(v3,v2,v1,v3)給定G如圖所示，a)寫出鄰接矩陣b)G中長度為4的路有幾條？c)G中有幾條回路？28題圖30題圖試用矩陣法判斷有向圖G=({a,b,c,d},{<a,b>,<a,d>,<c,b>,<c,d>})的連通性。解答：1）圖G的鄰接矩陣：因為B（G）中存在0元素，所以圖G不是強連通圖。2）圖G的可達矩陣為：因為可達矩陣關于主對角線對稱位置的存在全為0的元素，所以圖G不是單向連通。3）若將圖G視為無向圖，則鄰接矩陣為B無(G)的元素全為1，所以圖G是弱連通。求出所示圖G的鄰接矩陣、可達矩陣，找出從v2到v3長度為3的通路，并計算出A2,A3進行驗證。設圖G中的邊滿足W(G-e)>W(G),稱e為G的割邊（橋）。證明：e是割邊，當且僅當e不包含在G的任一回路中。證明： 1）e為割邊=〉e不包含于G的任一回