離散數(shù)學(xué)形成性考核作業(yè)（二）

1、離散數(shù)學(xué)形成性考核作業(yè)（二）第4章 幾種特殊圖1試分別構(gòu)造滿足下列條件的無(wú)向歐拉圖（1）有偶數(shù)個(gè)結(jié)點(diǎn)，奇數(shù)條邊（2）有偶數(shù)個(gè)結(jié)點(diǎn)，偶數(shù)條邊（3）有奇數(shù)個(gè)結(jié)點(diǎn)，偶數(shù)條邊（4）有奇數(shù)個(gè)結(jié)點(diǎn)，奇數(shù)條邊2分別構(gòu)造滿足下列條件的四個(gè)漢密爾頓圖（1）偶數(shù)個(gè)結(jié)點(diǎn)，奇數(shù)條邊（2）有偶數(shù)個(gè)結(jié)點(diǎn)，偶數(shù)條邊（3）有奇數(shù)個(gè)結(jié)點(diǎn)，偶數(shù)條邊（4）有奇數(shù)個(gè)結(jié)點(diǎn)，奇數(shù)條邊3試畫出一個(gè)沒有一條歐拉回路，但有一條漢密爾頓回路的圖4如圖2.8是否為歐拉圖？試說(shuō)明理由圖2.8 判斷是否為歐拉圖 5如圖2.9是否為漢密爾頓圖？試說(shuō)明理由圖2.9 判斷是否為漢密爾頓圖6試分別說(shuō)明圖4.3（a）、（b）與（c）是否為平面圖圖2.10判斷是

2、否為平面圖7試分別求出圖2.11（a）、（b）與（c）的每個(gè)圖的面的次數(shù)圖2.11 求面的次數(shù) 8試?yán)庙f爾奇鮑威爾算法分別對(duì)圖2.12（a）、（b）與（c）著色圖2.12 圖的著色9若G是一個(gè)漢密爾頓圖，則G一定是( )A歐拉圖 B平面圖 C連通圖10設(shè)G是有n個(gè)結(jié)點(diǎn)m條邊的連通平面圖，且有k個(gè)面，則k等于( )Am-n+2 Bn-m-2 Cn+m-2 Dm+n+211無(wú)向連通圖 G 是歐拉圖的充分必要條件是_12設(shè)G是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于_，則在G中存在一條漢密爾頓路13現(xiàn)有一個(gè)具有個(gè)奇數(shù)度結(jié)點(diǎn)的圖，若要使圖中有一條歐拉回路，最少要向圖中添加_條邊第5章

3、 樹及其應(yīng)用1試指出圖2.13中那些是樹，那些是森林，并說(shuō)明理由圖2.13習(xí)題1的圖2試畫出圖2.14中的一個(gè)生成樹，并說(shuō)明其中的樹枝、弦，以及對(duì)應(yīng)生成樹的補(bǔ)圖2.14習(xí)題2的圖3試畫出如圖2.15的完全圖K5 的所有不同構(gòu)的生成樹圖2.15習(xí)題3的圖4試求出圖2.16中的最小生成樹及其權(quán)值圖2.16習(xí)題4的圖 5給定一組權(quán)值為1，2，2，3，6，7，9，12，是求出相應(yīng)的一個(gè)最優(yōu)樹6無(wú)向樹T有7片樹葉, 3個(gè)3度結(jié)點(diǎn),其余的都是4度結(jié)點(diǎn)，則T有（ ）個(gè)4度結(jié)點(diǎn)？ A1 B2 C3 D4 7無(wú)向樹T有3個(gè)3度結(jié)點(diǎn),2個(gè)4度結(jié)點(diǎn),其余的都是樹葉，則T有（ ）片樹葉？ A3 B7 C9 D11 8無(wú)向樹T有1個(gè)2度結(jié)點(diǎn),3個(gè)3度結(jié)點(diǎn),4個(gè)4度結(jié)點(diǎn),1個(gè)5度結(jié)點(diǎn),其余的都是樹葉，則T有（ ）片樹葉？ A12 B14 C16 D20