路與回路ppt課件-wenkub
2023-05-18 18:30:31 本頁面
【正文】 的所有結(jié)點(diǎn)后 ,所得到的子圖是不連通圖 ,而刪除了 V1的任何真子集后 ,所得到的子圖仍是 連通圖 ,則稱 V1是 G的一個(gè) 點(diǎn)割集 (cutset of nodes) 。 顯然在連通圖中，任意兩個(gè)結(jié)點(diǎn)之間必是連通的。 結(jié)點(diǎn)之間的連通性是結(jié)點(diǎn)集 V上的等價(jià)關(guān)系，對(duì)應(yīng)該等價(jià)關(guān)系，必可將作出一個(gè)劃分，把 V分成非空子集 V1, V2, … , Vm,使得兩個(gè)結(jié)點(diǎn) vj和 vk是連通的，當(dāng)且僅當(dāng)它們屬于同一個(gè) Vi 。 v1到 v3的一條路為：v1e2v3e3v2e3v3e4v2e6v5e7v3 此路中有 6條邊，去掉 e3有路 v1e2v3e4v2e6v5e7v3 有 4條邊。 證明思路：多于 n1條邊的路中必有重復(fù)出現(xiàn)的結(jié)點(diǎn)，反復(fù)刪去夾在兩個(gè)重復(fù)結(jié)點(diǎn)之間的邊之后，剩余的邊數(shù)不會(huì)超過 n1條邊 。（沒有重復(fù)結(jié)點(diǎn)亦沒有重復(fù)邊） 在簡(jiǎn)單圖中一條路 v0e1v1e2…e nvn，由它的結(jié)點(diǎn)序列 v0v1…v n確定，所以 簡(jiǎn)單圖的路，可由其結(jié)點(diǎn)序列表示 。 若一條路中所有的邊 e1, … , en均不相同 ,稱作跡 （ 路徑 walk） 。 學(xué)習(xí)本節(jié)要熟悉如下術(shù)語（ 22個(gè)）： 路、 路的長(zhǎng)度、 跡、 回路、 通路、 圈、 連通、 連通分支、 點(diǎn)割集、 連通圖、 割點(diǎn)、 點(diǎn)連通度、 邊割集、 邊連通度、 割邊、 可達(dá)、 單側(cè)連通、 強(qiáng)連通、 強(qiáng)分圖、 弱連通、 弱分圖、 單側(cè)分圖 掌握 5個(gè)定理，一個(gè)推論。離散數(shù)學(xué) Discrete Mathematics 課程回顧 圖的定義 ：結(jié)點(diǎn)集、邊集、圖的分類、點(diǎn)和邊的關(guān)聯(lián)、點(diǎn)與點(diǎn)的相鄰、邊與邊的鄰接、孤立結(jié)點(diǎn)、零圖、平凡圖、環(huán)、平行邊 點(diǎn)的度數(shù) ：度數(shù)、出度、入度、最大度、最小度、 握手定理 、相關(guān)定理 特殊的圖 ：多重圖、 簡(jiǎn)單圖 、 完全圖 、補(bǔ)圖、子圖、生成子圖、圖的同構(gòu) 第七章 圖論第 2講 7— 2 路與回路 72 路與回路 在實(shí)際應(yīng)用中，比如在市內(nèi)乘出租車去參觀一個(gè)博覽會(huì)，一定要司機(jī)選一條最短的路。 一、路 定義 給定 圖 G=V,E,設(shè) v0,v1,… ,vn?V， e1,… ,en?E, 其中 ei是關(guān)聯(lián)于結(jié)點(diǎn) vi1,vi的邊，交替序列 v0e1v1e2…e nvn稱為結(jié)點(diǎn) v0到 vn的 路 （ 擬路徑Pseudo path） 。 若一條路中所有的結(jié)點(diǎn) v0, v1,… , vn均不相同 ,稱作 通路 （ Path） 。 在有向圖中，結(jié)點(diǎn)數(shù)大于 1的一條路亦可由邊序列e1e2…e n表示。 定理 : Vs Vk Vj Vs Vs Vk Vj Vj Vk ? 定理 如果從結(jié)點(diǎn) vj到 vk存在一條路，該路上的結(jié)點(diǎn)序列是 vj…v i…v k，如果在這條路中有 L條邊，則序列中必有 L+1個(gè)結(jié)點(diǎn)，若 Ln1，則必有結(jié)點(diǎn) vs，它在序列中不止出現(xiàn)一次，即必有結(jié)點(diǎn)序列 vj…v s…v s…v k，在路中去掉從 vs到 vs的這些邊，仍是 vj到 vk的一條路，但此路比原來的路邊數(shù)要少，如此重復(fù)進(jìn)行下去，必可得到一條從 vj到 vk的不多于 n1條邊的路。 v1到 v3最短的路為 v1e2v3 二、無向圖的連通性 連通 定義 在無向 圖 G中，如果從結(jié)點(diǎn) u和結(jié)點(diǎn) v之間若 存在一條路，則稱結(jié)點(diǎn) u和結(jié)點(diǎn) v是連通的 （ connected） 。 把子圖 G(V1) , G(V2) , … , G(Vm)稱為圖 G的 連通分支 （ connected ponents） ,圖 G的連通
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1