圖論與網(wǎng)絡(luò)流

圖論與網(wǎng)絡(luò)應(yīng)用1.2.3.B題災(zāi)情巡視路線下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。災(zāi)情巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。若分三組（路）巡視，試設(shè)計總路程最短且各組盡可能均衡的災(zāi)情巡視路線。1998年全國大學(xué)生數(shù)學(xué)建模競賽題目4.

假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要24小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的災(zāi)情巡視路線。在上述關(guān)于T,t和V的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認(rèn)為最佳的災(zāi)情巡視路線。若巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t和V改變對最佳災(zāi)情巡視路線的影響。5.

6.2001建模競賽題目（大專組）C題基金使用計劃某?；饡幸还P數(shù)額為M元的基金，打算將其存入銀行或購買國庫券。當(dāng)前銀行存款及各期國庫券的利率見下表。假設(shè)國庫券每年至少發(fā)行一次，發(fā)行時間不定。取款政策參考銀行的現(xiàn)行政策。校基金會計劃在n年內(nèi)每年用部分本息獎勵優(yōu)秀師生，要求每年的獎金額大致相同，且在n年末仍保留原基金數(shù)額。校基金會希望獲得最佳的基金使用計劃，以提高每年的獎金額。7.

請你幫助?；饡谌缦虑闆r下設(shè)計基金使用方案，并對M=5000萬元，n=10年給出具體結(jié)果：

1.只存款不購國庫券；

2.可存款也可購國庫券；

3.學(xué)校在基金到位后的第3年要舉行百年校慶，基金會希望這一年的獎金比其它年度多20%。8.銀行存款稅后年利率（%）國庫券年利率（%）活期0.792半年期1.664一年期1.800二年期1.9442.55三年期2.1602.89五年期2.3043.149.2000“網(wǎng)易杯”全國大學(xué)生數(shù)學(xué)建模競賽試題B題

鋼管訂購和運輸

要鋪設(shè)一條的輸送天然氣的主管道,如圖一所示(見下頁)。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有。圖中粗線表示鐵路，單細(xì)線表示公路，雙細(xì)線表示要鋪設(shè)的管道(假設(shè)沿管道或者原來有公路，或者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程(單位km)。為方便計，1km主管道鋼管稱為1單位鋼管。10.一個鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個單位，鋼管出廠銷價1單位鋼管為萬元，如下表：1單位鋼管的鐵路運價如下表：

11.1000km以上每增加1至100km運價增加5萬元。公路運輸費用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算）。鋼管可由鐵路、公路運往鋪設(shè)地點（不只是運到點，而是管道全線）。（1）請制定一個主管道鋼管的訂購和運輸計劃，使總費用最?。ńo出總費用)。（2）請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運計劃和總費用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。（3）如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。12.13.2008年北京奧運會的建設(shè)工作已經(jīng)進入全面設(shè)計和實施階段。奧運會期間，在比賽主場館的周邊地區(qū)需要建設(shè)由小型商亭構(gòu)建的臨時商業(yè)網(wǎng)點，稱為迷你超市（MiniSupermarket,以下記做MS）網(wǎng)，以滿足觀眾、游客、工作人員等在奧運會期間的購物需求，主要經(jīng)營食品、奧運紀(jì)念品、旅游用品、文體用品和小日用品等。在比賽主場館周邊地區(qū)設(shè)置的這種MS，在地點、大小類型和總量方面有三個基本要求：滿足奧運會期間的購物需求、分布基本均衡和商業(yè)上贏利。2004年A題奧運會臨時超市網(wǎng)點設(shè)計14.鳥巢國家體育館水立方15.16.請你按以下步驟對圖2的20個商區(qū)設(shè)計MS網(wǎng)點：1）根據(jù)附錄中給出的問卷調(diào)查數(shù)據(jù)，找出觀眾在出行、用餐和購物等方面所反映的規(guī)律。2）假定奧運會期間（指某一天）每位觀眾平均出行兩次，一次為進出場館，一次為餐飲，并且出行均采取最短路徑。依據(jù)1的結(jié)果，測算圖2中20個商區(qū)的人流量分布（用百分比表示）。3）如果有兩種大小不同規(guī)模的MS類型供選擇，給出圖220個商區(qū)內(nèi)MS網(wǎng)點的設(shè)計方案（即每個商區(qū)內(nèi)不同類型MS的個數(shù)），以滿足上述三個基本要求。4）闡明你的方法的科學(xué)性，并說明你的結(jié)果是貼近實際的。17.例1最短路問題（SPP－shortestpathproblem）

一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應(yīng)選擇哪條線路呢？例2公路連接問題

某一地區(qū)有若干個主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？

假設(shè)貨柜車的運行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。18.例3指派問題（assignmentproblem）

一家公司經(jīng)理準(zhǔn)備安排n名員工去完成n項任務(wù)，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務(wù)時所獲得的回報是不同的。如何分配工作方案可以使總回報最大？例4中國郵遞員問題（CPP－chinesepostmanproblem）

一名郵遞員負(fù)責(zé)投遞某個街區(qū)的郵件。如何為他設(shè)計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？

由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。

（匹配問題）19.例5旅行商問題（TSP－travelingsalesmanproblem）

一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商(推銷員）問題。例6運輸問題（transportationproblem）

某種原材料有M個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往N個使用這些原材料的工廠。假定M個產(chǎn)地的產(chǎn)量和N家工廠的需求量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？20.

上述問題有兩個共同的特點：

一，其目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題；

二，都易于用圖形的形式直觀地描述和表達，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)（network）。

與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問題就是網(wǎng)絡(luò)最優(yōu)化或稱網(wǎng)絡(luò)優(yōu)化（networkoptimization）問題。

由于多數(shù)網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)上的流（flow）為研究的對象，因此網(wǎng)絡(luò)優(yōu)化又常常被稱為網(wǎng)絡(luò)流（networkflows）或網(wǎng)絡(luò)流規(guī)劃等。21.

故事的背景是十八世紀(jì)的東普魯士，美麗的Pregel河穿過哥尼斯堡；人們在河的兩岸及河中兩個小島間建立了七座橋，將它們連結(jié)成一個風(fēng)景優(yōu)美的公園。有一天，有人突發(fā)奇想：如何才能走遍七座橋，而每座橋都只能經(jīng)過一次，最后又回到原先的出發(fā)點？

22.例1

七橋問題

18世紀(jì)東普魯士哥尼斯堡被普列格爾河分為四塊，它們通過七座橋相互連接起來，問能否從某塊陸地出發(fā)，經(jīng)每座橋一次而且僅一次，回到出發(fā)點？ACBDABCD

任何一個點作為出發(fā)點都必須先“出”后“回”，才能行遍與該點相連的橋。行遍性問題23.對此問題，歐拉給出了一個通用判定規(guī)則：

從圖的某一個頂點出發(fā)，經(jīng)過每條線正好一次，最后回到原來的頂點，當(dāng)且僅當(dāng)這個圖連成一片且每個頂點都有偶數(shù)條線和它連接。思考：能否將圖的每一條線走遍，但只走一次。（不必回到原頂點）

從圖的某一個頂點出發(fā)，經(jīng)過每條線正好一次，當(dāng)且僅當(dāng)這個圖連成一片且最多只有兩個頂點是奇次的，且必須從某奇次點出發(fā)，到另一奇次點結(jié)束。ABCD24.

以下網(wǎng)絡(luò)中哪一個是可以遍歷的(即一筆而不重復(fù)地畫成)？

25.26.一筆畫問題

歐拉注意到：一個奇頂點在這種遍歷式的旅行中，要么是起點，要么是終點．由于一個遍歷的網(wǎng)絡(luò)只能有一個起點和一個終點，因而這種網(wǎng)絡(luò)的奇點數(shù)不能多于兩個．27.例2

人、狼、羊、菜渡河問題一個擺渡人F希望用一條小船把一只狼W、一頭羊G和一籃白菜C從一條河的左岸渡到右岸去，而船小只能容納F、W、G、C中的兩個，決不能在無人看守情況下，留下狼和羊在一起，羊和白菜在一起，問應(yīng)怎樣渡河才能將狼、羊、白菜都運過去？

用小圓圈（頂點）表示河岸左邊的各個狀態(tài)，兩點連線當(dāng)且僅當(dāng)兩狀態(tài)可在規(guī)定允許下轉(zhuǎn)移。FWGCFWGFWCFGCFGWCWGC00FWGCWCFWCCWFGCFWGGFG28.

一個人帶三只狼和三只羊過河，一條船可容兩只動物，沒人在時，如果狼的數(shù)量不少于羊的數(shù)量就會吃掉羊，如何安全渡河?29.

有一天，一家人（爸爸、媽媽、2個女兒、2個兒子）和警察、小偷，想過河，船上只能裝兩個人，爸爸、媽媽、警察三人會劃船，在過河的時候，爸爸不在的時候，媽媽會打兒子，媽媽不在的時候，爸爸會打女兒。警察不在的時候，小偷會打一家人。怎樣才能使他們安全的過河？？？30.例3

化學(xué)藥品存放問題某公司生產(chǎn)幾種化學(xué)藥品a,b,c,d,e,f,g，其中某些化學(xué)藥品不相容，為安全，公司要把相容的藥品放在不同格中，問至少應(yīng)將倉庫劃分為多少格？

我們可以用頂點表示各個化學(xué)藥品，兩頂點連線當(dāng)且僅當(dāng)兩藥品不相容，便可得一個圖G:adcbefg圖G的點色數(shù)便是所求的最少格數(shù)為每個頂點賦一色，使凡有連線的兩頂點異色，點色數(shù)即是使圖得到正常點上色的最少色數(shù)?！鷪D的正常點上色31.

地圖著色問題（四色問題）：

任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。

111223344

用數(shù)學(xué)語言表示，即“將平面任意地細(xì)分為不相重迭的區(qū)域，每一個區(qū)域總可以用1，2，3，4這四個數(shù)字之一來標(biāo)記，而不會使相鄰的兩個區(qū)域得到相同的數(shù)字?！?2.33.

世界近代三大數(shù)學(xué)難題：1.費爾馬大定理（1637年）

在閱讀丟番圖《算術(shù)》拉丁文譯本時，曾在第11卷第8命題旁寫道：將一個立方數(shù)分成兩個立方數(shù)之和，或一個四次冪分成兩個四次冪之和，或者一般地將一個高于二次的冪分成兩個同次冪之和，這是不可能的。

關(guān)于此，我確信已發(fā)現(xiàn)了一種美妙的證法，可惜這里空白的地方太小，寫不下。

經(jīng)過三個半世紀(jì)的努力，這個世紀(jì)數(shù)論難題才由普林斯頓大學(xué)英國數(shù)學(xué)家安德魯?懷爾斯和他的學(xué)生理查?泰勒于1995年成功證明。34.3.哥德巴赫猜想（1742年6月7日，德國數(shù)學(xué)家在寫給著名數(shù)學(xué)家歐拉的一封信中提出）：2.四色問題1）任何不小于6的偶數(shù)，都是兩個奇質(zhì)數(shù)之和；

2）任何不小于9的奇數(shù)，都是三個奇質(zhì)數(shù)之和。

世界近代三大數(shù)學(xué)難題：

任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。

35.路線著色問題

一個人來到他從未造訪過的小鎮(zhèn)上，駕著車到處尋找他朋友的家，即使連路名都沒有。朋友說，別擔(dān)心，他會指示他如何到達，先向左，再向右，接著向左……”

這個難題的假設(shè)是，在出發(fā)點（圓點）及道路（直線）的數(shù)量都固定的情況下，應(yīng)該有辦法以不同顏色標(biāo)示道路，讓人不管從哪一個點出發(fā)，都能到達固定的點。這在真實生活中的情況就像是，不管朋友住在哪里，只要知道你家的位置，繞再遠(yuǎn)都有辦法到你家。以圖為范本，如果按照"藍(lán)—紅—紅,藍(lán)—紅—紅,藍(lán)—紅—紅..."的方式行走，不管從哪個點出發(fā)都能到黃色的點；如果是"藍(lán)—藍(lán)—紅,藍(lán)—藍(lán)—紅,藍(lán)—藍(lán)—紅..."則一定能到綠點…（萬能地圖）36.圖：是指某類具體事物和這些事物之間的聯(lián)系

如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。

圖與網(wǎng)絡(luò)是運籌學(xué)（OperationsResearch）中的一個經(jīng)典和重要的分支，所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交通運輸、計算機科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。

最短路問題、行遍性問題、最大流問題、最小費用流問題和匹配問題等都是圖與網(wǎng)絡(luò)的基本問題。37.38.例1線性方程組的解取決于：系數(shù)常數(shù)項復(fù)習(xí)：

★矩陣對線性方程組的研究可轉(zhuǎn)化為對這張表的研究.線性方程組的系數(shù)與常數(shù)項按原位置可排為39.例2對隨機抽取的1000人按性別（男或女）及色覺（正常或色盲）兩個屬性分類，得到二行二列的列聯(lián)表:40.行列

由個數(shù)排成的行列的數(shù)表定義：稱為行列矩陣.簡稱矩陣.簡記為這個數(shù)稱為的元素，簡稱為元.41.★幾種特殊矩陣1.方陣(SquareMatrix):例如：是一個3階方陣.行數(shù)與列數(shù)都等于的矩陣，也可記作注意2、矩陣的行數(shù)和列數(shù)可以不等1、矩陣是一張數(shù)表42.2.行矩陣(RowMatrix)(或行向量)

:3.列矩陣(ColumnMatrix)

(或列向量):只有一行的矩陣只有一列的矩陣43.形如的方陣,4.對角矩陣

(DiagonalMatrix):記作元素不全為0主對角線5.單位矩陣(IdentityMatrix):主對角線上元素全為1,其他元素都是0的方陣44.6.零矩陣(ZeroMatrix):注意不同階數(shù)的零矩陣是不相等的.例如：

元素全為零的矩陣稱為零矩陣，零矩陣記作或.?45.★矩陣的基本運算1.矩陣相等矩陣相等:例同型矩陣：兩個矩陣的行數(shù)相等、列數(shù)也相等46.設(shè)有兩個矩陣那么矩陣與的和記作，規(guī)定為2.矩陣的加減法加法：47.例說明

只有當(dāng)兩個矩陣是同型矩陣時，才能進行加法運算.48.減法:負(fù)矩陣：49.矩陣加法滿足的運算規(guī)律:50.3.數(shù)與矩陣相乘數(shù)乘:51.數(shù)乘矩陣的運算規(guī)律：（設(shè)為矩陣，為數(shù)）矩陣相加與數(shù)乘矩陣合起來,統(tǒng)稱為矩陣的線性運算.52.并把此乘積記作設(shè)是一個矩陣，是一個矩陣，那么規(guī)定矩陣與矩陣的乘積是一個矩陣，其中4、矩陣與矩陣相乘53.設(shè)例解求54.注意只有當(dāng)?shù)谝粋€矩陣的列數(shù)等于第二個矩陣的行數(shù)時，兩個矩陣才能相乘.例如不存在.55.矩陣乘法的運算規(guī)律（其中為數(shù)）;

若A是階矩陣，則為A的次冪，即并且滿足結(jié)合律、分配率56.矩陣不滿足交換律例設(shè)則

（并非所有的矩陣都不滿足交換律）矩陣是否滿足交換律？57.矩陣乘法不滿足消去律矩陣乘法是否滿足消去律？例：有但是58.★輸入矩陣的方法(1)用中括號[]把所有矩陣元素括起來；(2)同一行的不同元素之間用空格或逗號間隔；(3)用分號(;)指定一行結(jié)束；(4)也可以分成幾行進行輸入，用回車符代替分號；(5)數(shù)據(jù)元素可以是表達式，系統(tǒng)將自動計算結(jié)果；59.例：輸入矩陣matlab輸入格式：ans=-39-1137ans=360.61.★特殊矩陣函數(shù)函數(shù)描述舉例[]空矩陣A(:,2)=[]%刪除矩陣A的第2列eye單位矩陣A=eye(3)ones元素全部為1的矩陣A=ones(2,3)%A為2×3元素全為1的矩陣zeros元素全部為0的矩陣A=zeros(2,3)%A為2×3元素全為0的矩陣rand元素值為0到1之間均勻分布的隨機矩陣A=rand(3)62.函數(shù)描述舉例randn元素值服從均值為0方差為1的正態(tài)分布的隨機矩陣A=randn(4)triu求給定矩陣的上三角陣B=triu(A)tril求給定矩陣的下三角陣B=tril(A)63.矩陣的基本運算運算功能命令形式矩陣加法和減法將兩個同型矩陣相加(減)A±B

數(shù)乘將數(shù)與矩陣做乘法k*A

k是一個數(shù),A是一個矩陣矩陣乘法將兩個矩陣進行矩陣相乘A*B

A的列數(shù)與B的行數(shù)相等矩陣的左除計算A\B

A必須為方陣矩陣的右除計算A/B

B必須為方陣求矩陣行列式計算方陣的行列式det(A)

A必須為方陣64.矩陣的基本運算運算功能命令形式求矩陣的逆求方陣的逆Inv(A)或

矩陣乘冪計算AnA?nA必須為方陣,n是正整數(shù)矩陣的轉(zhuǎn)置求矩陣的轉(zhuǎn)置Transpose(A)或A′

矩陣求秩求矩陣的秩rank(A)

矩陣行變換化簡求A階梯形的行最簡形式rref(A)

65.66.

一、圖與網(wǎng)絡(luò)的基本概念

是由一個非空有限集合和中某些元素的無序?qū)蠘?gòu)成的二元組，記為。頂點集或節(jié)點集邊集Vertex，edge67.完備圖若表示集合中的元素個數(shù)），中無相鄰頂點對，中亦然，則稱為二分圖；特別地，若則，則稱為完全二分圖，記成。68.

簡而言之，就是頂點集V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點都分屬于這兩個互不相交的子集。圖中(a),(b)為二分圖，(c)為完全二分圖K3,369.70.樹71.最小生成樹：72.73.

二、圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)74.75.76.（每邊有兩個頂點與其相關(guān)聯(lián)）77.78.79.15346780.三、最短距離問題

在生產(chǎn)管理、交通運輸和通訊領(lǐng)域，經(jīng)常會碰到這樣的問題：沿著哪條路線可以最短的時間或最少的費用把貨物運往目的地？沿著哪條路線傳送信息最可靠或最快捷？如何組織生產(chǎn)可使生產(chǎn)成本最低？如何制定投資計劃可使利潤最大？這些都可看成是在給定的加權(quán)圖中，求最短路徑問題。81.82.83.鄰接矩陣84.85.86.87.88.89.90.91.92.93.

2v1v3v4v5v657080502031003094.95.96.97.

2v1v3v4v5v657080502031003098.例某公司在六個城市中有分公司，從到的直接航程票價記在下述矩陣的位置上。（表示無直接航路），請幫助該公司設(shè)計一張城市到其它城市間的票價最便宜的路線圖。99.行遍性問題100.一、中國郵遞員問題二、推銷員問題（一）歐拉圖（二）中國郵遞員問題（一）哈密爾頓圖（二）推銷員問題101.e3v1v2v3v4e1e2e4e5e6歐拉圖e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1歐拉道路：v1e1v2e2v3e5v1e4v4e3v3歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1102.e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6歐拉圖非歐拉圖

推論1設(shè)G是非平凡連通圖，則G有歐拉道路的充要條件是G最多有兩個奇次頂點.該推論為判別圖形能否一筆畫給出了依據(jù)103.中國郵遞員問題-定義

郵遞員發(fā)送郵件時，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行程最短的路線。這就是中國郵遞員問題。

若將投遞區(qū)的街道用邊表示，街道的長度用邊權(quán)表示，郵局街道交叉口用點表示，則一個投遞區(qū)構(gòu)成一個賦權(quán)連通無向圖.

中國郵遞員問題轉(zhuǎn)化為：在一個非負(fù)加權(quán)連通圖中，尋求一個權(quán)最小的巡回．這樣的巡回稱為最佳巡回．（管梅谷1962年）——一筆畫問題104.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割邊

割邊的定義：設(shè)G連通，eE(G),若從G中刪除邊e后，圖G-{e}不連通，則稱邊e為圖G的割邊．G的邊e為割邊e不含在G的圈中圈：起點與終點重合的路徑頂點、邊均不重復(fù)的通路105.中國郵遞員問題-算法Fleury算法-基本思想：從任一點出發(fā)，每當(dāng)訪問一條邊時，先要進行檢查．如果可供訪問的邊不只一條，則應(yīng)選一條不是未訪問的邊集的導(dǎo)出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止.

此時G的任何一個歐拉巡回便是最佳巡回．問題歸結(jié)為在歐拉圖中確定一個歐拉巡回．1.G是歐拉圖106.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10107.

若G不是歐拉圖，則G的任何一個巡回經(jīng)過某些邊必定多于一次．

解決這類問題的一般方法是，在一些點對之間引入重復(fù)邊（重復(fù)邊與它平行的邊具有相同的權(quán)），使原圖成為歐拉圖，但希望所有添加的重復(fù)邊的權(quán)的總和為最?。甧3v1v2v3v4e1e2e4e52.G不是歐拉圖108.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9109.

先將奇次頂點配對，要求最佳配對，即點對之間距離總和最?。傺攸c對之間的最短路徑添加重復(fù)邊得歐拉圖G*，G*的歐拉巡回便是原圖的最佳巡回．基本思想：110.（3）求出G1的最小權(quán)理想匹配M，得到奇次頂點的最佳配對．（2）以G的所有奇次頂點為頂點集（個數(shù)為偶數(shù)），作一完備圖，邊上的權(quán)為兩端點在原圖G中的最短距離，將此完備加權(quán)圖記為G1．111.定義：設(shè)M是G的一個匹配，（1）若M滲透了G的每個頂點，則稱M是G的理想匹配（2）若M是G中含邊最多的匹配，則稱M為G的最大匹配顯然理想匹配是最大匹配，但最大匹配不一定是理想匹配理想匹配可能有多個，權(quán)最小的為最小權(quán)理想匹配。112.113.中國郵遞員問題的應(yīng)用與推廣：1.鏟雪車的行使路線問題：馬里蘭州維克米城被大雪覆蓋，有兩輛鏟雪車清除積雪。如何安排行使路線，使得兩輛車同時完成任務(wù)。2.容量約束中國郵遞員問題：城市環(huán)保局每天要派出灑水車為城市街道灑水。由于灑水車的容量有限，中途需要返回加水，若已知每英里道路需要的水量以及灑水車的容量，問如何安排車的行使路線使總行程最短？又如：城市垃圾收集、流動餐車、道路灑鹽….114.哈密爾頓圖