結(jié)構(gòu)模型與技術(shù)ppt課件(編輯修改稿)
2025-05-26 04:13 本頁面
【文章內(nèi)容簡介】 我們稱賦權(quán)圖為網(wǎng)絡(luò)，賦權(quán)有向圖為有向網(wǎng)絡(luò)，賦權(quán)無向圖為無向網(wǎng)絡(luò)。V3 V5V4V2V6V1V3 V5V4V2V6V1圖 5a b 樹、最小支撐樹在各式各樣的圖中，有一類圖極其簡單而卻是很有用的。例： 一支由五個(gè)城市，要在其之間架電話線，要求任兩個(gè)城市都可以互相通話（允許通過其他城市），并且電話線根數(shù)最少。解：用 V1， … ， V5五個(gè)點(diǎn)代表五個(gè)城市，若在某兩城市之間架設(shè)電話線，則在相應(yīng)的兩個(gè)點(diǎn)之間連一條邊，這樣一個(gè)電話網(wǎng)就可以用一個(gè)圖來表示。為使任兩個(gè)城市之間都可以通話，這樣的圖必須是連通的，其次，若圖中有圈的話，從圈上任意去掉一條邊，余下的圖仍是連通的，這樣可省去一根電話線。因而要求得到滿足的電話網(wǎng)所對應(yīng)的圖必定是不含圈的連通圖。（樹可滿足這一要求）V1V4V2V3 V5五城市電話網(wǎng) 例： 某廠組織機(jī)構(gòu)，用樹表示。 樹：一個(gè)無圈的連通圖稱為樹，通常以 T表示。從定義推出性質(zhì)：（ 1）具有 n個(gè)頂點(diǎn)的樹，其邊數(shù)恰好為 n1條。（ 2）樹的任意兩頂點(diǎn)之間有且僅有一條鏈。（ 3）在樹 T中去掉任一條邊，則 T成為不連通圖。（ 4）在樹 T中不相鄰的兩個(gè)頂點(diǎn)間添上一條邊，則恰好得到一個(gè)圈。進(jìn)一步地說，若再從這個(gè)圈上任意去掉一條邊，則可得到一個(gè)樹。（ 5）圖的支撐樹：設(shè)圖 T=（ V， E）是圖 G=（ V， E）的支撐子圖，若圖 T=（ V， E’）是一個(gè)樹，則稱 T是 G的一個(gè)支撐樹。如圖 5b是圖 5a的一個(gè)支撐樹。V3 V5V4V2V6V1V3 V5V4V2V6V1圖 5a b由此可得出兩種尋求連通圖的支撐樹的方法。（ 1）破圖法：在圖 G中任取一個(gè)圈，從圈中去掉一邊，對余下的圖中重復(fù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1