§2-3图的矩阵表示 关联矩阵A2和A 增广关联矩阵A2表示G的节点和支路的关联关系 (augmented incidence matrix) A2=[,是一个t×b的矩阵。 +1第k条支路与第个节点相关联,且支路方向离开节点j; =-1第k条支路与第个节点相关联,且支路方向指向节点; 0第k条支路与第j个节点无关联。 若若 ,若 k
§2—3 图的矩阵表示 一、关联矩阵Aa和A 增广关联矩阵Aa表示G的节点和支路的关联关系 (augmented incidence matrix) Aa=[ajk]是一个nt × b的矩阵。 ＋1第k条支路与第j个节点相关联，且支路方向离开节点j； - 1第k条支路与第j个节点相关联，且支路方向指向节点j； 0第k条支路与第j个节点无关联。 ajk= ⎪⎩ ⎪⎨⎧ = − 若 若 若 0 , 1 , 1 , a jk j j j k k k
② 5 6 b4 6 0 ①②③④⑤ 000 00 0001 00101
b6 b1 b2 b3 b4 b ① 5 ② ③ ④ ⑤ b7 ⎥⎥⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎢⎢⎣⎡−0 0 0 0 1 1 1 0 0 - 1 - 1 0 - 1 0 0 1 1 0 0 0 - 1 1 - 1 0 0 0 0 0 1 0 0 1 - 1 0 0 b1 b2 b3 b4 b5 b6 b7 ① ③ ② ④ ⑤
6, b2 b3 b4 55 56 b, ① 100 000 011 ④ 10010 0010 ⑤000 ①A的每一行对应一个节点; ②每一列对应一条支路。且一列中只有两个非零元 素,一个为+1,另一个为-1。 ③A2与有向图G一一对应
⎥⎥⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎢⎢⎣⎡−0 0 0 0 1 1 1 0 0 -1 -1 0 -1 0 0 1 1 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 1 -1 0 0 b1 b2 b3 b4 b5 b6 b7 ① ③ ② ④ ⑤ ① Aa的每一行对应一个节点； ② 每一列对应一条支路。且一列中只有两个非零元 素，一个为+1，另一个为–1。 ③ Aa与有向图G一一对应
定理4一个节点数为η的连通图,其增广关联矩阵Aa 的秩为n=n1-1,从中去掉一行所得矩阵称为关联矩 阵( (incidence matrix),用A表示,是n×b矩阵 , b2 b3 b4 b5 56 6, 100 0011 001 1000 001
定理4 一个节点数为nt的连通图，其增广关联矩阵Aa 的秩为n= nt －1,从中去掉一行所得矩阵称为关联矩 阵(incidence matrix)，用A表示，是n×b矩阵 ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡− = 0 0 -1 -1 0 -1 0 0 1 1 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 1 -1 0 0 A b1 b2 b3 b4 b5 b6 b7
①按“A2每一列中只有两个非零元素,一个为+1, 另一个为-1”的关系,可由A还原成Aa ②故A也与有向图G一一对应。即已知G可唯一地写 出A;已知A也可唯一地画出G。 ③通常采用的是A,且A也简称为关联矩阵。 定理5:连通图G的A的n×n子阵非奇异的充分必 要条件是:此子阵的列所对应的支路形成G的 个树,且该子阵的行列式之值为±1 定理6:连通图G满足: 秩Aa=秩(A=n=n1-1
① 按“Aa每一列中只有两个非零元素，一个为+1， 另一个为–1”的关系，可由A还原成Aa 。 ② 故A也与有向图G一一对应。即已知G可唯一地写 出A；已知A也可唯一地画出G 。 ③ 通常采用的是A，且A也简称为关联矩阵。 定理5：连通图G的A的n×n子阵非奇异的充分必 要条件是：此子阵的列所对应的支路形成G的一 个树，且该子阵的行列式之值为±1 定理6：连通图G满足： 秩(Aa )= 秩(A )=n= nt –1