博客

2 节点邻接矩阵

2.1无向图

2.2有向图

有向图节点邻接矩阵A中元素的“负号”是指始节点vi到终节点vj的流向与图1-1中所约定的流向相反，因此以“负号”来表示。

3关联矩阵与基本关联矩阵

3.1关联矩阵

3.1.1无向图

3.1.2有向图

3.2基本关联矩阵

4回路矩阵与基本回路矩阵

4.1回路矩阵

回路是由支路所构成的一条闭合路径。回路矩阵是用回路与支路的关系描述有向图的拓扑性质。

4.1.1无向图

4.1.2有向图

4.2基本回路矩阵

将满秩的回路矩阵称为基本回路矩阵，有时也简称回路矩阵，并也用C表示，在无特别说明的情况下本书所提的回路矩阵均指基本回路矩阵。构造基本回路的方法通常是先找出图G中的一棵支撑树T，支撑树之外的分支为余支，支撑树每增加一条余支即可构成一个基本回路，并定义在有向图中基本回路的方向与余支方向相同。这种通过加余支形成基本回路的方法，可保证所选择的n-m+1个回路都是满秩的（m是节点个数，n是边的条数）。