圖與網(wǎng)絡(luò)分析ppt課件-在線瀏覽
2025-03-03 12:34本頁面
【正文】 , E2 ?E1 稱 G2 是 G1 的 子圖 ；如果 V2 = V1 , E2 ?E1 稱 G2 是 G1 的部分圖或 支撐子圖 。 有向圖中 ， 以 vi 為始點(diǎn)的邊數(shù)稱為點(diǎn) vi的 出次 ， 用 表示 ；以 vi 為終點(diǎn)的邊數(shù)稱為點(diǎn) vi 的 入次 ， 用 表示； vi 點(diǎn)的出次和入次之和就是該點(diǎn)的次 。 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 d(v1)= ？ 4 d(v2)= ？ 3 度（次） 定理 1 所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的 2倍。懸掛點(diǎn)的關(guān)聯(lián)邊稱為 懸掛邊 。 ? 有向完全圖 則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡單圖。 ? 一個(gè)無環(huán)，無多重邊的圖稱為 簡單圖 ，一個(gè)無環(huán)，有多重邊的圖稱為 多重圖 。 ? ?jvV ?}{ keE ?jv keVv1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 例 ? ?654321 , vvvvvvV ?},{ 10987654321 eeeeeeeeeeE ，?},{ 211 vve ? },{ 212 vve ?},{ 323 vve ? },{ 434 vve ?},{ 315 vve ? },{ 536 vve ?},{ 537 vve ? },{ 658 vve ?},{ 669 vve ? },{ 6110 vve ?圖 1 v4 v6 v1 v2 v3 v5 V = {v1 , v2 , v3 , v4 , v5 , v6 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) } 無向圖與有向圖 ? 如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無向圖（ undirected graph） ? 如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖(directed graph)，記作 D=(V, A) 簡單圖與完全圖 ? 一條邊的兩個(gè)端點(diǎn)是相同的 ,那么稱為這條邊是 環(huán) 。本講學(xué)習(xí)目標(biāo) ? 圖與網(wǎng)絡(luò)的基本知識 ? 樹及最小支撐樹問題 ? 最短路問題 ? 網(wǎng)絡(luò)最大流問題 ? 最小費(fèi)用最大流問題 圖與網(wǎng)絡(luò)的基本知識 B D A C A B C D 哥尼斯堡七橋問題 一筆畫問題 歐拉 E A D C B 一個(gè)圖是由點(diǎn)和連線組成。（連線可帶箭頭，也可不帶，前者叫 弧 ，后者叫 邊 ） 圖的組成與表示 一個(gè)圖是由點(diǎn)集 和 中元素的無序?qū)Φ囊粋€(gè)集合 構(gòu)成的二元組 ， 記為 G =(V， E)， 其中 V 中的元素 叫做頂點(diǎn) ,V 表示圖 G的點(diǎn)集合； E中的元素 叫做邊 ， E 表示圖 G 的邊集合 。 ? 如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)?多重邊 。 ? 每一對頂點(diǎn)間都有邊相連的無向簡單圖稱為 完全圖 。 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 ? 以點(diǎn) v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn) v 的 度（次） ，記作d(v) ? 度為零的點(diǎn)稱為 弧立點(diǎn) ，度為 1的點(diǎn)稱為 懸掛點(diǎn) 。度為奇數(shù)的點(diǎn)稱為 奇點(diǎn) ，度為偶數(shù)的點(diǎn)稱為 偶點(diǎn) 。 所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。 入次與出次有這樣的關(guān)系： )( ivd?)( ivd?定理 2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 v1 v2 v3 v4 v5 v6 v7 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 (a) e5 e7 v1 v2 v5 v6 v7 e1 e6 e8 (b) 子圖 v1 v2 v3 v4 v5 v6 v7 e1 e6 e7 e9 e10 e11 (c) 支撐子圖 子圖與支撐子圖 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為 鏈 。 網(wǎng)絡(luò) 給定一個(gè)圖 G=(V,E)或有向圖 D=(V,A),在 V中指定兩個(gè)點(diǎn)，一個(gè)稱為始點(diǎn) (或發(fā)點(diǎn) ),記作 v1,一個(gè)稱為終點(diǎn)(或收點(diǎn) ),記作 vn，其余的點(diǎn)稱為中間點(diǎn)。通常把這種賦權(quán)的圖稱為 網(wǎng)絡(luò) 。 樹中次為 1的點(diǎn)稱為 樹葉 ，次大于 1的點(diǎn)稱為分支點(diǎn)。 ? 樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。 ? 樹無回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。 ),( 39。EVK ?生成樹 如果圖 是圖 G的一個(gè)生成樹 ， 那么稱 E‘上所有邊的權(quán)的和為生成樹 T 的權(quán) ， 記作 S(T)。 ),( 39。 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 5 v1 v2 v3 v4 v5 v6 1 2 3 4 4 求最小支撐樹的方法 ? 避圈法 ? 將所有邊按權(quán)值從小到大排序，每次從未選的邊中選一條權(quán)最小的，逐步銜接，但不接成圈 ? 破圈法 ? 任取一個(gè)圈，從中去掉權(quán)最大的邊。即： 最小。 vi 為剛得到 P標(biāo)號的點(diǎn)，考慮點(diǎn) vj， 其中 ，且 vj為 T標(biāo)號。若全部節(jié)點(diǎn)均為 P標(biāo)號，則停止，否則用 vk代替 vi， 返回步驟（ 2）。 v1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 解 （ 1） 首先給 v1以 P標(biāo)號 ， 給其余所有點(diǎn) T標(biāo)號 。 顯然 ， 從 v1到 vj的最短路是從 v1出發(fā) ， 沿著這條路到某個(gè)點(diǎn) vi再沿弧 (vi,vj)到 vj， 則 v1到 vi的這條路必然也是 v1到 vi的所有路中的最短路 。 第 2步，使用遞推公式： 求 ，當(dāng)進(jìn)行到第 t步，若出現(xiàn) 停止計(jì)算， 即為 v1到各點(diǎn)的最短路長。 第 i年度 1 2 3 4 5 購置費(fèi) 11 11 12 12 13
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1