軟件測試第四章測試人員的圖論-展示頁
2024-10-10 20:25本頁面
【正文】 0 0 1 0 n3 0 0 1 0 0 n4 0 1 1 0 1 n5 0 0 0 1 0 n6 0 0 0 0 1 n7 0 0 0 0 0 相鄰矩陣 東北大學(xué)軟件學(xué)院 定義 擁有 m個節(jié)點(diǎn)和 n條邊的圖 G=(V， E)的相鄰矩陣是一種m m矩陣 ， 其中第 i行第 j列的元素是 1， 當(dāng)且僅當(dāng)節(jié)點(diǎn) i和節(jié)點(diǎn) j之間存在一條邊 ， 否則該元素是 0。我們把節(jié)點(diǎn) n的度記做 deg(n)。 V={n1， n2， … ， nm) 和 E={el， e2， … ， ep} 其中每條邊 ek=(ni， nj)， ni、 nj ∈V 。第四章 測試人員的圖論 東北大學(xué)軟件學(xué)院 圖 東北大學(xué)軟件學(xué)院 圖 (又叫做線性圖 )是一種由兩個集合定義的抽象數(shù)學(xué)結(jié)構(gòu) ， 即一個節(jié)點(diǎn)集合和一個構(gòu)成節(jié)點(diǎn)之間連接的邊集合 。 定義 圖 G=(V， E)由節(jié)點(diǎn)的有限 (并且非空 )集合 V和節(jié)點(diǎn)無序?qū)ε技?E組成 。 舉例 東北大學(xué)軟件學(xué)院 V={nl， n2， n3， n4， n5， n6， n7) E={e1， e2， e3， e4， e5}={(nl， n2)， (nl， n4)， (n3， n4)， (n2， n5)， (n4， n6)} 圖 41 有 7個節(jié)點(diǎn)和 5條邊的圖 n1 n2 n4 n3 n5 n6 n7 e1 e2 e3 e4 e5 節(jié)點(diǎn)的度 東北大學(xué)軟件學(xué)院 定義 圖中節(jié)點(diǎn)的度是以該節(jié)點(diǎn)作為端點(diǎn)的邊的條數(shù)。 deg(n1) = 2 deg(n2) = 2 deg(n3) = 1 deg(n4) = 3 deg(n5) = 1 deg(n6) = 1 deg(n7) = 0 關(guān)聯(lián)矩陣 東北大學(xué)軟件學(xué)院 定義 擁有 m個節(jié)點(diǎn)和 n條邊的圖 G=(V， E)的關(guān)聯(lián)矩陣是一種 m n矩陣 ， 其中第 i行第 j列的元素是 1， 當(dāng)且僅當(dāng)節(jié)點(diǎn)i是邊 j的一個端點(diǎn) ， 否則該元素是 0。 n1 n2 n3 n4 n5 n6 n7 n1 0 1 0 1 0 0 0 n2 1 0 0 0 1 0 0 n3 0 0 0 1 0 0 0 n4 1 0 1 0 0 1 0 n5 0 1 0 0 0 0 0 n6 0 0 0 1 0 0 0 n7 0 0 0 0 0 0 0 路徑 東北大學(xué)軟件學(xué)院 定義 路徑是一系列的邊 ， 對于序列中的任何相鄰邊對偶 ei、ej， 邊都擁有相同的 (節(jié)點(diǎn) )端點(diǎn) 。一般更常見的是節(jié)點(diǎn)序列 。 “ 連接性 ” 是一種圖的節(jié)點(diǎn)集合上的等價(jià)關(guān)系 。 2． 連接性是對稱的 ， 由于如果 ni和 nj在一條路徑上 ，則 nj和 ni也在同一條路徑上 。 組件 東北大學(xué)軟件學(xué)院 定義 圖的組件是相連節(jié)點(diǎn)的最大集合 。 圖 41種的圖有兩個組件： ? {n1， n2， n3， n4， n5， n6} ? {n7}
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1