網(wǎng)絡(luò)12離散結(jié)構(gòu)下重修試卷答案

1、。裝。訂。線。12 年13 年第二學(xué)期離散結(jié)構(gòu)（下） 重修時間共 120 分鐘1. 設(shè) V=,其中+ 和分別代表普通加法和乘法,對下面給定的每個集合確定它是否構(gòu)成 V 的子代數(shù), 為什么? (1)S1=2n|nZ; (2)S2=2n+1|nZ; (3)S3=-1,0,1.解:能不能,不能,子代數(shù),因?yàn)?S1 對加法和乘法封閉.(2 分)(2 分)(2 分)因?yàn)?S2 對加法不封閉.因?yàn)?S3 對加法不封閉.2. 畫出群的子群格.解 :是 循 環(huán) 群 ,由于 18的正因子有 1,2,3,6,9,18,故的子群有 ,.(2 分) 子群格如下:(4 分)3. 寫出下圖中頂點(diǎn) u1 的先驅(qū)元集-(u1

2、), 后繼元集+(u1), 鄰域 N(u1) 及閉鄰域題號一二三四總分得分閱卷人解:-(u1)=u3,u4, +(u1)=u2,u3, N(u1)=u2,u3,u4,1. 有向圖 D. 求:(1)v2 到 v5 長度為 1,2,3,4 的通路數(shù). (2)v5 到 v5 長度為 1,2,3,4 的回路數(shù). (3)D 中長度為 4 的通路數(shù)(含回路).(4)D 中長度小于或等于 4 的回路數(shù).解: 利用 D 的鄰接矩陣的前 4 次冪解此題.aS, 故 S 非空. x,yS, S 關(guān)于的封閉性:xyxa xyS S 關(guān)于的封閉性:xaya xya (1 分)(3 分)xyS(3 分)因此是 L 的.

3、3. 證明代數(shù) B 滿足模律.a,b,cB, ac, a(bc)=(ab)c證明:a(bc)=(ab)(ac)=(ab)c.(6 分)4. 設(shè) T 為非平凡的無向樹, (T)k, 證明 T 至少有 k 片樹葉.證明:方法一 設(shè)T 中有s 片樹葉, 剩余的n-s 個頂點(diǎn)的度數(shù)大于等于 2. (1 分)性質(zhì)及握手定理, 有又因?yàn)?T)k, 由樹的2m=2n-2k+2(n-s-1)+s(6 分)整理后得 sk.(1 分)方法二 利用 T 中最大度頂點(diǎn)是割點(diǎn).(1 分)設(shè) vV(T), 且 d(v)=(T)k, 則 v 為 T 的割點(diǎn), 因而 T-v 至少產(chǎn)生 k 個連通分支(均為樹)T1,T2,Tk

4、.(3 分)若Ti 為平凡樹, 則它是T 的樹葉; 否則Ti 至少有兩片樹葉, 其中至少有 1 片是T 的樹葉. 所以, T 至少有 k 片樹葉.(4 分)5. 設(shè) G 是簡單平面圖, 面數(shù) r12, (G)3. 證明 G 中存在次數(shù)小于或等于 4 的面.證明:不妨設(shè) G 是連通的,由 G 的連通性, 有n-m+r=2否則可對它的某個連通分支.(2 分)又因?yàn)?G)3, 由握手定理知2m3n=3(m-r+2)(2 分)m3r-6.(1 分)得假設(shè)每個面的次數(shù)至少是 5, 則2m5r(2 分)于是3r-6m2.5r(2 分)得 r12. 因此, 當(dāng) r12 時必存在次數(shù)小于或等于 4 的面.(1

5、 分)四、應(yīng)用題 （第 1 題 10, 第 2 題 11 分，共 21 分）1. 某工廠生產(chǎn)由 6 種不同顏色的紗織成的雙色布. 已知在一批雙色布中, 每種顏色至少與其他3 種顏色相搭配. 證明可以從這批雙色布中挑出 3 種, 它們由 6 種不同顏色的紗織成.解:作無向簡單圖 G=, V=v|v 為 6 種顏色之一, E=(u,v)|u,vV, uv 且在這批布中有 u與 v 搭配的雙色布.(2 分)由已知條件可知, u,vV, 有d(u)+d(v)3+3=6=|V|(2 分)根據(jù)圖的充分條件可知, G 為圖.(2 分)設(shè)C=vi1vi2vi6vi1 是G 中的一條這兩個頂點(diǎn)代表的顏色搭配成的雙色布.回路. 任何兩個頂點(diǎn)若在C 中相鄰, 則在這批布中有于是,在這批布中有vi1 與vi2, vi3 與vi4, vi5 與vi6 搭配成的 3 種雙色布, 它們使用了全部 6 種顏色.(4 分)2. n 位教員教n 門課程, 已知每個教員至少能教兩門課程, 而每門課程至多有兩位教員能教, 問能否每位教員正好教一門課?解:作二部圖 G=, 其中V1=v|v 是教員, V2=u|u 為課程, E=(u,v)|vV1uV2v 能教 u.(3 分)由題設(shè)|V1|=|V2