路與回路ppt課件-展示頁(yè)
2025-05-12 18:30本頁(yè)面
【正文】 ： v5e8v4e5v2e6v5e7v3e4v2 通路： v4e8v5e6v2e1v1e2v3 圈： v2e1v1e2v3e7v5e6v2 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 v2 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 從 v1到v3的一條路，長(zhǎng)度為 6 從 v5到 v2的一條跡，長(zhǎng)度為 5 從 v4到v3的一條通路，長(zhǎng)度為 4 從 v2到v2的一條圈，長(zhǎng)度為 4 定理 在一個(gè)具有 n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn) vj到結(jié)點(diǎn) vk存在一條路，則從結(jié)點(diǎn) vj到結(jié)點(diǎn)vk必存在一條不多于 n1條邊的路 。 在有向圖中，結(jié)點(diǎn)數(shù)大于 1的一條路亦可由邊序列e1e2…e n表示。 注 ：通路都是跡，跡不都是通路。 若一條路中所有的結(jié)點(diǎn) v0, v1,… , vn均不相同 ,稱作 通路 （ Path） 。 當(dāng) v0=vn時(shí)，這條路稱作 回路 （ 閉路徑 closed walk） 。 一、路 定義 給定 圖 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） 。這就是 路與回路 的問題。離散數(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ī)選一條最短的路。到博覽會(huì)后，最好選一條這樣的路徑，使得每個(gè)展臺(tái)都參觀一次后，再回到原來存包處。 學(xué)習(xí)本節(jié)要熟悉如下術(shù)語(yǔ)（ 22個(gè)）： 路、 路的長(zhǎng)度、 跡、 回路、 通路、 圈、 連通、 連通分支、 點(diǎn)割集、 連通圖、 割點(diǎn)、 點(diǎn)連通度、 邊割集、 邊連通度、 割邊、 可達(dá)、 單側(cè)連通、 強(qiáng)連通、 強(qiáng)分圖、 弱連通、 弱分圖、 單側(cè)分圖 掌握 5個(gè)定理，一個(gè)推論。 v0和 vn分別稱為路的 起點(diǎn) 和 終點(diǎn) ， 邊的數(shù)目 n稱作路的 長(zhǎng)度 。 若一條路中所有的邊 e1, … , en均不相同 ,稱作跡 （ 路徑 walk） 。 閉的通路 ,即除 v0=vn之外，其余結(jié)點(diǎn)均不相同的路，稱作 圈 （ 回路 circuit） 。（沒有重復(fù)結(jié)點(diǎn)亦沒有重復(fù)邊） 在簡(jiǎn)單圖中一條路 v0e1v1e2…e nvn，由它的結(jié)點(diǎn)序列 v0v1…v n確定，所以 簡(jiǎn)單圖的路，可由其結(jié)點(diǎn)序列表示 。 路長(zhǎng)度 ：邊的數(shù)目 n。 證明思路：多于 n1條邊的路中必有重復(fù)出現(xiàn)的結(jié)點(diǎn)，反復(fù)刪去夾在兩個(gè)重復(fù)結(jié)點(diǎn)之間的邊之后，剩余的邊數(shù)不會(huì)超過 n1條邊 。 ? 定理
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1