圖的基本概念

1、第一章 圖的基本概念第一節(jié) 圖和有向圖 定義1.1 一個(gè)無向圖圖（graph）是指一個(gè)二元組，其中集合中的元素稱為頂點(diǎn)（或點(diǎn),或端點(diǎn), 或結(jié)點(diǎn)）（or vertice, or node, or point), 集合中元素為中元素組成的無序?qū)ΓQ為邊 (edge). 注意：1. 上述集合中的元素可以相同，有的文獻(xiàn)稱這樣的集合為多重集。 2. 圖稱為空?qǐng)D，它有時(shí)在舉反例的時(shí)候用到，且有時(shí)將一個(gè)結(jié)論推廣到包含空?qǐng)D時(shí)會(huì)引起不必要的麻煩, 故本書中假設(shè)所討論的圖都不是空?qǐng)D。 3. 在一個(gè)圖中，為了表示和分別是頂點(diǎn)集合邊集，常將和分別記為和. 我們經(jīng)常用圖形來表示一個(gè)圖。用小圓圈或?qū)嵭狞c(diǎn)表示圖的頂點(diǎn)，用線

2、段把無序?qū)χ袃蓚€(gè)頂點(diǎn)連接起來表示邊。其中頂點(diǎn)的位置，連線的曲直、是否相交等都無關(guān)緊要. 例如，=，的圖形如下. e 圖. 1. 設(shè). 若為有限集，則稱為有限圖（finite graph）；若為單點(diǎn)集，則稱為平凡圖 (trivial graph ). 為方便起見，常用e表示邊，例如在圖1中表示邊, 而,稱為的端點(diǎn). 兩個(gè)頂點(diǎn)相同的邊稱為環(huán) (loop), 具有相同頂點(diǎn)的多條邊稱為重邊 (multiple edge), 不含環(huán)和重邊的圖稱為簡(jiǎn)單圖 (simple graph). 例如在圖1中為環(huán), 為重邊，所以此圖不是簡(jiǎn)單圖. 定義1.2 設(shè)圖的頂點(diǎn)集為，邊集為.的鄰接矩陣（adjacency m

3、atrix）是一個(gè)矩陣，元素為端點(diǎn)的邊的數(shù)目。的關(guān)聯(lián)矩陣（incidence matrix）是一個(gè)矩陣，元素為1，當(dāng)是的端點(diǎn). 否則，元素為0. 頂點(diǎn)的度（degree）是其作為邊的端點(diǎn)的個(gè)數(shù), 記為. 例1.3 圖1的鄰接矩陣和關(guān)聯(lián)矩陣分別如下: 注意：鄰接矩陣由頂點(diǎn)的順序決定. 任意鄰接矩陣都是對(duì)稱的. 鄰接矩陣法是將一個(gè)圖儲(chǔ)存于計(jì)算機(jī)的方法之一. 在關(guān)聯(lián)矩陣或鄰接矩陣中，將某頂點(diǎn)對(duì)應(yīng)的行的元素求和，就得到該頂點(diǎn)度數(shù). 關(guān)于頂點(diǎn)度數(shù)，我們有下面的基本定理. 定理1.4 設(shè)圖的頂點(diǎn)集為，邊集為=, 則 = 推論 圖中度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù). 我們稱一個(gè)圖的所有頂點(diǎn)度數(shù)的非遞增序列為這個(gè)圖的

4、度序列. 例如圖1的度序列為（4,3,2,2,1）. 每個(gè)圖都有一個(gè)度序列，反之，并非每個(gè)非遞增序列都為度序列，例如（5,4,3,2,1）就不可能是某個(gè)圖的度序列，因?yàn)槎ɡ?.4告訴我們，一個(gè)非遞增序列要成為某個(gè)圖的度序列，必須先滿足序列的元素和為偶數(shù). 其實(shí)，這個(gè)顯然的必要條件也是充分的. 定理1.5 非負(fù)整數(shù),.,是某個(gè)圖的所有頂點(diǎn)度數(shù)當(dāng)且僅當(dāng)是偶數(shù). 證明 顯然. 設(shè). 顯然集合: 是奇的元素個(gè)數(shù)為偶數(shù). 將此集合中元素兩兩配對(duì)，對(duì)每個(gè)元素對(duì)，構(gòu)造一條邊使其端點(diǎn)為元素對(duì). 則此時(shí)每個(gè)頂點(diǎn)需要的度數(shù)是偶數(shù)（非負(fù)），在處加上個(gè)環(huán)，就得到以為頂點(diǎn)集的圖，且的度為. 定理1.5的證明是構(gòu)造性的，

5、當(dāng)然可以用其它方法來證明，例如用歸納法（對(duì)或 是偶數(shù)的條件就不充分了. 我們?cè)诹?xí)題中給出無環(huán)圖度序列的刻畫. 關(guān)于簡(jiǎn)單圖度序列的刻畫以及更多關(guān)于度序列的內(nèi)容參考1 . 定義1.6 圖中頂點(diǎn)和邊的交替序列=稱為一條-通道-walk, 如果和是的端點(diǎn). 和分別稱為通道的起點(diǎn)(origin)和終點(diǎn)(terminus)，其它頂點(diǎn)稱為內(nèi)點(diǎn). 中邊的數(shù)目稱為通道的長(zhǎng)度. 若起點(diǎn)和終點(diǎn)相同，稱此通道是閉的. 如果中的邊互不相同，則稱為一條跡（tail）; 如果中的頂點(diǎn)互不相同，則稱為一條路徑（path）. 起點(diǎn)和內(nèi)點(diǎn)互不相同的閉通道稱為圈（cycle). 若對(duì)于圖中任意兩個(gè)頂點(diǎn)和，都存在一條-通道，則稱此圖

6、是連通的（connected）. 在圖2中， 為通道， 為閉跡， 為路徑 定義1.7 設(shè)，是兩個(gè)圖. 若, 則稱是的子圖（subgraph). 若是的子圖且, 則稱是的生成子圖（spanning subgraph). 設(shè), 以 為頂點(diǎn)集, 以兩端點(diǎn)全在中的全體邊為邊集的的子圖稱為的導(dǎo)出子圖(induced subgraph), 記為. 在圖3中， 定義1.8 圖的連通分支(connected component) 是指其最大連通子圖. 圖的割點(diǎn)(cutvertex) (割邊 (cut-edge or bridge)是指一個(gè)頂點(diǎn)（一條邊）且刪除它會(huì)增加連通分支的數(shù)目. 我們用來表示刪除點(diǎn)邊所得到

7、的子圖. 在圖4中， 下面來刻畫割邊.定理1.9 一條邊是割邊當(dāng)且僅當(dāng)它不屬于任何一個(gè)圈.證明: 設(shè),不妨設(shè)是連通的（為什么?）. 若位于某個(gè)圈中, 則不難證明連通，這與是割邊矛盾，故不屬于任何一個(gè)圈. 若不是割邊, 則連通. 設(shè)的兩個(gè)頂點(diǎn)分別為. 由于連通.連通，故中存在一條()-路徑，這條路徑加上就構(gòu)成了一個(gè)圈. 定義1.10 一個(gè)有向圖（digraph）是指一個(gè)二元組，其中集合中的元素稱為頂點(diǎn)（或點(diǎn),或端點(diǎn), 或結(jié)點(diǎn)), 集合中元素為中元素組成的有序?qū)?，稱為邊或有向邊. 有向圖也可以用圖形表示. 例如：但要注意有向圖中邊是有方向的，箭頭必須從指向. 有些概念對(duì)有向圖或無向圖都適用; 有些

8、概念對(duì)有向圖和無向圖而言是有差異的. 在習(xí)題中我們給出有向圖中一些基本概念的定義. 習(xí) 題 1. 證明：一條-通道都包含一條-路徑. 2. (1) 如果簡(jiǎn)單圖的每個(gè)頂點(diǎn)的度數(shù)為2，一定是圈嗎？ (2) 證明：如果圖中每一個(gè)點(diǎn)的度至少是2，則含有一個(gè)圈. 3. 給定下列各序列： （1）（2,2,2,2,2）； （2）（3,2,2,1,1）； （3）（2,2,2,1,1）； （4）（3,3,3,1,0）； （5）（5,4,4,3,1）.以上五組數(shù)中，那幾組數(shù)可以構(gòu)成簡(jiǎn)單圖的度數(shù)序列?4. 證明：含有個(gè)頂點(diǎn)和條邊的圖至少有個(gè)連通分支.5. 證明：如果一個(gè)圖的所有頂點(diǎn)的度都為偶數(shù)(這樣的圖稱為偶圖)，

9、則此圖沒有割邊.6. 對(duì)于含有個(gè)頂點(diǎn)的簡(jiǎn)單圖，如果任意兩個(gè)頂點(diǎn)都有邊相連(即每個(gè)頂點(diǎn)的度為)，則稱此圖為完全圖(complete graph), 記為. 確定是否包含以下情況(給出例子或證明不包含). (1) 一個(gè)不是跡的通道. (2) 一個(gè)不是路徑的閉跡. (3). 一個(gè)不是圈的閉跡. 7. 對(duì)于圖和，如果存在兩個(gè)雙射：和使得對(duì)于任意的, 是的兩個(gè)端點(diǎn), 則稱和同構(gòu)(isomorphism), 記為. 一個(gè)簡(jiǎn)單圖的補(bǔ)圖（complement）也是一個(gè)簡(jiǎn)單圖，其頂點(diǎn)集為, 且. (1) 證明：（4個(gè)頂點(diǎn)的路徑）和其補(bǔ)圖同構(gòu). 像這樣和其補(bǔ)圖同構(gòu)的圖稱為自補(bǔ)的 (self-complementa

10、ry). (2) 證明：. (3) 證明簡(jiǎn)單圖集合的同構(gòu)關(guān)系時(shí)一種等價(jià)關(guān)系. (4) 按同構(gòu)關(guān)系給下面4個(gè)圖分類. 第2節(jié) 樹的性質(zhì) 本節(jié)和下一節(jié)學(xué)習(xí)圖論中最有用的概念之一樹. 作為圖，樹在數(shù)據(jù)存儲(chǔ)、查詢，通信，電網(wǎng)分析，化學(xué)等方面有著重要應(yīng)用. 定義2.1 一個(gè)森林（forest ）是指一個(gè)無圈圖. 一棵樹（tree）是指一個(gè)連通的森林. 度為1的頂點(diǎn)稱為葉子（leaf）. 若果一個(gè)圖的生成子圖是一棵樹，則稱該樹是圖的生成樹 (spanning tree). 例2.2 給一所大學(xué)的所有學(xué)生編排學(xué)號(hào)，形成一顆樹. 以0表示學(xué)校，以01, 02, 03,. 表示學(xué)院, 以01, 02, 03.表

11、示各個(gè)學(xué)院的班級(jí)，以001, 002, 003,.表示各班級(jí)的學(xué)生這一結(jié)果如下圖所示，注意樹中的葉子表示一個(gè)學(xué)生. 下面給出樹的定價(jià)刻畫. 定理 2.3 對(duì)于個(gè)頂點(diǎn)的圖，下面命題等價(jià): （1）是連通的且無圈. (2) , 中只有一條-路徑且無環(huán). （3）有條邊且無圈. （4）是連通的且有條邊. 證明：（1）（2）. 由于是連通的，故, 中有一條-路徑. 若中還有一條不同的-路徑，則不難證明中有圈 (證明留作練習(xí)) ，與中無圈矛盾，所以中只有一條-路徑. 無圈推出無環(huán). （2）（3）. 上面證明已經(jīng)指出：, 若中只有一條-路徑，則中無圈. 下面用歸納法證明有條邊. 如果，結(jié)論是顯然的 (由于無環(huán)

12、)，下設(shè)對(duì)于頂點(diǎn)數(shù)小于()的圖命題成立. 對(duì)于中任意一條邊，在圖中刪除此邊得到圖. 由于中只有一條-路徑，故不連通. 不難證明 有兩個(gè)連通分支且無圈，設(shè)這兩個(gè)連通分支分別為和. 由（1）（2）知這兩個(gè)連通分支中任意兩頂點(diǎn)間只有一條路徑，又由于和的頂點(diǎn)數(shù)都小于，由歸納假設(shè)知 (其中分別表示的邊和頂點(diǎn)數(shù)，). 又+=+1+1=+1, 證畢. （3）（4）. 設(shè)使的連通分支. 由 (1) (2) (3)知，對(duì)每個(gè)連通分支都有 (其中分別表示的邊和頂點(diǎn)數(shù), ) . 故 ，即.由于，故，即連通. （4）（1）. 若中有圈，則從各個(gè)圈中刪除邊. 直到中無圈. 又因?yàn)閯h除圈中的邊不會(huì)破壞連通性 (也即圈中的

13、邊一定不是割邊，見定理1.9)，故最后得到的圖是連通的無圈圖且頂點(diǎn)數(shù)為. 由于(1) (2) (3)，故有條邊. 所以且是無圈的. 我們?cè)诹?xí)題中給出樹的其它的定價(jià)刻畫，下面給出關(guān)于生成樹的一個(gè)結(jié)果. 定理2.4. 是連通的當(dāng)且僅當(dāng)它有生成樹. 充分性是顯然的，必要性的證明類似于定理2.3證明中的（4）（1），故我們略去. 注意定理2.4給出了確定圖是否連通的方法，我們將在下一節(jié)討論檢測(cè)是否有一個(gè)生成樹的算法. 我們下面討論樹在計(jì)算機(jī)學(xué)科的一些應(yīng)用，先給出根樹的定義. 每一顆樹都可以按下面的方式畫出來 (例如圖 ). 每一個(gè)頂點(diǎn)都有層次 (level)0, 1, 2,., k. 存在的唯一的層次

14、為0的頂點(diǎn)稱為根 (root). 所有相鄰的頂點(diǎn)相差一個(gè)層次, 且層次上的頂點(diǎn)正好與一個(gè)層次上的頂點(diǎn)相鄰. 這樣的樹稱為根樹 (rooted tree）. 顯然指定一個(gè)頂點(diǎn)作為根后，每一顆樹都可以認(rèn)為是根數(shù). 稱為樹高 (height). 與頂點(diǎn)相鄰且比層次低的頂點(diǎn)稱為的孩子 (children), 比層次低且與有路徑相連的頂點(diǎn)稱為的后代(descendant). 如果一顆樹的每個(gè)頂點(diǎn)有不多于個(gè)孩子，則稱此樹為元 (-ary)樹.如果每個(gè)頂點(diǎn)有0個(gè)或個(gè)孩子，則稱此樹為完全元樹. 2元根樹也稱為二叉樹 (binary tree).下圖給出了一顆高為3的二叉樹. 當(dāng)傳輸數(shù)據(jù)時(shí)，每一個(gè)字符被編碼或被

15、指定一個(gè)二進(jìn)制串. 例如我們要傳送這五個(gè)符號(hào)時(shí)就需要至少三位二進(jìn)制串 (為什么？). 由于我們可能要處理一些很大的文件且計(jì)算機(jī)的儲(chǔ)存空間有限，我們常常希望將字符編碼成二進(jìn)制串使得文件總長(zhǎng)最小. 不妨設(shè)這五個(gè)字符在文件中出現(xiàn)得頻率分別為，則如果用三位二進(jìn)制串傳輸這一數(shù)據(jù)集合需要 位.如果允許使用變長(zhǎng)度的二進(jìn)制串，則可能節(jié)省很多. 例如我們給上面5個(gè)字符分別編碼如下： 則傳輸這一數(shù)據(jù)集合需要 位.顯然變長(zhǎng)度的傳輸方式節(jié)省了傳輸位數(shù)，然而卻出現(xiàn)了問題. 如果我們收到二進(jìn)制串：001.則沒有辦法解碼. 出現(xiàn)這樣問題的原因很簡(jiǎn)單，是因?yàn)槲覀冊(cè)诰幋a過程中一個(gè)字符的二進(jìn)制串是某個(gè)字符二進(jìn)制串的前面部分. 例

16、如上例中的二進(jìn)制串是的前面部分等等. 因此我們分不清楚00是表示兩個(gè)還是一個(gè). 我們稱這種情況不出現(xiàn)得編碼為前綴碼 (prefix code). 下面我們來介紹構(gòu)造最優(yōu)前綴編碼的算法 (Huffman 1952). Huffman 算法：最優(yōu)前綴編碼 輸入：權(quán)值 (頻率或概率) . 輸出：前綴碼 (一顆二叉樹). 思想：權(quán)值小的字符 (或數(shù)據(jù)) 應(yīng)該有較長(zhǎng)的編碼, 將權(quán)值小的數(shù)據(jù)置于二叉樹的深層. 步驟：1.取權(quán)值最小的為葉子，做一個(gè)新頂點(diǎn)為這兩個(gè)樹葉的父親且其權(quán)為 . 從所有的權(quán)中刪去加上. 2.重復(fù)次過程1 后就得到一顆二叉樹. 3.從二叉樹的樹根出發(fā)，給左邊的邊標(biāo)記0，右邊的邊標(biāo)記1，則

17、樹葉的編碼為從樹根到樹葉的路徑上標(biāo)記的字符串. 關(guān)于這一算法最優(yōu)性的證明可參考1或2 . 下面我們用一個(gè)例子說明求最優(yōu)前綴編碼的過程. 例2.5 在通信中， 0,1,2,3,4,5出現(xiàn)的頻率如下： 0: 45% 1: 20% 2: 15% 3: 15% 4: 10% 5: 5%求傳輸它們的最優(yōu)前綴碼. 解：按照Huffman算法得到的二叉樹如下圖所示. 所以0,1,2,3,4,5的最優(yōu)前綴編碼分別為 0: 1 1: 011 2: 012 3: 001 4: 0001 5: 0000 按比例傳輸上述字符1000個(gè)需要的二進(jìn)制數(shù)字個(gè)數(shù)為 1000（45%1+20%3+15%3+15%3+10%4+

18、5%4）=2150個(gè).如果所有字符都用長(zhǎng)為3的碼字傳輸，則需要二進(jìn)制數(shù)字3000個(gè). 所以用最優(yōu)前綴編碼省了850個(gè)二進(jìn)制數(shù)字. 考慮搜索個(gè)數(shù)字列表中的某個(gè)數(shù)字. 最壞情況是，該數(shù)字處于列表的最后位置，則我們需要步找到它.下面我們用二叉搜索樹儲(chǔ)存這些數(shù)據(jù)，并證明通過這種方法我們搜索某個(gè)數(shù)的步驟將大大降低. 一顆二叉搜索樹 (binary search tree) 是一顆給每一個(gè)頂點(diǎn)賦值了的二叉樹, 且對(duì)每一個(gè)頂點(diǎn)如果它有孩子，那么它的左孩子和左孩子的后代的賦值比該頂點(diǎn)的賦值小；它的右孩子和右孩子的后代比該頂點(diǎn)的賦值大. 圖2.1中給出了一個(gè)完全二叉搜索樹. 各頂點(diǎn)的賦值為1, 2, .,7. 例如要搜索7，先是和5比較，7大于5故而和5的右孩子比較，7又大于6，故在和7比較，這樣用了3步就找到了. 如果按照列表1,2,3,. 7則需要7步. 假如已知一顆二叉搜索樹，最壞情況下用多少步可以搜索到某個(gè)頂點(diǎn)取決于這顆二叉樹的高度. 對(duì)于個(gè)頂點(diǎn)的二叉樹，我們自然關(guān)心它的最小高度是多少. 定理2.6 個(gè)頂點(diǎn)的二叉樹的最小高度為. 定理的證明我們留作習(xí)題. 由此定理知對(duì)于個(gè)數(shù)據(jù), 我們利用二叉搜索樹搜索某個(gè)數(shù)據(jù)最多需要步. 這比按順序查找列表中的項(xiàng)要好很多，因?yàn)?. 習(xí)題. 1. 圖中有兩條-路徑，則中含圈. 2. 圖是樹連通且中每一條邊都是割邊 在中任意添加一條