軟件測試第四章測試人員的圖論-在線瀏覽
2024-11-05 20:25本頁面
【正文】 壓縮圖 東北大學(xué)軟件學(xué)院 定義 給定圖 G = (V， E)， 其壓縮圖通過用壓縮節(jié)點替代每個組件構(gòu)成 。 S1 = {n1， n2， n3， n4， n5， n6} S2 = {n7} 圈數(shù) 東北大學(xué)軟件學(xué)院 定義 ． 圖 G的圈數(shù)由 V(G) = e – n + p給出 ， 其中： e是 G中的邊數(shù) 。 p是 G中的組件數(shù) 。 有向圖例子 東北大學(xué)軟件學(xué)院 n1 n2 n4 n3 n5 n6 n7 e1 e2 e3 e4 e5 V={nl， n2， n3， n4， n5， n6， n7) E={e1， e2， e3， e4， e5}={nl， n2， nl， n4， n3， n4， n2， n5， n4， n6} 圖 42 一個有向圖 外度和內(nèi)度 東北大學(xué)軟件學(xué)院 定義 有向圖中節(jié)點的內(nèi)度 ， 是將該節(jié)點作為終止節(jié)點的不同邊的條數(shù) 。 節(jié)點 n的外度記做 outdeg(n) indeg(n1) = 0 Outdeg(n1) = 2 indeg(n2) = 1 Outdeg(n2) = 1 indeg(n3) = 0 Outdeg(n3) = 1 indeg(n4) = 2 Outdeg(n4) = 1 indeg(n5) = 1 Outdeg(n5) = 0 indeg(n6) = 1 Outdeg(n6) = 0 indeg(n7) = 0 Outdeg(n7) = 0 節(jié)點的類型 東北大學(xué)軟件學(xué)院 定義 內(nèi)度為 0的節(jié)點是源節(jié)點 。 內(nèi)度不為 0， 并且外度不為 0的節(jié)點是傳遞節(jié)點 。 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é)點 。 (有向 )半路徑是一系列邊 ， 使得對于該序列中至少有一個相鄰邊對偶 ei,ej來說 ， 第一 條邊的初始節(jié)點是第二條邊的初始節(jié)點 ， 或第一條邊的終止節(jié)點是第二條邊的終止節(jié)點 。 有向圖 D的可到達(dá)性矩陣可以通過相鄰矩陣 A計算如下： R = I+A+A2+A3+… +Ak 其中 k是 D最長路徑的長度 ， I是單位矩陣 。 l連接 ， 當(dāng)且僅當(dāng) ni和 nj之間有一條半路徑 ， 但是沒有路徑 。 3連接 ， 當(dāng)且僅當(dāng)從 ni和 nj有一條路徑 ， 并且從 nj到ni有一條路徑 。 n2和 n6是 1— 連接 。 n3和 n6是 3— 連接 。 n1
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1