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

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

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

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

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

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

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