圖與網(wǎng)絡(luò)1(編輯修改稿)
2024-10-22 17:10 本頁面
【文章內(nèi)容簡介】 列成點(diǎn)和邊的交錯(cuò)序列，則稱此為一條鏈。 定義（圈）如一條鏈中起點(diǎn)和終點(diǎn)重合，則稱此為一條圈。 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向圖 v1 v5 v4 v2 e1 e7 e6 e3 v1 v5 v4 v2 e1 e7 e6 e3 圈 二、圖的矩陣表示 一個(gè)圖非常直觀，但是不容易計(jì)算，特別不容易在計(jì)算機(jī)上進(jìn)行計(jì)算，一個(gè)有效的解決辦法是將圖表示成矩陣形式，通常采用的矩陣是鄰接矩陣、邊長鄰接矩陣、弧長矩陣和關(guān)聯(lián)矩陣。 1 鄰接矩陣 鄰接矩陣 A表示圖 G的頂點(diǎn)之間的鄰接關(guān)系，它是一個(gè) nxn的矩陣，如果兩個(gè)頂點(diǎn)之間有邊相聯(lián)時(shí)，記為 1，否則為 0。 v1 v2 v3 v4 2 5 6 4 3 4 v1 v2 v3 v4 v1 0 1 1 1 v2 1 1 1 0 v3 1 1 0 1 v4 1 0 1 0 無向圖的鄰接矩陣是對稱矩陣。 v1 v5 v4 v3 v2 也可以對有向圖 v1 v2 v3 v4 v5 v1 0 0 0 1 1 v2 1 0 0 1 0 v3 0 1 1 0 0 v4 0 1 1 0 1 v5 1 0 0 1 0 二、邊長鄰接矩陣 在圖的各邊上一個(gè)數(shù)量指標(biāo)，具體表示這條邊的權(quán)（距離，單價(jià)，通過能力等） —— 賦權(quán)圖或網(wǎng)絡(luò)。 無向網(wǎng)絡(luò)；有向網(wǎng)絡(luò)；混合網(wǎng)絡(luò)；邊權(quán)網(wǎng)絡(luò)；點(diǎn)權(quán)網(wǎng)絡(luò)； 以邊長代替鄰接矩陣中的元素得到邊長鄰接矩陣。 v1 v2 v3 v4 2 5 6 4 3 4 v1 v2 v3 v4 v1 0 2 5 6 v2 2 4 3 ? v3 5 3 0 4 v4 6 ? 4 0 其中 ?表示兩點(diǎn)之間不能連接 。 3 弧長矩陣 對有向圖的弧可以用弧長矩陣來表示。其中 ?表示兩點(diǎn)之間沒有 弧 連接 。 v1 v5 v4 v3 v2 1 4 2 3 2 2 6 1 2 v1 v2 v3 v4 v5 v1 0 1 ? ? 2 v2 ? 0 2 ? 4 v3 ? 2 0 1 ? v4 ? 3 2 0 6 v5 ? ? ? ? 0 4 關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1