幾種特殊的圖

關(guān)于幾種特殊的圖第1頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖教學(xué)要求理解歐拉通路(回路)、歐拉圖的概念，掌握歐拉圖的判別方法。

理解哈密頓通路(回路)、哈密頓圖的概念

了解平面圖的概念：平面圖、面、邊界、面的次數(shù)和非平面圖。掌握歐拉公式的應(yīng)用。

了解無向樹、樹葉、分支點(diǎn)、平凡樹、生成樹和最小生成樹等概念。會(huì)求最小生成樹。

了解有向樹、根樹、有序樹、最優(yōu)二元（叉）樹等概念，會(huì)用哈夫曼算法求最優(yōu)二叉樹。

第2頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖本章重點(diǎn)：歐拉圖和哈密頓圖平面圖樹的基本概念。

第3頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖歐拉圖包含圖G的每一條邊，且每條邊僅出現(xiàn)一次的通路，就是歐拉通路。包含圖G的每一條邊，且每條邊僅出現(xiàn)一次的回路，就是歐拉回路。存在歐拉回路的圖，就是歐拉圖。

第4頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖歐拉圖歐拉圖的判定：(1)無向連通圖G是歐拉圖

G不含奇數(shù)度的結(jié)點(diǎn)(即G

的所有結(jié)點(diǎn)的度均為偶數(shù)(0視為偶數(shù)))；(定理1)(2)非0平凡圖G

是歐拉圖

G

最多有兩個(gè)奇數(shù)度的結(jié)點(diǎn)；(定理1的推論)(3)有向圖D是歐拉圖

D是連通的，且D的所有結(jié)點(diǎn)的入度等于出度?；虺齼蓚€(gè)結(jié)點(diǎn)外，均出度等于入度，且這兩點(diǎn)deg－(v)－deg＋(v)＝1。

(定理2)第5頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖哈密頓圖通過圖G的每個(gè)結(jié)點(diǎn)一次，且僅一次的通路，就是哈密頓通路通過圖G的每個(gè)結(jié)點(diǎn)一次，且僅一次的回路，就是哈密頓回路。存在哈密頓回路的圖就是哈密頓圖。第6頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖哈密頓圖哈密頓圖的判定：(1)在無向簡單圖G=<V,E>中，若則G是哈密頓圖；——充分條件(2)如果無向圖<V,E>時(shí)哈密頓圖，V1是V的任意非空子集，則有P（G－V1）<|V1|,。其中P（G－V1）是從G中刪除V1后所得的圖的連通支數(shù)?！匾獥l件(3)有向完全圖D＝<V,E>,若，則圖D是哈密頓圖。第7頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖平面圖

重要結(jié)論

(1)平面圖(所有面的次數(shù)之和＝邊數(shù)的2倍)。

(2)歐拉公式：平面圖

面數(shù)為r，則(結(jié)點(diǎn)數(shù)與面數(shù)之和＝邊數(shù)＋2)。

(3)平面圖（2）和（3）僅為必要條件，只能判斷一個(gè)圖不是平面圖判定條件：一個(gè)圖是平面圖G的充分必要條件是G不含與K3，3或K5在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。

第8頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖平面圖相關(guān)概念面和面的邊界面的次數(shù)有限面與無限面同胚或同構(gòu)圖的著色結(jié)點(diǎn)著色、邊著色、面著色結(jié)點(diǎn)著色的方法：韋而奇.鮑威爾面著色－>邊著色->結(jié)點(diǎn)著色定理11：P205對(duì)偶圖第9頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖樹樹的判別：圖，是樹的充分必要條件是：G是無回路的連通圖；無回路，且m＝n－1；連通且m＝n－1無回路，若增加一條邊，就得到一條僅一條回路連通，若刪去任一邊，G則不連通；每一對(duì)結(jié)點(diǎn)之間有一條且僅有一條通路。證明略第10頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖樹相關(guān)概念樹和森林無向樹與有向樹樹葉與分支點(diǎn)平凡樹、生成樹和最小生成樹

樹枝、弦和生成樹的補(bǔ)根數(shù)、樹葉、分支點(diǎn)（樹根、內(nèi)點(diǎn)）層數(shù)和樹高祖先、父親、兒子和兄弟m元樹、m元完全樹和m元正則完全數(shù)第11頁，講稿共14頁，2023年5月2日，星期三幾種特殊的圖樹任何非平凡樹至少有兩片樹葉求最小生成樹的算法－－Kruskal算法定理17：（m-1）i＝t－1哈夫曼樹：最優(yōu)二叉樹定理19：P215（證明略）哈夫曼算法前綴碼前綴碼和二叉樹第12頁，講稿共14頁，2