第五章圖論（第二部分）-全文預(yù)覽
【正文】 [{A,B,C,D,E,F}]， G[{P,Q,S,T}] A B C D E F P Q S T 19 ?若 n階圖 G的鄰接矩陣為 A=(aij)n n， V(G)={v1,v2,… ,vn}, 則： （ 1） 若ａ ij＝ 1， 表明 vi到 vj有一條邊 ， 即 vi到 vj連通 ； （ 2） 若 ａ ij＝０ ， 表明 vi到 vj沒有長度為 1的通路 。 G [定義 ]連通圖：只有 一個 連通分支的圖。 證明： ? ： Ｇ中有一條包含所有頂點的回路，顯然強連通。 10 連通性定義 ? [定義 ]兩結(jié)點連通 (可達 ) 若 u與 v之間有通路相連 ，則稱 u與 v連通（可達）。 (2) 再證基本通路長度不大于 n1 （ 反證法 ） 設(shè) u和 v之間的基本通路的長度 ≥ｎ 。 A B C D E 基本通路： ACEBD 基本回路： ABCDEA 6 有向通 (回 )路 ? [定義 ]有向通 (回 )路 若通路 v0v1 … vn各邊是 有向邊 ，且 vi1和 vi分別是有向邊的 始點 與 終點 ，則稱該通路為有向通 (回 )路 。 注意 ： (1)通路中 允許有重復(fù)的結(jié)點和邊 。1 第 五 章 圖 論 (第二部分 ) ?1. 通路 ?2. 圖的 連通性 2 1. 通路 [定義 ]通路 pseudo path ? 設(shè) G＝ (V， E)是圖， v0， vn是 G中兩點。 ? 通路中包含的邊數(shù)稱為該 通路的長度 。 中間結(jié)點各不相同 的回路稱為 基本回路 。 證明： (1)先證明 u和 v之間存在基本通路 若 uv之間的通路 P中有相同的頂點 ， 則從 P中刪除相同頂點之間路徑 ， 直到 P中沒有相同頂點 ， 這樣得到的路徑為 u和 v之間的基本通路 。 ∴ 基本通路的長度 = n 1 9 路徑： 回路定理 ? [定理 ]回路定理 在有 n個頂點的圖 G中，如果有頂點 v到自身的 通路 ，那么必定有一條從 v到 v的長度不大于 n的 基本回路 。 ? 單向連通的有向圖 ? 任意兩個頂點，至少從一個頂點到另一個是 連通 的 ? 弱連通的有向圖 ? 底圖 連通 的 b c a 12 強連通圖性質(zhì)（補充） 定理 ：一個有向圖 G是強連通的 當且僅當 Ｇ中有一條包含所有頂點至少一次的 回路 。 A B C D E F E A B D E F D CE強連通圖 弱連通圖 強連通圖 單向連通圖14 無向圖的連通分支 ?
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1