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

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

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

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

D．wm7pl2b是割點YE.{b,c}是點割集NF.{a,f}是點割集Y設V'和E'分別為無向連通圖G的點割集和邊割集，G-E'的連通分支數一定是多少？G-V'的連通分支數也是定數嗎?解答：G-E'的連通分支數一定是2，G-V'的連通分支數不是一個確定的數。一個有向圖是強連通的，當且僅當G中有一個回路，它至少包含每個結點一次。證明：必要性：如果圖中的任何一個回路都不能包含所有結點，則可知未被包含在回路內的結點不能與其他結點中的某一結點連通。這與本圖是強連通的相矛盾。因此必有這樣一個回路它至少包含每個結點一次。充分性：當G中有一個回路，它至少包含每個結點一次時，可以知道，任一結點可達其他所有結點，因此它是強連通的若有簡單圖至多有2n個結點，每個結點度數至少為n，G是連通圖。又若簡單圖G至多有2n個結點，每個結點度數至少為n-1，那么G是連通圖嗎？為什么？證明：假設G是不連通的，有兩個連通分支，若簡單圖至多有2n個結點，則至少有一個連通分支的結點數n，這個連通分支的結點最大度數n-1，和每個結點度數至少為n矛盾，所以G是連通圖。若簡單圖G至多有2n個結點，每個結點度數至少為n-1，那么G不一定是連通圖。因為由2個n個結點的完全圖組成的圖有2n個結點，每個結點度數為n-1，是不連通的圖。簡單圖G有n個結點，e條邊，設e>0.5(n-1)(n-2),證明：G是連通的。證明：用反證法。假若簡單無向圖G不是連通圖，那么G必可成K（≥2）個連通分支G1，G2，…，Gk，每個連通分支Gi（1≤i≤k）都是一個簡單無向圖，因此它們的結點數分別為n1，n2，m2，…nk，邊數分別為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的路徑總數，并指出其中有多少條是回路。v3到v4的簡單通路有幾條。26題圖27題圖給定圖G，求：a)給出G的鄰接矩陣，b)求各結點的出、入度，c)求從結點V3出發長度為3的所有回路(1).給出G的鄰接矩陣按結點順序v1,v2,v3,v4給出鄰接矩陣如下: [0110]A=[1000] [0101] [0001](2).各結點的出入度 v1 v2 v3 v4出度:2 1 2 1入度:1 2 1 2(3).從結點V3出發長度為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的任一回