系列文章目錄

【管理運(yùn)籌學(xué)】第 7 章 | 圖與網(wǎng)絡(luò)分析（2，最小支撐樹問題）
【管理運(yùn)籌學(xué)】第 7 章 | 圖與網(wǎng)絡(luò)分析（3，最短路問題）
【管理運(yùn)籌學(xué)】第 7 章 | 圖與網(wǎng)絡(luò)分析（4，最大流問題）
【管理運(yùn)籌學(xué)】第 7 章 | 圖與網(wǎng)絡(luò)分析（5，最小費(fèi)用流問題及最小費(fèi)用最大流問題）

引言

按照正常進(jìn)度應(yīng)該學(xué)習(xí)動(dòng)態(tài)規(guī)劃了，但我想換換口味，而且動(dòng)態(tài)規(guī)劃聽說也有一定難度，還不一定會(huì)考。

先說說圖論的一些背景知識(shí)和發(fā)展情況吧。

圖論是幾十年來發(fā)展迅速、應(yīng)用廣泛的一個(gè)新的數(shù)學(xué)分支。它與數(shù)學(xué)的其他分支如矩陣論、概率論、數(shù)值分析等都有著密切地的聯(lián)系。事實(shí)上，圖論為任何一個(gè)包含了一種二元關(guān)系的系統(tǒng)提供了一個(gè)數(shù)學(xué)模型；也因?yàn)樗褂昧藞D解式的表示法，圖就具有了一種直觀的和符合美學(xué)的外形。

圖論的發(fā)展大致分為 3 個(gè)階段。

第一階段是從 18 世紀(jì)中葉到 19 世紀(jì)中葉，稱為萌芽期。起源是“七橋游戲”問題，如下圖所示。

問題是：能否從這四塊陸地中的任何一塊開始，通過每一座橋一次，并且僅一次，再次回到起點(diǎn)。

瑞士數(shù)學(xué)家歐拉（Euler）就這一問題發(fā)表了圖論的第一篇論文，證明了不存在七橋游戲問題的解，并且把這個(gè)問題（邊一筆畫問題）深入一步地一般化了，給出了一個(gè)圖存在歐拉圈的判定法則。

自從中國(guó)郵遞員問題（Chinese Postman Problem）提出來以后，歐拉問題才具有了強(qiáng)烈的實(shí)用價(jià)值。

中國(guó)郵遞員問題是這樣的：郵遞員在沿著郵路出發(fā)前，必須先從郵局取走他所應(yīng)分發(fā)的郵件。為了節(jié)約時(shí)間，每一位郵遞員都愿意以盡可能少的行程走完他所必須走的所有路線。用圖論的話來說，是指如何以盡可能少的行程遍歷郵路上所有各條街道后又回到他的出發(fā)點(diǎn)。

這類問題的第一篇論文是由中國(guó)數(shù)學(xué)家、山東師范大學(xué)的管梅谷教授在 1962 年提出的，因而得名“中國(guó)郵遞員問題”。

19 世紀(jì)中葉到 20 世紀(jì)中葉是圖論發(fā)展的第二階段，這一時(shí)期圖論大量問題涌現(xiàn)，其中以 Hamilton 問題和四色猜想最為著名。

1856 年英國(guó)數(shù)學(xué)家 William Hamilton 爵士發(fā)明了“繞行世界”的游戲。這個(gè)游戲用一個(gè)規(guī)則十二面體，它的 20 個(gè)頂點(diǎn)標(biāo)以 20 個(gè)城市的名字，要求游戲者找一條從某一城市出發(fā)的路線，它經(jīng)過每個(gè)城市恰好一次，并且最終回到出發(fā)點(diǎn)。

將正十二面體投影到平面上，就得到了下圖。

實(shí)際上 Hamilton 周游世界問題，是圖論中的點(diǎn)一筆畫問題，是要在上圖中找具有以下兩個(gè)特點(diǎn)的一個(gè)圈 $H$ ：1.圖中的每一個(gè)頂點(diǎn)都在圈 $H$ 中出現(xiàn)；2.在 $H$ 中頂點(diǎn)不重復(fù)出現(xiàn)（起終點(diǎn)不算重復(fù)）。這個(gè)圈稱為 Hamilton 圈。

四色猜想問題，即能否僅用 4 種顏色給地圖染色，使得相鄰國(guó)家有不同的顏色。用圖來描述就是：用點(diǎn)來表示國(guó)家，兩個(gè)國(guó)家若有公共邊界，就用一條邊將這兩點(diǎn)連接起來，于是，四色猜想問題就轉(zhuǎn)化為能否用四種顏色給平面的點(diǎn)染色，使得相鄰的點(diǎn)有不同顏色。

20 世紀(jì)中葉以后，是圖論發(fā)展的第三個(gè)階段，這一時(shí)期圖論經(jīng)過爆炸性的發(fā)展，成長(zhǎng)為一門獨(dú)立學(xué)科。其中最重要的是：出現(xiàn)了研究問題和解決問題的強(qiáng)有力工具：計(jì)算機(jī)。

一、圖與網(wǎng)絡(luò)的基本知識(shí)

1.1 圖與網(wǎng)絡(luò)的基本概念

1.1.1 圖的定義

自然界和人類社會(huì)中，大量的事物及事物之間的關(guān)系，常可以用圖形來描述。常將所研究對(duì)象看成一個(gè)點(diǎn)，用連線（帶箭頭或者不帶箭頭）表示對(duì)象之間的某種特定關(guān)系。為了區(qū)別起見，我們稱不帶箭頭連線稱為邊，帶箭頭的連線稱為弧。

定義 1.1 —— 一個(gè)圖是由一個(gè)非空集合 $V$ ，以及 $V$ 中元素的無序（或有序）點(diǎn)對(duì)組成的集合 $E$ （或 $A$）所組成。$V$ 中元素的無序點(diǎn)對(duì)所構(gòu)成的集合稱為邊集合 $E$ ，由點(diǎn)集合 $V$ 和邊集合 $E$ 構(gòu)成的圖稱為無向圖（簡(jiǎn)稱圖），記作 $G=(V,E)$ 。一條連接點(diǎn) $v_i,v_j$ 的邊 $e_{ij}$ ，記為 $e_{ij}=[v_i,v_j]$ 或 $e_{ij}=[v_j,v_i]$ 。$V$ 中元素的有序點(diǎn)對(duì)構(gòu)成的集合稱為弧集合 $A$ ，由點(diǎn)集合 $V$ 和弧集合 $A$ 構(gòu)成的圖為有向圖，記為 $D=(V,A)$ 。一條方向是從 $v_i$ 指向 $v_j$ 的弧記為 $a_{ij}=(v_i,v_j)$ 。

若圖 $G$ 中，某個(gè)邊的兩個(gè)端點(diǎn)相同，稱該邊為環(huán)，若兩個(gè)點(diǎn)之間有多于一條的邊，稱為多重邊。一個(gè)無環(huán)、無多重邊的圖稱為簡(jiǎn)單圖，無環(huán)但允許有多重邊的圖稱為多重圖。

圖 $G$ 或 $D$ 中的點(diǎn)數(shù)記為 $n=|V|$ ，邊（?。?shù)記為 $m=|E|(m=|A|)$ ，在不引起混亂的情況下，分別簡(jiǎn)記為 $n,m$ ，其中 $n$ 為圖的階，若 $n$ 為有限的，稱為有限階。

1.1.2 圖中相關(guān)術(shù)語(yǔ)

1. 端點(diǎn)。當(dāng) $e_{ij}=[v_i,v_j]$ 時(shí)，與邊 $e_{ij}$ 相連的頂點(diǎn)稱為邊 $e_{ij}$ 的端點(diǎn)。
2. 邊與點(diǎn)相關(guān)聯(lián)。當(dāng) $e_{ij}=[v_i,v_j]$ 時(shí)，$e_{ij}$ 與 $v_i,v_j$ 稱為邊頂相關(guān)聯(lián)。
3. 鄰點(diǎn)。
4. 鄰邊。
5. 環(huán)。只與一個(gè)頂點(diǎn)相關(guān)聯(lián)的邊稱為環(huán)。
6. 平行邊。具有相同的兩個(gè)端點(diǎn)的邊稱為平行邊。
7. 鄰域。與某點(diǎn)相鄰接的點(diǎn)的集合。
8. 次。以點(diǎn) $v_i$ 為端點(diǎn)的邊的數(shù)目稱為點(diǎn) $v_i$ 在 $G$ 中的次，記為：$d(v_i)$ 。
   如果有環(huán)，則按兩條邊記，即 $$d(v_i)=d_l(v_i)+2l(v_i)$$ 其中：$d_l(v_i)$ 是與 $v_i$ 相關(guān)聯(lián)的非環(huán)邊數(shù)，$l(v_i)$ 是與 $v_i$ 相關(guān)聯(lián)的環(huán)數(shù)。
9. 次序列。若 V = { v 1 , v 2 , … , v p } V=\{v_1,v_2,\dots,v_p\} V={v1?,v2?,…,vp?} ，則相對(duì)于每個(gè)點(diǎn)都有一個(gè)次，則可以得到一個(gè)次序列 $(d(v_1),d(v_2),\dots )$ 。

定理 1.1 —— 對(duì)于圖 $G=(V,E)$ ，其中 $|V|=n,|E|=m$ ，則有：$$\sum _{v\in V}d(v)=2m$$ 定理 1.2 —— 奇數(shù)次頂點(diǎn)的總數(shù)是偶數(shù)。

10. 懸點(diǎn)。次為 1 的點(diǎn)。
11. 懸邊。懸點(diǎn)關(guān)聯(lián)的邊。
12. 孤立點(diǎn)。次為 0 的點(diǎn)。
13. 鏈。
14. 初等鏈。鏈 $Q$ 中的頂點(diǎn)均不相同。
15. 簡(jiǎn)單鏈。鏈中邊都不相同。
16. 鏈的長(zhǎng)度。為所包含的邊數(shù)。
17. 圈。
18. 路。
19. 路徑。有向圖中路每個(gè)頂點(diǎn)均不相同稱為路徑。
20. 回路。路的第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)相同。

1.1.3 一些特殊圖類

1. 平凡圖。節(jié)點(diǎn)數(shù) $n=1$ ，邊數(shù) $m=0$ 的圖。
2. 零圖。邊數(shù) $m=0$ 。
3. 連通圖。圖中每對(duì)節(jié)點(diǎn)都有一條鏈（路）連接，稱這個(gè)圖是連通的。
4. 樹。無圈的連通圖。
5. 完備圖。任意兩個(gè)頂點(diǎn)之間恰有一條邊相關(guān)聯(lián)。
6. 二分圖。
7. 完全二分圖。
8. 正則圖。每個(gè)點(diǎn)的次數(shù)均相同。
9. 有向網(wǎng)絡(luò)。加權(quán)的有向圖。

1.1.4 圖的運(yùn)算

（1）子圖和支撐
子圖、支撐子圖都是圖 $G$ 的點(diǎn)或邊作刪除運(yùn)算得到的。子圖點(diǎn)和邊都是原圖的子集，支撐子圖點(diǎn)和原圖一樣，邊是原圖子集。

（2）圖的收縮運(yùn)算

（3）割集
常記為 $\Phi (X)$ ，如下圖中，若 X = { V 1 } X=\{V_1\} X={V1?} ，則割集為 $\Phi (X)=\{[v_1,v_2],[v_1,v_3],[v_1,v_4\}$ 。即用一條線去割，要求可以將 $X$ 完整割出來，這條線碰著的邊記為割集。

（4）圖的同構(gòu)
設(shè) $G_1,G_2$ 為兩個(gè)同階圖，若頂點(diǎn)集合 $V_1,V_2$ 以及邊集合 $E_1,E_2$ 之間在保持關(guān)聯(lián)性質(zhì)條件下一一對(duì)應(yīng)，則稱圖 $G_1,G_2$ 同構(gòu)。如下圖所示。

1.2 圖的矩陣表示

為了方便利用計(jì)算機(jī)識(shí)別圖的相關(guān)信息，我們通過矩陣表示法來表示一個(gè)圖，主要有鄰接矩陣、關(guān)聯(lián)矩陣、可達(dá)矩陣、權(quán)矩陣等。

1.2.1 鄰接矩陣

鄰接矩陣用于描述兩個(gè)頂點(diǎn)之間是否有邊（弧）相連。若兩點(diǎn)之間有邊（弧）相連，對(duì)應(yīng)矩陣元素為 1 ，否則對(duì)應(yīng)矩陣元素為 0 。

顯然，無向圖的鄰接矩陣是一個(gè)關(guān)于對(duì)角線對(duì)稱的矩陣。

1.2.2 可達(dá)矩陣

在有向圖中可達(dá)矩陣用于描述兩點(diǎn)之間是否有路相連，若有路相連，對(duì)應(yīng)矩陣元素為 1 ，否則為 0 。

1.2.3 關(guān)聯(lián)矩陣

有向圖的關(guān)聯(lián)矩陣也稱為頂點(diǎn)—邊關(guān)聯(lián)矩陣。其每一行表示一個(gè)點(diǎn) $v_i$ ，每一列表示一條弧 $a_j$ ，若 $v_i$ 是弧 $a_j$ 的起點(diǎn)，則對(duì)應(yīng)矩陣元素 $m_{ij}=1$ ；若為弧的終點(diǎn)，記為 -1 ，無關(guān)則記為 0 。

1.2.4 權(quán)矩陣

可以理解為鄰接矩陣的延伸，當(dāng)兩點(diǎn)之間存在邊或弧時(shí)，對(duì)應(yīng)矩陣元素為該邊或弧的權(quán)重；當(dāng)兩點(diǎn)之間無邊時(shí)，對(duì)應(yīng)元素為 $\infty$ ；權(quán)矩陣對(duì)角元素全為 0 。

寫在最后

這概念可是真的多，不過結(jié)合圖來理解就還好，后面我們就來說說圖論中的一些經(jīng)典問題。文章來源地址http://www.zghlxwxcb.cn/news/detail-699462.html

到了這里，關(guān)于【管理運(yùn)籌學(xué)】第 7 章 | 圖與網(wǎng)絡(luò)分析（1，圖論背景以及基本概念、術(shù)語(yǔ)、矩陣表示）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！