圈演算法

㈠ 圖論演算法及其MATLAB實現的圖書目錄

第1章 圖論的基礎知識1
1.1圖論的起源1
1.2著名的圖論學者——歐拉1
1.3圖2
1.4特殊圖類3
1.5有向圖4
1.6圖的矩陣表示5
1.6.1鄰接矩陣5
1.6.2關聯矩陣5
1.7圖論的基本性質和定理6
1.8計算有向圖的可達矩陣的演算法及其MATLAB實現6
1.9關聯矩陣和鄰接矩陣的相互轉換演算法及其MATLAB實現7
習題一11
第2章 最短路12
2.1路12
2.2最短路問題13
2.3求連通圖最短距離矩陣的演算法及其MATLAB實現14
2.4求兩點間最短路的Dijkstra演算法及其MATLAB實現15
2.4.1 Dijkstra演算法16
2.4.2 Dijkstra演算法的MATLAB實現16
2.5求兩點間最短路的改進的Dijkstra演算法及其MATLAB實現18
2.5.1 Dijkstra矩陣演算法Ⅰ18
2.5.2 Dijkstra矩陣演算法Ⅱ18
2.6 求兩點間最短路的WarshallFloyd演算法及其MATLAB實現21
2.6.1 Floyd演算法的基本思想22
2.6.2 Floyd演算法的基本步驟22
2.6.3 WarshallFloyd演算法的MATLAB實現22
2.7求任意兩點間最短路的演算法及其MATLAB實現25
2.8求從一固定點到其他所有點最短路的演算法及其MATLAB實現27
2.9求必須通過指定兩個點的最短路的演算法及其MATLAB實現29
2.10求圖的兩頂點間最短路與次短路的演算法及其MATLAB實現32
2.11求最大可靠路的演算法及其MATLAB實現34
2.12求最大期望容量路的演算法及其MATLAB實現36
習題二38
第3章 連通圖40
3.1判斷圖的連通性演算法及其MATLAB實現40
3.2連通圖的中心和加權中心的演算法及其MATLAB實現42
3.3連通無向圖一般中心的演算法及其MATLAB實現44
習題三46
第4章 樹48
4.1樹及其性質48
4.2割點、割邊、割集50
4.3二元樹與Huffman樹51
4.3.1有序二元樹51
4.3.2 Huffman樹51
4.4求Huffman樹及其MATLAB實現52
4.5廣度優先搜索演算法及其MATLAB實現55
4.6深度優先搜索演算法及其MATLAB實現57
4.7求割點演算法及其MATLAB實現61
4.8生成樹及其個數65
4.9求無向圖的生成樹演算法及其MATLAB實現67
4.10求有向圖的生成樹演算法及其MATLAB實現69
4.11求有向連通圖的外向樹與內向樹數目的演算法及其MATLAB實現71
4.12最小生成樹問題73
4.13求最小生成樹的Kruskal演算法及其MATLAB實現74
4.13.1 Kruskal演算法的基本思想74
4.13.2 Kruskal演算法的MATLAB實現74
4.14求最小生成樹的Prim演算法及其MATLAB實現76
4.14.1 Prim演算法的基本思想76
4.14.2 Prim演算法的MATLAB實現77
習題四79
第5章Euler圖和Hamilton圖81
5.1 Euler圖81
5.2「一筆畫」問題及其理論81
5.3中國郵遞員問題82
5.4 Fleury演算法及其MATLAB實現82
5.4.1 Fleury演算法的步驟82
5.4.2 Fleury演算法的MATLAB實現82
5.5 Hamilton圖87
5.6旅行售貨員問題88
5.7改良圈演算法及其MATLAB實現89
習題五92
第6章 匹配問題及其演算法93
6.1問題起源——婚配問題93
6.2二分圖的有關知識93
6.3匹配、完美匹配、最大匹配93
6.4匹配的基本定理94
6.5應用案例——BernolliEuler錯放信箋問題95
6.6尋求圖的一個較大基數匹配演算法及其MATLAB實現95
6.7人員分配問題97
6.8匈牙利演算法及其MATLAB實現97
6.8.1匈牙利演算法基本步驟97
6.8.2匈牙利演算法的MATLAB實現98
6.8.3案例及其MATLAB實現100
6.9最優分配問題101
6.10 KuhnMunkres演算法及其MATLAB實現101
6.10.1 KuhnMunkres演算法的基本思想101
6.10.2利用可行頂點標記求最佳匹配的KuhnMunkras演算法步驟102
6.10.3 KuhnMunkres演算法的MATLAB實現102
6.10.4簡單實驗105
習題六107
第7章 網路流的演算法108
7.1網路、流和割108
7.1.1網路和流108
7.1.2割109
7.2網路的最大流問題110
7.3最大流最小割定理110
7.4 FordFulkerson標號演算法及其MATLAB實現111
7.4.1 FordFulkerson標號演算法的基本步驟111
7.4.2 FordFulkerson 標號演算法的MATLAB實現112
7.4.3案例及其MATLAB實現113
7.5 Dinic演算法及其MATLAB實現114
7.5.1 Dinic演算法的基本思想114
7.5.2 Dinic演算法的MATLAB實現115
7.5.3案例

㈡ 數學建模 旅行商路線規劃問題。第一問用改良圈演算法已經解決，請問第二問該用什麼演算法（每段高速和普通公

每段高速和普通公路里程數不同
導致總費用=油費+路費不同
這個題目有點意思
要不要考慮高速和普通公路的單位油耗不同

㈢ 什麼是改良圈演算法

首先求一個 Hamilton 圈C ，然後適當修改C 以得到具有較小權
的另一個 Hamilton 圈。修改的方法叫做改良圈演算法。

㈣ 求助：圖的遍歷並且路徑最短的演算法（vb6.0）

我汗。。。最短哈密爾頓路。。這個是np問題，沒有什麼好的演算法。不過有幾個近似演算法，如「改良圈演算法」，如果要精確的那就只能回溯搜索了。。。不過會很慢。

㈤ 求教有負環的最小費用最大流

我現在也沒有編出來。正如你所說，這個程序需要用消圈或者單純形。它們很難編，也非常耗時，比賽的時候寫這樣的程序容易吃虧。並且，這類題目基本上不會出現。
需要程序和解釋的話，你可以參考王曉東寫的一本書《計算機演算法設計與分析》，裡面非常詳盡！

㈥ 用破圈法求最小生成樹

感覺上你那裡的「演算法基本思想」實現難度很大，因為圖的連通性不好維護
找圈的話，隨便找個節點為根DFS整個圖，然後在這樣的DFS生成樹中，每條非樹邊都對應了一個圈，每次找一條非樹邊，刪去所在圈中最長邊生成一個新樹，直到不存在非樹邊為止，剩下的就是最小生成樹了
具體實現的時候，先求出一個DFS生成樹，然後遞歸處理每棵子樹

假設要處理的子樹根節點為u，對該子樹破圈法的粗略偽代碼如下：

void 破圈法(u)
{
for ( v是u的每個子節點 ) 破圈法(v);
for ( e是連接u與其後繼的每條非樹邊 )
{
v=e的另一個端點;
e'=u到v之間的最長樹邊;
if (w[e]>=w[e']) 刪除邊e;//w[e]表示e的權
else
{
//用w表示原先e'的在樹中較深的端點,p[v]表示v的親節點
刪除邊e';
if (v!=w)
{
將v列入u的子節點列表;
將p[v]、p[p[v]]、...、w這條路徑反向，並將p[v]列入v的子節點列表;
}
}
}
}

上述過程不加優化的時間復雜度為O(VE)，效率非常差
貌似其中找最長邊和將v的若干祖先節點路徑反向的兩步優化空間比較大，或許可將整個時間復雜度下降到O(ElgV)，研究中

㈦ 生產與作業管理--破圈法的概念、步驟。

1、生產戰略：是企業根據所選定的目標市場和產品特點來構造其生產系統時所遵循指導思想，以及在這種指導思想下的一系列決策規劃、內容和程序。2、生產管理的任務：運用組織、計劃、控制的職能，把投入生產過程的各種要素組織起來，形成有機整體，按最經記得方式，生產出滿足社會需要的廉價、優質的產品。3、生產管理的內容：1.生產准備和組織 2.生產計劃 3.生產控制4、生產管理的原則：1.講求經濟效益 2.堅持以銷定產 3實行科學管理4.組織均衡生產 5.實施可持續發展戰略5、生產按工藝特性分類：1.加工裝配型 2.流程型6、生產按組織生產的特點分類：1.備貨型 2.訂貨型：訂貨組裝型、訂貨製造型、訂貨工程型7、備貨型生產(MTS)：是指在沒有接到用戶訂單時，按已有的標准產品或產品系列進行生產，生產目的是為了完成產品庫存。8、訂貨型生產(MTO)：是指按用戶的訂單進行生產。9、生產按專業化程度分類：1.大量生產 2.單件生產 3.成批生產 4.多品種小批量生產10、多品種小批量生產組織工作的特徵：1.生產品種多樣性 2.生產過程復雜性 3.生產能力的適應性4.環境條件的多變性 5.生產計劃的變動性 6.生產管理的動態性11、生產過程的組成：1.生產技術准備過程 2.基本生產過程 3.輔助生產過程 4.生產服務過程12、工序：是指一個工人或一組工人在同一工作上對同一勞動對象進行加工的生產環節。13、合理組織生產過程的基本要求：1.生產過程的連續性 2.生產過程的比例性3.生產過程的節奏性 4.生產過程的柔性14、生產時間計算：*P25--2815、文明生產：是指在生產現場管理中，要按照現代工業生產的客觀要求，為生產現場保持良好的生產環境和生產秩序v16、「5S」活動的內容：1.整理 2.整頓 3.清掃 4.清潔 5.素養17、安全生產：是指在保持領導者生命安全和健康的前提下進行生產活動。二工作研究1、工作研究：是指在既定的工作條件下，運用系統分析的方法，研究資源的更合理利用，排除作業中不合理、不經濟和混亂的因素，尋求一種更佳、更經濟的工作方法，以提高系統的生產率，降低系統的運營成本。2、工作研究的內容：1.方法研究：過程分析、動作分析 2.時間研究：定額制訂、工作抽樣3、工作研究的步驟：1.發掘問題，選擇研究項目 2.確定目標3.記錄 4.分析研究記錄的事實，尋求新的方法5.評價新的工作方法 6.實施新的方法7.追檢與再評價4、過程分析：是指對現行作業方法予以系統的記錄，這種記錄採用的是一種以簡明符號為基礎繪制的程序圖。5、過程分析基本符號：1.加工： 2.搬運： 3.儲存：4.延誤： 5.檢驗：6、過程分析的內容：1.產品工序分析 2.零件加工分析 3.平面流程分析4.搬運分析 5. 人—機聯合分析7、動作分析：是把某項作業的動作分解為最小的分析單位，對作業進行定性、定量分析，省去不必要和不合理的動作，制定出最合理的動作和動作的順序，使作業達到准化的一種科學分析方法和技術。8、動作的基本類型：1.必要動作 2.輔助動作 3.延遲動作 9、工作研究中動作經濟合理的要求：1.動作應同時進行 2.動作應對稱 3.動作應自如4.動作應有節奏 5.動作應考慮慣性6.能用腳完成的動作，應避免用手10、工作環境：是指人、機共處的特定條件，如溫度、濕度、雜訊等物理環境；有害氣體等化學環境和人際關系等社會環境。11、工作環境的三類因素：1.氣候狀況 2.照明和色彩狀況 3.雜訊與振動狀況三 生產計劃和控制1、生產計劃系統：是一個包括需要預測、中期生產計劃、生產作業計劃、材料計劃、能力計劃、設備計劃、新產品開發計劃等相關計劃和職能，並以生產控制信息迅速反饋連接構成的復雜系統。2、生產計劃的層次：1.長期生產計劃。屬於戰略計劃，任務是進行產品決策、生產能力決策以及確立何種競爭優勢的決策。2.中期生產計劃。屬於B戰術性計劃，任務是對企業在計劃年度內的生產任務作出統籌安排，規定企業的品種、質量、數量和進度。3.短期生產計劃。任務是直接依據用戶的訂單，合理的安排生產活動的每個細節。3、年生產計劃的主要指標：1.品種 2.產量 3.質量 4.產值 5.出產期4、生產計劃的產值指標分為：1.商品產值 2.總產值 3.凈產值5、生產計劃編制的原則：以銷定產的原則，即以產品銷路來決定生產什麼樣的產品。6、生產計劃編制的步驟：1.調查、掌握編制生產計劃的依據。 2.統籌安排，初步提出生產計劃指標。3.綜合平衡，確B定生產計劃指標。 7、滾動式計劃方法的優點：1.計劃是動態型的，計劃的應變性和嚴肅性得到保證。2.提高了計劃的連續性。8、生產計劃主要考慮的成本項目：1.正常生產成本 2.加班成本 3.外協成本 4.庫存成本

㈧ hamilton圈演算法是什麼意思

哈密頓圖（哈密爾頓圖）（英語：Hamiltonian path，或Traceable path）是一個無向圖，由天文學家哈密頓提出，由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次。在圖論中是指含有哈密頓迴路的圖，閉合的哈密頓路徑稱作哈密頓迴路（Hamiltonian cycle），含有圖中所有頂點的路徑稱作哈密頓路徑。

從圖中的任意一點出發，路途中經過圖中每一個結點當且僅當一次，則成為哈密頓迴路。
要滿足兩個條件：
⒈封閉的環
⒉是一個連通圖，且圖中任意兩點可達
經過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。
經過圖中所有頂點一次且僅一次的迴路稱為哈密頓迴路。
具有哈密頓迴路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓迴路的圖稱為半哈密頓圖。
平凡圖是哈密頓圖。