【正文】 的邊稱為 有向弧 （簡(jiǎn)稱 弧 ） ,用 ai 表示 . 有向圖的各弧用邊對(duì)應(yīng)替換后所得的無(wú)向圖稱為該有向圖的 基礎(chǔ)圖 。 賦權(quán)圖中一條 路的權(quán) 稱為路長(zhǎng) 。 ? 如果圖 G包含一條 Hamilton圈，則稱 G是 Hamilton型 的 . 6. 賦權(quán)圖 對(duì)圖 G的每條邊 e，賦予一實(shí)數(shù) w(e),稱為邊 e的 權(quán) ，可得一 賦權(quán)圖（網(wǎng)絡(luò)） 。 ? 如果圖 G包含一條 Euler圈，則稱 G是 Euler型 的 . Hamilton 型（ Hamilton 圖） ? Hamilton路 是指包含 G的每個(gè)頂點(diǎn)的一條路。 Euler鏈：除了兩個(gè)頂點(diǎn)度數(shù)為奇數(shù) ,其余為偶數(shù) . Euler 型（ Euler 圖） ? 定理 設(shè) G是連通圖，則 G是 Euler 型的充要條件是 G沒(méi)有奇次數(shù)的頂點(diǎn)。 ? Euler鏈 是指過(guò)所有邊一次且恰好一次的鏈。 割點(diǎn) ：刪除掉這個(gè)點(diǎn)后圖 G不連通。 一個(gè)連通圖稱為一個(gè) 連通分支 。 不連通圖 （ 分離圖 ）至少有兩個(gè)連通分支。 ? 稱一個(gè)圈是 偶圈 （ 奇圈 ），如果它的圈長(zhǎng)是偶數(shù)（奇數(shù)）。 0 1 2 kW v v v v?5. 連通性 鏈、路 如果徑 W 的邊各不相同，則稱 W為一條 鏈 ， kvvd k ?),( 0如果 W 頂點(diǎn)互不相同，則稱 W 是一條 路 。 ? 在簡(jiǎn)單圖中，徑可由頂點(diǎn)序列表示。 定義圖 G1與 G2的 和 ，記為 ，是 G的一個(gè)子圖，其頂點(diǎn)集為 ,邊集為 若 G1與 G2是不相交的，則記 。 記 GF 表示以 E(G)\F 為邊集的 G的 支撐子圖 ，它是從 G中刪除 F 中的邊所得到的子圖。 如果 W僅含一個(gè)頂點(diǎn) v，則把 }{vG ? 簡(jiǎn)記為 vG?e1 e3 e2 G v3 v4 v5 v2 v1 e3 e2 v3 v4 v2 G[v2 ,v3 ,v4 ] G{v1 ,v5 } e1 e3 e2 v3 v4 v5 v2 v1 邊導(dǎo)出子圖 設(shè) F是圖 G的非空邊子集，以 F為邊集，以 F中邊的端點(diǎn)全體為頂點(diǎn)集所構(gòu)成的子圖稱為由 F導(dǎo)出的 G的子圖，簡(jiǎn)稱 G的 邊導(dǎo)出子圖 。 GH ? )()( GVHV ? 稱 H是 G的 支撐子圖（或 生成子圖 ） . 如果 ， e1 e3 e2 G v3 v4 v5 v2 v1 H1: 真子圖 v3 v5 v2 v1 H2:支撐子圖 e1 e3 e2 v3 v4 v5 v2 v1 頂點(diǎn)導(dǎo)出子圖 設(shè) W是圖 G的一個(gè)非空頂點(diǎn)子集 ,以 W為頂點(diǎn)集，以二端點(diǎn)均在 W中的 邊的全體 為邊集的子圖稱為由 W導(dǎo)出的 G的子圖，簡(jiǎn)稱 導(dǎo)出子圖 ，記為 G[W]。 度為 1的點(diǎn)稱為 懸掛點(diǎn) , 連結(jié)懸掛點(diǎn)的邊稱為 懸掛邊 . 度為 0的點(diǎn)稱為 孤立點(diǎn) 。 戊 甲 乙 丙 丁 工人 工作 D C B A 完全二分圖 K3,3 完全二分圖是具有二分劃 (X,Y)的二分圖，并且 X的每個(gè)頂點(diǎn)與 Y的每個(gè)頂點(diǎn)都相連。 E） 二分圖是一個(gè)簡(jiǎn)單圖，其頂點(diǎn)集合可分劃成兩個(gè)子集 X與 Y，使得每條邊的一個(gè)端點(diǎn)在 X，另一個(gè)端點(diǎn)在 Y。 只有一個(gè)頂點(diǎn)的圖稱為 平凡圖 ； 邊集是空集的圖稱為 空?qǐng)D 。 連接同一對(duì)頂點(diǎn)的多條邊稱為 多重邊 。例如 4e1e2e3e5e6e1v2v3v4v4e1e2e3e5e6e1v2v3v 4v有時(shí)也用 m(G)=|E| 表示圖 G 中的 邊數(shù) ， 用 n(G)=|V| 表示圖 G 中的 頂點(diǎn)個(gè)數(shù) ，簡(jiǎn)記為 m, n. 圖 G 中的點(diǎn)數(shù)記為 p(G)，邊數(shù)記為 q(G) . 在不引起混淆的情況下，簡(jiǎn)記為 p, q. 此時(shí)，圖 G 可以表示為 G = ( p, q ). 平面圖 一個(gè)圖稱為 平面圖 ，如它有一個(gè)平面圖形，使得邊與邊僅在頂點(diǎn)相交。 我們常常把一個(gè)圖的圖形當(dāng)作這個(gè)抽象圖自身 . 并稱圖形的點(diǎn)為 頂點(diǎn) ,圖形的線為 邊 . 圖論中大多數(shù)概念是根據(jù)圖的表示形式提出的，例如：頂點(diǎn)、邊、多重邊、環(huán)、路、圈、樹(shù)等。 V(G)中的元素 vi 稱為 頂點(diǎn) ,E(G)中的元素 ek 稱為 邊 . 一個(gè)圖習(xí)慣 記作 G=(V, E). 當(dāng) V, E為有限集合時(shí)， G稱為 有限圖 ，否則，稱為無(wú)限圖 . 我們只討論有限圖 . 一、基本概念 １ .圖 設(shè) G是一個(gè)圖， G=(V(G),E(G))， ( ) , , ( ) ,e E G u v V G??則稱 e 連接 u和 v，稱 u和 v是 e的 端點(diǎn) . 若 稱端點(diǎn) u， v與邊 e是 關(guān)聯(lián) 的， 稱兩個(gè)頂點(diǎn) u， v是 鄰接（相鄰） 的 . 兩條邊 e, e1有公共端點(diǎn) v，則稱 e, e1相鄰 . 一個(gè)圖可用一個(gè)幾何圖形表示 ,稱為圖的 幾何實(shí)現(xiàn) ，其中每個(gè)頂點(diǎn)用點(diǎn)表示，每條邊用連接端點(diǎn)的線表示。 ?應(yīng)用領(lǐng)域：物理學(xué)、化學(xué)、控制論、信息論、管理科學(xué)、通信系統(tǒng)、交通運(yùn)輸系統(tǒng)、建筑、計(jì)算機(jī)科學(xué)、生產(chǎn)工藝流程以及軍事后勤保障系統(tǒng)等的問(wèn)題常用圖論模型來(lái)描述。 ?隨著電子計(jì)算機(jī)的蓬勃發(fā)展，圖論不僅得到了迅速發(fā)展，而且應(yīng)用非常廣泛。 圖的理論和方法 ，就是從形形色色的具體的圖以及與它們相關(guān)的實(shí)際問(wèn)題中，抽象出共同性的東西，找出其規(guī)律、性質(zhì)、方法，再應(yīng)用到解決實(shí)際問(wèn)題中去。這里只關(guān)心圖中有多少個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間有無(wú)連線，至于連線的方式是直線還是曲線，點(diǎn)與點(diǎn)的相對(duì)位置如何，都是無(wú)關(guān)緊要的。 圖是反映對(duì)象之間關(guān)系的一種工具。 如公路或鐵路交通圖、管網(wǎng)圖、通訊聯(lián)絡(luò)圖等。 圖 ：點(diǎn)及邊（或?。┙M成。 對(duì)稱關(guān)系：橋、道路、邊界； 用不帶箭頭的連線表示，稱為 邊 。 例： 有甲、乙、丙、丁、戊五個(gè)球隊(duì)，各隊(duì)之間比賽 情況如表： 甲 乙 丙 丁 戊 甲 勝 負(fù) 勝 勝 乙 負(fù) 勝 丙 勝 負(fù) 勝 丁 負(fù) 負(fù) 負(fù) 戊 負(fù) 勝 點(diǎn)：球隊(duì)； 連線：兩個(gè)球隊(duì)之間比賽過(guò)，如甲勝乙，用 v1 v2表示。 1962年，由我國(guó)數(shù)學(xué)家管梅谷提出，國(guó)際上稱為 中國(guó)郵遞員問(wèn)題 。如何走路線最短。 例：中國(guó)郵路問(wèn)題 一個(gè)郵遞員送信，要走完他所負(fù)責(zé)的全部街道分送信件，最后返回郵局。 問(wèn)題 ：如何判斷一個(gè)圖是否具有這樣的性質(zhì)。 例： Hamilton圖 游戲：用正十二面體上 20個(gè)頂點(diǎn)表示 20個(gè)城市，要求參加游戲者沿著各邊行走，走遍每一個(gè)城市且僅走一次，最后回到出發(fā)城市。 公元 1852年，格里斯發(fā)現(xiàn)無(wú)論多么復(fù)雜的地圖，只要用四種顏色就能將相鄰的區(qū)域區(qū)分開(kāi)來(lái)，這就是所謂“四色猜想”。 點(diǎn)：國(guó)家； 邊：兩個(gè)國(guó)家有公共邊界。第十章 圖論與網(wǎng)絡(luò)優(yōu)化 1 圖的基本概念 2 最小樹(shù)問(wèn)題 3 最短路問(wèn)題 4 網(wǎng)絡(luò)最大流問(wèn)題 5 最小費(fèi)用最大流問(wèn)題 一 些 問(wèn) 題 圖論中著名問(wèn)題 . 1736年，圖論的創(chuàng)始人 Euler巧妙地將此問(wèn)題化為圖的不重復(fù) 一筆畫(huà)問(wèn)題 ，并證明了該問(wèn)題不存在肯定回答，發(fā)表了第一篇論文 . 例：七橋問(wèn)題 A B C D 問(wèn)題：一個(gè)散步者能否走過(guò)七座橋，且每座橋只走 過(guò)一次，最后回到出發(fā)點(diǎn)。 例：四色猜想 能否用四種顏色給地圖染色，使相鄰的國(guó)家有不同的顏色。 問(wèn)題： 能否用四種顏色給平面圖的點(diǎn)染色，使有公共邊的點(diǎn)有不同的顏色。 直到公元 1976年，才由美國(guó)數(shù)學(xué)家同時(shí)操作三臺(tái)超大型汁算機(jī)作了近 200億個(gè)邏輯判斷，花費(fèi) 1200個(gè)機(jī)時(shí)，才取得了“四色猜想”的證明。 公元 1859年，哈密爾頓(Hamilton)在給朋友格拉伍斯（ Grares）的信中提出了這個(gè)游戲。如果有，這樣的行走路線如何確定。郵遞員都會(huì)本能地以盡可能少的行程完成送信任務(wù)。 點(diǎn)：路口； 邊：兩路口之間道路，第 i條道路長(zhǎng) ei。 問(wèn)題 ：求一個(gè)圈，過(guò)每邊至少一次，并使圈的長(zhǎng)度最 短。 v1 v2 v3 v4 v5 點(diǎn) ：研究對(duì)象（陸地、路口、國(guó)家、球隊(duì)）； 點(diǎn)間連線：對(duì)象之間的特定關(guān)系（陸地間有橋、路 口之間道路、兩國(guó)邊界、兩球隊(duì)比賽及 結(jié)果 )。 非對(duì)稱關(guān)系：甲隊(duì)勝乙隊(duì)，用帶箭頭的連線表示， 稱為 弧 。 實(shí)際生活中，人們經(jīng)常用“圖”來(lái)表示一些對(duì)象以及這些對(duì)象之間的特定關(guān)系。 對(duì)所要研究的問(wèn)題確定具體對(duì)象及這些對(duì)象間的性質(zhì)關(guān)系，并用圖的形式表示出來(lái)，這就是對(duì)所研究原問(wèn)題建立的模型。 這里所研究的圖與平面幾何中的圖不同。 是組合意義下的圖。 ?圖論 (Graph Theory)是運(yùn)籌學(xué)中的一個(gè)重要分支，主要研究具有某種 二元關(guān)系 的 離散系統(tǒng) 的組合結(jié)構(gòu)和性質(zhì)。它直觀清晰，使用方便，易于掌握。 ?網(wǎng)絡(luò)規(guī)劃是圖論與線性規(guī)劃的交叉學(xué)科 ,具有廣泛的應(yīng)用背景，比如，最短路問(wèn)題、最小樹(shù)問(wèn)題、最大流問(wèn)題、最優(yōu)匹配問(wèn)題等 . 圖的基本概念 一個(gè) 圖 (Graph) 定義為三元有序組 G=(V(G), E(G), ?G )， V(G)是圖的 頂點(diǎn)集合 ， E(G)是圖的 邊集合 ， ?G稱為 頂點(diǎn) 與 邊 之間的 關(guān)聯(lián)函數(shù) 。圖的幾何實(shí)現(xiàn)有助與我們直觀的了解圖的許多性質(zhì) . ( , )e u v?u v e w e1 e u v?或設(shè) G是一個(gè)圖， ( , )G V E?1 2 3( ) { , , }V G v v v?1 2 3 4 5( ) { , , , , }E G e e e e e?1 1 2e v v?2 1 2e v v?3 1 3e v v?4 2 3e v v?5 3 3e v v?G的幾何實(shí)現(xiàn) 其中： 1e2e3e4e5e1v2v3v例 說(shuō)明 一個(gè)圖的幾何實(shí)現(xiàn)并不是唯一的；表示頂點(diǎn)的點(diǎn)和表示邊的線的相對(duì)位置并不重要，重要的是圖形描繪出 邊與頂點(diǎn)之間保持的相互關(guān)系 。 在一個(gè)圖的幾何實(shí)現(xiàn)中，兩條邊的交點(diǎn)可能不是圖的頂點(diǎn)。下圖就是一個(gè)平面圖： 4e1e2e3e5e6e1v2v3v 4v非平面圖 環(huán)、多重邊 端點(diǎn)重合為一點(diǎn)的邊稱為 環(huán) 。 1e2e3e4e5e1v2v3v簡(jiǎn)單圖 一個(gè)圖稱為 簡(jiǎn)單圖 ,如果它既沒(méi)有環(huán)也沒(méi)有多重邊 . 含有多重邊的圖稱為 多重圖 . 我們只討論有限簡(jiǎn)單圖， 即頂點(diǎn)集與邊集都是有限的圖。 2e3e4e5e 7e1v2v3v4v完全圖 K n 完全圖是每一對(duì)不同頂點(diǎn)都恰有一邊的簡(jiǎn)單圖； 具有 n 個(gè)頂點(diǎn)的完全圖記為 K n. K5 2 ( 1 )| ( ) |2 2nnn nnE K C ?? ?? ? ?????二分圖（ X, Y。 (X,Y)也稱為圖的 二分劃 。完全二分圖記為 Km,n X: Y: 特殊圖例 都是 極小 的 非平面圖 . K5 K3,3 （次） 3)( 2 ?vd4)( 1 ?vd3)( 3 ?vd 4)( 4 ?vd稱度為奇數(shù)的頂點(diǎn)為 奇點(diǎn) ； 稱度為偶數(shù)的頂點(diǎn)為 偶點(diǎn) . 設(shè) G是一個(gè)圖， G=(V(G), E(G), ?G)，定義圖 G的頂點(diǎn) v 的度 為與頂點(diǎn) v相關(guān)聯(lián)的邊數(shù)，記作 d(v). 2e3e4e5e6e7e1v2v3v4v1e定理 設(shè) G是一個(gè)圖，則 ()( ) 2v V Gd v q???推論 ：圖中奇點(diǎn)的數(shù)目為偶數(shù)。 2e3e4e5e6e7e1v2v3v4v1e5v8e6v 有兩個(gè)圖 G和 H，如果 )()( GVHV ?)()( GEHE ?稱圖 H是圖 G的 子圖 ，記為 GH ?GH ?GH ?若 且 稱 H是 G的 真子圖 。 導(dǎo)出子圖 G[V W]記為 GW，即 ]\)([( WGVGWG ??它是從 G中刪除 W中頂點(diǎn)以及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖。記為 G[F]。 }{ eGeG ???如 F={ e }，則記 e1 e3 e2 G v3 v4 v5 v2 v1 G[e1 ,e2 ,e3 ]