圖與網(wǎng)絡(luò)規(guī)劃ppt課件-在線瀏覽
2025-03-06 17:00本頁面
【正文】 的端點(diǎn)；而邊 稱為與節(jié)點(diǎn) 關(guān)聯(lián)的邊。 2．圖 G的頂點(diǎn)數(shù) ：集合 V中元素的個數(shù)。 ()qG,uv,ijee,ijee,uv6．環(huán) ：若一條邊的兩個端點(diǎn)（起點(diǎn)和終點(diǎn)）是同一個頂點(diǎn)，稱該邊為環(huán)（ loop）。無環(huán)也無多重邊的圖稱為簡單圖。 9．奇數(shù)節(jié)點(diǎn)（ 奇點(diǎn) ） — 度為奇數(shù)的節(jié)點(diǎn)。 10．懸掛點(diǎn)與懸掛邊 ：度為 1 的點(diǎn)稱為懸掛點(diǎn)，與懸掛點(diǎn)連接的邊稱為懸掛邊 。 圖的連通性 1．鏈的概念 ：在圖 G中，由兩兩相鄰的點(diǎn) 及其相關(guān)聯(lián)的邊 構(gòu)成的點(diǎn)邊序列 （其中 與 關(guā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．開鏈與閉鏈 ：若 ，則稱該鏈為開鏈，反之稱為閉鏈或回路。除起點(diǎn)和終點(diǎn)外點(diǎn)均不同的閉鏈，稱為 初等回路或圈 。如果一個問題所對應(yīng)的圖是一個非連通圖，則該問題一定可以分解成互不相關(guān)的子問題來加以研究， 即可以把不連通的圖分解成連通的子圖來考慮 。 2. 有向圖 ：邊是有方向的， ，如誰指揮誰的關(guān)系，表示為 ， V是頂點(diǎn)集， A是有向邊的集合 。 4. 有向圖中的路與初等路 ：若有向圖 中， P是從 u到 v的鏈，且對 P中每一條弧而言，在序列中位于該弧前面的點(diǎn)恰好是其起點(diǎn)，而位于該弧后面的點(diǎn)恰好是其終點(diǎn)，這個鏈 P就稱為是 D中從 u到 v的一條路。 ( , )D V A?5. 有向圖中的回路與初等回路 ：當(dāng)有向圖中路的起點(diǎn)和終點(diǎn)相同時，即 時，稱作 回路 。 6. 連通圖與非連通圖 ：若在有向圖 D中，任意兩點(diǎn)間均存在一條鏈，則稱 D是連通圖，否則稱為非連通圖。 uv?樹 1. 林 ：一個沒有圈的圖稱為林 。 3. 部分樹 ：若 T是圖 的部分圖，且 T是樹，則稱 T為 G的部分樹。 T路 (通路 )
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1