【天津大學】《運籌學》（精品課） P30 - 30. 圖的基本概念 教學錄像

同學們好 今天我們一起來學習第三章圖與網絡分析 圖論是應用十分廣泛的暈圖學的一個重要的分支 我們這一章的結構是這樣來展開的 首先介紹圖的基本概念 在學習完圖的基本概念以後 我們就要進行一系列的網絡分析內容的學習 這其中包括最小支撐數問題 最短路問題 網絡最大流問題 以及工程網絡計劃 那麼所有這些問題 都是體現了暈圖學的一個特點 最優化 在此我們先來看一下圖論的起源問題 非常著名的一個問題 哥尼斯堡橋問題 哥尼斯堡是位於17、18世紀東普魯市的一個城鎮 有一個河流叫普雷根爾河穿過這個城鎮 把城鎮翻成了河的兩岸AB 以及河中還有兩個島嶼CD 那麼這些陸地之間有若干座橋相連 一共有七座橋 比如說A和C之間有兩座橋 CD之間有一座橋相連 那麼當時居住在這個城鎮的人們都熱衷於尋找這樣一個問題是否存在答案 就是一個散步者能否從任何一塊陸地出發 走過這七座橋 每座橋只走一次 最後再回到出發點 也就是說是否存在這樣的線路 人們經過幾代的追尋都沒有找到這個問題最終的答案 後來就求助於當時著名的數學家歐拉 那麼歐拉在1736年發表了圖論的第一篇論文 成功地解決了這個著名的哥尼斯堡橋問題 那麼歐拉是怎麼想的呢 實際上我們也可以事先自己想一想 歐拉是對這個問題做了一個簡單的處理 把這樣一個實際問題轉換爲一個圖形 具體的考慮是這樣的 首先這個問題是不是存在答案 也就是說是不是存在這樣的線路 它跟陸地 島嶼的大小形狀沒有任何關係 於是陸地和島嶼就都可以抽象成一個點來表示 其次呢 那麼這個問題是不是存在答案 它跟橋樑的長度 寬度 形狀也都沒有任何關係 那麼這樣的話 每一座橋樑都可以用一條線來表示 於是這樣一個實際問題就轉化爲這樣一個 由點和線組成的圖形 並且我們知道如何在這個圖形中尋找一種特殊的線路 那麼經歷所有的邊 並且再回到出發點 這樣一個問題 那麼這個問題呢 也就是我們現在大夥所熟知的一筆畫問題 那麼歐拉呢 不僅做了這樣一種簡單的處理 而且呢 給了一個判定定理 這個定理非常的好用 它的主要結論可以這麼來描述 就是說這個問題要想要存在答案的話 要求每個節點關聯的邊數 必須都得是偶數 那我們看一看這個圖形 每個節點的關聯的邊數恰恰都是奇數 也就是說不符合這個定義的條件 所以也就不存在答案 那麼這就是古典圖論中非常著名的一個問題 那麼隨着科學技術發展 尤其是信息技術的發展 到了二十世紀中後葉 圖論的理論得到進一步的發展 將龐大複雜的工程系統和管理問題用圖來描述 可以解決很多工程設計和管理決策的最優化問題 例如要完成工程任務 它時間最少 距離最短 費用最省等等 所以圖論的方法在數學 工程技術 管理決策等各個方面得到越來越廣泛的重視 那麼接下來呢 我們將要介紹圖的一些基本概念 3.1節圖的基本概念 在這些基本概念的基礎上呢 我們才能進行後面的網絡分析 首先來看 什麼叫圖 從剛纔的根麗斯堡橋問題 我們可以看到圖 由兩部分來組成 點和邊 那麼我們就可以把這個圖記作 J等於位E 那具體的這個位和E 表示什麼呢 表示的是節點集合和邊集 那麼在這兒 同學們要注意了 節點集合 這個集合呢 我們用大寫的字母V來表示 而它內部的每一個元素 也就是說每一個節點 用小寫的字母來表示 假設一共有N個節點 同樣 這個邊集這個集合呢 也用大寫字母來表示 而邊 每一條具體的邊呢 都用小寫字母來表示 那麼在應用圖論 來解決實際問題的時候 我們這個節點和邊 往往都能代表 一定的具體的含義 一般的來說 這個節點 往往表示被研究的對象 而邊呢 表示研究對象之間的 一種特定的關係 好 這是圖的基本概念 接下來 我們對圖進行簡單的分類 在實際應用圖 來解決問題的過程中 根據問題的需要 有的時候 每一條邊 可能是用一個無序的 節點對來表示 那麼這種圖呢 就叫無向圖 那麼有的時候 節點對之間 描述的邊 必須是有序的 也稱作有向邊 那麼由有序邊 組成的圖形呢 叫有向圖 在這兒我們要注意一下 在無向圖裏邊 這個邊集呢 我們還記得 有向圖裏邊 有的時候 這個邊集呢 爲了跟無向圖做區別呢 也習慣上記作A 進一步的我們要注意 在用節點對來 表示邊的時候 那麼無向邊呢 用中括號來表示 而有向邊呢 用圓括號來表示 這也是爲了區別起見 下面我們具體的 來看幾個例子 例一 像哥尼斯堡橋問題 它當時這個圖形 是一個無向圖 再來看一個有向圖的例子 有五個球隊進行比賽 如果僅僅用無向圖來描述 這個球隊的比賽關係的話 可能只能表示 或者只能描述 哪些球隊進行了比賽 如果想進一步地描述 哪個球隊贏了另外一支球隊 那這時候就必須得用 這種帶箭頭的 有向邊來表示了 從而形成一個有向圖形 這是一個有向圖的例子 下面我們繼續來看 相關的一些概念 下面的概念 就基於剛纔 我們對圖形的分類 分成無向圖和有向圖 分別地來進行定義 首先來看無向圖情形 有鏈和圈的概念 什麼是鏈呢 所謂鏈非常形象 就實際上是一條鏈子 具體地來說 就是由點和邊來交錯的序列 我們具體地來看一下 這個公式 這個點邊交錯序列 位一 義一 位二 義二等等 一直到義開減一 位開 如果滿足這樣的關係 義i等於 位i到位i加一 什麼意思呢 也就是說 這些點和邊都連接到一塊 一個節點一條邊 又一個節點 又一條邊 首尾相接 這樣就形成了一條鏈 具體地我們來看一個這樣的圖形 請同學們跟着這個動畫演示一塊來看一下 比如說我從位一 想要找一條 到位四的鏈 那麼可以從位一 經過 位一位二這條邊到達位二 然後呢 再經過位二位三這條邊 到達位三 再經過位三到位四這條邊 到達位四 這就形成了 連接位一和位四 之間的一條鏈 當然了 位一到位四之間還有別的鏈 比如說 位一可以走上面到位五 最後到達位四 也可以 位一直接到達位四 位一經過位三到達位四 這都是不同的 連接位一和位四的鏈 那麼有一種特殊的鏈 叫做圈 特殊在哪裏呢 就是起點等於終點的鏈 也就是說 咱們拿剛纔的圖形爲例 如果這個鏈繼續往前走 走 回到這個出發點 那麼這樣的形成了一個圈 無向圖情形 有鏈和圈的概念 相應的 在有向圖裏邊 我們分別叫做路和迴路 那麼具體的路的定義 就是點邊交錯的序列 每一條邊 當然 在這表示的是有向邊 EI等於VI到VI加1 或者是我們可以稱作弧 迴路也是起點等於終點的路 在這我們也是來一塊看一下 一個具體的有向圖形 好 下面我動態演示一下 比如我從位一 經過位一位二這條有向邊 到達了位二 然後呢 從位二這個接點 繼續沿着位二到位三這條邊 到達了位三 這樣就形成了 位一到位三的一條路 如果這條路繼續往回走 那就形成了起點等於終點的路 我們叫回路 好 這是這樣的兩組概念 接下來呢 我們一起來看一種特殊的圖形 連通圖 所謂連通圖呢 它的定義是這樣的 任何兩點之間 至少存在一條鏈 那麼這個圖形呢 就稱作連通圖 否則呢 稱作不連通圖 顯然 在這個定義裏邊 我們指的這個連通圖和不連通圖呢 都是無相圖形性 有相圖形性的連通性啊 討論起來也比較複雜 我們在這個運車學 這個網絡分析裏邊 也用不到 所以呢就不再討論了 那麼就是專門來看 無相圖的連通性 無相圖呢 就可以簡單的分成 連通圖和不連通圖 在這我們來看一個例子 有這樣兩個圖形 J1和J2 那麼這兩個圖形 請同學們來判斷一下 哪個是連通圖 哪個是不連通圖呢 顯然 J1是不連通圖 而J2呢 是連通圖 因爲J1爲什麼是不連通圖呢 它並不能保證 任何兩點之間 至少存在一條鏈 比如說這個點 跟這個點之間 那麼就沒法有一條鏈 把它給連接起來 而J2就滿足這個條件了 任何兩點之間 都可以找到一條鏈 把它們給連接起來 所以說連通圖 我們還可以從另外一個角度說 任何兩點之間 如果都是可答的 那麼這樣一種圖像圖 就叫連通圖 這是圖的連通性問題 再接下來介紹這樣一組概念 子圖與支撐子圖 那麼子圖或者是支撐子圖 描述的是兩個圖形之間的 一種特殊的關係 我們先來看什麼叫子圖 它描述的是兩個圖形之間的關係 剛纔說到了 假設有兩個圖 一個是J等於位E 再一個是J'等於位'E' 如果滿足這樣的條件 位'包含於位 並且E'包含於E 換句話說 就是說第二個圖形的點擊 是第一個圖形點擊的子擊 第二擊也是它的子擊 那麼第二個圖形 就稱爲第一個圖形的子圖 子圖說的就是圖的這兩個構成要素 節點集和邊集 都是子集的關係 那麼一個圖形就稱爲 另外一個圖的子圖 支撐子圖是一種特殊的子圖 我們具體來看它的定義 兩個圖J和J' 若滿足V'等於V 並且E'包含於E 那麼則稱J'爲J的支撐子圖 我們看到支撐子圖跟普通的子圖 它的概念上最大的區別 就是這兩支撐子圖要求節點集相等 它當然也是一種子圖了 也是一種子圖 是一種特殊的子圖 好 下面我們來看個例子 我在這畫了兩個圖 J2和J1 那麼請同學判斷一下 J2和J1是什麼關係 是不是子圖的關係 進一步是不是支撐子圖的關係 顯然J2既是J1的子圖 又是它的支撐子圖 那麼點集是子集 邊集是子集 並且關鍵是點集相等 所以是支撐子圖 支撐子圖 我們在下一塊網絡分析內容 也就是第二節課中 最小支撐數問題 會繼續要用到這個概念 請同學們尤其要注意一下 接下來一個概念 負全圖或者叫網絡 那麼我們這一章的題目 就叫網絡分析 實際上網絡分析 特指這樣一種負全圖 我們來看它的定義 圖的每一條邊 都有一個表示一定實際含義的全數 那麼這種圖形就叫負全圖 記住D等於VAC 我們可以看到 負全圖跟一般的圖形相比 它的構成要素上 多了一個要素 也就是說一共有三個要素了 普通的圖形只有兩個要素 那就是接點集 邊集或者叫弧集 而在網絡或者是負全圖裏邊 多了第三個要素 全數的集合 那麼這個全數 根據問題的不同 它可能會表示各種各樣的實際的含義 比如說可以表示距離 兩點之間的距離 可以表示時間 可以表示費用 可以表示流量等等 諸多的問題 諸多的含義都可以用這個全數來表示 那麼有了這個全數 可以說我們就有了進行定量分析的基礎 就有了數據了 我們就可以做定量分析了 而我們運輸學的一個重要特點 就是要做基於數據的大量的定量分析 好 關於負全圖 或者網絡 我們在這也一塊來看一個例題 比如說這就是一個負全圖 那麼我們可以用節點來表示五個居民點 那麼邊表示居民點之間的鋪設道路 那麼這個全數就可以表示道路的長度 或者我表示修設道路所需要的花費 或者表示修設道路所需要的時間等等 根據不同的問題 我可以表示不同的含義 好 這是這個概念 再接下來呢 我們來一塊看一下多重圖和簡單圖的定義 爲此先來看多重邊的定義 所謂多重邊 就是說一個節點對能對應多條邊 那麼這樣的多條邊就互稱爲多重邊 或者說具有多重邊關係 因爲我們從前面會看到 那麼每一條邊都可以用節點對來表示 但有的時候節點對之間 它對應的邊可能不止一條 那麼這樣一些邊就叫多重邊 如果一個圖形還有多重邊 那麼這個圖就叫多重圖 否則稱爲簡單圖 也就是說所有的邊都不是多重邊的話 才叫簡單圖 在這我們分別從無相圖和有相圖兩種情形 來舉幾個例子 先來看無相圖情形 請同學們一塊來判斷一下 這個無相圖是不是多重圖呢 或者是不是簡單圖呢 顯然這個無相圖是一個多重圖 因爲它存在着多重邊 比如說A和B之間有兩條邊了 B和D之間也有兩條邊 這些都是多重邊關係 而後面這個無相圖我們會看到 它就是一個簡單圖了 任何兩點之間 都只有一條邊 或者說都是簡單邊 沒有多重邊 好 這是無相圖情形 我們繼續來看下面的有相圖情形 有相圖要注意了 我們看後面的圖 A和B之間有兩條邊 好像是有兩條邊 但是這個不是多重邊 而前面這個是多重邊 爲什麼呢 A和B之間這有兩個邊 這個確實是有相的多重邊 而後面這兩個邊 它並不是多重邊 請同學們一定要注意這個問題 上面這條邊 它是A到B這個接點都是描述的 而下面這條邊 是B到A這個接點都是描述的 它對應的是不同的接點對 所以不應該稱爲多重邊 所以也就是一個簡單圖 那麼最後 我們在第一節圖的基本概念 最後一塊來看一下圖的矩陣表示 在這之前 我們來描述圖的時候 都是用圖形 就直接來畫圖來表示的 但是爲了更進一步的 便於對圖形進行處理 尤其是用計算機來處理 那麼計算機來識別 直接圖形的時候 會遇到一些問題 那怎麼樣來表示圖呢 實際上圖還有其他的表示方法 其中最重要最常用的 一種表示方法 就是用矩陣來表示 我們要用到線性代數中 矩陣這個工具來描述圖 首先來看臨接矩陣的定義 臨接矩陣 它描述了或者表示了 點與點之間的一種臨接關係 假設一個圖 由n個節點來組成 這個圖是J等於V1 它的臨接矩陣是這麼定義的 定義爲A A是一個n乘n的方陣 它的構成元素是Aij 具體的來說 這個Aij是由1或者0來組成的 什麼情況等於1呢 當Vij屬於1的時候 相應的Aij的元素是1 當Vij不屬於1的時候 那麼Aij相應的位置 這個元素等於0 或者更簡單的說 當兩個節點之間 如果有邊的時候 一個節點到另外一個節點 存在邊的時候 相應的位置上 那個元素應該複製爲1 否則複製爲0 我們具體來看一個例子 這是一個有像圖 那麼有像圖 首先來判斷一下 它是有幾個節點呢 一共有四個節點 所以它的臨接矩陣表示 應該是一個四階的方陣 我們可以很容易寫出 它的四階方陣臨接矩陣了 每一個元素都表示了 邊與邊之間的一種特定的關係 比如說第一個0 那當然了 自己跟自己之間 什麼情況下 一般情況都是0 什麼情況下才是1呢 就是說一個節點 跟它自己之間有邊 也就是所謂的 形成環的時候 對應的這個位置纔是1 其他情況只要沒有環 那麼對角線元素應該都是0 再比如說第二個元素 A12與A1 那我們可以看到 A1到A2應該是有一條邊的 A1到A2有一條邊 而A2到A1沒有有像邊 所以A21這個位置 它相應的元素是0 等等其他的 元素我們都可以表示 這個邊 接點之間是否存在邊 剛纔這個例子 是一個有像圖的臨接矩陣 那麼無像圖 當然也可以用臨接矩陣來表示 而且我們可以很容易想到 無像圖的臨接矩陣 肯定是一個對稱矩陣 舉例說明 這是一個無像圖 那麼 V1和V2之間 任何兩個點之間 只要有邊 那麼相當於 正向有邊 反向也有邊 所以相應的 A12位置是1的話 它A21位置一定是1 如果兩個點之間沒有邊的話 你想 A42是0 說明V2到V4之間沒有邊 那麼 V2到V4之間也沒有邊 剛纔說是V4到V2沒有邊 那V2到V4當然也就沒有邊了 所以相應的對稱的位置都是0 從這來看的話 我們得到一種結論 那就是 無像圖 每一條無像邊 實際上都可以把它 簡單的轉換成一種有像邊 什麼樣的有像邊呢 那就是一對方向相反的有像邊 這樣的話 任何一個無像圖 都可以等價的轉換成一個有像圖 那麼只要把每一條邊 都用一對雙向的 方向相反的有像邊來表示 這樣無像圖就可以轉換成有像圖了 所以無像就相當於雙向 雙向就相當於無像 可以這麼來理解 剛纔舉的這些例子 都是用臨接矩陣來描述 我們會看到一個特點 那就是 這些圖都沒有全數 也就是說不是復全圖 只是普通的圖形 那麼復全圖怎麼來描述呢 用矩陣來表示呢 那麼相應的矩陣 那麼叫全矩陣 一個n階復全圖 就是說只有n個節點 它的三個構成要素是 V E C 節點集 邊集和全數集合 它的全矩陣是這麼來定義的 A等於AijnN 也是個n階方陣 其中呢 每一個元素 是這樣定義的 如果Vi到Vj存在邊 那麼相應的位置上 Aij呢 就等於這個邊上那個全數 如果Vi到Vj不存在邊呢 相應的位置 對應的元素 應該是無窮大 特別的當i等於j的時候 就是說節點到 它自身那個位置上 應該復值爲零 這樣的話就構成了這個 n階復全圖的 它的一個全矩陣 那麼可以看到 任何一個有限的簡單圖呢 都可以用全矩陣來表示 或者說都可以 唯一的寫出它的全矩陣了 一塊來看一個例子 那麼這是一個 四階的 有四個節點的 簡單圖 有向簡單圖 而且是一個帶全數的 復全圖 那麼就可以 寫出它的全矩陣了 按照剛纔的定義 同學們可以很容易理解 這個全矩陣 各個元素它的含義 這就是圖的基本概念 有了這些基本概念 我們就可以進行 後面的網絡分析了