【正文】 ；含 Hamilton圈的圖叫做 Hamilton圖 。 5 Euler圖和 Hamilton圖 ? 基本概念 ? 定義 經(jīng)過 G的每條邊的跡叫做 G的 Euler跡 ；閉的 Euler跡叫做 Euler回路或 E回路 ；含 Euler回路的圖叫做 Euler圖 。 但是如何乘船渡河的大權(quán)掌握在商人們 手中 。 河南城建學(xué)院 課后作業(yè) 四名商人各帶一個(gè)隨從乘船渡河 ， 一只小船 只能容納二人 ， 由他們自己劃行 。 可用圖表示為 河南城建學(xué)院 河南城建學(xué)院 實(shí)例三 循環(huán)比賽的名次 問題 n支球隊(duì)循環(huán)比賽 ， 每場(chǎng)只計(jì)勝負(fù) ， 沒有平局 . 根據(jù)比賽結(jié)果排出各隊(duì)名次 .圖 （ 1） 給出了 6支 球隊(duì)的比賽結(jié)果 ， 即 1隊(duì)?wèi)?zhàn)勝 6隊(duì) ， 而 輸給了 3隊(duì)； 5隊(duì)?wèi)?zhàn)勝 6隊(duì) ， 而輸給了 4 隊(duì)等等 . 河南城建學(xué)院 循環(huán)比賽的名次 方法 1：尋找按箭頭方向通過全部頂點(diǎn)的路徑 . 312456 146325 …… ?無法排名 方法 2：計(jì)算得分： 1隊(duì)勝 4場(chǎng) ， 2， 3隊(duì)各勝 3 場(chǎng) ， 4， 5隊(duì)各勝 2場(chǎng) ， 6隊(duì)勝 1場(chǎng) .2， 3 隊(duì) ， 4， 5隊(duì)無法排名 .3→ 2， 4→ 5? 排名 132456合理嗎 ？ 用圖論的知識(shí)可以解決這個(gè)問題 . 河南城建學(xué)院 循環(huán)比賽的名次 競(jìng)賽圖及其性質(zhì) 循環(huán)比賽的結(jié)果 —— 競(jìng)賽圖：每對(duì)頂點(diǎn)之間都有 一條邊相連的有向圖 .名次是由出度由大到小排序 。 例如表示人帶狗過河 。 河南城建學(xué)院 現(xiàn)在用狀態(tài)運(yùn)算來完成狀態(tài)轉(zhuǎn)移 。 而人不在場(chǎng)時(shí) ， 狗要吃羊 ， 羊要吃菜 ， 問此人應(yīng)如何過河 ？ 模型構(gòu)成此問題可化為狀態(tài)轉(zhuǎn)移問題 ， 用四 維向量 （ 人 ， 狗 ， 羊 ， 菜 ） 來表示狀態(tài) ， 當(dāng)一物 在此岸時(shí)相應(yīng)分量取 1， 而在彼岸時(shí)則取 0。 河南城建學(xué)院 握手的次數(shù) 要知道史密斯太太和別人握手的次數(shù) ， 只需確定除史 密斯先生外的 9人中哪一個(gè)是史密斯太太即可 。 ? —— 除史密斯先生外 ， 每個(gè)人握手的次數(shù)最多是 8次 ，最少為 0次 。 ? 每個(gè)人都不會(huì)跟同一個(gè)人握手兩次 —— 兩個(gè)人間的握手最多是一次 。 河南城建學(xué)院 握手的次數(shù) 分析：從題目我們得到了哪些信息 ? ? 史密斯和太太邀請(qǐng)四對(duì)夫妻參加晚會(huì) —— 房間里共有10 人 。 之后 ， 史密斯先生問每個(gè)人和別人握了幾 次手 ， 他們的答案都不一樣 。 4．圖的矩陣表示 定義 1 關(guān)聯(lián)矩陣 (1) 對(duì)無向圖 G ，其關(guān)聯(lián)矩陣()ij vMm???，其中 ij1 , v v0 , ijm???? ij若 與 相 關(guān) 聯(lián)若 v 與 v 不 關(guān) 聯(lián) (2) 對(duì)有向圖 G ，其關(guān)聯(lián)矩陣()ij vMm???，其中 1 , 1 , 0 , iij iivmvv???????jjj若 是 e 的 起 點(diǎn)若 是 e 的 終 點(diǎn)若 與 e 不 關(guān) 聯(lián) 河南城建學(xué)院 1 3 4 5 2 關(guān)聯(lián)矩陣示例 右上圖的關(guān)聯(lián)矩陣是 右下圖的關(guān)聯(lián)矩陣是 1e1 3 4 2 ????????????????110100001010010001101010000110010000011154321?????????????????1100010110011010001143212e3e4e5e6e 7e8e1e2e3e4e5e1e1e2e2e3e3e 4e4e 5e5e6e 7e 8e河南城建學(xué)院 定義 2 鄰接矩陣 (1) 對(duì)無向圖 G ，其鄰接矩陣()ij v vAa??，其中 1 , 0 , ijijijvvavv????若 與 相 鄰若 與 不 相 鄰 (2) 對(duì)有向圖 G = V ， E ，其鄰接矩陣()ij v vAa??，其中 1 , ( , )0 , ( , )ijijijv v Eav v E??????若若 （ 3 ） 對(duì)有向賦權(quán)圖 G ，其鄰接矩陣()ij v vAa??， 其中 , ( , )0 , , ( , )i j i j i jijijw v v E wa i jv v E? ?????????若 , 且 為 其 權(quán)若若 河南城建學(xué)院 鄰接矩陣示例 右上圖的鄰接矩陣是 右下圖的鄰接矩陣是 1 3 4 5 2 1 3 4 2 ????????????????01110101011101110101011105432154321????????????010000001100011043214321河南城建學(xué)院 定義 3 可達(dá)矩陣： 對(duì)有向圖 G = （ V ， E ），其可達(dá)矩陣()ij v vPp??，其中 1 , 0 , ijijijvvpvv????若 與 可 達(dá)若 與 不 可 達(dá) 1 3 4 2 1 2 3 41 1 1 1 12 0 1 1 13 0 0 1 04 0 0 1 1????????????例 右圖的可達(dá)矩陣是 河南城建學(xué)院 二、圖論模型實(shí)例分析 實(shí)例一 握手的次數(shù) 史密斯先生和他太太邀請(qǐng)四對(duì)夫妻參加晚會(huì)每個(gè)人 到的時(shí)候 ， 房間里的一些人都要與別的一些人握手 。 (4) 連通的無圈圖稱為 樹 。 定義 2 (1) 在無向圖 G中 ,若存在一條從頂點(diǎn) u到 w的路 徑 , 則稱 從 u到 w可達(dá) .約定每個(gè)結(jié)點(diǎn)到自身 可達(dá) 。 河南城建學(xué)院 定義 3 (1) 設(shè) 是賦權(quán)圖 G中從 u到 v的路徑 ， 則稱 為 路徑 P的權(quán) 。 河南城建學(xué)院 167。 (4)若子圖 G?無孤立點(diǎn)且 G?由 E?唯一確定，則稱 G?是 由邊集E?導(dǎo)出的子圖 ； (5)若對(duì)子圖 G?=?V?,E??中任二頂點(diǎn) u,v,(u,v)?E ?(u,v)?E?，則 稱 G?是 由頂點(diǎn)集 V?導(dǎo)出的子圖 (易見 :V?導(dǎo)出的子圖 G?是以 V?為其頂點(diǎn)集 ,所有在 G中同時(shí)關(guān)聯(lián)于V?中兩點(diǎn)的邊為其邊集 ). 圖的定義與記號(hào) 河南城建學(xué)院 圖的定義與記號(hào) 定義 3 : （ 1 ） 在無向圖中，與頂點(diǎn) v 關(guān)聯(lián)的邊數(shù)（環(huán)算 兩次）稱為 v 的 次數(shù)（度） ， 記為()dv。 圖的定義與記號(hào) 河南城建學(xué)院 定義 2 子圖：給定兩個(gè)無 (有 )向圖 G=（ V,E） ， G?=（ V?,E?） 。 ( 8) 若, V X Y X Y? ? ?， X 中任兩頂點(diǎn)不相鄰， Y 中任兩頂點(diǎn)不相鄰，稱 G 為 二部圖 ；若 X 中每一頂點(diǎn)都和Y 中一切頂點(diǎn)相鄰，稱為 完全二部圖 ，記為,nmK，其中 m ， n 分別為 X 與 Y 的頂點(diǎn)數(shù)。 ( 7) 任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖稱為 完全圖 。 (4)不與任何結(jié)點(diǎn)鄰接的頂點(diǎn)稱為孤立點(diǎn)，全為孤立點(diǎn)組成的圖 (無向圖和有向圖均可 )稱為空?qǐng)D。當(dāng)無向邊 ( , )ije v v?時(shí)，稱 e 與 iv，jv關(guān)聯(lián)，或 iv，jv與 e 關(guān)聯(lián)，或 iv與 jv 相鄰接；關(guān)聯(lián)于同一頂點(diǎn)的一條邊稱為環(huán)。 2．圖的定義與記號(hào) 定義 1 （ 1 ） 圖 G 是一個(gè)二重組： G= （ V ， E ），其中V =12{ , , , }nv v v是非空有限集合，稱為頂點(diǎn)集，它的元素稱為圖 G 的頂點(diǎn)； E 也是 ( 可空 ) 有限集合 ， 稱為邊集，它的元素稱為圖 G 的邊。 所以上面例子中介紹的問題都是網(wǎng)絡(luò)優(yōu)化問題。假定個(gè)產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？ 河南城建學(xué)院 ? 上述問題有兩個(gè)共同的特點(diǎn)： 一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最優(yōu)化或優(yōu)化（ optimization）問題；二是它們都易于用圖形的形式直觀地描述和表達(dá)，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為（ work）。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題 。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國(guó)管梅谷教授 1960年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問題。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的。 河南城建學(xué)院 ? 例 2 公路連接問題 ? 某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。 河南城建學(xué)院 ? 例 1 最短路問題（ SPP－ shortest path problem） ? 一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。 圖論簡(jiǎn)介 Konigsberg 七橋問題 是否可以 一筆畫？ A B D C D C A B 河南城建學(xué)院 1 概論 圖與網(wǎng)絡(luò)是運(yùn)籌學(xué)（ Operations Research）中的一個(gè)經(jīng)典和重要的分支，所研究的問題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。 1857年，凱萊在計(jì)數(shù)烷的同分異構(gòu)物時(shí)，也發(fā)現(xiàn)了“樹”。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于 1736 年發(fā)表的“哥尼斯堡的七座橋”。河南城建學(xué)院 圖論及其應(yīng)用 主講老師：李德英 數(shù)學(xué)建模培訓(xùn)班 河南城建學(xué)院 你的獎(jiǎng)杯有多大 ， 就有多少的汗水和 淚水 ， 把獎(jiǎng)杯敲碎后 ， 里面就是你的 眼淚和血汗 ．．． 天道酬勤 河南城建學(xué)院 參考書： １ 、 高隨祥 《 圖