一、填空題
1．已知圖g中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則g的邊數是 15
2．設給定圖g(如右由圖所示)，則圖g的點割集是
和，e=，試
(1) 給出g的圖形表示2) 寫出其鄰接矩陣；
(3) 求出每個結點的度數4) 畫出其補圖的圖形．
解：(1)如右圖
(2)(3) v1的度數為1，v2的度數為2，v3的度數為4，v4的度數為3，v5的度數為2
(4) 如右圖
2．圖g=，其中v=，e=，對應邊的權值依次為2、1、2、3、6、1、4及5，試
（1）畫出g的圖形2）寫出g的鄰接矩陣；
（3）求出g權最小的生成樹及其權值．
解：(1) 如右圖
(2) (3)最小生成樹:
t=3．已知帶權圖g如右圖所示．
(1) 求圖g的最小生成樹； (2)計算該生成樹的權值．
解：(1)最小生成樹由權為1、2、3、5、7的邊組成。
(2)4．設有一組權為2, 3, 5, 7, 17, 31，試畫出相應的最優二叉樹，計算該最優二叉樹的權．
解：四、證明題
1．設g是乙個n階無向簡單圖，n是大於等於3的奇數．證明圖g與它的補圖中的奇數度頂點個數相等．
證明：∵是大於等於3的奇數，∴在無向完全圖中每個結點的度數為是偶數，
如果在圖g中結點的度數為是奇數，則在它的補圖中結點的度數為也是奇數，
如果在圖g中結點的度數為是偶數，則在它的補圖中結點的度數為也是偶數，
故圖g與它的補圖中的奇數度頂點個數相等．
2．設連通圖g有k個奇數度的結點，證明在圖g中至少要新增條邊才能使其成為尤拉圖．
證明：∵連通圖g有k個奇數度的結點，∴根據握手定理，必為偶數。
∵連通圖g是尤拉圖的充分必要條件是所有結點的度數都為偶數，∴要使圖g成為尤拉圖必須使圖g中k個奇數度的結點全部變成偶數度的結點。
∵在圖g中新增1條邊連線2個奇數度的結點，則可以使圖g中奇數度的結點減少2個，∴要使圖g中k個奇數度的結點全部變成偶數度的結點至少要新增條邊。
離散數學形成性考核作業2答案
1.若集合a 則下列表述正確的是 a.a b.a c.a d.a 2.設a b是兩個任意集合，側a b a.a b b.ab c.ab d.b 3.集合a 上的關係r r是a上的二元關係，其關係矩陣為 則r的關係表示式是 a.b.c.d.5.設集合a 上的二元關係r s 則s是r的 閉包 a.自反 ...
離散數學作業
離散數學集合論部分形成性考核書面作業 本課程形成性考核書面作業共3次，內容主要分別是集合論部分 圖論部分 數理邏輯部分的綜合練習，基本上是按照考試的題型 除單項選擇題外 安排練習題目，目的是通過綜合性書面作業，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點複習，爭取盡快掌握 本次形考書面作業是第...
離散數學 大作業 與答案
1 請給出乙個集合a，並給出a上既具有對稱性，又具有反對稱性的關係。10分 解 a r 2 請給出乙個集合a，並給出a上既不具有對稱性，又不具有反對稱性的關係。10分 3 設a 請給出a上的所有關係。10分 答 4 設a 問a上一共有多少個不同的關係。10分 5 證明 命題公式g是恆真的當且僅當在等...