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

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

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

  命題成立(2 分)。

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

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

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

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

  2. 所謂 n 維網(wǎng)格就是一個(gè)無向圖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 是偶圖(無奇數(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)度不超過連接這些點(diǎn)的最小生成樹(不添加額外頂點(diǎn))的長(zhǎng)度的2 倍。子圖的長(zhǎng)度就是這個(gè)子圖上的邊的長(zhǎng)度之和?!?/p>

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

  命題成立(2 分)。

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

  沿著歐拉回路前進(jìn),“抄近路”避開已經(jīng)訪問過的頂點(diǎn),就得出哈密頓回路(3 分)。

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

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

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

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

  5.證明或推翻下列命題:“設(shè)連通簡(jiǎn)單平面圖G 的最小度δ(G)≥4,則G 的點(diǎn)色數(shù)χ(G)≥3.”

  解答與評(píng)分標(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 分)

報(bào)考資格評(píng)估
請(qǐng)?zhí)峁┮韵滦畔?,招生老師?huì)盡快與您聯(lián)系。符合報(bào)考條件者為您提供正式的報(bào)名表,我們承諾對(duì)您的個(gè)人信息嚴(yán)格保密。

相關(guān)文章

0/300
精彩留言

熱門學(xué)校

更多

熱門專題

2025年在職研究生報(bào)名時(shí)間、報(bào)名入口、報(bào)考條件 2025年上海交通大學(xué)在職研究生學(xué)費(fèi)詳解 在職研究生報(bào)考條件 非全日制研究生