測試人員的圖論ppt課件(編輯修改稿)
2025-05-28 06:59 本頁面
【文章內(nèi)容簡介】 節(jié)點的類型 東北大學(xué)軟件學(xué)院 定義 內(nèi)度為 0的節(jié)點是源節(jié)點 。 外度為 0的節(jié)點是吸收節(jié)點 。 內(nèi)度不為 0， 并且外度不為 0的節(jié)點是傳遞節(jié)點 。 有向圖的相鄰矩陣 東北大學(xué)軟件學(xué)院 定義 有 m個節(jié)點的有向圖 D = (V， E)的相鄰矩陣是一種m m矩陣： A = (a(i， j))， 其中 a(i， j)是 1， 當(dāng)且僅當(dāng)從節(jié)點 i到節(jié)點 j有一條邊 ， 否則該元素為 0。 n1 n2 n3 n4 n5 n6 n7 n1 0 1 0 1 0 0 0 n2 0 0 0 0 1 0 0 n3 0 0 0 1 0 0 0 n4 0 0 0 0 0 1 0 n5 0 0 0 0 0 0 0 n6 0 0 0 0 0 0 0 n7 0 0 0 0 0 0 0 路徑和半路徑 東北大學(xué)軟件學(xué)院 定義 (有向 )路徑是一系列邊 ， 使得對于該序列中的所有相鄰邊對偶 ei,ej來說 ， 第一條邊的終止節(jié)點是第二條邊的初始節(jié)點 。 環(huán)路是一個在同一個節(jié)點上開始和結(jié)束的有向路徑 。 (有向 )半路徑是一系列邊 ， 使得對于該序列中至少有一個相鄰邊對偶 ei,ej來說 ， 第一 條邊的初始節(jié)點是第二條邊的初始節(jié)點 ， 或第一條邊的終止節(jié)點是第二條邊的終止節(jié)點 。 可到達(dá)性矩陣 東北大學(xué)軟件學(xué)院 定義 有 m個節(jié)點的有向圖 D = (V， E)的可達(dá)性矩陣是一種 m m矩陣 R = (r(i,j))， 其中 r(i， j)是 1， 當(dāng)且僅當(dāng)從節(jié)點 i到節(jié)點 j有一條路徑 ， 否則該元素為 0。 有向圖 D的可到達(dá)性矩陣可以通過相鄰矩陣 A計算如下： R = I+A+A2+A3+… +Ak 其中 k是 D最長路徑的長度 ， I是單位矩陣 。 圖 42的可到達(dá)性矩陣 東北大學(xué)軟件學(xué)院 n1 n2 n3 n4 n5 n6 n7 n1 0 1 0 1 1 1 0 n2 0 0 0 0 1 0 0 n3 0 0 0 1 0 1 0 n4 0 0 0 0 0 1 0 n5 0 0 0 0 0 0 0 n6 0 0 0 0 0 0 0 n7 0 0 0 0 0 0 0 n連接性 東北大學(xué)軟件學(xué)院 定義 有向圖中的兩個節(jié)點 ni和 nj是： 0連接 ， 當(dāng)且僅當(dāng) ni和 nj之間沒有路徑 。 l連接 ， 當(dāng)且僅當(dāng) ni和 nj之間有一條半路徑 ， 但是沒有路徑 。 2連接 ， 當(dāng)且僅當(dāng) 從 ni和 nj之間有一條路徑 。 3連接 ， 當(dāng)且僅當(dāng)從 ni和 nj有一條路徑 ， 并且從 nj到ni有一條路徑 。 圖 42的連接性 東北大學(xué)軟件學(xué)院 n1和 n7是 0— 連接 。 n2和 n6是 1— 連接 。 n1和 n6是 2— 連接 。 n3和 n6是 3— 連接 。 n1 n2 n4 n3 n5 n6 n7 e1 e2 e3 e4 e5 強組件 東北大學(xué)軟件學(xué)院 定義 有向圖的強組件是 3連接節(jié)點的最大集
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1