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

1、圖與網(wǎng)絡(luò)的基本概念,一個(gè)圖是由一些點(diǎn)及這些點(diǎn)之間的連線所組成的. 兩點(diǎn)間不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧. 如果一個(gè)圖是由點(diǎn)及邊所構(gòu)成的，則稱之為無向圖（也簡稱為圖），記為G=(V,E). 如果一個(gè)圖是由點(diǎn)及弧所構(gòu)成的，則稱之為有向圖，記為D=(V,A).,若邊e=u,v，則稱e連接u與v；點(diǎn)u和v稱為e的頂點(diǎn)；稱u或v與e關(guān)聯(lián)；u與v是鄰接的頂點(diǎn). 如果兩條邊有一個(gè)公共的頂點(diǎn)，則稱這兩條邊是鄰接的；兩個(gè)頂點(diǎn)重合為一點(diǎn)的邊稱為環(huán). 如果有兩條邊的頂點(diǎn)是同一對頂點(diǎn)，則稱這兩條邊為重邊；不與任何邊關(guān)聯(lián)的點(diǎn)稱為孤立點(diǎn). 沒有環(huán)的圖稱為無環(huán)圖；既沒有環(huán)也沒有重邊的圖稱為簡單圖.,設(shè)G=(V,E

2、)是一個(gè)簡單圖，則有 若上式等號成立，則說明該圖中每對頂點(diǎn)間都恰好有一條邊相連，稱此圖為完全圖. 一個(gè)簡單圖 的補(bǔ)圖 是與 有相同頂點(diǎn)的簡單圖，且 中兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們在 中不相鄰. 一個(gè)圖 ，若存在 的一個(gè)分劃 ，使 的每條邊有一個(gè)頂點(diǎn)在 中，另一個(gè)在 中，則稱 為二分圖.,設(shè)有兩個(gè)圖 ， ，如果 則稱 為 的子圖；若進(jìn)一步有 ，則稱 為 的支撐子圖. 設(shè)有圖 ， 是 的非空子集，若以 為點(diǎn)集，以兩頂點(diǎn)均在 中的所有邊為邊集的子圖稱為由 導(dǎo)出的 的子圖，記為 ，簡稱點(diǎn)導(dǎo)出子圖；若 是 的一個(gè)非空子集，則以 為邊集以 中邊的所有頂點(diǎn)作為點(diǎn)集的子圖，稱為由 導(dǎo)出的 的子圖，記為 ，簡稱邊導(dǎo)

3、出子圖.,圖 中頂點(diǎn) 的度定義為和 關(guān)聯(lián)的邊的數(shù)目（與 關(guān)聯(lián)的每個(gè)環(huán)算作兩條邊），記為 . 定理1：設(shè) 是一個(gè)圖，則 ，從而度數(shù)為奇數(shù)的頂點(diǎn)有偶數(shù)個(gè). 設(shè)一個(gè)有向圖的弧a=(u,v)，稱a為從u連向v的弧，a為u的出弧，v的入??；u稱為a的尾，v稱為a的頭；u稱為v的前繼，v稱為u的后繼；頭尾重合的弧稱為環(huán)，若兩條弧有相同頭和尾，則稱這兩條弧為重弧。,沒有環(huán)和重弧的有向圖稱為簡單有向圖. 如果把有向圖 中每條弧(u,v)用邊u,v來代替，就得到一個(gè)無向圖，稱為 的基圖. 設(shè)D=(V,A)是一個(gè)簡單有向圖，則 . 若上式等號成立，則說明每對頂點(diǎn)間都恰好有一對方向相反的弧相連，稱這樣的圖為完全有向

4、圖.,有向圖D中頂點(diǎn)v的出弧的數(shù)目稱為v的出度，記為 ，頂點(diǎn)v的入弧的數(shù)目稱為v入度，記為 . 定理2：設(shè)D=(V,A)是一有向圖，則有 有向圖的子圖，支撐子圖，點(diǎn)、弧導(dǎo)出子圖.,關(guān)聯(lián)矩陣,一個(gè)簡單圖G=(V,E)對應(yīng)一個(gè)如下定義的 階矩陣 ，稱為G的關(guān)聯(lián)矩陣，其中,一個(gè)簡單有向圖D=(V,A)也對應(yīng)一個(gè)如下定義的 階矩陣 ，稱為D的關(guān)聯(lián)矩陣，其中,鄰接矩陣,一個(gè)簡單圖G=(V,E)對應(yīng)一個(gè)如下定義的 階矩陣 ，稱為G的鄰接矩陣，其中,一個(gè)簡單有向圖D=(V,A)也對應(yīng)一個(gè)如下定義的 階矩陣 ，稱為D的鄰接矩陣，其中,例1：試寫出下圖所示簡單無向圖和簡單有向圖的關(guān)聯(lián)矩陣和鄰接矩陣. 1 2 2

5、 4 5 1 3 3 4,定理3：G是二分圖當(dāng)且僅當(dāng)G的鄰接矩陣可表示為 設(shè)有圖G=(V,E)，如果它的某些頂點(diǎn)與邊可以排成一個(gè)非空的有限交錯(cuò)序列 且 ，則稱它為由 到 的一條途徑；如果該途徑中邊互不相同，則稱為跡；如果頂點(diǎn)不相同，則稱為路. 路必為跡，反之未必.,如果某途徑至少含一條邊，且起點(diǎn)與終點(diǎn)重合，則稱它為一條閉途徑. 類似有閉跡和回路（又稱圈）. 若G為簡單圖，則兩個(gè)頂點(diǎn)間邊若存在必是唯一的，故由 到 的一條途徑可以用頂點(diǎn)序列 表示.,圖G中若存在一條從頂點(diǎn)u到v途徑，則稱u與v是連通的. 如果圖G中任何兩個(gè)頂點(diǎn)都是連通的，則稱G是連通圖. 完全圖一定是連通圖；頂點(diǎn)數(shù)大于等于3的二分

6、圖一定不是完全圖.,如果H是G的子圖，且H是連通的，則稱H為G的連通子圖. 稱H為G的極大連通子圖，是指H為G的連通子圖，且不存在連通子圖J，使H是J的子圖. 圖G的極大連通子圖又稱為G的連通分支；一個(gè)圖可以有多個(gè)連通分支，連通圖恰好有一個(gè)連通分支.,有向圖D=(V,A)中某些頂點(diǎn)與弧組成的非空有限序列 ，且 ，則稱它為從 到 的有向途徑. 有向跡；有向路；有向閉途徑；有向閉跡；有向回路（有向圈）. D中若既存在從u到v的有向途徑，又存在從v到u的有向途徑，則稱u和v是強(qiáng)連通的；如果D中任意兩點(diǎn)都是強(qiáng)連通的，則稱D是強(qiáng)連通的；D的極大強(qiáng)連通子圖稱為強(qiáng)連通分支；若D強(qiáng)連通，則D恰好有一個(gè)強(qiáng)連通分支.,設(shè)有圖G=(V,E)，e是G的一條邊，如果從G中刪去e，使它的連通分支數(shù)量增加1，則稱e是G的割邊. G的一條邊是割邊當(dāng)且僅當(dāng)該邊不包含在G的任何閉跡中. 設(shè) 是 的一個(gè)非空子集， ，記 ，若 ， 且從G中刪去這些邊后，G的連通分支數(shù)至少增加1， 則稱 是G的一個(gè)邊割.,若 是一個(gè)邊割，且 的任何真子集都不是邊割，則稱它為極小邊割. G的極小邊割又稱為割集.顯然每條割邊