17.2 回路树 割集 一、回路（loop） 回路L是连通图G的一个子图。 具有下述性质

（1）连通； （2）每个节点关联支路数恰好为2。

1 2 3 7 5 6 3 2 1 2 7 8 5 8 4 图G 5 回路 9 不是回路

二、树（tree）

树T是连通图G的一个子图，具有下述性质： （1）连通； （2）包含G的所有节点； （3）不包含回路。

16个 树T1 图G 树支（tree branch）：属于树的支路。 树T2 树不唯一

连支（link）：属于G而不属于T的支路。

树支数 bt= n-1 连支数 bl = b-(n-1)

单连支回路（基本回路（fundamental loop））：每个 回路中只包含一个连支，其余均为树支。

4 1 2

3

5

6

树支数 4

连支数 3

7

单连支回路 单连支回路

独立回路

以2，3，6，7为树支， 分别加入1，4，5形成 三个单连支回路

4

1 65

3

独立回路

2

7

三、割集（cut set）

例 1 ② 2 ①

5 4 3 ④ ③ 2 ② 1 5 ① ③ 4 3 6 闭合面与支路 2，5，4，6相交 6 移去支路 2，5，4，6 ④ 图分成两个 分离部分

割集Q是连通图G中一个支路的集合，具有下述性质：

（1）把Q中全部支路移去，将图分成两个分离部分； （2）保留Q中的一条支路，其余都移去， G还是连通的。