離散數(shù)學(xué)必備知識(shí)點(diǎn)總結(jié)-資料下載頁(yè)
2025-04-04 04:48本頁(yè)面
【正文】 ： ①連通圖；②有0個(gè)或2個(gè)奇數(shù)度節(jié)點(diǎn)； （2）無(wú)向圖中存在歐拉回路的充要條件： ①連通圖；②所有節(jié)點(diǎn)度數(shù)均為偶數(shù)； （3）連通有向圖含有單向歐拉路的充要條件：①除兩個(gè)節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)入度=出度；②這兩個(gè)節(jié)點(diǎn)中，一個(gè)節(jié)點(diǎn)的入度比出度多1，另一個(gè)節(jié)點(diǎn)的入；度比出度少1；（4） 連通有向圖含有單向歐拉回路的充要條件： 圖中每個(gè)節(jié)點(diǎn)的出度=入度；27. 哈密頓路：經(jīng)過(guò)圖中每個(gè)節(jié)點(diǎn)一次且僅一次的通路； 哈密頓回路：經(jīng)過(guò)圖中每個(gè)節(jié)點(diǎn)一次且僅一次的回路； 哈密頓圖：具有哈密頓回路的圖；28. 判定哈密頓圖（沒(méi)有充要條件） 必要條件： 任意去掉圖中n個(gè)節(jié)點(diǎn)及關(guān)聯(lián)的邊后，得到的分圖數(shù)目小于等于n； 充分條件： 圖中每一對(duì)節(jié)點(diǎn)的度數(shù)之和都大于等于圖中的總節(jié)點(diǎn)數(shù)；29. 哈密頓圖的應(yīng)用：安排圓桌會(huì)議； 方法：將每一個(gè)人看做一個(gè)節(jié)點(diǎn)，將每個(gè)人與和他能交流的人連接，找到一條經(jīng)過(guò)每個(gè)節(jié)點(diǎn)一次且僅一次的回路(哈密頓圖)，即可；30. 平面圖：將圖形的交叉邊進(jìn)行改造后，不會(huì)出現(xiàn)邊的交叉，則是平面圖；31. 面次：面的邊界回路長(zhǎng)度稱為該面的次；32. 一個(gè)有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍；33. 歐拉定理：假設(shè)一個(gè)連通平面圖有v個(gè)節(jié)點(diǎn)，e條邊，r個(gè)面，則 ve+r=2；34. 判斷是平面圖的必要條件：(若不滿足，就一定不是平面圖) 設(shè)圖G是v個(gè)節(jié)點(diǎn)，e條邊的簡(jiǎn)單連通平面圖，若v=3，則e=3v6；35. 同胚：對(duì)于兩個(gè)圖G1,G2，如果它們是同構(gòu)的，或者通過(guò)反復(fù)插入和除去2度節(jié)點(diǎn)可以變成同構(gòu)的圖，則稱G1，G2是同胚的；36. 判斷G是平面圖的充要條件： ；37. 二部圖：①無(wú)向圖的節(jié)點(diǎn)集合可以劃分為兩個(gè)子集V1，V2； ②圖中每條邊的一個(gè)端點(diǎn)在V1，另一個(gè)則在V2中； 完全二部圖：二部圖中V1的每個(gè)節(jié)點(diǎn)都與V2的每個(gè)節(jié)點(diǎn)鄰接； 判定無(wú)向圖G為二部圖的充要條件： 圖中每條回路經(jīng)過(guò)邊的條數(shù)均為偶數(shù)；38. 樹：具有n個(gè)頂點(diǎn)n1條邊的無(wú)回路連通無(wú)向圖；39. 節(jié)點(diǎn)的層數(shù)：從樹根到該節(jié)點(diǎn)經(jīng)過(guò)的邊的條數(shù)；40. 樹高：層數(shù)最大的頂點(diǎn)的層數(shù)；41. 二叉樹： ①二叉樹額基本結(jié)構(gòu)狀態(tài)有5種； ②二叉樹內(nèi)節(jié)點(diǎn)的度數(shù)只考慮出度，不考慮入度； ③二叉樹內(nèi)樹葉的節(jié)點(diǎn)度數(shù)為0，而樹內(nèi)樹葉節(jié)點(diǎn)度數(shù)為1； ④二叉樹內(nèi)節(jié)點(diǎn)的度數(shù)=邊的總數(shù)(只算出度)；握手定理“節(jié)點(diǎn)數(shù)=邊的兩倍”是在同時(shí)計(jì)算入度和出度的時(shí)成立； ⑤二叉樹內(nèi)節(jié)點(diǎn)的總數(shù)=邊的總數(shù)+1； ⑥位于二叉樹第k層上的節(jié)點(diǎn)，最多有個(gè)(k=1)； ⑦深度為k的二叉樹的節(jié)點(diǎn)總數(shù)最多為1個(gè)，最少k個(gè)(k=1)； ⑧如果有個(gè)葉子，個(gè)2度節(jié)點(diǎn)，則=+1； ： 先根順序（DLR）； 中根順序（LDR）； 后根順序（LRD）； 43. 哈夫曼樹：用哈夫曼算法構(gòu)造的最優(yōu)二叉樹；44. 最優(yōu)二叉樹的構(gòu)造方法： ①將給定的權(quán)值按從小到大排序； ②取兩個(gè)最小值分支點(diǎn)的左右子樹(左小右大)，去掉已選的這兩個(gè)權(quán)值，并將這兩個(gè)最小值加起來(lái)作為下一輪排序的權(quán)值； ③重復(fù)②，直達(dá)所有權(quán)值構(gòu)造完畢；45. 哈夫曼編碼：在最優(yōu)二叉樹上，按照左0右1的規(guī)則，用0和1代替所有邊的權(quán)值； 每個(gè)節(jié)點(diǎn)的編碼：從根到該節(jié)點(diǎn)經(jīng)過(guò)的0和1組成的一排編碼；
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1