2015年同等學力計算機綜合模擬4

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

解答與評分標準：

命題成立(2 分)。

無向圖 G=，V 是平面上的這100 個點，兩個點相鄰當且僅當這兩點距離恰好是1(2 分)。

每個頂點的度數不超過 6(3 分)。

根據握手定律(3 分)，

2|E|=頂點度數之和≤100*6, 所以這個圖的邊數不超過300(2 分)。

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

解答與評分標準：

分情況討論。注意 G 的頂點數是m1*m2*m3*…*mn。

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

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

(3) 至少有兩個mj 大于1：G 是偶圖(無奇數長度回路)(2 分)。

(3a) m1*m2*m3*…*mn 是偶數：G 是哈密頓圖，用歸納法構造哈密頓回路(2 分)。

(3b) m1*m2*m3*…*mn 是奇數：G 不是哈密頓圖，偶哈密頓圖兩部分頂點數相等，總頂點數是偶數(2 分)。

3. 證明或推翻下列命題：“任意給定平面上有限個點，則連接這些點的最短

哈密頓回路的長度不超過連接這些點的最小生成樹(不添加額外頂點)的

長度的2 倍。子圖的長度就是這個子圖上的邊的長度之和。”

解答與評分標準：

命題成立(2 分)。

(課本圖論部分最后一章定理)先求最小生成樹奇數度頂點之間的“最小”匹配，加入匹配“邊”得到歐拉圖(3 分)。

沿著歐拉回路前進，“抄近路”避開已經訪問過的頂點，就得出哈密頓回路(3 分)。

由于距離的三角形不等式，這條哈密頓回路長度不超過最小生成樹長度的2 倍(2 分)。

更多關注：

同等學歷報考指南  同等學歷考試用書 同等學歷考試模擬試題

（責任編輯：中大編輯）

共2頁,當前第1頁  第一頁  前一頁  下一頁