[互联网]现代网络分析PPT课件

[Cf
]
0 0 1 0 0 1 0 树0 支0：10、21、30、05、19
1 1 0 1 0 0 [Bf ]1 1 1 0 1 0
0 1 1 0 0 1
1 0 0 1 1 0 [Cf ]0 1 0 1 1 1
0 0 1 0 1 1
故有： Cl BtT 或 Bt ClT
BtT At1Al
Cl BtT
At 1Al
15
1 0 0 0 0 -1 0 0 1 0 0
习题0 ：1 求0Bf、0 C0f 1 -1 -1 0 -1 1
举例：写出所示图的基本割集关联矩阵。
1 1 1 0 0 0 Cf 1 0 1 1 1 0
1集关联矩阵性质
（1）节点数为n的连通图G，全割集关联矩阵Ca的秩等于n -1。 （2）割集关联矩阵C中的任意阶方块子矩阵行列式的值不外乎
等于0，+1或-1。
具有这种性质的矩阵叫做单模矩阵，简称E矩阵。 （3）设同一连通图G的矩阵Cf和 Bf的列具有相同的排列顺序，
第一章 网络图论
网络分析主要问题： 1）选择独立变量 ——拓扑学理论 2）列写网络方程 ——矩阵代数方程 3）网络方程求解 ——计算机应用
1
1-1 基本定义和概念
一、网络拓扑图
1、支路(Branch)：每个 元件代表一条支路，用线 段表示。 2、节点(Node)：每一条 支路的端点。 3、图（Graph)：支路与
矩阵的秩为n-1。
7
3、节点关联矩阵性质
（1）节点数为n的连通图G，其全节点关联矩阵Aa的秩等于n-1。
（2）节点关联矩阵A中的任意阶方块子矩阵行列式的值不外乎等 于0，+1或-1。
具有这种性质的矩阵叫做单模矩阵，简称E矩阵。 （3）若L为连通图G的任意一个回路，则在Aa中，由L的各支路所
对应的各列必定线性相关。 （4）基本关联矩阵A的任意一个n-1阶行列式不等于零的充分必要
例： 选树：（2，5，6）
基本回路：（1，2，5,6）
（3，2，5）
（4，5，6）
4
3、割集（Cut)
割集是连通图G的一些支路的集合，满足： 1）移去该支路集合，则图恰好分成两部分；
2）少移一条支路，则图连通。
例： 割集：（1，2，5） （2，4，5） （3，5，6） （1，2，5，6）
基本割集：单树支割集，树支方向为割集方向。
连支：不属于树的支路（树余） 连支数 b-(n-1) b:支路数
3
2、回路（Loop)
回路是连通图G的一个子图，满足：
1）连通图
2）每个节点仅关联两条支路
3）移去任一支路，则无闭合路径 例： 回路：（4，5，6） （1，3，6） （3，2，5） （1，4，5，3）
基本回路：单连支回路，连支方向为回路 方向。
矩阵元素取值:
1
c ij
1
0
——同向关联：支路j与割集i关联,支路j方向与 割集i方向一致。
——反向关联：支路j与割集i关联,支路j方向与 割集i方向相反。
——无关联：支路j与割集i没有关联。
12
2、基本割集关联矩阵Cf
选一棵树，写基本割集与支 路的关联矩阵Cf,注意：基本割 集方向为单树支的方向。
例： 选树：（2，5，6） 基本割集：（2，3，1） （5，3，1，4） （6，4，1）
5
② 1-2 节点关联矩阵
1、增广关联矩阵Aa
①
行：代表节点序号
列：代表支路序号
③ ④
矩阵元素取值:
1
a ij
1
0
——同向关联：支路j与节点i关联,支路j方向离 开节点i。
——反向关联：支路j与节点i关联,支路j方向指 向节点i。
条件是：该行列式各列所对应的支路构成图G的树。
4、基尔藿夫第一定律的矩阵形式：
Ai0 或 Aai 0
8
1-3 回路关联矩阵
1、回路关联矩阵B 行：代表回路序号 列：代表支路序号
矩阵元素取值:
1
2
3
1 ——同向关联：支路j与回路i关联,支路j方向与
b ij
1
回路i方向一致。 ——反向关联：支路j与回路i关联,支路j方向与
则
CfBf 0 或 BfCf 0
4、基尔藿夫第一定律应用于割集的矩阵形式：
Cfi 0 或
Cai 0
14
5、A、Bf、Cf关系
1 0 0 1 1 0
对于一个有向图， 选一棵树，支路编号
[A]0
1
1
1
0
0
先树支后连支。则有： 0 0 1 0 1 1
AA t A l
BBt Bl Bt 1
CCt Cl 1 Cl
节点的集合。
连通图 非连通图
有向图 无向图
平面图 非平面图
子图 母图
孤立节点 自环
2
二、树、回路、割集 1、树（Tree): 连通图G的一个子图，满足： 1）连通图
2）含有G全部节点
3）无回路
例： （2，5，6） （1，3，4） （1，2，5，6） （1，3，4，5）
树支：构成树的所有支路 树支数 n-1 n:节点数
序，则
ABf 0 或 BfA 0
（4）若连通图G已选定树，对应此树的的矩阵A和 Bf均按先
连支后树支的顺序排其列，即 B[1 Bt] A[Al At] 则 Bt AlT(At1)T
4、基尔藿夫第二定律的矩阵形式：Bfu 0
11
1-4 割集关联矩阵
1、割集关联矩阵C 行：代表割集序号 列：代表支路序号
——无关联：支路j与节点i没有关联。
6
举例：写出右图的节点关联矩阵。
②
1 0 0 1 0 1
[Aa]
1 0
110 0 1 0
0 1
0 ① 1
0
1
0
1 1
0
③ ④
（增广关联矩阵Aa）
1 0 0 1 0 1 [A]1 1 1 0 0 0
0 0 1 0 1 1
2、降阶关联矩阵A
从增广关联矩阵Aa中去 掉任意一行，所得到的 （n-1)xb阶矩阵A。该A
网孔回路关联矩阵M
回路方向习惯取顺时针，写关联矩阵。
1
2
3
10
3、回路关联矩阵性质
（1）节点数为n，支路数为b的连通图G，全回路关联矩阵Ba的 秩等于L= b - n +1。
（2）回路关联矩阵B中的任意阶方块子矩阵行列式的值不外乎 等于0，+1或-1。
具有这种性质的矩阵叫做单模矩阵，简称E矩阵。
（3）设同一连通图G的矩阵A和 Bf的列具有相同的支路排列顺
0
回路i方向相反。 ——无关联：支路j与回路i没有关联。
9
2、基本回路关联矩阵Bf 选一棵树，写基本回路与支路的关
联矩阵Bf,注意：基本回路方向为单 连支的方向。 举例：写出所示图的基本回路关联矩阵。
1 110 0110 00 0
MBf0011
011 11 01 001 00 10
01 11
0 1