電大離散數(shù)學(xué)期末復(fù)習(xí)要點與重點考試資料小抄-文庫吧
2025-05-17 03:33 本頁面
【正文】 理． 圖是一個有序?qū)?V， E， V 是結(jié)點集， E 是聯(lián)結(jié)結(jié)點的邊的集合． 掌握無向邊與無向圖，有向邊與有向圖，混合圖，零圖，平凡圖、自回路 (環(huán) )，無向平行邊，有向平行邊等概念． 3 簡單圖，不含 平行邊和環(huán) (自回路 )的圖、 在無向圖中，與結(jié)點 v(?V)關(guān)聯(lián)的邊數(shù)為結(jié)點 度數(shù) deg (v)；在有向圖中，以 v(?V)為終點的邊的條數(shù)為入度 deg－ (v)， 以 v(?V)為起點的邊的條數(shù)為出度 deg ＋ (v)， deg(v)=deg+(v) +deg－ (v)． 無向完全圖 Kn 以其邊數(shù) )1(21 ?? nnE ；有向完全圖以其邊數(shù) )1( ?? nnE ． 了解子圖、真子圖、補圖和生成子圖的概念 ． 生成子圖 —— 設(shè)圖 G＝ V, E， 若 E??E， 則圖 V, E?是 V, E的生成子圖． 知道圖的同構(gòu)概念，更應(yīng)知道圖同構(gòu)的必要條件，用其判斷 圖不同構(gòu) . 重要定理 ： (1) 握手定理 設(shè) G=V， E，有 ?? ?Vv Ev 2)deg(； (2) 在 有向 圖 D＝ V, E中， ??? ?? ? ? VvVv vv )(de g)(de g； (3) 奇數(shù)度結(jié)點的個數(shù)為偶數(shù)個． 2． 了解通路與回路概念：通路 (簡單通路、 基本 通路和復(fù)雜通路 )，回路 (簡單回路、 基本 回 路和復(fù)雜回路 )． 會求通路和回路的長度． 基本 通路 (回路 )必是簡單通路 (回路 )． 了解無向圖的連通性，會求無向圖的連通分支．了解點割集、邊割集、割點、割邊等概念 ． 了解有向圖的強連通強性；會判別其類型． 設(shè)圖 G＝ V， E，結(jié)點與邊的交替序列為 通路 ． 通路中邊的數(shù)目就是通路的 長度 ． 起點和終點重合的通路為回路 ． 邊不重復(fù)的通路 (回路 )是簡單通路 (回路 )；結(jié)點不重復(fù)的通路 (回路 )是 基本 通路 (回路 ). 無向圖 G中，結(jié)點 u, v 存在通路 ， u, v是連通的， G中任意結(jié)點 u, v 連通， G 是連通圖 ． P(G)表示圖 G連通分支的個數(shù)． 在無向圖中，結(jié)點集 V??V，使得 P(G－ V?)P(G)，而任意 V??V?,有 P（ G－ V?）＝ P(G)， V?為點割集 . 若 V?是單元集，該結(jié)點 v 叫割點；邊集 E??E，使得 P(G－ V?)P(G)，而任意 E??E?，有 P（ G－ E?）＝ P(G)， E?為邊割集 ． 若E?是單元集，該邊 e 叫割邊 (橋 )． 要 知 道： 強連通 ???必是 單側(cè)連通 ???必是 弱連通 ，反之不成立 ． 3． 了解鄰接矩陣和可達矩陣的概念，掌握 其 構(gòu)造方法及其應(yīng)用 ． 重點 ：圖 的概念，握手定理，通路、回路以及圖的矩陣表示． 第 4 章 幾種特殊圖 復(fù)習(xí)要點 1． 理解歐拉通路 (回路 )、歐拉圖的概念，掌握歐拉圖的判別方法． 通過 連通 圖 G 的每條邊一次且僅一次的通路 (回路 )是歐拉通路 (回路 )． 存在歐拉回路的圖是歐拉圖 . 歐拉回路要求邊不能重復(fù)，結(jié)點可以重復(fù) ． 筆不離開紙，不重復(fù)地走完所有的邊，走過所有結(jié)點，就是所謂的一筆畫 ． 歐拉圖或通路的判定定理 (1) 無向連通圖 G 是歐拉圖 ?G 不含奇數(shù)度結(jié)點 (即 G 的所有結(jié)點為偶數(shù)度 )； (2) 非平凡連通圖 G 含有歐拉通路 ?G 最多有兩個奇數(shù)度的 結(jié)點； (3) 連通有向圖 D 含有有向歐拉回路 ?D 中每個結(jié)點的入度＝出度． 連通有向圖 D 含有有向歐拉通路 ?D 中除兩個結(jié)點外，其余每個結(jié)點的入度＝出度，且此兩點滿足 deg－ (u)－deg＋ (v)＝ ?1． 2． 理解 漢 密 爾 頓通路 (回路 )、 漢密爾頓 圖的概念，會做簡單判斷． 通過 連通 圖 G 的每個結(jié)點一次，且僅一次的通路 (回路 )，是 漢密爾頓 通路 (回路 )． 存在 漢密爾頓 回路的圖是 漢密爾頓 圖 . 漢密爾頓 圖的充分條件和必要條件 (1) 在無向簡單圖 G=V， E中， ?V??3， 任意不同結(jié)點 VvuGvu ??? )d e g ()d e g (, ， 則 G 是 漢密爾頓 圖 ． (充分條件 ) 4 (2) 有向完全圖 D＝ V， E, 若 3?V ，則圖 D 是 漢密爾頓 圖 . (充分條件 ) (3) 設(shè)無向圖 G=V， E，任意 V1?V，則 W(G－ V1)??V1?(必要條件 ) 若此條件不滿足，即 存在 V1?V，使得 P(G－ V!)?V1?,則 G 一定不是 漢密爾頓 圖 (非 漢密爾頓 圖的充分條件 )． 3． 了解平面圖概念，平面圖、面、邊界、面的次數(shù)和非平面圖 ． 掌握歐拉公式的應(yīng)用 ． 平面圖 是指 一個圖能畫在平面上，除結(jié)點之外，再沒有邊與邊相交． 面、邊界和面的次數(shù) )deg(r 等概念． 重要結(jié)論 ： (1)平面圖 ereEvVEVG ri i 2)de g (, 1 ?????? ??則． (2)歐拉公式：平面圖 , eEvVEVG ????? 面數(shù)為 r，則 2??? rev (結(jié)點數(shù)與面數(shù)之和＝邊數(shù)＋ 2) (3)平面圖 633, ???????? veveEvVEVG ，則若． 會用定義判定一個 圖 是不是平面圖． 4． 理解平面圖與對偶圖的關(guān)系、對偶圖在圖著色中的作用 ， 掌握 求 對偶圖的 方法 ． 給定平面圖 G＝〈 V， E〉 ，它有面 F1， F2， … ， Fn，若有圖 G*＝〈 V*， E*〉滿足下述條件： ⑴ 對于圖 G的任一個面 Fi，內(nèi)部有且僅有一個結(jié)點 vi*∈ V*； ⑵ 對于圖 G的面 Fi， Fj的公共邊 ek，存在且僅存在一條邊 ek*∈ E*，使 ek*＝ (vi*， vj*)，且 ek*和 ek相交 ； ⑶ 當(dāng)且僅當(dāng) ek只是一個面 Fi的邊界時， vi*存在一個環(huán) ek*和 ek相交 ； 則圖 G*是圖 G的 對偶圖 ． 若 G*是 G的對偶圖，則 G也是 G*的對偶圖．一個連通平面圖的對偶圖也必是平面圖． 5． 掌握圖論中常用的證明方法 ． 重點 ：歐拉圖和哈密頓圖、平面 圖的基本概念及判別 ． 第 5 章 樹及其應(yīng)用 復(fù)習(xí)要點 1． 了解樹、樹葉、分支點、平凡樹、生成樹和最小生成樹等概念 ，掌握 求最小生成樹 的方法 ． 連通無回路的無向圖是樹 ． 樹的判別 可以用 圖 T 是樹的充要條件 (等價定義 )． 注意： (1) 樹 T 是連通圖； (2)樹 T 滿足 m＝ n－ 1（即邊數(shù) =頂點數(shù) 1） ． 圖 G 的生成子圖是樹，該樹就是生成樹． 每邊指定一正數(shù)，稱為權(quán)，每邊帶權(quán)的圖稱為帶權(quán)圖 ． G的生成樹 T 的所有邊的權(quán)之和是生成樹 T 的權(quán)，記作W(T)． 最小生成樹是帶權(quán)最小的生成樹 ． 2． 了解有向樹、根樹、有序樹、二 叉 樹、二 叉 完全樹、正則二 叉 樹和最優(yōu)二 叉 樹等概念． 了解 帶權(quán)二叉樹、最優(yōu)二叉樹的概念， 掌握 用哈夫曼算法求最優(yōu)二叉樹 的方法 ． 有向圖刪去邊
試題試卷相關(guān)推薦
鄂ICP備17016276號-1