《離散數(shù)學(xué)之圖論》ppt課件-全文預(yù)覽
【正文】 簡(jiǎn)單通路 ? 各點(diǎn)全不同的通路叫做基本通路 ? 基本通路必是簡(jiǎn)單通路，反之不然 通路、回路、連通性 ? 一條通路，若起點(diǎn)終點(diǎn)是同一個(gè)結(jié)點(diǎn)，則稱之為回路； ? 各邊全不同的回路叫做簡(jiǎn)單回路 ? 各點(diǎn)全不同的回路叫做基本回路 ? 一個(gè)通路，若刪除其中所有回路，則得基本通路；一個(gè)回路，若刪除除自己外的所有回路，則得基本回路 ? 定理：對(duì)于有向 (n,m)圖中，任何基本通路長(zhǎng)度均小于等于 n1，任何基本回路的長(zhǎng)度小于或等于 n 通路、回路、連通性 ? 可達(dá)性 ? 從一個(gè)有向圖的結(jié)點(diǎn) V1到 V2之間若存在一個(gè)通路，則稱從 V1到 V2是可達(dá)的 ? 結(jié)點(diǎn)間的距離 ? 兩個(gè)可達(dá)結(jié)點(diǎn)間可能存在多條通路，最短的（經(jīng)過(guò)的邊數(shù)最少）那條通路中邊的個(gè)數(shù)稱為兩結(jié)點(diǎn)間的距離 通路、回路、連通性 ? 對(duì)于無(wú)向圖 ? 可以化解為有向圖，于是上述定義均可應(yīng)用到無(wú)向圖中 通路、回路、連通性 ? 連通性 ? 無(wú)向圖：若任何兩個(gè)結(jié)點(diǎn)間均可達(dá)，則稱為連通圖 ，否則叫做非連通圖 ? 有向圖：若任何兩個(gè)結(jié)點(diǎn)間均相互可達(dá)，則稱為 強(qiáng)連通圖 ，若任何兩個(gè)結(jié)點(diǎn)間至少有一個(gè)方向是可達(dá)的，則稱為 單向連通圖 ，若忽略掉邊的方向得到的無(wú)向圖是連通的，則稱為 弱連通圖 ? P127 圖 歐拉圖 ? 圖 G的一個(gè)回路，若通過(guò) G的每條邊一
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1