【正文】 從結(jié)點(diǎn) vi到結(jié)點(diǎn) vj (vi≠v j)存在一條道路 ， 則從 vi到 vj存在一條不多于 n1條邊的道路 。 若 k＞ n－ 1， 則此道路上的結(jié)點(diǎn)數(shù) k+1＞ n， 必存在一個(gè)結(jié)點(diǎn)在此道路中不止一次出現(xiàn) ， 設(shè) vis=vit，其中 ， 0≤s ＜ t≤k 。 證明 :設(shè) vi0,vi1,… ,vik為從 vi到 vj的長(zhǎng)度為 k的一條道路 ，其中 vi0=vi， vik=vj。 去掉 vis到 vit中間的道路 ， 至少去掉一條邊 ， 得道路 vi0,vi1,… ,vis,vit+1,… vik， 此道路比原道路的長(zhǎng)度至少少 1。 此道路上有 k+1個(gè)結(jié)點(diǎn) 。 如此重復(fù)進(jìn)行下去 ， 必可得一條從 vi到 vj不多于 n1條邊的道路 。 若 k≤n 1， 這條道路即為所求 。 ■ 2022/2/13 計(jì)算機(jī)學(xué)院 84/172 167。 ?我們可以利用連通關(guān)系對(duì) G的結(jié)點(diǎn)集進(jìn)行一個(gè)劃分 : {V1， V2， … ， Vk}（ 顯然 ， Vi是一個(gè)等價(jià)類 ） ， 使得 G中 的任意兩個(gè)結(jié)點(diǎn) u和 v連通當(dāng)且僅當(dāng) u和 v同屬于一個(gè) Vi(1≤i≤k) 。對(duì)任意結(jié)點(diǎn) u， 規(guī)定 u～ u。 圖 G的分支數(shù)記為 ?（ G） 。 ?我們可以利用連通關(guān)系對(duì) G的結(jié)點(diǎn)集進(jìn)行一個(gè)劃分 : {V1， V2， … ， Vk}（ 顯然 ， Vi是一個(gè)等價(jià)類 ） ， 使得 G中 的任意兩個(gè)結(jié)點(diǎn) u和 v連通當(dāng)且僅當(dāng) u和 v同屬于一個(gè) Vi(1≤i≤k) 。 ?定義 ′ 只有一個(gè)分支的無(wú)向圖稱為連通圖 ， 支數(shù)大于 1的無(wú)向圖稱為非連通圖 。 ?無(wú)向完全圖 Kn（ n≥ 1） 都是連通圖 ， 而多于一個(gè)結(jié)點(diǎn)的零圖都是非連通圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 91/172 例 G1是連通圖 ， 所以 ?(G1)＝ 1。 d(vi， vj)滿足下列性質(zhì)： ① d(vi,vj)≥ 0； （ 非負(fù)性 ） ② d(vi,vi)＝ 0； （ 對(duì)稱性 ） ③ d(vi,vk)+d(vk， vj)≥d(v i， vj)。 特別地 ， 若點(diǎn)割集中只有一個(gè)結(jié)點(diǎn) v，則稱 v為割點(diǎn) 。 特別地 ， 若點(diǎn)割集中只有一個(gè)結(jié)點(diǎn) v，則稱 v為割點(diǎn) 。 特別地 ， 若點(diǎn)割集中只有一個(gè)結(jié)點(diǎn) v，則稱 v為 割點(diǎn) 。 e2 v5 v1 v2 v3 v4 e3 e5 e1 e4 e7 e6 e9 v6 v7 e8 2022/2/13 計(jì)算機(jī)學(xué)院 99/172 邊割集 ? 定義 設(shè)無(wú)向圖 G＝ V,E。 2022/2/13 計(jì)算機(jī)學(xué)院 100/172 邊割集 ? 定義 設(shè)無(wú)向圖 G＝ V,E。 2022/2/13 計(jì)算機(jī)學(xué)院 101/172 邊割集 ? 定義 設(shè)無(wú)向圖 G＝ V,E。 2022/2/13 計(jì)算機(jī)學(xué)院 102/172 例 ? {e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9}, {e6,e7,e9}, {e1,e2,e5,e6,e8}等都是 邊割集 ； ? {e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9} 等都是基本邊割集； ? e9是割邊。 又若 ?(G)≥k ， 則稱 G為 k連通圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 105/172 點(diǎn)連通度、邊連通度 ? 定義 1) 設(shè)無(wú)向圖連通圖 G＝ V,E， 稱 ?(G)＝ min{|V?||V?為 G的點(diǎn)割集 }為 G的點(diǎn)連通度 ， 簡(jiǎn)稱連通度 。 規(guī)定非連通圖的邊連通度為 0。 又若 ?(G)≥k ， 則稱 G為 k連通圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 107/172 例 ? 右圖所示圖的點(diǎn)連通度為 1，它是 1連通圖 ， 但不是 2連通圖；它的邊連通度為 1， 它是 1邊 連通圖 ， 但不是 2邊 連通圖 。 e2 v5 v1 v2 v3 v4 e3 e5 e1 e4 e7 e6 e9 v6 v7 e8 彼得森圖 2022/2/13 計(jì)算機(jī)學(xué)院 109/172 ?定理 在非平凡連通圖 G中 ， 結(jié)點(diǎn) v為 G的割點(diǎn)的充分必要條件 是存在結(jié)點(diǎn) u和 w， 使 u到 w的每一條道路都以 v為內(nèi)部結(jié)點(diǎn) 。 割點(diǎn) v是圖中任何道路的必經(jīng)之處！ “一夫當(dāng)關(guān)，萬(wàn)夫莫開(kāi)” 2022/2/13 計(jì)算機(jī)學(xué)院 111/172 ?定理 在非平凡連通圖 G中 ， 結(jié)點(diǎn) v為 G的割點(diǎn)的充分必要條件是存在結(jié)點(diǎn) u和 w， 使 u到 w的每一條道路都以 v為內(nèi)部結(jié)點(diǎn) 。 （ 證明略 ， p213） ?推論：對(duì)任意無(wú)向圖 G＝ V,E， 若 G是 k連通圖 ， 則 G必為 k邊 連通圖 。 為什么 ？ 理由： ?(G)≤?(G) 2022/2/13 計(jì)算機(jī)學(xué)院 114/172 ?定理 ： 對(duì)任意無(wú)向圖 G＝ V,E， 均有下面不等式成立：?(G)≤ ?(G)≤ ?(G)。 對(duì)任意結(jié)點(diǎn) u， 規(guī)定 u→u 。 v3 v1 v4 v2 2022/2/13 計(jì)算機(jī)學(xué)院 116/172 有向圖的連通性 ?定義 u,v為有向圖 G＝ V,E中的兩個(gè)結(jié)點(diǎn) ， 若存在從結(jié)點(diǎn) u到結(jié)點(diǎn) v的道路 ， 則稱從結(jié)點(diǎn) u到結(jié)點(diǎn) v是可達(dá)的 ， 記為 u→v 。 因此 ， 可達(dá)關(guān)系 不是等價(jià)關(guān)系 。 ?有向圖結(jié)點(diǎn)之間的可達(dá)關(guān)系具有 自反性 和 傳遞性 ， 但一般說(shuō)來(lái) ， 可達(dá)關(guān)系 沒(méi)有對(duì)稱性 。 例如右圖中 v3到 v2可達(dá) ， 但 v2到 v3不可達(dá) 。 ?推論 ：對(duì)任意無(wú)向圖 G＝ V,E， 若 G是 k連通圖 ， 則 G必為 k邊 連通圖 。 其中 ， ?(G)、 ?(G)和 ?(G)分別為 G的點(diǎn)連通度 、 邊連通度和結(jié)點(diǎn)的最小度數(shù) 。 （ 證明略 ， p212） 2022/2/13 計(jì)算機(jī)學(xué)院 112/172 ?定理 ： 對(duì)任意無(wú)向圖 G＝ V,E， 均有下面不等式成立： ?(G)≤ ?(G)≤ ?(G)。 2022/2/13 計(jì)算機(jī)學(xué)院 110/172 ?定理 在非平凡連通圖 G中 ， 結(jié)點(diǎn) v為 G的割點(diǎn)的充分必要條件 是存在結(jié)點(diǎn) u和 w， 使 u到 w的每一條道路都以 v為內(nèi)部結(jié)點(diǎn) 。 e2 v5 v1 v2 v3 v4 e3 e5 e1 e4 e7 e6 e9 v6 v7 e8 2022/2/13 計(jì)算機(jī)學(xué)院 108/172 例 ? 右圖所示圖的點(diǎn)連通度為 1，它是 1連通圖 ， 但不是 2連通圖；它的邊連通度為 1， 它是 1邊 連通圖 ， 但不是 2邊 連通圖 。 規(guī)定非連通圖的邊連通度為 0。 2022/2/13 計(jì)算機(jī)學(xué)院 106/172 點(diǎn)連通度、邊連通度 ? 定義 1) 設(shè)無(wú)向圖連通圖 G＝ V,E， 稱 ?(G)＝ min{|V?||V?為 G的點(diǎn)割集 }為 G的點(diǎn)連通度 ， 簡(jiǎn)稱連通度 。 又若 ?(G)≥k ， 則稱 G為 k連通圖 。 規(guī)定非連通圖的邊連通度為 0。 e2 v5 v1 v2 v3 v4 e3 e5 e1 e4 e7 e6 e9 v6 v7 e8 2022/2/13 計(jì)算機(jī)學(xué)院 104/172 點(diǎn)連通度、邊連通度 ? 定義 1) 設(shè)無(wú)向圖連通圖 G＝ V,E， 稱 ?(G)＝ min{|V?||V?為 G的點(diǎn)割集 }為 G的 點(diǎn)連通度 ， 簡(jiǎn)稱 連通度 。 特別地 ， 若割集中只有一條邊 e， 則稱 e為割邊 。 特別地 ， 若割集中只有一條邊 e， 則稱 e為割邊 。 特別地 ， 若割集中只有一條邊 e， 則稱 e為割邊 。 2022/2/13 計(jì)算機(jī)學(xué)院 98/172 例 ?{v3,v5},{v2},{v6},{v2,v4},{v2,v3,v5} … 為 點(diǎn)割集 ； ?{v3,v5},{v2},{v6}為 基本割集 。 2022/2/13 計(jì)算機(jī)學(xué)院 97/172 點(diǎn)割集 ? 定義 設(shè)無(wú)向圖 G＝ V,E。 2022/2/13 計(jì)算機(jī)學(xué)院 96/172 點(diǎn)割集 ? 定義 設(shè)無(wú)向圖 G＝ V,E。 G1 v4 v1 v3 v2 v5 v6 v1 v4 v3 v2 G2 v5 v7 2022/2/13 計(jì)算機(jī)學(xué)院 95/172 點(diǎn)割集 ? 定義 設(shè)無(wú)向圖 G＝ V,E。 v2 v1 v3 v5 v4 v6 v10 v8 v9 v7 v11 G2 v2 v1 v5 v4 G1 v3 v6 v7 2022/2/13 計(jì)算機(jī)學(xué)院 92/172 ?定義 在圖 G＝ V， E中 ， 對(duì) ?vi， vj?V，如果從 vi到 vj存在道路 ， 則稱 長(zhǎng)度最短 的道路為從 vi到 vj的 距離 ， 記為 d(vi,vj)。 ?定義 ′ 只有一個(gè)分支的無(wú)向圖稱為連通圖 ， 支數(shù)大于 1的無(wú)向圖稱為非連通圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 89/172 連通圖 ?定義 若無(wú)向圖 G＝ V， E中任意兩個(gè)結(jié)點(diǎn)都是連通的 ， 則稱 G是連通圖 ， 否則稱 G是非連通圖 (或分離圖 )。 圖 G的分支數(shù)記為 ?（ G） 。對(duì)任意結(jié)點(diǎn) u， 規(guī)定 u～ u。 ?我們可以利用連通關(guān)系對(duì) G的結(jié)點(diǎn)集進(jìn)行一個(gè)劃分 : {V1， V2， … ， Vk}（ 顯然 ， Vi是一個(gè)等價(jià)類 ） ， 使得 G中 的任意兩個(gè)結(jié)點(diǎn) u和 v連通當(dāng)且僅當(dāng) u和 v同屬于一個(gè) Vi(1≤i≤k) 。 圖 G的分支數(shù)記為 ?（ G） 。對(duì)任意結(jié)點(diǎn) u， 規(guī)定 u～ u。 去掉 vis到 vit中間的道路 ， 至少去掉一條邊 ， 得道路 vi0,vi1,… ,vis,vit+1,… vik， 此道路比原道路的長(zhǎng)度至少少 1。 證明 :設(shè) vi0,vi1,… ,vik為從 vi到 vj的長(zhǎng)度為 k的一條道路 ，其中 vi0=vi， vik=vj。 若 k＞ n－ 1， 則此道路上的結(jié)點(diǎn)數(shù) k+1＞n， 必存在一個(gè)結(jié)點(diǎn)在此道路中不止一次出現(xiàn) ， 設(shè) vis=vit，其中 ， 0≤s ＜ t≤k 。 ■ 2022/2/13 計(jì)算機(jī)學(xué)院 82/172 定理 ? 在一個(gè)具有 n個(gè)結(jié)點(diǎn)的圖中 ， 如果從結(jié)點(diǎn) vi到結(jié)點(diǎn) vj (vi≠v j)存在一條道路 ， 則從 vi到 vj存在一條不多于 n1條邊的道路 。 若 k≤n 1，這條道路即為所求 。 如此重復(fù)進(jìn)行下去 ， 必可得一條從 vi到 vj不多于 n1條邊的道路 。 此道路上有 k+1個(gè)結(jié)點(diǎn) 。 去掉 vis到 vit中間的道路 ， 至少去掉一條邊 ， 得道路 vi0,vi1,… ,vis,vit+1,… vik， 此道路比原道路的長(zhǎng)度至少少 1。 證明 :設(shè) vi0,vi1,… ,vik為從 vi到 vj的長(zhǎng)度為 k的一條道路 ，其中 vi0=vi， vik=vj。 若 k＞ n－ 1， 則此通路上的結(jié)點(diǎn)數(shù) k+1＞ n， 必存在一個(gè)結(jié)點(diǎn)在此通路中不止一次出現(xiàn) ， 設(shè) vis=vit，其中 ， 0≤s ＜ t≤k 。 例 P5 C6 2022/2/13 計(jì)算機(jī)學(xué)院 78/172 定理 ? 在一個(gè)具有 n個(gè)結(jié)點(diǎn)的圖中 ， 如果從結(jié)點(diǎn) vi到結(jié)點(diǎn) vj (vi≠v j)存在一條道路 ， 則從 vi到 vj存在一條不多于 n1條邊的道路 。 例 P5 C6 2022/2/13 計(jì)算機(jī)學(xué)院 77/172 道路圖和圈圖 ?若一個(gè)圖能以一條基本道路表示出來(lái) ， 則稱此圖為道路圖 。 例 P5 C6 2022/2/13 計(jì)算機(jī)學(xué)院 76/172 道路圖和圈圖 ?若一個(gè)圖能以一條基本道路表示出來(lái) ， 則稱此圖為道路圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 75/172 道路圖和圈圖 ?若一個(gè)圖能以一條基本道路表示出來(lái) ， 則稱此圖為 道路圖 。 為什么 ？ 2022/2/13 計(jì)算機(jī)學(xué)院 71/172 例 在圖 G1中： v1e1v2e2v3e3v4e4v5e7v6： 基本道路 v1e1v2e5v4e3v3e2v2e9v6: 簡(jiǎn)單道路 V2e10v2e2v3e3v4e5v2: 回路 V2e2v3e3v4e5v2: 圈 e1 v6 v1 v4 v3 v2 G1 e2 e5 e3 e9 e7 e6 e8 v5 e4 v7 e10 2022/2/13 計(jì)算機(jī)學(xué)院 72/172 G2 v4 v1 v3 v2 v5 e1 e2 e3 e4 e5 e7 e8 e6 e9 在圖 G2中： v1e2v5e