離散數(shù)學之圖論ppt課件-資料下載頁
2025-05-02 05:11本頁面
【正文】 次，則稱為歐拉回路，具有這種回路的圖叫做歐拉圖 ? 定理：無向連通圖 G是歐拉圖的充分必要條件是 G的每個結(jié)點均有偶數(shù)度數(shù) ? 必要性：經(jīng)過一個結(jié)點，該結(jié)點度數(shù)就加 2 ? 充分性：存在回路，存在簡單回路，反證法證明最大簡單回路是歐拉回路 歐拉圖 ? 若通過 G的每條邊一次的通路（不是回路）稱為歐拉通路 ? 定理：無向連通圖 G中結(jié)點 vi, vj間存在歐拉通路的充分必要條件是 vi, vj的度數(shù)為奇數(shù)，而其他結(jié)點度數(shù)均為偶數(shù) ? 在 vi, vj間加一條邊，則可構(gòu)造歐拉回路 ? 圖 8. 21 歐拉圖 ? 歐拉圖應(yīng)用題 ? 例 8. 8. 8. 8 漢密爾頓圖 ? 歐拉回路 (通路 )是簡單的回路 (通路 ) ? 漢密爾頓回路 (通路 )是基本的回路 (通路 ) ? 周游世界游戲：圖 8. 25, 8. 26 漢密爾頓圖 ? 定義：若圖 G的一個回路，通過 G的每個點一次，則稱為漢密爾頓回路，具有這種回路的圖叫做漢密爾頓圖 ? 定義：若通過 G的每個結(jié)點一次的通路（不是回路）稱為漢密爾頓通路 漢密爾頓圖 ? 一個圖是漢密爾頓圖的充分必要條件仍未解決 ? 有一些充分條件和必要條件 ? 考察右邊的圖 作業(yè) ? P140 ? 按完全無向圖 ? ?
教學課件相關(guān)推薦
鄂ICP備17016276號-1