圖與網絡模型第1頁，課件共33頁，創作于2023年2月§1圖與網絡的基本概念一、圖的三要素

頂點無序的圖為無向圖。頂點有序的圖為有向圖。二、鏈

一個由點和邊的交替序列。三、回路(圈)若鏈的第一個點和最后一個點相同，則該路為回路(圈)。2第2頁，課件共33頁，創作于2023年2月§1圖與網絡的基本概念四、連通圖

對無向圖G，若任何兩個不同的點之間，至少存在一條鏈，則G為連通圖。五、子圖及生成子圖1．子圖設無向圖G=（V、E），若2．生成子圖3第3頁，課件共33頁，創作于2023年2月§1圖與網絡的基本概念六、賦權圖對一個無向圖G的每一條邊(Vi,Vj)，相應地有一個數Cij，則稱圖G為賦權圖，Cij稱為邊(Vi,Vj)上的權。七、網絡在賦權的有向圖D中指定一點，稱為發點，指定另一點稱為收點，其它點稱為中間點，并把D中的每一條弧的賦權數稱為弧的容量，D就稱為網絡。4第4頁，課件共33頁，創作于2023年2月§2最小生成樹問題一、樹的概念１、樹一個無圈的連通圖稱為樹。在自然科學和社會科學中有廣泛的應用。如組織結構、比賽圖等。２、生成樹若T是無向圖G的生成子圖，且T又是樹，稱T為G的生成樹３、最小生成樹(MinimumSpannirngTree)

就是指在一個賦權的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權數之和為最小。

5第5頁，課件共33頁，創作于2023年2月§2最小生成樹問題二、求解最小生成樹的破圈算法算法步驟：1、在給定的賦權的連通無向圖上任找一個圈。2、在所找的圈中去掉一個權數最大的邊（如果有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條）。3、如果所余下的圖已不包含圈，則計算結束，所余下的圖即為最小生成樹，否則返回第１步。6第6頁，課件共33頁，創作于2023年2月§2最小生成樹問題三、應用

例、某大學準備對其所屬的7個學院辦公室計算機聯網，這個網絡的可能聯通的途徑如下圖，圖中v1,…,v7

表示7個學院辦公室，請設計一個網絡能聯通7個學院辦公室，并使總的線路長度為最短(單位:百米)。v1331728541034v7v6v5v4v2v37第7頁，課件共33頁，創作于2023年2月§2最小生成樹問題

例用破圈算法求圖（a）中的一個最小生成樹v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)8第8頁，課件共33頁，創作于2023年2月作業:求下圖的最小樹V9V1V2V3V6V5V8V7V46758344239165479第9頁，課件共33頁，創作于2023年2月§3最短路問題一、最短路問題：對一個賦權的有向圖D(或無向圖)中指定的兩個點Vs和Vt找到一條從Vs

到Vt

的路，使得這條路上所有弧(或邊)的權數的總和最小，這條路被稱之為從Vs到Vt的最短路。在線路安排、管道鋪設、設備更新和廠區布局中有廣泛的應用。10第10頁，課件共33頁，創作于2023年2月§3最短路問題例1電信公司準備在甲、乙兩地沿路架設一條光纜線，問如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權數表示兩地間公路的長度（單位：公里）。

V1（甲地）15176244431065v2V7（乙地）v3v4v5v611第11頁，課件共33頁，創作于2023年2月§3最短路問題12第12頁，課件共33頁，創作于2023年2月三、基本方法有兩個方法１、Dijkstra法(1959提出適用：Cij≥0）解決兩指定點間的最短路或指定點到任意點的最短路。

Dijkstra，（1930年5月11日~2002年8月6日）荷蘭人。計算機科學家。13第13頁，課件共33頁，創作于2023年2月§3最短路問題Dijkstra算法：①從起點標號，標號有兩個內容（aj,bj），aj表示從起點到該點的最小距離，bj表示此最小距離鏈的緊前一個頂點的足標。起點的標號為（0、0）。②從已標號的頂點出發，找出與這些已標號的頂點緊鄰的所有頂點的距離，并選最小值進行標號。直到所有頂點都標號完為止。14第14頁，課件共33頁，創作于2023年2月§3最短路問題例２.求V１至各點的最短路6V４V2V３V５V６V７V１１０10203015829583215第15頁，課件共33頁，創作于2023年2月§3最短路問題例３.求V１至各點的最短路V４V2V３V５V６V７V１１０106203015829583216第16頁，課件共33頁，創作于2023年2月§3最短路問題

例4：求V１至各點的最短路V2８－55V1V317第17頁，課件共33頁，創作于2023年2月§3最短路問題2、逐次逼近法（適用某些Cij<0）解決指定點到任意點的最短路或兩指定點間最短路。算法：1．先賦予起點標號（0、0）及與起點鄰近點的標號（Cij、1），其它標號為（∞，1）2．檢查各頂點標號是否得到最小值，否則，逐個調整。18第18頁，課件共33頁，創作于2023年2月

例6.求

V１至各點的最短路§3最短路問題V1V2V4V6V3V53-434-2-25219第19頁，課件共33頁，創作于2023年2月§3最短路問題例7.求

V１至各點的最短路V1V2V4V6V3V53-434-6-25220第20頁，課件共33頁，創作于2023年2月§3最短路問題

循環，路長單調下降而趨向-∞，無結果。回路上的權值之和為正數或零，可求得結果。回路上的權值之和為負數時，此法失效。

21第21頁，課件共33頁，創作于2023年2月§3最短路問題四、應用舉例例７已知某地區的交通網絡如下圖所示,其中點代表居民小區,邊表示公路,問區中心醫院應建在哪個小區,可使離醫院最遠的小區居民就診時所走的路程最短。22第22頁，課件共33頁，創作于2023年2月V7V130302520V215V61518V4§3最短路問題V5v55v1v3v2v4V^v7602030203025181515V56020V323第23頁，課件共33頁，創作于2023年2月§3最短路問題小區號V1V2V3V4V5V6V7D(VI)V1030506393456093V2300203363153063V3502002050254050V4633320030183363V5936350300486393V6451525184801548V760304033631506324第24頁，課件共33頁，創作于2023年2月§4最大流問題

在交通運輸、物資供應中，經常會遇到人流、車流、信息流、物流、現金流，稱“網絡流理論”。二十世紀中葉以后，Ford和Fulkerson建立了網絡流理論。一、最大流問題：給一個帶收發點的網絡，其每條弧的賦權稱之為容量，在不超過每條弧的容量的前提下，求出從發點到收點的最大流量。

25第25頁，課件共33頁，創作于2023年2月§4最大流問題例1某石油公司擁有一個管道網絡，使用這個網絡可以把石油從采地運送到一些銷售點，這個網絡的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬加侖/小時。如果使用這個網絡系統從采地v1向銷地v7運送石油，問每小時能運送多少加侖石油？63522241263v1v2v7v4v3v6v526第26頁，課件共33頁，創作于2023年2月§4最大流問題

Ford—Fulkerson算法二、概念及原理1．可行流:滿足約束條件式o≤fij≤cij的fij稱為一組可行流。可行流總是存在的，如取所有fij=027第27頁，課件共33頁，創作于2023年2月§4最大流問題2．增值鏈：設fij是一組可行流，如果存在一條從V1到Vn的初等鏈，在這條鏈上所有的前向弧fij<cij，在所有的后向弧上所有的fij>0，則稱這條鏈是一條關于可行流fij的可擴充鏈。在所有前向弧上計算在所有后向弧上計算調整量28第28頁，課件共33頁，創作于2023年2月§4最大流問題新的可行流

在V1→Vn間增加了一個流量，直至找不到可擴充鏈為止，就得到了最大流。3．原理:在發點和收點之間是否存在增值鏈。29第29頁，課件共33頁，創作于2023年2月§4最大流問題三、計算（標號法）1．給出第1個可行流令2．尋找增值鏈，若無，則取得最大流。否則，確定調整量，將調整為一個更大的可行流，直到得到最大流為止。例2．求下圖的最大流．1246532315284430第30頁，課件共33頁，創作于2023年2月例3.求下圖的最大流．１257643325543432152§4最大流問題31