圖論及其應(yīng)用ppt-展示頁
2025-08-03 15:19本頁面
【正文】 其應(yīng)用 任課教師：楊春 數(shù)學(xué)科學(xué)學(xué)院 1 0 x t 0 1 2 ?1 ? 0 1 n 2 第二章 樹 本章主要內(nèi)容 一、樹的概念與性質(zhì) 二、生成樹 三、最小生成樹 授課學(xué)時 授課學(xué)時： 6學(xué)時 1 0 x t 0 1 2 ?1 ? 0 1 n 3 本次課主要內(nèi)容 (一 )、樹的概念與應(yīng)用 (二 )、樹的性質(zhì) (三 )、樹的中心與形心 1 0 x t 0 1 2 ?1 ? 0 1 n 4 樹的概念 (一 )、樹的概念與應(yīng)用 定義 1 不含圈的圖稱為無圈圖，樹是連通的無圈圖。 例如：下面的圖均是樹 樹 T1 樹 T2 樹 T3 樹 T4 1 0 x t 0 1 2 ?1 ? 0 1 n 5 定義 2 稱無圈圖 G為森林。 (2) 樹與森林都是偶圖。 解：按樹中存在的最長路進(jìn)行枚舉。 1 0 x t 0 1 2 ?1 ? 0 1 n 6 樹是圖論中應(yīng)用最為廣泛的一類圖。在實(shí)際問題中，許多實(shí)際問題的圖論模型就是樹。如此得到的圖，是一顆樹，稱為根樹。 例 3 道路的鋪設(shè)與樹 假設(shè)要在某地建造 4個工廠，擬修筑道路連接這 4處?，F(xiàn)在每條邊的長度已經(jīng)測出并標(biāo)記在圖的對應(yīng)邊上，如果我們要求鋪設(shè)的道路總長度最短，這樣既能節(jié)省費(fèi)用 ，又能縮短工期 ，如何鋪設(shè)？ v2 v 3 v 4 e 2 e 3 e 4 v 1 e 1 e 5 e6 1 0 x t 0 1 2 ?1 ? 0 1 n 8 該問題歸結(jié)于在圖中求所謂的最小生成樹問題。 例 4 化學(xué)中的分子結(jié)構(gòu)與樹 例如： C4H10的兩種同分異構(gòu)結(jié)構(gòu)圖模型為： h h h h h h h h h h h h h h h h h h h h 1 0 x t 0 1 2 ?1 ? 0 1 n 9 例 5 電網(wǎng)絡(luò)中獨(dú)立回路與圖的生成樹 早在 19世紀(jì)，圖論還沒有引起人們關(guān)注的時候，物理學(xué) 家克希荷夫就已經(jīng)注意到電路中的獨(dú)立回路與該電路中的所 謂生成樹的關(guān)系。 例 6 通信網(wǎng)絡(luò)中的組播樹 在單播模型中，數(shù)據(jù)包通過網(wǎng)絡(luò)沿著單一路徑從源主機(jī)向 目標(biāo)主機(jī)傳遞，但在組播模型中，組播源向
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1