離散數學之圖論ppt課件(編輯修改稿)
2025-05-29 05:11 本頁面
【文章內容簡介】 自圈、無平行邊 圖的基本概念 ? 補圖 ? 有圖 G=V,E及其生成子圖 G’=V,E’，若 V, E’∪ E是完全圖，且 E’∩ E=?，則稱G’是 G的補圖 ? G的補圖的補圖是其自身 圖的基本概念 ? 圖的同構 ? 有圖 G=V,E和 G’=V’,E’，若結點間存在一一對應關系，且這種對應關系也體現(xiàn)在表示邊的結點對中，則 G、 G’同構 ? 有圖 G=V,E和 G’=V’,E’，若存在 雙射 f：V→ V’ 和雙射 g： E→ E’, 使得對于任意 e∈ E及 v1, v2 ∈ V都有： g(e)=(f(v1), f(v2)), 若 e=(v1, v2) ? , 圖 , 圖 圖的基本概念 ? 多重圖 ? 含平行邊的圖叫做多重圖 ? 不含平行邊且不含自圈的圖叫做簡單圖 ? 圖 8. 13 ? 帶權圖（加權圖） ? 描述邊的一些性質，因為邊只代表結點間的連接關系； ? 舉例：物流求最短路徑 通路、回路、連通性 ? 先討論有向圖，若 G=V,E中有一個邊的序列為 (v1,v2)(v2,v3)… (vk1,vk)，即其中每條邊均首尾相連，可簡寫為(v1,v2,v3… vk1,vk)，這是圖 G中的一個通路，其中 v1叫起點、 vk叫終點 ? 允許出現(xiàn)相同的結點和邊 ? 各邊全不同的通路叫做
教學課件相關推薦
鄂ICP備17016276號-1