軟件測試第四章測試人員的圖論-文庫吧資料
2024-10-08 20:25本頁面
【正文】 e1 e2 e3 e4 e5 強組件 東北大學軟件學院 定義 有向圖的強組件是 3連接節(jié)點的最大集合 。 n1和 n6是 2— 連接 。 圖 42的連接性 東北大學軟件學院 n1和 n7是 0— 連接 。 2連接 ， 當且僅當 從 ni和 nj之間有一條路徑 。 圖 42的可到達性矩陣 東北大學軟件學院 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連接性 東北大學軟件學院 定義 有向圖中的兩個節(jié)點 ni和 nj是： 0連接 ， 當且僅當 ni和 nj之間沒有路徑 。 可到達性矩陣 東北大學軟件學院 定義 有 m個節(jié)點的有向圖 D = (V， E)的可達性矩陣是一種 m m矩陣 R = (r(i,j))， 其中 r(i， j)是 1， 當且僅當從節(jié)點 i到節(jié)點 j有一條路徑 ， 否則該元素為 0。 環(huán)路是一個在同一個節(jié)點上開始和結束的有向路徑 。 有向圖的相鄰矩陣 東北大學軟件學院 定義 有 m個節(jié)點的有向圖 D = (V， E)的相鄰矩陣是一種m m矩陣： A = (a(i， j))， 其中 a(i， j)是 1， 當且僅當從節(jié)點 i到節(jié)點 j有一條邊 ， 否則該元素為 0。 外度為 0的節(jié)點是吸收節(jié)點 。 節(jié)點 n的內度記做 indeg(n) 有向圖中節(jié)點的外度 ， 是將該節(jié)點作為開始節(jié)點的不同邊的條數(shù) 。 有向圖 東北大學軟件學院 定義 有向圖 （ 或框圖 ） D = (V， E)包含：一個節(jié)點的有限集合 V = (n1， n2， … ， nm)， 一個邊的集合 E = e1， e2， … ，ep}， 其中每條邊 ek = ni， nj是節(jié)點 ni、 nj∈ V的一個有序 對偶 。 n是 G中的節(jié)點數(shù) 。 給定圖的壓縮圖是惟一的 。 等價類中的節(jié)點是圖的組件 。 3． 連接性是傳遞的 。 為了說明這一點 ， 可以再復習一遍定義等價關系的三個性質： 1． 連接性是自反的 ， 因為每個節(jié)點顯然都在到其本身長度為 0的路徑上 。 路徑 節(jié)點序列 邊序列 n1和 n5之間 n1， n2， n5 e1， e4 n6和 n5之間 n6， n4， n1， n2， n5 e5， e2 ， e1， e4 n3和 n2之間 n3， n4， n1 ， n5 e3， e2 ， e1 連接性 東北大學軟件學院 定義 節(jié)點 ni和 nj是被連接的 ， 當且僅當它們都在同一條路徑上 。 路徑可以描述為一系列邊 ， 也可以描述為一系列節(jié)點 。 e1 e2 e3 e4 e5 n1 1 1 0 0 0 n2 1
醫(yī)療健康相關推薦
鄂ICP備17016276號-1