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

發(fā)表時(shí)間：2015/4/2 11:24:46 來(lái)源：互聯(lián)網(wǎng) 點(diǎn)擊關(guān)注微信：

關(guān)注公眾號(hào)

1. 證明或推翻下列命題：“設(shè)平面上有 100 個(gè)點(diǎn)，其中任意兩點(diǎn)間的距離至少是1，則最多有300 對(duì)點(diǎn)距離恰好是1”。

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

命題成立(2 分)。

無(wú)向圖 G=，V 是平面上的這100 個(gè)點(diǎn)，兩個(gè)點(diǎn)相鄰當(dāng)且僅當(dāng)這兩點(diǎn)距離恰好是1(2 分)。

每個(gè)頂點(diǎn)的度數(shù)不超過(guò) 6(3 分)。

根據(jù)握手定律(3 分)，

2|E|=頂點(diǎn)度數(shù)之和≤100*6, 所以這個(gè)圖的邊數(shù)不超過(guò)300(2 分)。

2. 所謂 n 維網(wǎng)格就是一個(gè)無(wú)向圖G=，其中V={ | 1≤ij≤mj,1≤j≤n}，E={(v1,v2)| v1 和v2 恰好只在一個(gè)坐標(biāo)上相差1}。討論當(dāng)mj 和n 取哪些正整數(shù)值時(shí)，G 是哈密　　頓圖，并給出證明。

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

分情況討論。注意 G 的頂點(diǎn)數(shù)是m1*m2*m3*…*mn。

(1) 所有mj 都為1：G 是平凡圖，是哈密頓圖(2 分)。

(2) 恰好有一個(gè)mj 大于1：G 是長(zhǎng)度大于1 的初級(jí)路徑，不是哈密頓圖(2 分)。

(3) 至少有兩個(gè)mj 大于1：G 是偶圖(無(wú)奇數(shù)長(zhǎng)度回路)(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. 證明或推翻下列命題：“任意給定平面上有限個(gè)點(diǎn)，則連接這些點(diǎn)的最短

哈密頓回路的長(zhǎng)度不超過(guò)連接這些點(diǎn)的最小生成樹(shù)(不添加額外頂點(diǎn))的

長(zhǎng)度的2 倍。子圖的長(zhǎng)度就是這個(gè)子圖上的邊的長(zhǎng)度之和?！?/p>

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

命題成立(2 分)。