關于幾種特殊的圖第1頁，課件共14頁，創(chuàng)作于2023年2月幾種特殊的圖教學要求理解歐拉通路(回路)、歐拉圖的概念，掌握歐拉圖的判別方法。

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

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

了解無向樹、樹葉、分支點、平凡樹、生成樹和最小生成樹等概念。會求最小生成樹。

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

第2頁，課件共14頁，創(chuàng)作于2023年2月幾種特殊的圖本章重點：歐拉圖和哈密頓圖平面圖樹的基本概念。

第3頁，課件共14頁，創(chuàng)作于2023年2月幾種特殊的圖歐拉圖包含圖G的每一條邊，且每條邊僅出現(xiàn)一次的通路，就是歐拉通路。包含圖G的每一條邊，且每條邊僅出現(xiàn)一次的回路，就是歐拉回路。存在歐拉回路的圖，就是歐拉圖。

第4頁，課件共14頁，創(chuàng)作于2023年2月幾種特殊的圖歐拉圖歐拉圖的判定：(1)無向連通圖G是歐拉圖

G不含奇數(shù)度的結點(即G

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

是歐拉圖

G

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

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

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

重要結論

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

(2)歐拉公式：平面圖

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

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

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

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