《離散數(shù)學(xué)》同步練習(xí)參考答案

#/26第五章代數(shù)結(jié)構(gòu)一填空題(1)集合S的冪集P(S)關(guān)于集合的并運(yùn)算“U”的零元為S。(2)集合S的冪集p(S)關(guān)于集合的并運(yùn)算“n”的零元為一°—。(3)集合S的冪集P(S)關(guān)于集合的并運(yùn)算“U”的么元為一°。一個(gè)代數(shù)系統(tǒng)<S,*>，其中S是非空集合。*是S上的一個(gè)二元運(yùn)算，如果 *在S上是封閉的 ，則稱代數(shù)系統(tǒng)<S,*>為廣群。二.判斷題TOC\o"1-5"\h\z.含有零元的半群稱為獨(dú)異點(diǎn)。 (X).運(yùn)算“+”是整數(shù)集I上的普通加法，則群<I,+>的么元是1。 (x)三、填空題：在每小題的備選答案中只有一個(gè)正確答案，將正確答案序號填入下列敘述中的內(nèi)。i下列群一定為循環(huán)群的是 e)。<I,+>(運(yùn)算"+”是整數(shù)集I上的普通加法)<R—{0},義>(R是實(shí)數(shù)集，“義”是普通乘法)<Q,+>(運(yùn)算"+”是有理數(shù)集Q上的普通加法)<P(S),十>(P(S)是集合S的冪集，“十”為對稱差).運(yùn)算“一”是整數(shù)集I上的普通減法，則代數(shù)系統(tǒng)<I,->滿足下列性質(zhì)(3)。(1)結(jié)合律 (2)交換律 (3)有零元 (4)封閉性.設(shè)I是整數(shù)集，N是自然數(shù)集，P(S)是S的冪集，“x,+,n”是普通的乘法，加法和集合的交運(yùn)算。下面代數(shù)系統(tǒng)中(2)是群。<I，義>(2)<I,+> (3)<P(S),n> (4)<N,+>.下列代數(shù)系統(tǒng)不是群的是(2)。<I,+>(運(yùn)算"+”是整數(shù)集I上的普通加法)<p(s),n>(P(S)是集合S的冪集，“n”為交運(yùn)算)<Q,+>(運(yùn)算"+”是有理數(shù)集Q上的普通加法)<P(S),十>(P(S)是集合S的冪集，“十”為對稱差)第七章圖論一填空題（1）一個(gè)無向圖G=（V,E）是二部圖當(dāng)且僅當(dāng)G中無奇數(shù)長度的回路。（2）任何圖無向的或有向的中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為 偶數(shù)。（3）設(shè)D是一個(gè)有向圖，若D中任意一對頂點(diǎn)都是相互可達(dá)的，則稱D是雙向連通的。（4）既不含平行邊，也不含環(huán)的圖稱為簡單圖。（5）經(jīng)過圖中 每條邊一次且僅一次并的回路，稱為歐拉回路。（6）一棵有n個(gè)頂點(diǎn)的樹含有n-1邊。（7）設(shè)G=（V,E）,G=（▽,E）是兩個(gè)圖，若V′=V且_E'屋E,稱G是G的生成子圖。（8）經(jīng)過圖中 每個(gè)結(jié)點(diǎn)一次且僅一次的回路，稱為哈密爾頓回路。二.判斷題TOC\o"1-5"\h\z1.5個(gè)頂點(diǎn)的有向完全圖有20條邊。 （J）.連通無向圖的歐拉回路經(jīng)過圖中的每個(gè)頂點(diǎn)一次且僅一次。 （x）.圖中的初級通路都是簡單通路。 （J）.已知n（n22）階無向簡單圖G有n-1條邊，則G一定為樹。 （x）.n階無向完全圖Kn的每個(gè)頂點(diǎn)的度都是n。 （x）.一個(gè)無向圖是二部圖當(dāng)且僅當(dāng)它沒有奇數(shù)度的頂點(diǎn)。 （x）.任何圖都有一棵生成樹。 （x）.連通無向圖的哈密爾頓回路經(jīng)過圖中的每條邊一次且僅一次。 （x）.圖中的初級回路都是簡單回路。 （J）.任一圖G=（V,E）的頂點(diǎn)的最大度數(shù)必小于G的頂點(diǎn)數(shù)。 （x）.歐拉圖一定是漢密爾頓圖。 （x）.無向連通圖G的任意兩結(jié)點(diǎn)之間都存在一條路。 （J）.根樹中除一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)的入度為1。三、選擇題：在每小題的備選答案中只有一個(gè)正確答案，將正確答案序號填入下列敘述中的內(nèi)。1.下列為歐拉圖的是⑷。3.設(shè)無向圖G有12條邊，已知G中3度頂點(diǎn)有6個(gè)，其余頂點(diǎn)的度數(shù)都小于3,則該圖至少有(3)個(gè)頂點(diǎn)。(1)6 (2)8 (3)9 (4)124下列四個(gè)有個(gè)結(jié)點(diǎn)的圖⑶是連通圖。(1) (2) (3) (4)5.稱圖G'=<Vv,E'>為圖G=<V,E>的生成子圖是指—(3)(1)V’ 屋V (2) V‘ 屋V且E’ 屋E(3)V’ =V且E‘ 屋E (4) V’ uV且E’ uE6有向圖中結(jié)點(diǎn)之間的可達(dá)關(guān)系是 (2) 。()自反的，對稱的 (2)自反的，傳遞的()自反的，反對稱的 (4)反自反的，對稱的.在下列關(guān)于圖論的命題中，為真的命題是 d) 。a)完全二部圖Kn,m(n>1,m21)是歐拉圖b)歐拉圖一定是哈密爾頓圖c)無向完全圖Kn(n>3)都是歐拉圖d)無向完全圖Kn(n>3)都是哈密爾頓圖.下列各圖為平面圖的是 (3) 。.設(shè)G為任意的連通的平面圖，且G有n個(gè)頂點(diǎn)，m條邊，r個(gè)面，則平面圖的歐拉公式為(1)。(1)n-m+r=2(2)m-n+r=2(3)n+m-r=2(4)r+n+m=210. 下列四個(gè)圖中與其余三個(gè)圖不同構(gòu)的圖是(3) 。四、解答題.給定邊集：｛(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)},(1)畫出相應(yīng)的無向圖G(設(shè)G無孤立點(diǎn))；(2)畫出頂點(diǎn)子集V1={2,3,4,5}導(dǎo)出的導(dǎo)出子圖;(3)畫出圖G的一棵生成樹。⑴⑴.如圖所示帶權(quán)圖，用避圈法Kruskal算法求一棵最小生成樹并計(jì)算它的權(quán)值。它的權(quán)值為：1+2+4+4=11.如圖所示帶權(quán)圖，用避圈法Kruskal算法求一棵最小生成樹，并計(jì)算它的權(quán)值。它的權(quán)值為：1+2+3+5+7=18.求帶權(quán)圖G的最小生成樹，并計(jì)算它的權(quán)值。

它的權(quán)值為：1+1+2+3=75.給定權(quán)為2它的權(quán)值為：1+1+2+3=75.給定權(quán)為2,6,3,9,4；構(gòu)造一顆最優(yōu)二叉樹，并求此最優(yōu)二叉樹的權(quán)。最優(yōu)二叉樹的權(quán):2x3+3x3+4x2+6x2+9x2=53并求此最優(yōu)二叉樹的權(quán)。.給定權(quán)為1,9,4,7,3；構(gòu)造一顆