圖與網(wǎng)絡規(guī)劃ppt課件(編輯修改稿)
2025-02-13 17:00 本頁面
【文章內容簡介】 圖的連通性 1．鏈的概念 ：在圖 G中，由兩兩相鄰的點 及其相關聯(lián)的邊 構成的點邊序列 （其中 與 關聯(lián)）稱為鏈。其中 稱為鏈的起點，稱為鏈的終點。 01, , , nv v v12, , , le e e 0 1 1 2 2 1, , , , , , , ,n n nv e v e v v e v?ke 1,kkvv? 0v nv2．開鏈與閉鏈 ：若 ，則稱該鏈為開鏈，反之稱為閉鏈或回路。 0 nvv?3．若鏈中所含的邊均不相同，則稱為 簡單鏈 ；若點均不相同，則稱為 初等鏈或通路 。除起點和終點外點均不同的閉鏈，稱為 初等回路或圈 。 4． 若一個圖的任意兩點之間均至少有一條通路（初等鏈）連接起來，則稱這個 圖 G是一個連通圖 ，否則稱作 非連通圖 。如果一個問題所對應的圖是一個非連通圖，則該問題一定可以分解成互不相關的子問題來加以研究， 即可以把不連通的圖分解成連通的子圖來考慮 。 有向圖 1. 無向圖 ：邊是沒有方向的，如溝通關系 。 2. 有向圖 ：邊是有方向的， ，如誰指揮誰的關系，表示為 ， V是頂點集， A是有向邊的集合 。 ij jiee?( , )D V A?3. 有向圖中的鏈 ：在不考慮方向時，可以與無向圖一樣定義鏈 。 4. 有向圖中的路與初等路 ：若有向圖 中， P是從 u到 v的鏈，且對 P中每一條弧而言，在序列中位于該弧前面的點恰好是其起點，而位于該弧后面的點恰好是其終點，這個鏈 P就稱為是 D中從 u到 v的一條路。頂點都不相同的路稱為 初等路 。 ( , )D V A?5. 有向圖中的回路與初等回路 ：當有向圖中路的起點和終點相同時，即 時，稱作 回路 。除起點和終點外點均不相同的回路稱為 初等回路 。 6. 連通圖與非連通圖 ：若在有向圖 D中，任意兩點間均存在一條鏈，則稱 D是連通圖，否則稱為非連通圖。 7. 強連通與非強連通 ：若在 D的任意兩點之間存在互通的路，則稱 D為強連通，否則稱為非強連通圖。 uv?
教學課件相關推薦
鄂ICP備17016276號-1