離散數(shù)學(xué)第3章圖的基本概念.ppt

1、修正機(jī)數(shù)學(xué)基礎(chǔ)(上)第2編輯論，第3章圖的基本概念，3.1圖的概念和性質(zhì)，一，圖的定義和表示1。 圖節(jié)點(diǎn)的集合v和邊的集合e組成的秩序?qū)ΨQ為圖g.2。 有向圖表、無向圖表的各邊緣為有向邊緣的圖表稱為有向圖表，各邊緣為無向邊緣的圖表稱為無向圖表，不是的話稱為混合圖表。 三孤立點(diǎn)、零圖表與其他節(jié)點(diǎn)沒有關(guān)聯(lián)的節(jié)點(diǎn)稱為孤立點(diǎn)，全部由孤立點(diǎn)構(gòu)成的圖表稱為零圖表。 四。 邊的重量具有相同起點(diǎn)和終點(diǎn)的邊稱為平行邊，平行邊的根數(shù)稱為邊的重量。 五n次圖表具有n個(gè)節(jié)點(diǎn)的圖表稱為n次圖表，具有n個(gè)節(jié)點(diǎn)和m條邊的圖表稱為(n，m )圖6。 將節(jié)點(diǎn)的度數(shù)圖表即與節(jié)點(diǎn)v關(guān)聯(lián)的邊的數(shù)量(從循環(huán)開始數(shù)兩邊)稱為該節(jié)點(diǎn)的度數(shù)

2、，記作deg(v )。 其中，以v為起點(diǎn)的邊的數(shù)量為亮度deg (v )，以v為終點(diǎn)的邊的數(shù)量為亮度deg-(v )，因此設(shè)圖g中節(jié)點(diǎn)的最大最小頻度為(g )、(g )、二、圖的基本概念和握手定理1。 握手定理圖g中所有節(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。 推論1在任何圖中頻數(shù)為奇數(shù)的節(jié)點(diǎn)數(shù)必定為偶數(shù)。 在推論2有向圖中，所有節(jié)點(diǎn)的入度之和等于所有節(jié)點(diǎn)的出度之和。 例題1 :如果圖g知道1次節(jié)點(diǎn)有1個(gè)、2次節(jié)點(diǎn)有2個(gè)、3次節(jié)點(diǎn)有3個(gè)、4次節(jié)點(diǎn)有4個(gè)，則g的邊數(shù)為。 解：例題2 :圖G=的話，下面的結(jié)論成立的是。 例題3 :簡單連通無向圖g設(shè)為12邊，g設(shè)為1度節(jié)點(diǎn)2個(gè)，2度節(jié)點(diǎn)2個(gè)，4度節(jié)點(diǎn)3個(gè)，其

3、合適節(jié)點(diǎn)度數(shù)設(shè)為3，求g中有多少節(jié)點(diǎn)。 讓我們制作一個(gè)符合這個(gè)條件的簡單無向圖。 假設(shè)g中存在x個(gè)節(jié)點(diǎn)，則解：三個(gè)節(jié)點(diǎn)是x-7。 根據(jù)握手定理，因?yàn)橛薪猓詆有9個(gè)節(jié)點(diǎn)。 滿足條件的圖如下：2. 簡單圖不包含平行邊和環(huán)(自回路)的圖稱為簡單圖。 在一個(gè)簡單的圖中，任何節(jié)點(diǎn)的頻率都不大于n-1。 這是判斷一個(gè)頻度系列是否能構(gòu)成簡單的圖的主要依據(jù)。 三二部曲線圖將無向曲線圖g的節(jié)點(diǎn)集分為兩個(gè)部分，如果各部分的任何一個(gè)節(jié)點(diǎn)之間邊都沒有連接，則將g稱為二部曲線圖。 您可以使用、4。 完全圖將各節(jié)點(diǎn)對之間邊相連的無向簡圖稱為無向完全圖，將各節(jié)點(diǎn)對之間相反的2邊相連的有向簡圖稱為有向完全圖。 以具有n個(gè)

4、節(jié)點(diǎn)的無向完全圖Kn的邊數(shù)為例題4 :圖g為具有n個(gè)節(jié)點(diǎn)的無向完全圖時(shí)，g的邊數(shù)為。 A) n(n-1) B) n(n 1) C) D )、c和5。 設(shè)正則圖無向單純圖g中的各節(jié)點(diǎn)的頻數(shù)為k，則g被稱為k正則圖。 六如果授權(quán)地圖g的每個(gè)邊緣都有表示長度的實(shí)數(shù)，則圖g稱為授權(quán)地圖或網(wǎng)絡(luò)。 圖g把無向圖稱為無向權(quán)圖，圖g把有向圖稱為有向權(quán)圖。 七補(bǔ)充圖把由圖g中的所有節(jié)點(diǎn)和構(gòu)成完全圖的應(yīng)追加的邊構(gòu)成的圖稱為g的補(bǔ)充圖，并標(biāo)記。 例題5 :已知圖表的節(jié)點(diǎn)集以及圖表g和圖表d的邊集分別試制圖表g和圖表d，寫出各節(jié)點(diǎn)的頻數(shù)，回答圖表g、圖表d是簡單圖表還是多重圖表的解： a d a d b c b c圖

5、g圖d、圖g : 8、子圖1。 是已知的圖表G=，如果G=被稱為g的子圖表。 2 如果，將g稱為g的真子圖。 三如果，g被稱為g的生成子圖。 三、如果圖的同調(diào)圖g中的節(jié)點(diǎn)集v和圖g中的節(jié)點(diǎn)集v具有一對一的對應(yīng)關(guān)系，對應(yīng)的邊全部具有相同的重量，則記為g和g同調(diào)。 因此，兩個(gè)圖同體需要滿足接合點(diǎn)數(shù)相同、邊數(shù)相同、頻數(shù)相同的接合點(diǎn)數(shù)相同的條件。 上述條件是兩圖同體所需的條件，但并不是充分的條件，即，即使兩圖滿足上述條件，也未必是相同的結(jié)構(gòu)。對一個(gè)圖中的節(jié)點(diǎn)進(jìn)行重新排序，當(dāng)根據(jù)節(jié)點(diǎn)移動(dòng)時(shí)進(jìn)行任意彎曲，且可與另一個(gè)圖完全重疊，則這兩個(gè)圖是相同的結(jié)構(gòu)。 四、通路和回路1。 路徑、電路在G=中，如果從節(jié)點(diǎn)v

6、0依次經(jīng)由邊緣和節(jié)點(diǎn)到達(dá)vn，則稱為在v0和vn之間存在路徑、或者v0和vn聯(lián)系，表記為v0vn，如果是v0vn則表記為電路。 路徑經(jīng)過的邊數(shù)稱為路徑長度。 2 簡單路徑，沒有簡單電路重復(fù)邊的路徑稱為簡單路徑，沒有重復(fù)邊的路徑稱為簡單路徑。 三基本路徑，將基本環(huán)沒有重復(fù)節(jié)點(diǎn)的路徑稱為基本路徑，將沒有重復(fù)節(jié)點(diǎn)的環(huán)稱為基本環(huán)。 例題6 :設(shè)g圖，可知路徑分別是簡單路徑、簡單電路、基本路徑、基本電路。 解：簡單通道、基本通道、簡單回路，但不是基本回路，而是簡單回路、基本回路、簡單通道，但不是基本通道。 在v1 v2 v5 v3 v4、一、連通性無向圖g中，如果任何兩個(gè)不同的結(jié)點(diǎn)都連通，則將g稱為連通

7、圖。 無向圖中結(jié)點(diǎn)的連通關(guān)系具有自逆性、對稱性、傳遞性，因此結(jié)點(diǎn)的連通關(guān)系是等價(jià)關(guān)系。 圖g雖然不是連通圖，但將g分為幾個(gè)部分，如果各個(gè)部分連通，則將各個(gè)部分稱為連通子圖，將各個(gè)連通子圖g稱為g的連通分支。 在g中相互連通的節(jié)點(diǎn)必定在同一連通分支上。 設(shè)無向圖g的連通分支數(shù)為W(G )。 3.2圖的連通性，例如G: G雖然不是連通圖，但可以分為3個(gè)連通分支。 是連通分支，是連通分支，是連通分支。 被稱為v的區(qū)分。 有向連通圖1。 強(qiáng)連通圖、單側(cè)連通圖、弱連通圖在有向簡單圖d中為(1)無論哪個(gè)節(jié)點(diǎn)間都能夠到達(dá)，強(qiáng)連通圖；(2)無論哪個(gè)節(jié)點(diǎn)間，如果任意一個(gè)節(jié)點(diǎn)能夠到達(dá)另一個(gè)節(jié)點(diǎn)，則為單側(cè)連通圖兩個(gè)

8、定理61的有向圖足以是強(qiáng)連通性的要求是，在每個(gè)節(jié)點(diǎn)中至少存在一個(gè)通過的電路。 定理7在有向圖中，其各個(gè)節(jié)點(diǎn)必定位于一個(gè)強(qiáng)分圖上，并且只位于一個(gè)強(qiáng)分圖上。 例題7 :可以構(gòu)成va、b、c、d和強(qiáng)連通圖的邊集e、b、c、d和強(qiáng)連通圖。 當(dāng)節(jié)點(diǎn)集v (包括與v中的節(jié)點(diǎn)相關(guān)聯(lián)的所有邊)被刪除時(shí)，在無方向連通圖G=中獲得子圖GV。 如果v是不連通GV的最小點(diǎn)集，則v稱為g的點(diǎn)集。 如果v中只有一個(gè)節(jié)點(diǎn)，則稱為切割點(diǎn)。 換句話說，點(diǎn)剪輯是指，將圖g從連通圖變更為需要?jiǎng)h除為非連通圖的最小點(diǎn)集。 例如，由于g:v1刪除后G1，v3刪除后G2刪除v1，v3后G3，所以v1不是點(diǎn)切割集合，W(G1)=1，v3是點(diǎn)

9、切割集合，另外，在切割點(diǎn)處，當(dāng)給予w例題8 :圖g時(shí)，圖g的點(diǎn)切割集合成為。2。 邊緣切割集處于無向連通圖G=，如果刪除邊緣集e，則得到子圖GE。 如果e是不連通GE的最小邊集，則e稱為g的邊切集。 e中只有一條邊稱為剪切邊。 換句話說，邊緣切集是指從圖g的連通圖到非連通圖需要?jiǎng)h除的最小邊緣集。 例如，刪除g :邊(v1，v2)之后的G1，(v1，v2)，(v2)，刪除、3。 如果連通度(1)點(diǎn)連通度g是無向連通圖，v是g的結(jié)點(diǎn)數(shù)最少的點(diǎn)分集或者GV是平凡圖(孤立點(diǎn))，則將v中的結(jié)點(diǎn)數(shù)稱為g的點(diǎn)連通度。因此，(1)如果g是平凡的圖，則V=，(2)如果g是完全的圖，則除去n-1個(gè)節(jié)點(diǎn)成為平凡的圖

10、，所以，(3)如果g中存在切割點(diǎn)，則(4)如果g是非連通圖，則(2)邊連通度g是無向連通圖，e是g的邊數(shù)最少的邊分集因此，如果(1)g是平凡的圖，則如果E=、(2)g存在切斷，則如果(3)g是非連通圖。 (3)之間的關(guān)系無向圖g中，點(diǎn)連通度必須不比邊連通度大，邊連通度必須不比結(jié)點(diǎn)的最小度數(shù)大。 另一方面，如果無向圖的相鄰矩陣是無向圖G=、|V|=n，則3.3圖的矩陣表示設(shè)為與n次方矩陣A(G )中的表示相關(guān)聯(lián)的邊數(shù)。 例如，如圖g所示，可知A(G )是對稱矩陣。 主對角線上的要素表示各節(jié)點(diǎn)的自環(huán)數(shù)。 當(dāng)有向圖D=、|V|=n時(shí)，二、有向圖的鄰接矩陣表示距n次方矩陣A(D )中的表的邊數(shù)。 從下面的例子可以看出，A(D )不再是對稱矩陣。 矩陣中所有元素的和等于有向圖中的邊緣數(shù)。 第行元素的和表示節(jié)點(diǎn)的輸出度，第列元素的和表示節(jié)點(diǎn)的輸入度，圖d :例題9 :到圖d的相鄰矩陣為A(D)=，其中e。 例題10 :有向圖的鄰接矩陣(D)=第中行的要素之和是中的節(jié)點(diǎn)。 三、校正后的邊數(shù)在鄰接矩陣A(D )中為長度為1的邊數(shù)。 在A2(D )中，長度為2的邊數(shù)。 一般來說，長度是的邊數(shù)。 位置數(shù)表示距長度的邊數(shù)。 對于A(D) A2(D) Ak(D )，表示長度小于等于k的邊數(shù)的和，位置上的數(shù)量小于等于k的邊數(shù)的