例 ①05 8 7 7002 ④ 0 50048 04206 3
3 8 1 6 0 0 4 2 0 6 7 0 0 2 1 5 0 0 4 8 0 5 7 0 3 例 1 4 5 2 3 7 5 3 1 8 6 4 2
★关联矩阵一表示顶点与边的关联关系的矩阵 今定义:设G=(V,E)是有n≥1个顶点,e>0条边的图,G的关联矩 阵A是具有以下性质的nXe阶矩阵 1,顶点与边相连,且为尾 有向图:4玩,=0,顶点与边不相连 1,顷顶点与边相连,且为头 1,点与边相连 无向图:4[i,j 0,顶点与边不相连
关联矩阵——表示顶点与边的关联关系的矩阵 ❖定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩 阵A是具有以下性质的ne阶矩阵 − = 顶点与 边相连，且 为头 顶点与 边不相连 顶点与 边相连，且 为尾 有向图： i j i i j i j i A i j 1, 0, 1, [ , ] = ， 顶点与 边不相连 ， 顶点与 边相连 无向图： i j i j A i j 0 1 [ , ]
1234 例①12 ②-100O 4 ③0 334 例①1②2 23456 ①|110000 ②|10 G2 ③00 110 ④011000 ⑤L0000
− − − − 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 1 2 3 4 例 G1 24 13 1 2 3 4 例 1 5 3 2 4 G21 2 3 45 6 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 1 2 3 4 5 6
例 D 40 ABCD 2100 600 0
例 B D A C 1 2 3 4 5 6 A B C D 1 2 3 4 5 6 − − − − − − 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 0 0 0
心特点 关联矩阵每列只有两个非零元素.是稀疏矩阵:η越大,零 元素比率越大 ●无向图中顶点V的度TD()是关联矩阵A中第行元素之和 ●有向图中, ◆顶点V的出度是A中第行中“1”的个数 ◆顶点Ⅵ的入度是A中第行中“-1”的个数
❖特点 ⚫关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零 元素比率越大 ⚫无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和 ⚫有向图中， ◆顶点Vi的出度是A中第i行中“1”的个数 ◆顶点Vi的入度是A中第i行中“-1”的个数