《離散數學》試題帶答案一、填空20%（每小題2分）P：你努力，Q：你失敗。“除非你努力，否則你將失敗”的翻譯為；“雖然你努力了，但還是失敗了”的翻譯為。2、論域D={1，2}，指定謂詞PP(1,1)P(1,2)P(2,1)P(2,2)TTFF則公式真值為。設S={a1，a2，…，a8}，Bi是S的子集，則由B31所表達的子集是。設A={2，3，4，5，6}上的二元關系，則R= （列舉法）。R的關系矩陣MR=。5、設A={1，2，3}，則A上既不是對稱的又不是反對稱的關系R=；A上既是對稱的又是反對稱的關系R=。*abcabcabcbbcccb6、設代數系統<A，*>，其中A={a，b，c},則幺元是；是否有冪等性；是否有對稱性。7、4階群必是群或群。8、下面偏序格是分配格的是。9、n個結點的無向完全圖Kn的邊數為，歐拉圖的充要條件是。10、公式的根樹表示為。二、選擇20%（每小題2分）1、在下述公式中是重言式為（）A．；B．；C．；D．。2、命題公式中極小項的個數為（），成真賦值的個數為（）。A．0；B．1；C．2；D．3。3、設，則有（）個元素。A．3；B．6；C．7；D．8。設，定義上的等價關系則由R產生的上一個劃分共有（）個分塊。A．4；B．5；C．6；D．9。5、設，S上關系R的關系圖為則R具有（）性質。A．自反性、對稱性、傳遞性；B．反自反性、反對稱性；C．反自反性、反對稱性、傳遞性；D．自反性。6、設為普通加法和乘法，則（）是域。A．B．C．D．=N。7、下面偏序集（）能構成格。8、在如下的有向圖中，從V1到V4長度為3的道路有（）條。A．1；B．2；C．3；D．4。9、在如下各圖中（）歐拉圖。10、設R是實數集合，“”為普通乘法，則代數系統<R，×>是（）。A．群；B．獨異點；C．半群。三、證明46%設R是A上一個二元關系，試證明若R是A上一個等價關系，則S也是A上的一個等價關系。（9分）用邏輯推理證明：所有的舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。（11分）若是從A到B的函數，定義一個函數對任意有，證明：若f是A到B的滿射，則g是從B到的單射。（10分）若無向圖G中只有兩個奇數度結點，則這兩個結點一定連通。（8分）設G是具有n個結點的無向簡單圖，其邊數，則G是Hamilton圖（8分）四、計算14%設<Z6,+6>是一個群，這里+6是模6加法，Z6={[0]，[1]，[2]，[3]，[4]，[5]}，試求出<Z6,+6>的所有子群及其相應左陪集。（7分）權數1，4，9，16，25，36，49，64，81，100構造一棵最優二叉樹。（7分）試卷二答案：填空20%（每小題2分）1、；2、T3、4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>}6、a；否；有7、Klein四元群；循環群8、B9、；圖中無奇度結點且連通10、選擇20%（每小題2分）題目12345678910答案B、DD；DDBDABBBB、C證明46%1、（9分）S自反的，由R自反，，S對稱的S傳遞的由（1）、（2）、（3）得；S是等價關系。2、11分證明：設P(x)：x是個舞蹈者；Q(x)：x很有風度；S(x)：x是個學生；a：王華上述句子符號化為：前提：、結論：……3分① P② P③ US②④ T①I⑤ T③④I⑥ T①I⑦ T⑤⑥I⑧ EG⑦ ……11分３、１0分證明：。4、8分證明：設G中兩奇數度結點分別為u和v，若u，v不連通，則G至少有兩個連通分支G1、G2，使得u和v分別屬于G1和G2，于是G1和G2中各含有1個奇數度結點，這與圖論基本定理矛盾，因而u，v一定連通。5、8分證明：證G中任何兩結點之和不小于n。反證法：若存在兩結點u，v不相鄰且,令，則G-V1是具有n-2個結點的簡單圖，它的邊數,可得，這與G1=G-V1為n-2個結點為簡單圖的題設矛盾，因而G中任何兩個相鄰的結點度數和不少于n。所以G為Hamilton圖.計算14%7分解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>{[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]}{[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]}{[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]}Z6的左陪集：Z6。7分試卷三試題與答案填空20%（每空2分）設f，g是自然數集N上的函數，則。設A={a，b，c}，A上二元關系R={<a,a>,<a,b>,<a,c>,<c,c>},則s（R）=。A={1，2，3，4，5，6}，A上二元關系，則用列舉法T=；T的關系圖為；T具有性質。集合的冪集=。P，Q真值為0；R，S真值為1。則的真值為。的主合取范式為。設P（x）：x是素數，E(x)：x是偶數，O(x)：x是奇數N(x,y)：x可以整數y。則謂詞的自然語言是。謂詞的前束范式為。選擇20%（每小題2分）下述命題公式中，是重言式的為（）。A、；B、；C、；D、。的主析取范式中含極小項的個數為（）。A、2；B、3；C、5；D、0；E、8。給定推理① P② US①③ P④ ES③⑤ T②④I⑥ UG⑤推理過程中錯在（）。A、①->②;B、②->③;C、③->④;D、④->⑤;E、⑤->⑥設S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在條件下X與（）集合相等。X=S2或S5；B、X=S4或S5；C、X=S1，S2或S4；D、X與S1，…，S5中任何集合都不等。設R和S是P上的關系，P是所有人的集合，，則表示關系（）。A、；B、；C、；D、。下面函數（）是單射而非滿射。A、；B、；C、；D、。其中R為實數集，Z為整數集，R+，Z+分別表示正實數與正整數集。設S={1，2，3}，R為S上的關系，其關系圖為則R具有（）的性質。自反、對稱、傳遞；B、什么性質也沒有；C、反自反、反對稱、傳遞；D、自反、對稱、反對稱、傳遞。設，則有（）。A、{{1,2}}；B、{1,2}；C、{1}；D、{2}。設A={1,2,3}，則A上有（）個二元關系。A、23；B、32；C、；D、。10、全體小項合取式為（）。A、可滿足式；B、矛盾式；C、永真式；D、A，B，C都有可能。用CP規則證明16%（每小題8分）1、2、四、（14%）集合X={<1,2>,<3,4>,<5,6>,…}，R={<<x1,y1>,<x2,y2>>|x1+y2=x2+y1}。證明R是X上的等價關系。（10分）求出X關于R的商集。（4分）五、（10%）設集合A={a,b,c,d}上關系R={<a,b>,<b,a>,<b,c>,<c,d>}要求1、寫出R的關系矩陣和關系圖。（4分）2、用矩陣運算求出R的傳遞閉包。（6分）六、（20%）1、（10分）設f和g是函數，證明也是函數。2、（10分）設函數，證明有一左逆函數當且僅當f是入射函數。答案：填空20%（每空2分）1、2(x+1)；2、；3、；4、反對稱性、反自反性；4、；5、1；6、；7、任意x，如果x是素數則存在一個y，y是奇數且y整除x；8、。選擇20%（每小題2分）題目12345678910答案CCCCABDADC證明16%(每小題8分)1、① P（附加前提）② T①I③ P④ T②③I⑤ T④I⑥ T⑤I⑦ P⑧ T⑥⑦I⑨ CP2、① P（附加前提）② T①E③ ES②④ P⑤ US④⑥ T③⑤I⑦ EG⑥⑧ CP14%證明：自反性：對稱性：傳遞性：即由（1）（2）（3）知：R是X上的先等價關系。2、X/R=10%1、；關系圖2、 t(R)={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c.>,<b,d>,<c,d>}。六、20%1、（1）（2）。2、證明：。。

試卷四試題與答案填空10%（每小題2分）若P，Q，為二命題，真值為0當且僅當。命題“對于任意給定的正實數，都存在比它大的實數”令F(x)：x為實數，則命題的邏輯謂詞公式為。謂詞合式公式的前束范式為。將量詞轄域中出現的和指導變元交換為另一變元符號，公式其余的部分不變，這種方法稱為換名規則。設x是謂詞合式公式A的一個客體變元，A的論域為D，A(x)關于y是自由的，則被稱為存在量詞消去規則，記為ES。選擇25%（每小題2.5分）下列語句是命題的有（）。明年中秋節的晚上是晴天；B、；C、當且僅當x和y都大于0；D、我正在說謊。下列各命題中真值為真的命題有（）。2+2=4當且僅當3是奇數；B、2+2=4當且僅當3不是奇數；C、2+2≠4當且僅當3是奇數；D、2+2≠4當且僅當3不是奇數；下列符號串是合式公式的有（）A、；B、；C、；D、。下列等價式成立的有（）。A、；B、；C、；D、。若和B為wff，且則（）。A、稱為B的前件；B、稱B為的有效結論C、當且僅當；D、當且僅當。A，B為二合式公式，且，則（）。A、為重言式；B、；C、；D、；E、為重言式。“人總是要死的”謂詞公式表示為（）。（論域為全總個體域）M(x)：x是人；Mortal(x)：x是要死的。A、；B、C、；D、公式的解釋I為：個體域D={2}，P(x)：x>3,Q(x)：x=4則A的真值為（）。A、1；B、0；C、可滿足式；D、無法判定。下列等價關系正確的是（）。A、；B、；C、；D、。下列推理步驟錯在（）。① P② US①③ P④ ES③⑤ T②④I⑥ EG⑤A、②；B、④；C、⑤；D、⑥邏輯判斷30%用等值演算法和真值表法判斷公式的類型。（10分）下列問題，若成立請證明，若不成立請舉出反例：（10分）已知，問成立嗎？已知，問成立嗎？如果廠方拒絕增加工資，那么罷工就不會停止，除非罷工超過一年并且工廠撤換了廠長。問：若廠方拒絕增加工資，面罷工剛開始，罷工是否能夠停止。（10分）四、計算10%設命題A1，A2的真值為1，A3，A4真值為0，求命題的真值。（5分）利用主析取范式，求公式的類型。（5分）五、謂詞邏輯推理15%符號化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結論。六、證明：（10%）設論域D={a,b,c}，求證：。答案：填空10%（每小題2分）1、P真值為1，Q的真值為0；2、；3、；4、約束變元；5、，y為D的某些元素。選擇25%（每小題2.5分）題目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)邏輯判斷30%1、（1）等值演算法（2）真值表法PQA1111111100100101100010011111所以A為重言式。2、（1）不成立。若取但A與B不一定等價，可為任意不等價的公式。（2）成立。證明：即：所以故。3、解：設P：廠方拒絕增加工資；Q：罷工停止；R罷工超壺過一年；R：撤換廠長前提：結論：① P② P③ T①②I④ P⑤ T④I⑥ T⑤E⑦ T③⑥I罷工不會停止是有效結論。四、計算10%解：它無成真賦值，所以為矛盾式。五、謂詞邏輯推理15%解：證明：⑴ P⑵ ES⑴⑶ T⑵I⑷ T⑵I⑸ P⑹ US⑸⑺ T⑶⑹I⑻ T⑺E⑼ US⑷⑽ US⑻⑾ T⑼⑽I⑿ UG⑾證明10%試卷五試題與答案一、填空15%（每空3分）1、設G為9階無向圖，每個結點度數不是5就是6，則G中至少有個5度結點。2、n階完全圖，Kn的點數X(Kn)=。3、有向圖中從v1到v2長度為2的通路有條。4、設[R，+，·]是代數系統，如果①[R，+]是交換群②[R，·]是半群③則稱[R，+，·]為環。5、設是代數系統，則滿足冪等律，即對有。二、選擇15%（每小題3分）下面四組數能構成無向簡單圖的度數列的有（）。A、（2，2，2，2，2）；B、（1，1，2，2，3）；C、（1，1，2，2，2）；D、（0，1，3，3，3）。下圖中是哈密頓圖的為（）。如果一個有向圖D是強連通圖，則D是歐拉圖，這個命題的真值為（）A、真；B、假。下列偏序集（）能構成格。設，*為普通乘法，則[S，*]是（）。A、代數系統；B、半群；C、群；D、都不是。三、證明48%1、（10%）在至少有2個人的人群中，至少有2個人，他們有相同的朋友數。2、（8%）若圖G中恰有兩個奇數度頂點，則這兩個頂點是連通的。3、（8%）證明在6個結點12條邊的連通平面簡單圖中，每個面的面數都是3。4、（10%）證明循環群的同態像必是循環群。5、（12%）設是布爾代數，定義運算*為，求證[B，*]是阿貝爾群。四、計算22%1、在二叉樹中求帶權為2，3，5，7，8的最優二叉樹T。（5分）求T對應的二元前綴碼。（5分）下圖所示帶權圖中最優投遞路線并求出投遞路線長度（郵局在D點）。答案：一、填空（15%）每空3分1、6；2、n；3、2；4、+對·分配且·對+分配均成立；5、。二、選擇（15%）每小題3分題目12345答案A,BB,DBCD三、證明（48%）1、（10分）證明：用n個頂點v1，…，vn表示n個人，構成頂點集V={v1，…，vn}，設，無向圖G=（V，E）現證G中至少有兩個結點度數相同。事實上，（1）若G中孤立點個數大于等于2，結論成立。（2）若G中有一個孤立點，則G中的至少有3個頂點，既不考慮孤立點。設G中每個結點度數均大于等于1，又因為G為簡單圖，所以每個頂點度數都小于等于n-1，由于G中n頂點其度數取值只能是1，2，…，n-1，由鴿巢原理，必然至少有兩個結點度數是相同的。2、（8分）證：設G中兩個奇數度結點分別為u，v。若u，v不連通則至少有兩個連通分支G1、G2，使得u，v分別屬于G1和G2。于是G1與G2中各含有一個奇數度結點，與握手定理矛盾。因而u，v必連通。3（8分）證：n=6,m=12歐拉公式n-m+f=2知f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個面用3條邊圍成。4（10分）證：設循環群[A，·]的生成元為a，同態映射為f，同態像為[f（A），*]，于是都有對n=1有n=2,有若n=k-1時有對n=k時，這表明，f(A)中每一個元素均可表示為，所以[f(A),*]為f(a)生成的循環群。5、證：交換律：有結合律：有而：幺：有逆：綜上所述：[B，*]是阿貝爾群。四、計算（22%）1、（10分）（1）（5分）由Huffman方法,得最佳二叉樹為：（2）（5分）最佳前綴碼為：000，001，01，10，112、（12分）圖中奇數點為E、F，d(E)=3,d(F)=3,d(E,F)=28p=EGF復制道路EG、GF，得圖G‘，則G‘是歐拉圖。由D開始找一條歐拉回路：DEGFGEBACBDCFD。道路長度為：35+8+20+20+8+40+30+50+19+6+12+10+23=281。試卷六試題與答案填空15%（每小題3分）n階完全圖結點v的度數d(v)=。設n階圖G中有m條邊，每個結點的度數不是k的是k+1，若G中有Nk個k度頂點，Nk+1個k+1度頂點，則Nk=。算式的二叉樹表示為。如圖給出格L，則e的補元是。一組學生，用二二扳腕子比賽法來測定臂力的大小，則幺元是。二、選擇15%（每小題3分）1、設S={0,1,2,3},≤為小于等于關系，則{S，≤}是（）。A、群；B、環；C、域；D、格。2、設[{a,b,c}，*]為代數系統，*運算如下：*abcaabcbbaccccc則零元為（）。A、a；B、b；C、c；D、沒有。3、如右圖相對于完全圖K5的補圖為（）。4、一棵無向樹T有7片樹葉，3個3度頂點，其余頂點均為4度。則T有（）4度結點。A、1；B、2；C、3；D、4。5、設[A，+，·]是代數系統，其中+，·為普通加法和乘法，則A=（）時，[A，+，·]是整環。A、；B、；C、；D、。三、證明50%1、設G是（n,m）簡單二部圖，則。（10分）2、設G為具有n個結點的簡單圖，且，則G是連通圖。（10分）3、記“開”為1，“關”為0，反映電路規律的代數系統[{0，1}，+，·]的加法運算和乘法運算。如下：+01·01001000110101證明它是一個環，并且是一個域。（14分）是一代數格，“≤”為自然偏序，則[L，≤]是偏序格。（16分）四、10%設是布爾代數上的一個布爾表達式，試寫出的析取范式和合取范式（10分）五、10%如下圖所示的賦權圖表示某七個城市及預先算出它們之間的一些直接通信成路造價（單位：萬元），試給出一個設計方案，使得各城市之間既能夠通信又使總造價最小。答案：一、填空15%（每小題3分）1、n-1；2、n(k+1)-2m；3、如右圖；4、0；5、臂力小者二、選擇15%（每小題3分）題目12345答案DCAAD三、證明50%證：設G=（V，E）對完全二部圖有當時，完全二部圖的邊數m有最大值故對任意簡單二部圖有。證：反證法：若G不連通，不妨設G可分成兩個連通分支G1、G2，假設G1和G2的頂點數分別為n1和n2，顯然與假設矛盾。所以G連通。（1）[{0，1}，+，·]是環①[{0，1}，+]是交換群乘：由“+”運算表知其封閉性。由于運算表的對稱性知：+運算可交換。群：（0+0）+0=0+（0+0）=0；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0……結合律成立。 幺：幺元為0。 逆：0，1逆元均為其本身。②[{0，1}，·]是半群乘：由“·”運算表知封閉群：（0·0）·0=0·（0·0）=0；（0·0）·1=0·（0·1）=0；（0·1）·0=0·（1·0）=0；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0。③·對+的分配律Ⅰ0·（x+y）=0=0+0=(0·x)+(0·y)；Ⅱ1·（x+y）當x=y(x+y)=0則；當（）則所以均有同理可證：所以·對+是可分配的。由①②③得，[{0，1}，+，·]是環。（2）[{0，1}，+，·]是域因為[{0，1}，+，·]是有限環，故只需證明是整環即可。①乘交環：由乘法運算表的對稱性知，乘法可交換。②含幺環：乘法的幺元是1③無零因子：1·1=1≠0因此[{0，1}，+，·]是整環，故它是域。4、證：（1）“≤”是偏序關系，≤自然偏序①反自反性：由代數格冪等關系：。②反對稱性：若即：，則③傳遞性：則：（2）在L中存在{x,y}的下（上）確界設則：事實上：若{x,y}有另一下界c，則是{x,y}最大下界，即同理可證上確界情況。四、14%解：函數表為：00000011010001111000101111011111析取范式：合取范式：五、10%解：用庫斯克（Kruskal）算法求產生的最優樹。算法為：結果如圖：樹權C(T)=23+1+4+9+3+17=57（萬元）即為總造價

試卷七試題與答案填空15%（每小題3分）任何(n,m)圖G=(V,E),邊與頂點數的關系是。當n為時,非平凡無向完全圖Kn是歐拉圖。已知一棵無向樹T有三個3頂點,一個2度頂點,其余的都是1度頂點,則T中有個1度頂點。n階完全圖Kn的點色數X(KN)=。一組學生,用兩兩扳腕子比賽來測定臂力大小,則幺元是。選擇15%（每小題3分）1、下面四組數能構成無向圖的度數列的有()。A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。2、圖的鄰接矩陣為()。A、；B、；C、；D、。3、下列幾個圖是簡單圖的有()。G1=(V1,E1),其中V1={a,b,c,d,e},E1={ab,be,eb,ae,de}；G2=(V2,E2)其中V2=V1,E2={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}；G=(V3,E3),其中V3=V1,E3={ab,be,ed,cc}；G=(V4,E4),其中V4=V1,E4={（a,a）,（a,b）,（b,c）,（e,c）,（e,d）}。4、下列圖中是歐拉圖的有()。5、，其中，為集合對稱差運算，則方程的解為（）。A、；B、；C、；D、。證明34%證明：在至少有2個人的人群中，至少有2個人，他的有相同的朋友數。（8分）若圖G中恰有兩個奇數頂點，則這兩個頂點是連通的。（8分）證明：在6個結點12條邊的連通平面簡單圖中，每個面的面度都是3。（8分）證明循環群的同態像必是循環群。（10分）中國郵遞員問題13%求帶權圖G中的最優投遞路線。郵局在v1點。根樹的應用13%在通訊中，八進制數字出現的頻率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求傳輸它們最佳前綴碼（寫出求解過程）。10%設B4={e,a,b,ab}，運算*如下表，*則<B4,*>是一個群（稱作Klein四元群答案：填空15%（每小題3分）1、；2、奇數；3、5；4、n；5、臂力小者選擇15%（每小題3分）題目12345答案BCBBA證明34%1、（10分）證明：用n個頂點v1，…，vn表示n個人，構成頂點集V={v1，…，vn}，設，無向圖G=（V，E）現證G中至少有兩個結點度數相同。事實上，（1）若G中孤立點個數大于等于2，結論成立。（2）若G中有一個孤立點，則G中的至少有3個頂點，現不考慮孤立點。設G中每個結點度數均大于等于1，又因為G為簡單圖，所以每個頂點度數都小于等于n-1，由于G中頂點數到值只能是1，2，…，n-1這n-1個數，因而取n-1個值的n個頂點的度數至少有兩個結點度數是相同的。2、（8分）證：設G中兩個奇數度結點分別為u，v。若u，v不連通，即它們中無任何通路，則至少有兩個連通分支G1、G2，使得u，v分別屬于G1和G2。于是G1與G2中各含有一個奇數度結點，與握手定理矛盾。因而u，v必連通。3、（8分）證：n=6,m=12歐拉公式n-m+f=2知f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個面用3條邊圍成。4、（10分）證：設循環群[A，·]的生成元為a，同態映射為f，同態像為<f（A），*>，于是都有對n=1有n=2,有若n=k-1時有對n=k時，這表明，f(A)中每一個元素均可表示為，所以<f(A),*>是以f(a)生成元的循環群。中國郵遞員問題14%解：圖中有4個奇數結點，求任兩結點的最短路再找兩條道路使得它們沒有相同的起點和終點，且長度總和最短：在原圖中復制出，設圖G‘，則圖G‘中每個結點度數均為偶數的圖G‘存在歐拉回路，歐拉回路C權長為43。根樹的應用13%解：用100乘各頻率并由小到大排列得權數用Huffman算法求最優二叉樹：前綴碼用00000傳送5；00001傳送6；0001傳送7；100傳送3；101傳送4；001傳送2；11傳送1；01傳送0（頻率越高傳送的前綴碼越短）。10%證明：乘：由運算表可知運算*是封閉的。群：即要證明，這里有43=64個等式需要驗證但：①e是幺元，含e的等式一定成立。②ab=a*b=b*a，如果對含a，b的等式成立，則對含a、b、ab的等式也都成立。③剩下只需驗證含a、b等式，共有23=8個等式。即：(a*b)*a=ab*a=b=a*(b*a)=a*ab=b；(a*b)*b=ab*b=a=a*(b*b)=a*e=a；(a*a)*a=e*a=a=a*(a*a)=a*e=a；(a*a)*b=e*b=b=a*(a*b)=a*ab=b；(b*b)*a=e*a=a=b*(b*a)=b*ab=a；(b*b)*b=e*b=b=b*(b*b)=b*e=b；(b*a)*a=ab*a=b=b*(a*a)=b*e=b；(b*a)*b=ab*b=a=b*(a*b)=b*ab=a。幺：e為幺元逆：e-1=e；a-1=a；b-1=b；(ab)-1=ab。所以<B4,*>為群。試卷八試題與答案填空15%（每小題3分）n階完全圖Kn的邊數為。右圖的鄰接矩陣A=。圖的對偶圖為。完全二叉樹中，葉數為nt，則邊數m=。設<{a,b,c},*>為代數系統，*運算如下：*abcaabcbbaccccc

則它的幺元為；零元為；a、b、c的逆元分別為。選擇15%（每小題3分）圖相對于完全圖的補圖為（）。對圖G則分別為（）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。一棵無向樹T有8個頂點，4度、3度、2度的分枝點各1個，其余頂點均為樹葉，則T中有（）片樹葉。A、3；B、4；C、5；D、6設<A，+，·>是代數系統，其中+，·為普通的加法和乘法，則A=（）時<A，+，·>是整環。A、；B、；C、；D、。設A={1，2，…，10}，則下面定義的運算*關于A封閉的有（）。x*y=max(x,y)；B、x*y=質數p的個數使得；C、x*y=gcd(x,y)；(gcd(x,y)表示x和y的最大公約數)；D、x*y=lcm(x,y)（lcm(x,y)表示x和y的最小公倍數）。證明45%1、設G是（n,m）簡單二部圖，則。（8分）2、設G為具有n個結點的簡單圖，且則G是連通圖。（8分）3、設G是階數不小于11的簡單圖，則G或中至少有一個是非平圖。（14分）4、記“開”為1，“關”為0，反映電路規律的代數系統[{0，1}，+，·]的加法運算和乘法運算。如下：+01·01001000110101證明它是一個環，并且是一個域。（15分）生成樹及應用10%1、（10分）如下圖所示