4. 圖與網絡模型及方法

圖論起源於18 世紀。第一篇圖論論文是瑞士數學家歐拉於1736 年發表的「哥尼斯堡的七座橋」。1847 年，克希霍夫爲了給出電網絡方程而引進了「樹」的概念。1857年，凱萊在計數烷 CnH2n+2 $C_n{H}_{2n+2}$的同分異構物時，也發現了「樹」。哈密爾頓於 1859 年提出「周遊世界」遊戲，用圖論的術語，就是如何找出一個連通圖中的生成圈、近幾十年來，由於計算機技術和科學的飛速發展，大大地促進了圖論研究和應用，圖論的理論和方法已經滲透到物理、化學、通訊科學、建築學、運籌學，生物遺傳學、心理學、經濟學、社會學等學科中。

圖論爲任何一個包含了一種二元關係的離散系統提供了一個數學模型，藉助於圖論的概念、理論和方法，可以對該模型求解。哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡有七座橋將普萊格爾河中的兩個島及島與河岸聯結起來，問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點。圖1 哥尼斯堡七橋問題當然可以通過試驗去嘗試解決這個問題，但該城居民的任何嘗試均未成功。歐拉爲了解決這個問題，採用了建立數學模型的方法。他將每一塊陸地用一個點來代替，將每一座橋用連接相應兩點的一條線來代替，從而得到一個有四個「點」，七條「線」的「圖」。問題成爲從任一點出發一筆畫出七條線再回到起點。歐拉考察了一般一筆畫的結構特點，給出了一筆畫的一個判定法則：這個圖是連通的，且每個點都與偶數線相關聯，將這個判定法則應用於七橋問題，得到了「不可能走通」的結果，不但徹底解決了這個問題，而且開創了圖論研究的先河。

4.1 圖的基本概念與數據結構

4.1.1 基本概念

直觀第講，對於平面上的n個點，把其中一些點對用曲線或者直線連接起來，不考慮點的位置與連線曲直長短，這樣形成的一個關係結構就是一個圖。記成 G=(V,E) $G=(V,E)$, V $V$是以上述點爲元素的頂點集, E $E$是以上述連線爲元素的邊集。

各條邊都加上方向的圖稱爲有向圖，否則稱爲無向圖。如果有的邊有方向，有的邊無方向，則稱爲混合圖。任兩頂點間最多有一條邊，且每條邊的兩個端點皆不重合的圖，稱爲簡單圖。如果圖的兩頂點之間有邊相連，則稱此兩頂點相鄰，每一對頂點都相鄰的圖稱爲完全圖，否則稱爲非完全圖。完全圖記爲 K|V| $K_{|V|}$。

若 V=X⋃Y,X⋂Y=∅ $V=X\bigcup Y,X\bigcap Y=\mathrm{\varnothing }$， |X|⋅|Y|≠0 $|X|\cdot |Y|\ne 0$ (這裏 |X| $|X|$表示頂點集 X $X$中元素的個數)，且 X $X$中無相鄰的頂點對， Y $Y$中亦然，則稱圖 G $G$爲二分圖；特別地，若對任意 u∈X $u\in X$， u $u$與 Y $Y$中每個頂點相鄰，則稱圖 G $G$爲完全二分圖，記爲 K|X|,|Y| $K_{|X|,|Y|}$。

設 v∈V $v\in V$是邊 e∈E $e\in E$的端點，則稱 v $v$與 e $e$關聯，與頂點 v $v$關聯的邊數稱爲該頂點的度，記爲 d(v) $d(v)$，度爲奇數的頂點稱爲奇頂點，度爲偶數的頂點稱爲偶頂點。可以證明 ∑v∈V(G)d(v)=2|E| $\underset{v\in V(G)}{\sum }d(v)=2|E|$,即所有頂點的度數之和爲邊數的2倍，且由此可以知道奇頂點的總數是偶數。

設 W=v0e1v1e2...ekvk $W=v_0{e}_1{v}_1{e}_2...e_k{v}_k$，其中 ei∈E,1≤i≤k,vj∈V,0≤j≤k $e_i\in E,1\le i\le k,v_j\in V,0\le j\le k$， ei $e_i$與 vi−1 $v_{i-1}$和 vi $v_i$關聯，稱 W $W$是圖 G $G$的一條道路， k $k$爲路長， v0 $v_0$爲起點， vk $v_k$爲終點；各邊相異的道路稱爲跡；各頂點相異的道路稱爲軌道。若 W $W$是一軌道，則可記爲 P(v0,vk) $P(v_0,v_k)$；起點與終點重合的道路稱爲迴路。起點與終點重合的軌道稱爲圈，即對軌道 P(v0,vk) $P(v_0,v_k)$，當 v0=vk $v_0=v_k$時稱爲一圈；圖中任兩頂點之間都存在道路的圖，稱爲連通圖。圖中含有所有頂點的軌道稱爲Hamilton軌，閉合的Hamilton軌道稱爲Hamilton圈；含有Hamilton圈的圖稱爲Hamilton圖。

稱兩定點 u,v $u,v$分別爲起點和終點的最短軌道之長爲頂點 u,v $u,v$的距離；在完全二分圖 K|X|,|Y| $K_{|X|,|Y|}$中， X $X$中兩頂點之間的距離爲偶數， X $X$中的頂點與 Y $Y$中的頂點的距離爲奇數。

賦權圖是指每條邊都有一個（或者多個）實數對應的圖，這個（些）實數稱爲這條邊的權（每條邊可以具有多個權）。賦權圖在實際問題中非常有用。根據不同的實際情況，權數的含義可以各不相同。例如，可用權數代表兩地之間的實際距離火車行車時間，也可用權數代表某工序所需的加工時間等。

4.1.2 圖與網絡的數據結構

這裏介紹計算機上用來描述圖與網絡的兩種主要表示方法：鄰接矩陣表示法和稀疏矩陣表示法。在下面數據結構的討論中，首先假設 G=(V,E) $G=(V,E)$是一個簡單無向圖，頂點集合 V=v1,...vn $V=v_1,...v_n$，邊集 E=e1,...em $E=e_1,...e_m$，記爲 |V|=n,|E|=m $|V|=n,|E|=m$。

1. 鄰接矩陣表示法:

鄰接矩陣是表示頂點之間相鄰關係的矩陣，鄰接矩陣記爲 W=(wij)n×n $W=(w_{ij}{)}_{n\times n}$，當 G $G$爲賦權圖時，有：

當 G $G$爲非賦權圖時，有：

採用鄰接矩陣表示圖，直觀方便，通過查看鄰接矩陣元素的值可以很容易地查找圖中任意兩個頂點 vi $v_i$和 vj $v_j$之間有無邊，以及邊上的權重。當圖的邊數 m $m$遠小於頂點數 n $n$時，鄰接矩陣表示法會造成很大的空間浪費。

2. 稀疏矩陣表示法:

稀疏矩陣是指矩陣中零元素很多，非零元素很少的矩陣。對於稀疏矩陣，只要存放非零元素的行標，列標，非零元素的值即可，可以按如下方式存儲：

（非零元素的行地址，非零元素的列地址），非零元素的值。

在Matlab中，無向圖和有向圖鄰接矩陣的使用上有很大差異。

對於有向圖，只要寫出鄰接矩陣，直接使用Matlab的sparse命令，就可以將鄰接矩陣轉化爲稀疏矩陣的表示方式。

對於無向圖，由於鄰接矩陣是對稱陣，Matlab只需使用鄰接矩陣的下三角元素，即Matlab只存儲鄰接矩陣下三角元素中的非零元素。

稀疏矩陣只是一種存儲格式。Matlab中，普通矩陣使用sparse命令變成稀疏矩陣，稀疏矩陣使用full命令變成普通矩陣。

4.2 最短路徑問題

4.2.1 兩個指定頂點之間的最短路徑

問題如下：給出了一個連接若干個城鎮的鐵路網絡，在這個網絡的兩個指定城鎮間，找一條最短鐵路線。

構造賦權圖 G=(V,E,W) $G=(V,E,\mathbf{\text{W}})$。其中，頂點集 V={v1,...vn} $V=\{v_1,...v_n\}$表示各個小城鎮； E $E$爲邊的集合；鄰接矩陣 W=(wij)n×n $\mathbf{\text{W}}=(w_{ij}{)}_{n\times n}$表示頂點 vi $v_i$和 vj $v_j$之間直通鐵路的距離，若頂點 vi $v_i$和 vj $v_j$之間無鐵路，則 wij=∞ $w_{ij}=\mathrm{\infty }$。問題就是求賦權圖 G $G$中指定的兩個頂點 u0 $u_0$和 v0 $v_0$之間具有最小權的路徑。這條路徑稱爲 u0 $u_0$和 v0 $v_0$之間的最短路徑，它的權稱爲 u0 $u_0$和 v0 $v_0$之間的距離，也可以被記爲 d(u0,v0) $d(u_0,v_0)$。

求最短路徑已有成熟的算法，如Dijkstra算法，其基本思想是按照距離 u0 $u_0$從近到遠爲順序，依次求得 u0 $u_0$到 G $G$的各個頂點的最短路徑，直到 v0 $v_0$(或者直至 G $G$的所有頂點)，算法結束。爲避免重複並保留每一步的計算信息，採用了標號算法。下面是該算法的僞碼描述。

（1）令 l(u0)=0 $l(u_0)=0$，對 v≠u0 $v\ne u_0$，令 l(v)=∞,S0={u0},i=0 $l(v)=\mathrm{\infty },S_0=\{u_0\},i=0$。

（2）