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

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

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

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

4、節(jié)點的無向完全圖Kn的邊數(shù)為例題4 :圖g為具有n個節(jié)點的無向完全圖時，g的邊數(shù)為。 A) n(n-1) B) n(n 1) C) D )、c和5。 設(shè)正則圖無向單純圖g中的各節(jié)點的頻數(shù)為k，則g被稱為k正則圖。 六如果授權(quán)地圖g的每個邊緣都有表示長度的實數(shù)，則圖g稱為授權(quán)地圖或網(wǎng)絡(luò)。 圖g把無向圖稱為無向權(quán)圖，圖g把有向圖稱為有向權(quán)圖。 七補充圖把由圖g中的所有節(jié)點和構(gòu)成完全圖的應(yīng)追加的邊構(gòu)成的圖稱為g的補充圖，并標記。 例題5 :已知圖表的節(jié)點集以及圖表g和圖表d的邊集分別試制圖表g和圖表d，寫出各節(jié)點的頻數(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é)點集v和圖g中的節(jié)點集v具有一對一的對應(yīng)關(guān)系，對應(yīng)的邊全部具有相同的重量，則記為g和g同調(diào)。 因此，兩個圖同體需要滿足接合點數(shù)相同、邊數(shù)相同、頻數(shù)相同的接合點數(shù)相同的條件。 上述條件是兩圖同體所需的條件，但并不是充分的條件，即，即使兩圖滿足上述條件，也未必是相同的結(jié)構(gòu)。對一個圖中的節(jié)點進行重新排序，當根據(jù)節(jié)點移動時進行任意彎曲，且可與另一個圖完全重疊，則這兩個圖是相同的結(jié)構(gòu)。 四、通路和回路1。 路徑、電路在G=中，如果從節(jié)點v

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

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

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

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

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