2015年同等學(xué)力在職研究生考試已經(jīng)結(jié)束，沒(méi)能報(bào)考的考生，從現(xiàn)在起可以為2016年的考試做準(zhǔn)備了。為了幫助考生更好的完成備考工作，唯學(xué)網(wǎng)小編為考生準(zhǔn)備了大量的輔導(dǎo)資料及試題，下面是小編準(zhǔn)備的同等學(xué)力計(jì)算機(jī)提升練習(xí)題及答案，以供各位考生查看了解。

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íng)分標(biāo)準(zhǔn)：

命題成立(2 分)。

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

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

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

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

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

9 種(每種1 分，重復(fù)畫(huà)扣0.5 分，全畫(huà)10 分)。非同構(gòu)的5 階樹(shù)共有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 分)

6. 證明或推翻下列命題：“設(shè)⊕表示集合的對(duì)稱(chēng)差運(yùn)算，則對(duì)于任意集合A和B 成立：P(A)⊕P(B)=P(A)⊕P(C)⇔B=C”。

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

命題成立(2分)

證明：⊕有消去律，P(A)⊕P(B)=P(A)⊕P(C)⇔P(B)=P(C) (3分)

P(B)=P(C)⇔B=C (3分)

其他細(xì)節(jié)(2分)

7. 證明或推翻下列命題：“設(shè) R 是從A 到B 的二元關(guān)系，則下列兩個(gè)條件互為充要條件。條件一：存在C⊆A 且D⊆B”使得R=C×D。條件二：對(duì)于A中任意x1,x2 和B 中y1,y2，有(x1Ry1∧x2Ry2)→x1Ry2.”

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

命題成立(2 分)。

條件一 ⇒ 條件二：x1∈C，y2∈D(3 分)。

條件二⇒ 條件一：C=dom(R)，D=ran(R)(3 分)。

其他細(xì)節(jié)(2 分)

8. 設(shè) A={1,2,…,10}，定義A 上的二元關(guān)系R={|x,y∈A∧x+y=10}，說(shuō)明R具有哪些性質(zhì)并說(shuō)明理由。

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

討論 5 種性質(zhì)(各2 分)。

非自反：<1,1>不屬于A。

非反自反：<5,5>∈A。

對(duì)稱(chēng)：定義。

非反對(duì)稱(chēng)：<3,7>,<7,3>∈A 但7 不等于3。

非傳遞：<3,7>,<7,3>∈A 但<3,3>不屬于A。

以上是同等學(xué)力計(jì)算機(jī)提升練習(xí)題及答案，以供大家備考使用�？忌�如果想獲得更多在職研究生相關(guān)資訊，如在職研究生報(bào)名時(shí)間、考試時(shí)間以及報(bào)考條件、相關(guān)知識(shí)，敬請(qǐng)關(guān)注唯學(xué)網(wǎng)，小編會(huì)在第一時(shí)間作出相關(guān)報(bào)道!