關聯矩陣(incidence matrix)
設G=(V,E)是一簡單圖(有向或無向)，|V|=n，|E|=m ，并且設V={v1,v2,?,vn} ， E={e1,e2,?,em}已被強行命名，則 定義n′m階矩陣B=(bij) n′m為圖G的關聯矩陣，
(1)若G是有向圖，則
(2)若G是無向圖，則
可達矩陣(reachable matrix)
設G=(V,E)是一簡單圖(有向或無向)，|V|=n ，并且設V={v1,v2,?,vn}已被強行命名，則 定義n階方陣
R=(rij) n′n ，其中
為圖G的可達矩陣，
注：(1)對于有向圖
從結點vi可達結點vj?從結點vi到結點vj至少有一條有向路
從結點vi不可達結點vj?從結點vi到結點vj沒有有向路
(2)對于無向圖
從結點vi可達結點vj?從結點vi到結點vj至少有一條路
從結點vi不可達結點vj?從結點vi到結點vj沒有路，
鄰接矩陣的布爾冪
設G=(V,E)是一簡單圖(有向或無向)， n階方陣A是圖G 的鄰接矩陣，則 遞回的定義鄰接矩陣A的布爾冪
(1)A(1)=A；
(2)A(m+1)= A(m)ùA；
其中：
(1￡i￡n,1￡j￡n) ，
可達矩陣的計算方法一：Warshall演算法(1962年)
No1.R:=A
No2.k:=1
No3.i:=1
No4.for k:=1 step 1 until n do
rij := rij?(rik?rkj)
No5.i:=i+1;if i?n then goto No4
No6.k:=k+1;if k?n then goto No3
No7.if k?n then exit
可達矩陣的計算方法二：矩陣冪演算法
可達矩陣 R=Aú A(2) ú A(3) ú ?ú A(n)
注： ·這里ú是矩陣的布爾和運算，
·兩個矩陣的布爾和運算就是其對應元素做二元布爾和運算，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/248650.html
標籤：區塊鏈