有向图拓扑性质的描述 ： （1）关联矩阵(Incidence Matrix) （2）回路矩阵(Loop Matrix) （3）割集矩阵(Cutset Matrix) （4）连通图的主要关联矩阵的关系
(1)关联矩阵A
• 节点支路关联矩阵Aa：全阶点关联矩阵（增广关联矩阵） 行：节；列：支，流出为正，流入为正，无关为零。
因此就用抽象的点来代替原来的节点。用线段来代 替原来的支路，而得到的一个由节点和支路组成的 图，称为电路的图。
图(Graph) 图是拓扑（Topological）图的简称 是节点和支路的一个集合
:: 未赋以方向的图称为无向图。 只有部分支路赋以方向的图称为混合图。 所有支路都赋以方向的图称为有向图。图中的
4）有向图
(2)路径（简称路）：从图的某一个节点出发，沿着一些支路 连续移动到达另一个节点，这样的一系列支路称为图的 一条路径。一条支路本身也是一条路径。一般出发的节 点称为始节点，到达的节点称为终节点。支路和节点只 过一次。
(3) 回路： 回路L是连通图G的一个子图。 具有下述性质
1)连通； 2)每个节点关联支路数恰好为2。
5
（4） 割集
• 与广义节点（闭合面）的概念相关联。是被闭合面所切 割的支路集合。是把一个连通图恰好分成两部分的最少 支路集合。因此与节点有关的关系对割集也成立。
割集Q是连通图G中一个支路的集合，具有下述性质：
1) 把Q 中全部支路移去，将图恰好分成两个分离部分；
2)保留Q 中的一条支路，其于都移去， G还是连通的。
节点数 支路数 有向支路 j 背离 i 节点 有向支路 j 指向 i 节点 i节点与 j 支路无关
②
1
2
①5
③
2
1
5
①
43
4
④
6
6
Q1: { 2 , 5 , 4 , 6 }
②
③
3
④
②
②
1
2
①5
③
1
2
①5
③
43 ④6
43 ④6
Q2: { 2 , 3 , 6 }
Q3: { 1 , 5 , 4}
•单树支割集（基本割集）
②②Βιβλιοθήκη 12①5③
43 ④6
Q1: { 2 , 3 , 6 }
1
2
①5
③
43 ④6
Q2: { 3 , 5 , 4}
对于一个选定的树
树支(Tree Branch or Twig) ：属于树的支路 连支(Chord or Link) ：属于G而不属于T的支路
树支数 bt= n-1
连支数 bl=b-(n-1) 单连支回路（基本回路）
4
1 3 56
2
树支数 4 连支数 3
7 单连支回路 单连支回路
独立回路 独立回路
4 1
{1，5，3，6} {2，3，6} {3，4，5}
2） 由某个连支b3确定的单连支回路应包含那些树支，每个
这种树支所构成的基本割集中含有b3。
②
基本回路
基本割集
1
2
①5
③
43 ④6
{1，2，3，4} {1，4，5} {1，2，6}
{1，5，3，6} {2，3，6} {3，4，5}
§ 1-9 图的矩阵表示及其性质
123 75
6 84
23 5 回路
12 5
78 9 不是回路
(4) 树 (Tree)
树T是连通图G的一个子图，具有下述性质：
1)连通； 2)包含G的所有节点； 3)不包含回路。
•余树或补树：G中对应树T的余 子图称为余树或补树(Cotree).
4
13
2
5
6
4
13
2
5
6
4
13
2
5
6
16个 树不唯一
②
1
2
①5
③
43 ④6
Q4: { 1 , 5 , 2 }
②
1
2
①5
③
43 ④6
Q3: { 1 , 5 ,3 , 6 }
单树支割集 单树支割集
1
独立割集 独立割集
3
2
4
{1，2，3，4} 割集
1
2
3
4
{1，2，3，4} 割集
三个分离部分
4 保留4支路，图不连通的。
②
1
2
①5
③
43 ④6
基本回路 {1，2，3，4} {1，4，5} {1，2，6}
方向表示原电路中支路电压和电流关联参考方向
::图并不反映支路之间的耦合关系。
•元件的图
1
i1
i2 2
1
2
3
3
二端元件的图
i1 ＋ u1 －
三端元件的图
i2 ＋
u2 －
1
2
双口元件的图
•网络的图
网络拓扑 连接性质
i1 i2 i3
i1 i2 i3
i = 0
抽象
i1 i2 i3
+
抽象
支路 电路图
抽象图
抽象 +
不连通图 -
+
抽象
-
连通图
①
１
不含自环
②
允许孤立节点存在
2）子图
如果图G1中的每个节点和每条支路都是G图中的一部分， 则称G1为G 的子图(Subgraph)。
路径：从图G的一个节点出发沿着一些支路连续移动到达 另一节点所经过的支路构成路经。
3） 连通图 图G的任意两节点间至少有 一条路经时称G为连通图。
-
无
抽象
向
L
图
uS
R2 C
有 向
R1
抽象
图
(1)图的基本概念(名词和定义)
连通图
1） 图 G={支路，节点} 图
连通图
不连通图
如果图G中的任何两个节点之间都至少存在一 条路径，则G称为连通图(Connected Graph)，否则 称为非连通图。
铰链图
由电路中的多口元件造成的非连通图，可以把 不连通的各部分中的任一节点(一部分只能取一个 节点)之间假设有一条短路线相连。把这些假设短 路线连接的节点合并成一个节点，这样所得的图称 为铰链图(Hinged Graph)。
•任意去掉一行剩下的线性无关，去掉的节就做参考点节。称为 降阶关联矩阵。简称关联矩阵，记为A，（AI=0 对应独立的n-1 个KCL方程），A的秩为（N-1）Rank（Aa）=Rank（A）=n-1
用矩阵形式描述节点和支路的关联性质
关联矩阵
aij = 1
aij
aij= -1
aij =0
Aa={aij}n b
基本割集 {1，5，3，6} {2，3，6} {3，4，5}
•基本回路和基本割集关系
对同一个树
1）由某个树支bt (b4)确定的基本割集应包含那些连 支，每个这种连支构成的单连支回路中包含该树 支bt (b4) 。
②
基本回路
基本割集
1
2
①5
③
43 ④6
{1，2，3，4} {1，4，5} {1，2，6}
§1-8 网络图论的基本知识
1 网络(电路)的图（线图Graph）
主要复习:节点、支路、路径、回路、树、割集 （P43-P47）
众所周知，电路（网络）的约束分成两类，一为 元件约束，一为结构约束。
结构约束是电路的连接结构，对电网络中的电压和电 流的制约关系（KCL，KVL）,它与元件的性质无关。
既如此，讨论这部分关系时，就没有必要把元件画出。