圖論與網(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è)計(jì)總路程最短且各組盡可能均衡的災(zāi)情巡視路線。1998年全國大學(xué)生數(shù)學(xué)建模競(jìng)賽題目4.

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

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

請(qǐng)你幫助?；饡?huì)在如下情況下設(shè)計(jì)基金使用方案，并對(duì)M=5000萬元，n=10年給出具體結(jié)果：

1.只存款不購國庫券；

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

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

鋼管訂購和運(yùn)輸

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

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

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

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

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

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

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

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

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

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

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

上述問題有兩個(gè)共同的特點(diǎn)：

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

二，都易于用圖形的形式直觀地描述和表達(dá)，數(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）為研究的對(duì)象，因此網(wǎng)絡(luò)優(yōu)化又常常被稱為網(wǎng)絡(luò)流（networkflows）或網(wǎng)絡(luò)流規(guī)劃等。21.

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

22.例1

七橋問題

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

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

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

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

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

25.26.一筆畫問題

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

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

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

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

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

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

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

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

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

111223344

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

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

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

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

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

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

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

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

35.路線著色問題

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

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

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

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

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

★矩陣對(duì)線性方程組的研究可轉(zhuǎn)化為對(duì)這張表的研究.線性方程組的系數(shù)與常數(shù)項(xiàng)按原位置可排為39.例2對(duì)隨機(jī)抽取的1000人按性別（男或女）及色覺（正?；蛏ぃ﹥蓚€(gè)屬性分類，得到二行二列的列聯(lián)表:40.行列

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

:3.列矩陣(ColumnMatrix)

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

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

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

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

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

（并非所有的矩陣都不滿足交換律）矩陣是否滿足交換律？57.矩陣乘法不滿足消去律矩陣乘法是否滿足消去律？例：有但是58.★輸入矩陣的方法(1)用中括號(hào)[]把所有矩陣元素括起來；(2)同一行的不同元素之間用空格或逗號(hào)間隔；(3)用分號(hào)(;)指定一行結(jié)束；(4)也可以分成幾行進(jìn)行輸入，用回車符代替分號(hào)；(5)數(shù)據(jù)元素可以是表達(dá)式，系統(tǒng)將自動(dòng)計(jì)算結(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之間均勻分布的隨機(jī)矩陣A=rand(3)62.函數(shù)描述舉例randn元素值服從均值為0方差為1的正態(tài)分布的隨機(jī)矩陣A=randn(4)triu求給定矩陣的上三角陣B=triu(A)tril求給定矩陣的下三角陣B=tril(A)63.矩陣的基本運(yùn)算運(yùn)算功能命令形式矩陣加法和減法將兩個(gè)同型矩陣相加(減)A±B

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

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

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

A必須為方陣矩陣的右除計(jì)算A/B

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

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

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

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

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

65.66.

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

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

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

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

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

2v1v3v4v5v657080502031003094.95.96.97.

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

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

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

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

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

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

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

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

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

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