【正文】 第五章 網(wǎng)絡分析模型 167。 圖論基礎 167。 網(wǎng)絡分析模型 167。 最短路徑分析 167。 最佳路徑分析 167。 資源分配 167。 流分析 167。 圖論基礎（ 1） 一、圖 圖的概念 圖 :一個圖 G是指一個有序三元組（ V（ G）， E（ G）， Ψ G），其中 V（ G）是非空的頂點集， E（ G）是邊集， Ψ G是關連函數(shù)，它使 G的每條邊對應于 G的無序頂點對（不必相異）。 邊 :E中的每個頂點對（ u,v）稱為 G的邊，記為 e =（ u,v）或簡記為 e = uv，稱 u，v是邊 e的 端點 ，且稱 u和 v是 鄰接的頂點 。 孤立點 :沒有邊相鄰的頂點。 一條邊的端點稱為 與這條邊關聯(lián) ，若兩條不同的邊與一個公共的端點關聯(lián)，則稱這兩條邊是鄰接的 。 167。 圖論基礎（ 2） 若連結(jié)兩個頂點有不止一條邊，這些邊稱為 多重邊 。端點重合為一點的邊稱為 環(huán) 。 簡單圖 :沒有環(huán)也沒有多重邊的圖。 有限圖 ：一個圖中頂點集及邊集都是有限集。 （ u,v） 空圖 ：沒有邊的圖，記為 Φ 。 （ p,q）圖 ： 一個有 p個頂點和 q條邊的圖。 完全圖 ： 每一個不同的頂點均有邊相連的 簡單圖 。有 n個頂點的完全圖記作 Kn。 子圖 ：所有的頂點和邊都屬于 G的圖稱為 G的子圖。 生成子圖 ： 含有 G的所有頂點的子圖稱為 G的生成子圖。 167。 圖論基礎（ 3） 頂點的度 :G的頂點 v的度 d(v)是指 G中與 v關聯(lián)的邊的數(shù)目，每個環(huán)算作兩條邊。 設 G是一個（ p,q）圖，那么 G的各個頂點度的和是邊數(shù)的二倍，即 正則圖 ：如果圖 G的所有頂點的度均相等，則稱為正則的。頂點的度均為 r的正則圖，稱為 r度正則的 。 一個 0度正則的圖根本沒有邊。只有一條邊兩個頂點的圖是 1度正則的。完全圖是正則的。 路與連通性 路徑 :G的一條途徑是指一個有限非空序列 μ=v 0e1v1e2v2… envn,它的項 交替地為頂點和邊 ，使得對 1?i?n,e i的端點是 vi1和 vi。 稱 μ 是從v0到 vn的一條途徑。 這條路徑連接 v0和 vn，也可記作 v0v1… vn1vn，有時也稱它為（ v0, vn）路徑。如果 v0=vn，它稱為 閉合的 ，否則稱為 開的 。路徑中 邊的數(shù)目 稱為 路徑的長 。 ? ?? ? qvdGVv ii2???167。 圖論基礎（ 4） 鏈 :設 μ=v 0e1v1e2v2… envn是路徑，若路徑 μ 的邊e1,e2,… ,en均不同，則 μ 稱為鏈。 路 :若路徑的所有頂點都不同 (從而所有的邊必然不同 )，它稱為路。用 Pn記由一條有 n個頂點的路構成的一個圖。 回路 :一條閉合的路，也稱為 圈 。用Ｃ n記由一條有n個頂點的回路構成的一個圖。若 n為奇數(shù)，則Ｃ n稱為奇回路，若 n為偶數(shù)，則Ｃ n稱為偶回路。 連通 ：如果在 G中存在 (u,v)路。則 G的兩個頂點u和 v稱為連通的 。 連通圖 ：一個圖的每一對頂點都有一條路連接。 連通支 ： G的一個最大的連通子圖稱為一個連通支。簡稱為 G的一個支。 頂點距離 ：若在 G中頂點 u和 v是連通的，則 u和 v間的最短 (u,v)路的長稱為 u和 v間的距離，記為 d(u,v)。若不存在連接 u和 v的路，則記 d(u,v)=∞ 。 167。 圖論基礎（ 5） 圖的運算 設 G1和 G2是沒有孤立點的圖。 并 ：由 G1和 G2中的所有的邊組成的圖，記作 。 交 ：由 G1和 G2中的公共邊組成的圖，記作 。 差 ：由 G1中去掉 G2的邊所得到的圖稱為 G1和 G2的差，記作 。 環(huán)和 ：在 G1和 G2的并中去掉 G1和 G2的交得到的圖稱為 G1和 G2的環(huán)和，記作 。 環(huán)和運算滿足 交換律 和 結(jié)合律 ： 21 GG ?1221 GGGG ???? ? ? ? 321321 GGGGGG ?????21 GG ?21 GG ?21 GG ?167。 圖論基礎（ 6） 二、樹 基本概念 樹 :一個連通的無回路的圖。 林 :每個支都是樹的分離圖稱為林。 定理 ：設 T是一個（ p,q）圖，若Ｔ是一棵樹，則 q = p1。 定理 ：設 T是一棵樹。若在 T中的任何兩個不鄰接的頂點連一條邊 e，則Ｔ＋ e恰有一條回路。 定理 ：設Ｇ是一個（ p,q）圖，若Ｇ是連通的，且 q = p1，則Ｇ是一棵樹。 割邊 ：如果去掉圖的一條邊后，剩下的圖的支比原圖增加，則稱這樣的邊為割邊，或稱為 橋 。 167。 圖論基礎（ 7） 割邊 ： 如果去掉圖的一條邊后，剩下的圖的支比原圖增加，則稱這樣的邊為割邊，或稱為 橋 。 記 W(G)為圖 G不連通子圖的數(shù)目，則 G的割邊是指使得W(Ge)W(G)的邊 e。 167。 圖論基礎（ 8） 生成樹 生成樹 :若 T是連通圖 G的一個生成子圖而且是一棵樹 ,則稱 T是 G的一棵生成樹（支撐樹）。 T中的邊稱為 樹枝 ，屬于 G而不屬于 T中的邊稱為 弦 。 生成林 :若 G為分離圖，則稱 T為生成林。 定理 ：圖 G是生成樹的充要條件為 G連通。 定理 ： T是連通（ p,q）圖Ｇ的一棵生成樹的充要條件是 T為 G的有 p1條邊的連通生成子圖。 求一個連通圖 G的生成樹的主要方法有： 避回路法 ： 任取圖 G的一條邊 e1，再取一條邊 e2 ， e2和 e1不構成回路；然后再取一條邊 e3 ， e3和 e1 e2不構成回路。如此下去，最后得到的不含回路的連通生成子圖就是 G的一棵生成樹。 破回路法 ： 在 G中任取一回路，去掉其中的一條邊，然后取一條回路，再去掉這個回路中的一條邊。如此繼續(xù)下去，最后得到的連通的無回路的生成子圖就是 G的一棵生成樹。 167。 圖論基礎（ 9） 三、最短路徑和最小生成樹 最短路徑 賦權圖 :若圖 G的每一條邊（ vi,vj）相應的有一個數(shù) l（ vi,vj）（或簡記為 lij） ,稱此數(shù)為該邊的 權 ，則圖 G為賦權圖。 設 H是賦權圖 G的子圖， H的權是它的每條邊上的權的和。 最短路徑問題 :在所有的（ vi,vj）路中尋求權為最小的路。其中， vi,vj是賦權圖 G中給定的頂點， vi稱為起點， vj稱為終點。從 vi到 vj的最短路徑的權記作 d（ vi,vj）。 最短路徑通常研究兩類問題： 第一類問題 ：從一個始點到一個終點的最短路徑。 第二類問題 ：求賦權圖中任意兩頂點間的最短路徑。 167。 圖論基礎（ 10） 最小生成樹問題（ MST） 最小生成樹問題 :在賦權網(wǎng)絡 N中，求解權數(shù)總和最小的生成樹。即在連通網(wǎng)絡圖 N =（ N,E,W） 中尋求 T =（ V,Er）并滿足 連通賦權圖網(wǎng)絡中一顆生成樹為最小生成樹的充要條件是： 定理 ：生成樹 T是賦權網(wǎng)絡 N中的一棵最小權生成樹，其充要條件是不存在另一棵與 T距離為 l的生成樹，其總權小于 T的總權數(shù)。 定理 ：令 {(U1,ET1),(U2,ET2)… (Uk,ETk)}是網(wǎng)絡 N =（ V,E,W）的一個生成林。令邊是僅有一端為 U1中頂點的各條邊的最短邊，則在包含 中