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