2树(Tree T是连通图的一个子图满足下列条件: (1)连通 (2)包含所有节点 (3)不含回路 树 树支:属于树的支路 树支数b=n-1 连支:属于G而不属于T的支路连支数b=b-(m-1)
树 树支：属于树的支路 连支：属于G而不属于T的支路 树支数bT =n-1 连支数bl=b-(n-1) 2.树 (Tree) T是连通图的一个子图满足下列条件： (1)连通 (2)包含所有节点 (3)不含回路
基本回路(单连支回路) 5 基本回路数连支数=b(m1) 3割集Q( Cut set) Q是连通图G中支路的集合,具有下述性质: 1)把Q中全部支路移去,图分成二个分离部分 (2)任意放回Q中一条支路,仍构成连通图
基本回路(单连支回路) 1 2 3 4 5 6 1 2 3 5 1 2 3 6 基本回路数=连支数=b-(n-1) 3.割集Q (Cut set ) Q是连通图G中支路的集合，具有下述性质： (1)把Q中全部支路移去，图分成二个分离部分。 (2)任意放回Q 中一条支路，仍构成连通图
2,4,5,6} 2,36} 2 {1,3,5,6}是否割集? 5
2 4 5 6 {2,4,5,6} 1 3 2 {2,3,6} 1 4 5 • 1 2 3 4 6 5 7 {1,3,5,6}是否割集？ 2 4 7 1 3
23,4 是否割集? 6 78 8 找割集方法:作封闭曲面 6 {1,3,5,6}为割集 基本割集 2 单树支割集) 2,3,6}为割集 5 2,4,5,6}为割集基本割集数(n-1) 连支集合不能构成割集
1 2 5 3 6 4 7 8 {1,2,3,4} 是否割集？ 5 7 8 6 找割集方法：作封闭曲面 1 2 4 3 5 6 {1,3,5,6}为割集 {2,3,6}为割集 连支集合不能构成割集 基本割集 (单树支割集) 基本割集数=(n-1) {2,4,5,6}为割集
§15-2关联矩阵、回路矩阵、割集矩阵 一关联矩阵(描述节点和支路的关联性质) N个节点b条支路的图用n×b的矩阵描述 5 节支123456 ① 1-10 00 2001-1-10 2 3 4 0÷00 401-1 0-1 a1=1支路k与节点关联,方向背离节点 jk jk 支路k与节点j关联,方向指向节点 jk 支路k与节点j无关
§15-2 关联矩阵、回路矩阵、割集矩阵 一.关联矩阵 (描述节点和支路的关联性质) N个节点b条支路的图用nb的矩阵描述 1 ２ ３ ６ ４ ５ ① ② ④ ③ Aa = 1 2 3 4 节 支1 2 3 4 5 6 -1 -1 0 1 0 0 0 0 1 -1 -1 0 1 0 0 0 1 1 0 1 -1 0 0 -1 ajk ajk=1 支路k与节点j 关联，方向背离节点。 ajk= -1 支路k与节点j 关联，方向指向节点 ajk =0 支路k与节点j无关