2004圖論復(fù)習(xí)題答案.doc

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