2017同等學(xué)力申碩計算機(jī)訓(xùn)練題4-3
來源：新東方在線
時間：2017-01-31 15:54:21
備考2017同等學(xué)力申碩的考生，小編整理一些計算機(jī)訓(xùn)練題供大家練習(xí)，希望能幫助大家更好的復(fù)習(xí)。
1. 證明或推翻下列命題：“設(shè)平面上有 100 個點(diǎn)，其中任意兩點(diǎn)間的距離至少是1，則最多有300 對點(diǎn)距離恰好是1”。
解答與評分標(biāo)準(zhǔn)：
命題成立(2 分)。
無向圖 G=，V 是平面上的這100 個點(diǎn)，兩個點(diǎn)相鄰當(dāng)且僅當(dāng)這兩點(diǎn)距離恰好是1(2 分)。
每個頂點(diǎn)的度數(shù)不超過 6(3 分)。
根據(jù)握手定律(3 分)，
2|E|=頂點(diǎn)度數(shù)之和≤100*6, 所以這個圖的邊數(shù)不超過300(2 分)。
2. 所謂 n 維網(wǎng)格就是一個無向圖G=，其中V={ | 1≤ij≤mj,1≤j≤n}，E={(v1,v2)| v1 和v2 恰好只在一個坐標(biāo)上相差1}。討論當(dāng)mj 和n 取哪些正整數(shù)值時，G 是哈密頓圖，并給出證明。
解答與評分標(biāo)準(zhǔn)：
分情況討論。注意 G 的頂點(diǎn)數(shù)是m1*m2*m3*⋯*mn。
(1) 所有mj 都為1：G 是平凡圖，是哈密頓圖(2 分)。
(2) 恰好有一個mj 大于1：G 是長度大于1 的初級路徑，不是哈密頓圖(2 分)。
(3) 至少有兩個mj 大于1：G 是偶圖(無奇數(shù)長度回路)(2 分)。
(3a) m1*m2*m3*⋯*mn 是偶數(shù)：G 是哈密頓圖，用歸納法構(gòu)造哈密頓回路(2 分)。
(3b) m1*m2*m3*⋯*mn 是奇數(shù)：G 不是哈密頓圖，偶哈密頓圖兩部分頂點(diǎn)數(shù)相等，總頂點(diǎn)數(shù)是偶數(shù)(2 分)。
3. 證明或推翻下列命題：“任意給定平面上有限個點(diǎn)，則連接這些點(diǎn)的最短哈密頓回路的長度不超過連接這些點(diǎn)的最小生成樹(不添加額外頂點(diǎn))的長度的2 倍。子圖的長度就是這個子圖上的邊的長度之和。”
解答與評分標(biāo)準(zhǔn)：
命題成立(2 分)。
(課本圖論部分最后一章定理)先求最小生成樹奇數(shù)度頂點(diǎn)之間的“最小”匹配，加入匹配“邊”得到歐拉圖(3 分)。
沿著歐拉回路前進(jìn)，“抄近路”避開已經(jīng)訪問過的頂點(diǎn)，就得出哈密頓回路(3 分)。
由于距離的三角形不等式，這條哈密頓回路長度不超過最小生成樹長度的2 倍(2 分)。
4. 畫出所有非同構(gòu)的 5 階根樹。
解答與評分標(biāo)準(zhǔn)：
9 種(每種1 分，重復(fù)畫扣0.5 分，全畫10 分)。非同構(gòu)的5 階樹共有3種，分別選一個頂點(diǎn)做根。
5.證明或推翻下列命題：“設(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. 此時必有δ(G)=2, 與已知矛盾。(4 分)
結(jié)束
特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；
②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系我們溝通解決。
閱讀全文
一站式擇校服務(wù)！【免費(fèi)領(lǐng)取】專業(yè)規(guī)劃&擇校方案
500字以內(nèi)
發(fā)送
相關(guān)文章推薦
- 考后首發(fā)2019年同等學(xué)力申碩真題及答案解析
2019年同等學(xué)力申碩統(tǒng)考將于5月19日舉行，我們將于考后發(fā)布2019年同等學(xué)力申碩真題及答案解析。以下為2018年同等學(xué)力申碩各科
0贊0評論2019-05-15 09:01:06
評論0
“無需登錄，可直接評論...”