離散數(shù)學(xué)必備知識點總結(jié).doc

《離散數(shù)學(xué)必備知識點總結(jié).doc》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)必備知識點總結(jié).doc（17頁珍藏版）》請在裝配圖網(wǎng)上搜索。

總結(jié) 離散數(shù)學(xué)知識點 第2章 命題邏輯 1. →，前鍵為真，后鍵為假才為假；<—>，相同為真，不同為假； 2. 主析取范式：極小項(m)之和；主合取范式：極大項(M)之積； 3. 求極小項時，命題變元的肯定為1，否定為0，求極大項時相反； 4. 求極大極小項時，每個變元或變元的否定只能出現(xiàn)一次，求極小項時變元不夠合取真，求極大項時變元不夠析取假； 5. 求范式時，為保證編碼不錯，命題變元最好按P,Q,R的順序依次寫； 6. 真值表中值為1的項為極小項，值為0的項為極大項； 7. n個變元共有個極小項或極大項，這為(0~-1)剛好為化簡完后的主析取加主合??； 8. 永真式?jīng)]有主合取范式，永假式?jīng)]有主析取范式； 9. 推證蘊含式的方法(=>)：真值表法；分析法(假定前鍵為真推出后鍵為真，假定前鍵為假推出后鍵也為假) 10.命題邏輯的推理演算方法：P規(guī)則，T規(guī)則 ①真值表法；②直接證法；③歸謬法；④附加前提法； 第3章 謂詞邏輯 1. 一元謂詞：謂詞只有一個個體，一元謂詞描述命題的性質(zhì)； 多元謂詞：謂詞有n個個體，多元謂詞描述個體之間的關(guān)系； 2. 全稱量詞用蘊含→，存在量詞用合取^; 3. 既有存在又有全稱量詞時，先消存在量詞，再消全稱量詞； 第4章 集合 1. N，表示自然數(shù)集，1,2,3……，不包括0； 2. 基：集合A中不同元素的個數(shù)，|A|； 3. 冪集：給定集合A，以集合A的所有子集為元素組成的集合，P(A)； 4. 若集合A有n個元素，冪集P(A)有個元素，|P(A)|==； 5. 集合的分劃：(等價關(guān)系) ①每一個分劃都是由集合A的幾個子集構(gòu)成的集合； ②這幾個子集相交為空，相并為全(A)； 6. 集合的分劃與覆蓋的比較： 分劃：每個元素均應(yīng)出現(xiàn)且僅出現(xiàn)一次在子集中； 覆蓋：只要求每個元素都出現(xiàn)，沒有要求只出現(xiàn)一次； 第5章 關(guān)系 1. 若集合A有m個元素，集合B有n個元素，則笛卡爾A×B的基數(shù)為mn，A到B上可以定義種不同的關(guān)系； 2. 若集合A有n個元素，則|A×A|=，A上有個不同的關(guān)系； 3. 全關(guān)系的性質(zhì)：自反性，對稱性，傳遞性； 空關(guān)系的性質(zhì)：反自反性，反對稱性，傳遞性； 全封閉環(huán)的性質(zhì)：自反性，對稱性，反對稱性，傳遞性； 4. 前域(domR)：所有元素x組成的集合； 后域(ranR)：所有元素y組成的集合； 5. 自反閉包：r(R)=RU; 對稱閉包：s(R)=RU; 傳遞閉包：t(R)=RUUU…… 6. 等價關(guān)系：集合A上的二元關(guān)系R滿足自反性，對稱性和傳遞性，則R稱為等價關(guān)系； 7. 偏序關(guān)系：集合A上的關(guān)系R滿足自反性，反對稱性和傳遞性，則稱R是A上的一個偏序關(guān)系； 8. covA={|x,y屬于A，y蓋住x}； 9. 極小元：集合A中沒有比它更小的元素(若存在可能不唯一)； 極大元：集合A中沒有比它更大的元素(若存在可能不唯一)； 最小元：比集合A中任何其他元素都小(若存在就一定唯一)； 最大元：比集合A中任何其他元素都大(若存在就一定唯一)； 10. 前提：B是A的子集 上界：A中的某個元素比B中任意元素都大，稱這個元素是B的上界(若存在，可能不唯一)； 下界：A中的某個元素比B中任意元素都小，稱這個元素是B的下界(若存在，可能不唯一)； 上確界：最小的上界(若存在就一定唯一)； 下確界：最大的下界(若存在就一定唯一)； 第6章 函數(shù) 1. 若|X|=m,|Y|=n,則從X到Y(jié)有種不同的關(guān)系，有種不同的函數(shù)； 2. 在一個有n個元素的集合上，可以有種不同的關(guān)系，有種不同的函數(shù)，有n!種不同的雙射； 3. 若|X|=m,|Y|=n，且m<=n，則從X到Y(jié)有種不同的單射； 4. 單射：f:X-Y，對任意,屬于X,且≠，若f()≠f()； 滿射：f:X-Y，對值域中任意一個元素y在前域中都有一個或多個元素對應(yīng)； 雙射：f:X-Y，若f既是單射又是滿射，則f是雙射； 5. 復(fù)合函數(shù)：fog=g(f(x)); 6. 設(shè)函數(shù)f:A-B，g:B-C，那么 ①如果f,g都是單射，則fog也是單射； ②如果f,g都是滿射，則fog也是滿射； ③如果f,g都是雙射，則fog也是雙射； ④如果fog是雙射，則f是單射，g是滿射； 第7章 代數(shù)系統(tǒng) 1. 二元運算：集合A上的二元運算就是到A的映射； 2. 集合A上可定義的二元運算個數(shù)就是從A×A到A上的映射的個數(shù)，即從從A×A到A上函數(shù)的個數(shù)，若|A|=2,則集合A上的二元運算的個數(shù)為==16種； 3. 判斷二元運算的性質(zhì)方法： ①封閉性：運算表內(nèi)只有所給元素； ②交換律：主對角線兩邊元素對稱相等； ③冪等律：主對角線上每個元素與所在行列表頭元素相同； ④有幺元：元素所對應(yīng)的行和列的元素依次與運算表的行和列相同； ⑤有零元：元素所對應(yīng)的行和列的元素都與該元素相同； 4. 同態(tài)映射：,,滿足f(a*b)=f(a)^f(b),則f為由到的同態(tài)映射；若f是雙射，則稱為同構(gòu)； 第8章 群 1. 廣群的性質(zhì)：封閉性； 半群的性質(zhì)：封閉性，結(jié)合律； 含幺半群(獨異點)：封閉性，結(jié)合律，有幺元； 群的性質(zhì)：封閉性，結(jié)合律，有幺元，有逆元； 2. 群沒有零元； 3. 阿貝爾群(交換群)：封閉性，結(jié)合律，有幺元，有逆元，交換律； 4. 循環(huán)群中幺元不能是生成元； 5. 任何一個循環(huán)群必定是阿貝爾群； 第10章 格與布爾代數(shù) 1. 格：偏序集合A中任意兩個元素都有上、下確界； 2. 格的基本性質(zhì)： 1) 自反性 a≤a 對偶: a≥a 2) 反對稱性 a≤b ^ b≥a => a=b 對偶:a≥b ^ b≤a => a=b 3) 傳遞性 a≤b ^ b≤c => a≤c 對偶:a≥b ^ b≥c => a≥c 4) 最大下界描述之一 a^b≤a 對偶 avb≥a A^b≤b 對偶 avb≥b 5）最大下界描述之二 c≤a,c≤b => c≤a^b 對偶c≥a,c≥b =>Tc≥avb 6) 結(jié)合律 a^(b^c)=(a^b)^c 對偶 av(bvc)=(avb)vc 7)?? 等冪律 a^a=a 對偶 ava=a 8) 吸收律 a^(avb)=a 對偶 av(a^b)=a 9)??? a≤b <=> a^b=a avb=b 10) a≤c,b≤d => a^b≤c^d avb≤cvd 11) 保序性 b≤c => a^b≤a^c avb≤avc 12） 分配不等式 av(b^c)≤(avb)^(avc) 對偶 a^(bvc)≥(a^b)v(a^c) 13）模不等式 a≤c <=>? av(b^c)≤(avb)^c 3. 分配格：滿足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc)； 4. 分配格的充要條件：該格沒有任何子格與鉆石格或五環(huán)格同構(gòu)； 5.鏈格一定是分配格，分配格必定是模格； 6. 全上界：集合A中的某個元素a大于等于該集合中的任何元素，則稱a為格的全上界，記為1；(若存在則唯一) 全下界：集合A中的某個元素b小于等于該集合中的任何元素，則稱b為格的全下界，記為0；(若存在則唯一) 7. 有界格：有全上界和全下界的格稱為有界格，即有0和1的格； 8. 補元：在有界格內(nèi)，如果a^b=0,avb=1，則a和b互為補元； 9. 有補格：在有界格內(nèi)，每個元素都至少有一個補元； 10. 有補分配格(布爾格)：既是有補格，又是分配格； 11. 布爾代數(shù)：一個有補分配格稱為布爾代數(shù)； 第11章 圖論 1. 鄰接：兩點之間有邊連接，則點與點鄰接； 2. 關(guān)聯(lián)：兩點之間有邊連接，則這兩點與邊關(guān)聯(lián)； 3. 平凡圖：只有一個孤立點構(gòu)成的圖； 4. 簡單圖：不含平行邊和環(huán)的圖； 5. 無向完全圖：n個節(jié)點任意兩個節(jié)點之間都有邊相連的簡單無向圖； 有向完全圖:n個節(jié)點任意兩個節(jié)點之間都有邊相連的簡單有向圖； 6. 無向完全圖有n(n-1)/2條邊，有向完全圖有n(n-1)條邊； 7. r-正則圖：每個節(jié)點度數(shù)均為r的圖； 8. 握手定理：節(jié)點度數(shù)的總和等于邊的兩倍； 9. 任何圖中，度數(shù)為奇數(shù)的節(jié)點個數(shù)必定是偶數(shù)個； 10. 任何有向圖中，所有節(jié)點入度之和等于所有節(jié)點的出度之和； 11. 每個節(jié)點的度數(shù)至少為2的圖必定包含一條回路； 12. 可達：對于圖中的兩個節(jié)點,，若存在連接到的路，則稱與相互可達，也稱與是連通的；在有向圖中，若存在到的路，則稱到可達； 13. 強連通：有向圖章任意兩節(jié)點相互可達； 單向連通：圖中兩節(jié)點至少有一個方向可達； 弱連通：無向圖的連通；(弱連通必定是單向連通) 14. 點割集：刪去圖中的某些點后所得的子圖不連通了，如果刪去其他幾個點后子圖之間仍是連通的，則這些點組成的集合稱為點割集； 割點：如果一個點構(gòu)成點割集，即刪去圖中的一個點后所得子圖是不連通的，則該點稱為割點； 15. 關(guān)聯(lián)矩陣：M(G)，是與關(guān)聯(lián)的次數(shù)，節(jié)點為行，邊為列； 無向圖：點與邊無關(guān)系關(guān)聯(lián)數(shù)為0，有關(guān)系為1，有環(huán)為2； 有向圖：點與邊無關(guān)系關(guān)聯(lián)數(shù)為0，有關(guān)系起點為1終點為-1， 關(guān)聯(lián)矩陣的特點： 無向圖： ①行：每個節(jié)點關(guān)聯(lián)的邊，即節(jié)點的度； ②列：每條邊關(guān)聯(lián)的節(jié)點； 有向圖： ③所有的入度(1)=所有的出度(0); 16.鄰接矩陣：A(G)，是鄰接到的邊的數(shù)目，點為行，點為列； 17.可達矩陣：P(G)，至少存在一條回路的矩陣，點為行，點為列； P(G)=A(G)+(G)+(G)+(G) 可達矩陣的特點：表明圖中任意兩節(jié)點之間是否至少存在一條路，以及在任何節(jié)點上是否存在回路； A(G)中所有數(shù)的和：表示圖中路徑長度為1的通路條數(shù)； (G)中所有數(shù)的和：表示圖中路徑長度為2的通路條數(shù)； (G)中所有數(shù)的和：表示圖中路徑長度為3的通路條數(shù)； (G)中所有數(shù)的和：表示圖中路徑長度為4的通路條數(shù)； P(G)中主對角線所有數(shù)的和：表示圖中的回路條數(shù)； 18. 布爾矩陣：B(G)，到有路為1，無路則為0，點為行，點為列； 19. 代價矩陣：鄰接矩陣元素為1的用權(quán)值表示，為0的用無窮大表示，節(jié)點自身到自身的權(quán)值為0； 20. 生成樹：只訪問每個節(jié)點一次，經(jīng)過的節(jié)點和邊構(gòu)成的子圖； 21. 構(gòu)造生成樹的兩種方法：深度優(yōu)先；廣度優(yōu)先； 深度優(yōu)先： ①選定起始點； ②選擇一個與鄰接且未被訪問過的節(jié)點； ③從出發(fā)按鄰接方向繼續(xù)訪問，當(dāng)遇到一個節(jié)點所有鄰接點均已被訪問時，回到該節(jié)點的前一個點，再尋求未被訪問過的鄰接點，直到所有節(jié)點都被訪問過一次； 廣度優(yōu)先： ①選定起始點； ②訪問與鄰接的所有節(jié)點,,……,,這些作為第一層節(jié)點； ③在第一層節(jié)點中選定一個節(jié)點為起點； ④重復(fù)②③，直到所有節(jié)點都被訪問過一次； 22. 最小生成樹：具有最小權(quán)值(T)的生成樹； 23. 構(gòu)造最小生成樹的三種方法： 克魯斯卡爾方法；管梅谷算法；普利姆算法； （1）克魯斯卡爾方法 ①將所有權(quán)值按從小到大排列； ②先畫權(quán)值最小的邊，然后去掉其邊值；重新按小到大排序； ③再畫權(quán)值最小的邊，若最小的邊有幾條相同的，選擇時要滿足不能出現(xiàn)回路，然后去掉其邊值；重新按小到大排序； ④重復(fù)③，直到所有節(jié)點都被訪問過一次； （2）管梅谷算法(破圈法) ①在圖中取一回路，去掉回路中最大權(quán)值的邊得一子圖； ②在子圖中再取一回路，去掉回路中最大權(quán)值的邊再得一子圖； ③重復(fù)②，直到所有節(jié)點都被訪問過一次； （3）普利姆算法 ①在圖中任取一點為起點，連接邊值最小的鄰接點； ②以鄰接點為起點，找到鄰接的最小邊值，如果最小邊值比鄰接的所有邊值都小(除已連接的邊值)，直接連接，否則退回，連接現(xiàn)在的最小邊值(除已連接的邊值)； ③重復(fù)操作，直到所有節(jié)點都被訪問過一次； 24. 關(guān)鍵路徑 例2 求PERT圖中各頂點的最早完成時間, 最晚完成時間, 緩沖時間及關(guān)鍵路徑. 解：最早完成時間 TE(v1)=0 TE(v2)=max{0+1}=1 TE(v3)=max{0+2,1+0}=2 TE(v4)=max{0+3,2+2}=4 TE(v5)=max{1+3,4+4}=8 TE(v6)=max{2+4,8+1}=9 TE(v7)=max{1+4,2+4}=6 TE(v8)=max{9+1,6+6}=12 最晚完成時間 TL(v8)=12 TL(v7)=min{12-6}=6 TL(v6)=min{12-1}=11 TL(v5)=min{11-1}=10 TL(v4)=min{10-4}=6 TL(v3)=min{6-2,11-4,6-4}=2 TL(v2)=min{2-0,10-3,6-4}=2 TL(v1)=min{2-1,2-2,6-3}=0 緩沖時間 TS(v1)=0-0=0 TS(v2)=2-1=1 TS(v3)=2-2=0 TS(v4)=6-4=2 TS(v5=10-8=2 TS(v6)=11-9=2 TS(v7)=6-6=0 TS(v8)=12-12=0 關(guān)鍵路徑: v1-v3-v7-v8 25. 歐拉路：經(jīng)過圖中每條邊一次且僅一次的通路； 歐拉回路：經(jīng)過圖中每條邊一次且僅一次的回路； 歐拉圖：具有歐拉回路的圖； 單向歐拉路：經(jīng)過有向圖中每條邊一次且僅一次的單向路； 歐拉單向回路：經(jīng)過有向圖中每條邊一次且僅一次的單向回路； 26. （1）無向圖中存在歐拉路的充要條件： ①連通圖；②有0個或2個奇數(shù)度節(jié)點； （2）無向圖中存在歐拉回路的充要條件： ①連通圖；②所有節(jié)點度數(shù)均為偶數(shù)； （3）連通有向圖含有單向歐拉路的充要條件： ①除兩個節(jié)點外，每個節(jié)點入度=出度； ②這兩個節(jié)點中，一個節(jié)點的入度比出度多1，另一個節(jié)點的入；度比出度少1； （4） 連通有向圖含有單向歐拉回路的充要條件： 圖中每個節(jié)點的出度=入度； 27. 哈密頓路：經(jīng)過圖中每個節(jié)點一次且僅一次的通路； 哈密頓回路：經(jīng)過圖中每個節(jié)點一次且僅一次的回路； 哈密頓圖：具有哈密頓回路的圖； 28. 判定哈密頓圖（沒有充要條件） 必要條件： 任意去掉圖中n個節(jié)點及關(guān)聯(lián)的邊后，得到的分圖數(shù)目小于等于n； 充分條件： 圖中每一對節(jié)點的度數(shù)之和都大于等于圖中的總節(jié)點數(shù)； 29. 哈密頓圖的應(yīng)用：安排圓桌會議； 方法：將每一個人看做一個節(jié)點，將每個人與和他能交流的人連接，找到一條經(jīng)過每個節(jié)點一次且僅一次的回路(哈密頓圖)，即可； 30. 平面圖：將圖形的交叉邊進行改造后，不會出現(xiàn)邊的交叉，則是平面圖； 31. 面次：面的邊界回路長度稱為該面的次； 32. 一個有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍； 33. 歐拉定理：假設(shè)一個連通平面圖有v個節(jié)點，e條邊，r個面，則 v-e+r=2； 34. 判斷是平面圖的必要條件：(若不滿足，就一定不是平面圖) 設(shè)圖G是v個節(jié)點，e條邊的簡單連通平面圖，若v>=3，則e<=3v-6； 35. 同胚：對于兩個圖G1,G2，如果它們是同構(gòu)的，或者通過反復(fù)插入和除去2度節(jié)點可以變成同構(gòu)的圖，則稱G1，G2是同胚的； 36. 判斷G是平面圖的充要條件： 圖G不含同胚于K3.3或K5的子圖； 37. 二部圖：①無向圖的節(jié)點集合可以劃分為兩個子集V1，V2； ②圖中每條邊的一個端點在V1，另一個則在V2中； 完全二部圖：二部圖中V1的每個節(jié)點都與V2的每個節(jié)點鄰接； 判定無向圖G為二部圖的充要條件： 圖中每條回路經(jīng)過邊的條數(shù)均為偶數(shù)； 38. 樹：具有n個頂點n-1條邊的無回路連通無向圖； 39. 節(jié)點的層數(shù)：從樹根到該節(jié)點經(jīng)過的邊的條數(shù)； 40. 樹高：層數(shù)最大的頂點的層數(shù)； 41. 二叉樹： ①二叉樹額基本結(jié)構(gòu)狀態(tài)有5種； ②二叉樹內(nèi)節(jié)點的度數(shù)只考慮出度，不考慮入度； ③二叉樹內(nèi)樹葉的節(jié)點度數(shù)為0，而樹內(nèi)樹葉節(jié)點度數(shù)為1； ④二叉樹內(nèi)節(jié)點的度數(shù)=邊的總數(shù)(只算出度)；握手定理“節(jié)點數(shù)=邊的兩倍”是在同時計算入度和出度的時成立； ⑤二叉樹內(nèi)節(jié)點的總數(shù)=邊的總數(shù)+1； ⑥位于二叉樹第k層上的節(jié)點，最多有個(k>=1)； ⑦深度為k的二叉樹的節(jié)點總數(shù)最多為-1個，最少k個(k>=1)； ⑧如果有個葉子，個2度節(jié)點，則=+1； 42.二叉樹的節(jié)點遍歷方法： 先根順序（DLR）； 中根順序（LDR）； 后根順序（LRD）； 43. 哈夫曼樹：用哈夫曼算法構(gòu)造的最優(yōu)二叉樹； 44. 最優(yōu)二叉樹的構(gòu)造方法： ①將給定的權(quán)值按從小到大排序； ②取兩個最小值分支點的左右子樹(左小右大)，去掉已選的這兩個權(quán)值，并將這兩個最小值加起來作為下一輪排序的權(quán)值； ③重復(fù)②，直達所有權(quán)值構(gòu)造完畢； 45. 哈夫曼編碼：在最優(yōu)二叉樹上，按照左0右1的規(guī)則，用0和1代替所有邊的權(quán)值； 每個節(jié)點的編碼：從根到該節(jié)點經(jīng)過的0和1組成的一排編碼；