【教程】大學競賽數(shù)學建模與數(shù)學實驗行遍性問題ppt(已修改)
2025-08-13 16:20 本頁面
【正文】 行 遍 性 問 題 數(shù)學建模與數(shù)學實驗 行 遍 性 問 題 一、中 國 郵 遞 員 問 題 二、推 銷 員 問 題 三、建模案例：最佳災情巡視路線 （一） 歐 拉 圖 （二） 中 國 郵 遞 員 問 題 （一） 哈 密 爾 頓 圖 （二） 推 銷 員 問 題 定義 設圖 G = （ V ， E ）， M ? E ，若 M 的邊互不相鄰，則稱 M 是 G 的一個 匹配 . 若頂點 v 與 M 的一條邊關聯(lián)，則稱 v 是 M 飽和的 . 設 M 是 G 的一個匹配，若 G 的每個頂點都是 M 飽和的，則稱M 是 G 的 理想匹配 . 7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9 割邊 G的邊 是割邊的充要條件是 不含在 G的圈中． 割邊的定義 ：設 G連通， E(G),若從 G中刪除邊 后，圖 G{ }不連通，則稱邊 為圖 G的割邊． ?e ee ee evvvvvvveeeeeee ee e3 v1 v2 v3 v4 e1 e2 e4 e5 e6 歐 拉 圖 定義１ 設 G =( V , E ) 是連通無向圖 （１）經(jīng)過 G 的每邊至少一次的閉通路稱為 巡回 ． （２）經(jīng)過 G 的每邊正好一次的巡回稱為 歐拉巡回 ． （３）存在歐拉巡回的圖稱為 歐拉圖 ． （４）經(jīng)過 G 的每邊正好一次的道路稱為 歐拉道路 ． e3 v1 v2 v3 v4 e1 e 2 e4 e5 巡回： v1e1v2e2v3e5v1e4v4e3v3e5v1 歐拉道路： v1e1v2e2v3e5v1e4v4e3v3 歐拉巡回： v
法律信息相關推薦
鄂ICP備17016276號-1