1. 畫出所有非同構(gòu)的 5 階根樹。

解答與評分標(biāo)準(zhǔn)：

9 種(每種1 分，重復(fù)畫扣0.5 分，全畫10 分)。非同構(gòu)的5 階樹共有3種，分別選一個(gè)頂點(diǎn)做根。

2.證明或推翻下列命題：“設(shè)連通簡單平面圖G 的最小度δ(G)≥4，則G 的

點(diǎn)色數(shù)χ(G)≥3.”

解答與評分標(biāo)準(zhǔn)：

假設(shè)χ(G)<3.(反證法分情況討論2 分)

χ(G)=1 當(dāng)且僅當(dāng)G 為n 階零圖，與已知矛盾。(4 分)

χ(G)=2 當(dāng)且僅當(dāng)G 為二部圖，因?yàn)镚 為平面圖，只能為K2,s 或Kr,2. 此時(shí)必有δ(G)=2, 與已知矛盾。(4 分)

編輯推薦：

2015年同等學(xué)力計(jì)算機(jī)綜合模擬試題

同等學(xué)力英語寫作功能句式

2015年同等學(xué)力申碩英語寫作常用句子匯總

（責(zé)任編輯：lqh）

共2頁,當(dāng)前第1頁  第一頁  前一頁  下一頁