管理運(yùn)籌學(xué)（第五版）圖與網(wǎng)絡(luò)分析

圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本知識(shí)最短路問(wèn)題最大流問(wèn)題本章主要內(nèi)容：圖與網(wǎng)絡(luò)的基本知識(shí)圖論起源——哥尼斯堡七橋問(wèn)題問(wèn)題：一個(gè)散步者能否從任一塊陸地出發(fā)，走過(guò)七座橋，且每座橋只走過(guò)一次，最后回到出發(fā)點(diǎn)？結(jié)論：不能。每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)要均為偶數(shù)。BDACABCD一筆畫(huà)問(wèn)題圖與網(wǎng)絡(luò)的基本知識(shí)環(huán)球旅行問(wèn)題：圖與網(wǎng)絡(luò)的基本知識(shí)環(huán)球旅行問(wèn)題的解另一個(gè)著名的問(wèn)題:中國(guó)郵路問(wèn)題圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。圖的定義： 若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖G可以定義為點(diǎn)(頂點(diǎn))和邊的集合，記作：其中:V——點(diǎn)集E——邊集※

圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。圖與網(wǎng)絡(luò)的基本知識(shí)(v1)趙(v2)錢(qián)孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(qián)(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見(jiàn)圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示。圖與網(wǎng)絡(luò)的基本知識(shí)定義:圖中的點(diǎn)用v表示，邊用e表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5

端點(diǎn),關(guān)聯(lián)邊,相鄰若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6,e7,e8}，圖與網(wǎng)絡(luò)的基本知識(shí)邊數(shù)：m(G)=|E|=m頂點(diǎn)數(shù)：n(G)=|V|=n無(wú)向邊與無(wú)向圖：若圖中任一條邊的端點(diǎn)無(wú)序，即(vi,vj)與(vj,vi)是同一條邊，則稱它為無(wú)向邊，此時(shí)圖稱為無(wú)向圖。有向圖：若圖中邊(vi,vj)的端點(diǎn)是有序的，則稱它是有向邊（或弧），vi與vj分別稱為這條有向邊的始點(diǎn)和終點(diǎn)，相應(yīng)的圖稱為有向圖。有向圖無(wú)向圖圖與網(wǎng)絡(luò)的基本知識(shí)無(wú)向圖,有向圖

環(huán),多重邊,簡(jiǎn)單圖如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖。含多重邊的圖稱為多重圖。v3e7e4e8e5e6e1e2e3v1v2v4v5簡(jiǎn)單圖多重圖圖與網(wǎng)絡(luò)的基本知識(shí)環(huán)多重邊

完全圖圖與網(wǎng)絡(luò)的基本知識(shí)每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖稱為無(wú)向完全圖；有向完全圖是指每一對(duì)頂點(diǎn)間有且僅有一條有向邊的簡(jiǎn)單圖。完全圖頂點(diǎn)數(shù)n與邊數(shù)m間成立如下關(guān)系:m=n(n-1)/2

二部圖（偶圖）圖G=(V,E)的點(diǎn)集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=?,使得同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，稱這樣的圖為二部圖（偶圖）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明顯為二部圖，(b)也是二部圖，但不明顯，改畫(huà)為(c)時(shí)可以清楚看出。圖與網(wǎng)絡(luò)的基本知識(shí)

次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:

一個(gè)圖的次等于各點(diǎn)的次之和。圖與網(wǎng)絡(luò)的基本知識(shí)圖與網(wǎng)絡(luò)的基本知識(shí)v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3懸掛點(diǎn)孤立點(diǎn)懸掛邊偶點(diǎn)奇點(diǎn)圖與網(wǎng)絡(luò)的基本知識(shí)圖中頂點(diǎn)次的性質(zhì)定理1任何圖中頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。定理2任何圖中次為奇數(shù)的頂點(diǎn)必有偶數(shù)個(gè)。定義6在有向圖中，以頂點(diǎn)v為始點(diǎn)的邊數(shù)稱為頂點(diǎn)v的出次，記為d+(v)；以v為終點(diǎn)的邊數(shù)稱為v的入次，記為d-(v)。頂點(diǎn)v的出次與入次的和稱為點(diǎn)v的次。定義7圖G=(V,E),若E'是E的子集，若V'是V的子集，且E'中的邊僅與V'中的頂點(diǎn)相關(guān)聯(lián)，則稱G'=(V',E')為圖G的一個(gè)子圖，特別地，若V'=V,則稱G'為G的一個(gè)生成子圖（支撐子圖）。15例：下圖標(biāo)明了六個(gè)城市（A～F）之間的公路的公里數(shù)。為將部分公路改造成高速公路，使各個(gè)城市之間均可通達(dá)，至少要改造總計(jì)（1）公里的公路，這種總公里數(shù)最少的改造方案共有（2）個(gè)。（1）A.1000B.1300C.1600D.2000（2）A.1B.2C.3D.4答案1：B答案2：C

子圖，生成子圖(支撐子圖)圖G1={V1、E1}和圖G2={V2，E2}如果有稱G1是G2的一個(gè)子圖。若有，則稱G1是G2的一個(gè)生成子圖(支撐子圖)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G圖）圖與網(wǎng)絡(luò)的基本知識(shí)

網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖G＝（V，E），對(duì)G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量)等等。端點(diǎn)無(wú)序的賦權(quán)圖稱為無(wú)向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。①②③④⑤⑥910201571419256圖與網(wǎng)絡(luò)的基本知識(shí)

鏈，圈，連通圖定義8無(wú)向圖中一個(gè)點(diǎn)、邊交錯(cuò)的序列，序列中的第一個(gè)和最后一個(gè)元素都是點(diǎn)，若其中每條邊以序列中位于它之前和之后的點(diǎn)為端點(diǎn)，則稱這個(gè)點(diǎn)邊序列為圖中連接其第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)的稱為鏈。鏈中所含的邊數(shù)稱為鏈長(zhǎng)。圖與網(wǎng)絡(luò)的基本知識(shí)鏈，但只是簡(jiǎn)單鏈而非初等鏈簡(jiǎn)單鏈：沒(méi)有重復(fù)邊；初等鏈：既無(wú)重復(fù)邊也無(wú)重復(fù)點(diǎn)。對(duì)有向圖可類似定義鏈，如果各邊方向一致，則稱為道路。

鏈，圈，連通圖定義9若在無(wú)向圖中，一條鏈的第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)重合，則稱這條鏈為圈。只有重復(fù)點(diǎn)而無(wú)重復(fù)邊的圈為簡(jiǎn)單圈，既無(wú)重復(fù)點(diǎn)又無(wú)重復(fù)邊的圈為初等圈。圖與網(wǎng)絡(luò)的基本知識(shí)初等圈非簡(jiǎn)單的圈圖與網(wǎng)絡(luò)的基本知識(shí)有向圖無(wú)向圖道路鏈（或道路）回路圈（或回路）道路(邊的方向一致)

連通圖圖與網(wǎng)絡(luò)的基本知識(shí)定義10一個(gè)圖中任意兩點(diǎn)間至少有一條鏈相連，則稱此圖為連通圖。任何一個(gè)不連通圖總可以分為若干個(gè)連通子圖，每一個(gè)稱為原圖的一個(gè)分圖（連通分支）。連通圖非連通圖圖的基本概念與模型圖的基本性質(zhì)：定理1任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。定理2任何圖中，次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。證明：設(shè)V1和V2分別為圖G中奇點(diǎn)與偶點(diǎn)的集合。由定理1可得：2m為偶數(shù)，且偶點(diǎn)的次之和也為偶數(shù)，所以必為偶數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。歐拉回路定義13連通圖G中，若存在一條道路，經(jīng)過(guò)每邊一次且僅一次，則稱這條道路為歐拉道路。若存在一條回路經(jīng)過(guò)每邊一次也僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖（E圖）。定理3無(wú)向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無(wú)奇點(diǎn)歐拉回路推論1無(wú)向連通圖G為歐拉圖，當(dāng)且僅當(dāng)G的邊集可以劃分為若干個(gè)初等回路。推論2無(wú)向連通圖G中有歐拉道路，當(dāng)且僅當(dāng)G中恰好有兩個(gè)奇點(diǎn)。最短路問(wèn)題如何用最短的線路將三部電話連起來(lái)？此問(wèn)題可抽象為設(shè)△ABC為等邊三角形，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線者顯然是二邊之和（如AB∪AC）。ABC最短路問(wèn)題ABCP但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)P），連接4點(diǎn)的新網(wǎng)絡(luò)的最短路線為PA＋PB＋PC。最短新路徑之長(zhǎng)N比原來(lái)只連三點(diǎn)的最短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且穩(wěn)定性也更好。27B1B2B3B4B5B6B7B8B9B10A√√√√√√B√√√√C√√√√√D√√√E√√√F√√√√√

例：某學(xué)院10名博士生選修6門(mén)課程(A-F)的情況如下表(