運(yùn)籌學(xué)圖與網(wǎng)絡(luò)ppt課件-在線瀏覽
2025-06-29 13:31本頁面
【正文】 兩重邊 。 ? 無環(huán)也無多重邊的圖稱作 簡(jiǎn)單圖 。 ? 次為 1的點(diǎn)稱為 懸掛點(diǎn) ，與懸掛點(diǎn)連接的邊稱作懸掛邊 ； ? 次為 0的點(diǎn)稱為 孤立點(diǎn) 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 定理 ? 若圖 G中所有點(diǎn)都是孤立點(diǎn)，則稱圖 G為 空?qǐng)D 。即 qdV2)( ?????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 ? 定理 2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。由定理1有 qddVV2)()(21?? ???? ????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 鏈 ? 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為 鏈 。 ? 若 v0 ≠vn則稱該鏈為開鏈 ，反之稱為 閉鏈 或 回路 。 ? 除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的閉鏈，稱為初等回路 或稱為 圈 。 4312211 , ???? eee圈 ? 若鏈中所含的邊均不相同，則稱為 簡(jiǎn)單鏈 ；若點(diǎn)均不相同，則稱為 初等鏈 或 通路 。 ? 例如圖中 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 是一個(gè)圈。 ? 例如圖中， v1和 v6之間沒有通路，因此它不是連通圖，而如果去掉 v6，則構(gòu)成一個(gè)連通圖。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 子圖 ? 子圖的定義 設(shè)， G1=(V1,E1), G2=(V2,E2)，如果 V1?V2 ，又 E1?E2 ，則稱 G1是 G2的 子圖 。 特殊子圖 ? 當(dāng) G1中不包含 G2中所有的頂點(diǎn)和邊，則稱 G1是G2的 真子圖 。 ? 若 V1?V2 ， ? E1={ [u,v] | u∈ V1, v∈ V1}，則稱 G1是 G2中 由 V1導(dǎo)出的 導(dǎo)出子圖 。 ? 而有些關(guān)系是不對(duì)稱的，例如父子關(guān)系、上下級(jí)關(guān)系、加工工序的先后順序等都具有單向性，用圖來表示這些關(guān)系時(shí)，得到的邊是具有方向的，用帶箭頭的線來表示，稱為 弧 。仍以 V表示點(diǎn)的集合，以 A表示弧的集合，則有向圖表示為 D＝（ V， A） 有向圖例 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 有向圖的鏈路 ? 有向圖中，在不考慮邊的方向時(shí)，也可以相同地定義 鏈 ，若有向圖 D＝（ V， A）中， P是一個(gè)從 u到 v的鏈，且對(duì) P中每一條弧而言，在序列中位于該弧前面的點(diǎn)恰好是其起點(diǎn)，而位于該弧后面的點(diǎn)恰好是其終點(diǎn)，這個(gè)鏈 P就稱為是 D中從 u到 v的一條 路 。 ? 頂點(diǎn)全不相同的路稱為 初等路 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 樹及最小樹問題 ■ 任何樹至少有一個(gè)懸掛節(jié)點(diǎn) 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 ■ 如果樹的節(jié)點(diǎn)個(gè)數(shù)為 m，則邊的個(gè)數(shù)為 m1 ■ 樹中任意兩個(gè)節(jié)點(diǎn)之間只有唯一的一條鏈 ■ 在樹的任意兩個(gè)不相鄰的節(jié)點(diǎn)之間增加一條邊，則形成唯一的圈 樹及最小樹問題 ? 一個(gè)沒有圈的圖稱為一個(gè) 無圈圖 或稱為 林 。 定理 以下關(guān)于樹的六種不同描述是等價(jià)的： 1. 無圈連通圖 。 3. 連通 ， q=p1。 5. 連通 ， 但若任意舍棄一條邊 ， 圖便不連通 。 網(wǎng)絡(luò)概念 ? 圖只能用來研究事物之間有沒有某種關(guān)系 ， 而不能研究這種關(guān)系的強(qiáng)弱程度 。 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 網(wǎng)絡(luò)概念 ? 節(jié)點(diǎn)與（有向）邊 每一條邊和兩個(gè)節(jié)點(diǎn)關(guān)聯(lián)，一條邊可以用兩個(gè)節(jié)點(diǎn)的標(biāo)號(hào)表示（ i， j） j i ■ 路徑（ Path） 前后相繼并且方向相同的邊序列 P={(1,2),(2,3),(3,4)} 4 2 3 1 4 2 3 1 ■ 網(wǎng)絡(luò)由節(jié)點(diǎn)和邊組成 網(wǎng)絡(luò)概念 ■ 回路（ Circuit） 起點(diǎn)和終點(diǎn)重合的路徑稱為 回路 μ={(1,2),(2,4),(4,1)} 回路中各條邊方向相同 4 2 3 1 ■ 鏈（ Chain） 前后相繼并且方向不一
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1