2004圖論復習題答案.doc

圖論復習題答案一、 判斷題，對打，錯打1 無向完全圖是正則圖。( )2 零圖是平凡圖。( )3 連通圖的補圖是連通圖. ( )4 非連通圖的補圖是非連通圖。( )5 若連通無向簡單圖G中無圈，則每條邊都是割邊。( )6 若無向簡單圖G是（n，m）圖，并且m=n-1，則G是樹。( )7 任何樹都至少有2片樹葉。( )8 任何無向圖G都至少有一個生成樹。( )9 非平凡樹是二分圖 。( )10 所有樹葉的級均相同的二元樹是完全二元樹。( )11任何一個位置二元樹的樹葉都對應唯一一個前綴碼。( )12是歐拉圖也是哈密頓圖。( )13 二分圖的對偶圖是歐拉圖。()14平面圖的對偶圖是連通圖。( )15設G*是平面圖G的對偶圖，則G*的面數(shù)等于G的頂點數(shù)。( )二、填空題1無向完全圖K6有 15 條邊。2有三個頂點的所有互不同構的簡單無向圖有 4 個。3設樹T中有2個3度頂點和3個4度頂點，其余的頂點都是樹葉，則T中有 10 片樹葉。4若連通無向圖G是（n，m）圖，T是G的生成樹，則基本割集有 n-1 個，基本圈有 m-n+1 個。5設連通無向圖G有k個奇頂點，要使G變成歐拉圖，在G中至少要加 k / 2 條邊。6連通無向圖G是（n，m）圖，若G是平面圖，則G有 m-n+2 個面。abcde圖1三、解答題1有向圖D如圖1所示，利用D的鄰接矩陣及其冪運算求解下列問題：（1） D中長度等于3的通路和回路各有多少條。（2） 求D的可達性矩陣。（3） 求D的強分圖。解： （1）abcde圖1M= M2= M3= M4=由M3可知，D中長度等于3的通路有5條，長度等于3的回路有3條。（2）I+M+M2+M3+M4=+ + = D的可達性矩陣為R=B（I+M+M2+M3+M4）=（3）RT = RRT =由矩陣RRT可知，該有向圖的強分圖有：a， b，d，e， c2 畫出有1個4次頂點，2個2次頂點，4個1次頂點的所有非同構的樹。3 用Kruskal算法求圖2所示帶權圖的最小生成樹，并計算它的權。1294368571011C（T）=2512336227541394 試畫出帶權為1,2,3, 4,5,7,的最優(yōu)二元樹,并計算它的權。m（T）=（1+2）4+33+（7+4+5）2=535 出席某次國際學術報告會的六個成員被分在一組。他們的情況是：會講漢語、法語和日語；會講德語、日語和俄語；會講英語和法語；會講漢語和西班牙語；會講英語和德語；會講俄語和西班牙語。怎樣把他們安排在一張圓桌旁坐下，使得每個人都能和他兩旁的人交談？解 構造無向圖，其中，則得無向圖如圖所示。由該圖得一條哈密頓回路：，即為滿足要求的安排。四、證明題1 設T是完全二元樹，T中有m條弧和t片樹葉，證明：m = 2(t-1)。證明： 設完全二元樹T有n個頂點。因為它有t片樹葉，所以除樹葉以外的頂點有個。由于完全二元