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