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

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

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

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

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

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

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

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

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

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

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

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

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

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

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