圖論練習題2009(學生練習

1、圖論練習題一、基本題1、設G是由5個頂點構(gòu)成的完全圖，則從G中刪去（ ）邊可以得到樹。A6 B5 C8 D42、下面哪幾種圖不一定是樹（ ）。A無回路的連通圖B有n個結(jié)點，n-1條邊的連通圖C對每對結(jié)點間都有通路的圖D連通但刪去任意一條邊則不連通的圖。3、5階無向完全圖的邊數(shù)為（ ）。A5 B10 C15 D204、把平面分成x個區(qū)域，每兩個區(qū)域都相鄰，問x最大為（ ）A6 B4 C5 D35、設圖G有n個結(jié)點，m條邊，且G中每個結(jié)點的度數(shù)不是k，就是k+1，則G中度數(shù)為k的節(jié)點數(shù)是（ ）An/2 Bn(n+1) Cnk-2m Dn(k+1)-2m6、設G=為有向圖，則有（ ）。AEV x V

2、 BEV x V CV x VE DV x V=E7、圖G1和G2的結(jié)點和邊分別存在一一對應關(guān)系是G1和G2同構(gòu)的（ ）。A充分條件 B必要條件 C充分必要條件 D既不充分也不必要條件8、設G=為有向圖，V=a,b,c,d,e,f，E=,是（ ）。A強連通圖 B單向連通圖 C弱連通圖 D不連通圖9、無向圖G中的邊e是G的割邊（橋）的充分必要條件是（）。Ae是重邊 Be不是重邊 Ce不包含在G的任一簡單回路中 De不包含在G的某一簡單回路中10、在有n個結(jié)點的連通圖中，其邊數(shù)（ ）A最多有n-1條 B至少有n-1條 C最多有n條 D至少有n條11設無向簡單圖的頂點個數(shù)為n，則該圖最多有（ ）條邊

3、。An-1 Bn(n-1)/2 C n(n+1)/2 Dn212要連通具有n個頂點的有向圖，至少需要（ ）條邊。An-l Bn Cn+l D2n13n個結(jié)點的完全有向圖含有邊的數(shù)目（）。An*n n（n） Cn2 Dn*（nl）14一個有n個結(jié)點的圖，最少有（ ）個連通分量。A0 B1 Cn-1 Dn15一個有n個結(jié)點的圖，最多有（ ）個連通分量。A0 B1 Cn-1 Dn16在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ ）倍。A1/2 B2 C1 D417在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ ）倍。A1/2 B2 C1 D418、連通圖G是一棵樹，當且僅當G中（ ）

4、A有些邊不是割邊 B所有邊都是割邊 C無割邊集 D每條邊都不是割邊194個頂點的完全圖G，其生成樹個數(shù)是（ ）。A4 B8 C16 D6420、設有33盞燈，擬公用一個電源，則至少需有5插頭的接線板數(shù)（ ）。A7 B8 C9 D14二、應用題題1：（1996年全國數(shù)學聯(lián)賽）有n（n6）個人聚會，已知每個人至少認識其中的n/2個人，而對任意的n/2個人，或者其中有兩個人相互認識，或者余下的n-n/2個人中有兩個人相互認識。證明這n個人中必有3個人互相認識。注：n/2表示不超過n/2的最大整數(shù)。題2：已知圖的結(jié)點集V=a,b,c,d以及圖G和圖D的邊集合分別為：E(G)=(a,a), (a,b),

5、 (b,c), (a,c)E(D)=, , , , 試作圖G和圖D，寫出各結(jié)點的度數(shù)，回答圖G、圖D是簡單圖還是多重圖？題3：設簡單連通無向圖G有12條邊，G中有2個1度結(jié)點，2個2度結(jié)點，3個4度結(jié)點，其余結(jié)點度數(shù)為3求G中有多少個結(jié)點試作一個滿足該條件的簡單無向圖題4：設簡單連通無向圖G有9條邊，G中有4個3度結(jié)點，2個1度結(jié)點，其余結(jié)點度數(shù)為2求G中有多少個結(jié)點題5：兩個圖同構(gòu)有下列必要條件：（1） 結(jié)點數(shù)相同；（2） 邊數(shù)相同；（3） 度數(shù)相同的結(jié)點數(shù)相同.但它們不是兩個圖同構(gòu)的充分條件，下圖中(a)和(b)滿足上述三個條件，但這兩個圖并不同構(gòu)，請說明理由。(a)(b)題6：三名商人各

6、帶一隨從乘船過河，一只小船只能容納2人，由他們自己劃行。隨從們密約，在河的任一案，一旦隨從的人數(shù)比商人多，就殺人越貨。但是如何乘船渡河的大權(quán)掌握在商人手中，商人們怎樣安排每次乘船方案才能安全渡河？題7在平面上有n個點Sx1,x2,xn，其中任兩個點之間的距離至少是1，證明在這n個點中距離為1的點對數(shù)不超過3n。題8n個點由若干線段連接著。已知每一點與另外任何一點都有道路相連通。而任何兩點都沒有兩種不同的道路。證明：線段總數(shù)為n-1。題9：設無向圖G有12條邊，已知G中度數(shù)為3的節(jié)點個數(shù)為6個，其余結(jié)點的度數(shù)均小于3，問G中至少有多少邊？題10：若圖G是不連通的，則G的補圖是連通的。題11：當且

7、僅當G的一條邊e不包含在G的回路中，e才是G的割邊（橋）。題12：n個城市由k條公路網(wǎng)絡連接（一條公路定義為兩個城市間的一條道路，它們之間不能通過任何中間城市），證明：如果有k(n-1)(n-2)則人們總能通過連接城市的公路在任何城市間旅行。題13：判斷下圖是否能一筆畫出，并說明理由。V0VnVnV0 圖（a） 圖（b）題14：構(gòu)造一個歐拉圖，其結(jié)點數(shù)n與邊數(shù)m滿足下列條件 （1）、n，m的奇偶性一樣的簡單圖。 （2）、n，m的奇偶性相反的簡單圖。 如果不可能，請說明原因。題15：設G是一個具有n個結(jié)點的簡單無向圖，n3，設G的結(jié)點表示n個人，G的邊表示他們間的友好關(guān)系，若兩個結(jié)點杯一條邊連接

8、，當且僅當對應的人是朋友。（1）、結(jié)點的度數(shù)能做怎樣的解釋？（2）、G是連通圖能做怎樣的解釋？（3）、假定任意兩個人合起來認識所留下的n-2個人，證明n個人能站成一排，使得中間每個人兩旁站著自己的朋友，而兩端的兩個人，他們每個人旁邊只站著他的一個朋友。（4）、證明對于n4，（3）中保證n個人能站成一圈，使每個人的兩旁站著自己的朋友。題16：設G是有11個或更多結(jié)點的圖，證明G或（補圖）是非平面圖。題17：一棵樹有n2個結(jié)點度數(shù)為2，n3個結(jié)點度數(shù)為3，nk個結(jié)點度數(shù)為k，問它有幾個度數(shù)為1的結(jié)點。題18：證明在完全二叉樹中，邊的總數(shù)m等于2(nt-1)，nt是樹葉總數(shù)。題19：給設d=（d1,

9、d2,dn），其中di為正數(shù)，i=1,2, ,n。若存在n個結(jié)點的簡單圖，使得結(jié)點vi的度數(shù)為di，則稱d是可圖解的。下面給出的各序列中哪些是可圖解的，哪些不是，為什么？（1）、（1，1，1，2，3） （2）、（0，1，1，2，3，3） （3）、（3，3，3，3）（4）、（2，3，3，4，4，5） （5）、（2，3，4，4，5） （6）、（2，3，3，3）（7）、（2，3，3，4，5，6） （8）、（1，3，3，4，5，6，6） （9）、（2，2，4）（10）、（1，2，2，3，4，5）題20：給無向完全圖Kn（n7）的各邊隨意涂上紅色或綠色，若已知從某個結(jié)點v0引出的n-1條邊中至少有六條邊

10、涂紅色，則存在紅色的K4或綠色的K3。題21：證明：在任何兩個或兩個以上人的組內(nèi)，存在兩個人在組內(nèi)有相同個數(shù)的朋友。題22、設G為n個結(jié)點的簡單無向圖。（1）、若G的邊數(shù)m=(1/2)(n-1)(n-2)+2，證明G是哈密爾頓圖。（2）、若G的邊數(shù)m=(1/2)(n-1)(n-2)+1，那么圖G是否一定為哈密爾頓圖？請闡述你的理由。題23、把平面分成x個區(qū)域，每兩個區(qū)域都相鄰，問x最大為幾？題24、設圖G有n個結(jié)點，m條邊，其中有nk個結(jié)點的度數(shù)為k，其余結(jié)點的度數(shù)均為k+1，試證明：nk=(k+1)n-2m。題25、用Kruskal算法求下圖的的最小生成樹，并計算其權(quán)。題26、求出下圖中以v1為起點的一條中國郵路。題27、利用Dijkstra算法，求解下圖中從頂點1到其余各點的最短路徑題28、求下面PERT圖的關(guān)鍵路徑。題29、利用Huffman算法，求權(quán)為20,30,50,70,80的最優(yōu)二叉樹T，并求出其W(T)。 W(T)=550。題30：給定權(quán)1，4，9，16，25，36，49，64，81，100，利用Huffman算法構(gòu)造一棵最優(yōu)二叉樹，并求出其W(T)。題31、用Dinic算法求下圖最大流。題32、用2F標號算法求下圖的最大流。題33、用匈牙利算法求下圖的最大匹配。題34、對下圖頂