西安电脑维修电路图.pptVIP

* 第16章 网络图论基础 §1 网络的图 网络拓扑 i1 i2 i3 i1 i2 i3 i1 i2 i3 抽象 ?i = 0 连接性质 抽象 电路图 抽象图 支路 + - 一. 图的基本概念 R2 C L uS R1 抽象 抽象 无 向 图 有 向 图 + - 连通图 图 不连通图 + - 抽象 连通图 抽象 不连通图 1. 图 G={支路，节点} ① ② １ 不含自环 允许孤立节点存在 二 . 名词和定义 2.子图 路径：从图G的一个节点出发沿着一些支路连续移动到达 另一节点所经过的支路构成路经。 3. 连通图 图G的任意两节点间至少有 一条路经时称G为连通图。 4.有向图 图中的方向表示原电路中支路电压和 电流关联参考方向。 §2. 回路、树、割集 一. 回路 (1)连通； (2)每个节点关联支路数恰好为2。 1 2 3 4 5 6 7 8 2 5 3 1 2 7 5 8 9 回路 不是回路 回路L是连通图G的一个子图。 具有下述性质 树不唯一 树支：属于树的支路 连支：属于G而不属于T的支路 二 . 树 (Tree) 树T是连通图G的一个子图，具有下述性质： (1)连通； (2)包含G的所有节点； (3)不包含回路。 16个 树支数 bt= n-1 连支数 bl=b-(n-1) 单连支回路（基本回路） 1 2 3 4 5 6 7 1 4 5 树支数 4 连支数 3 单连支回路 独立回路 单连支回路 独立回路 三. 割集 (1) 把Q 中全部支路移去，将图分成两个分离部分； (2)保留Q 中的一条支路，其于都移去， G还是连通的。 ① 4 3 2 1 ② ④ ③ 5 6 ① 1 ② 3 ④ ③ 4 2 5 6 Q1: { 2 , 5 , 4 , 6 } 割集Q是连通图G中一个支路的集合，具有下述性质： ① 4 3 2 1 ② ④ ③ 5 6 ① 4 3 2 1 ② ④ ③ 5 6 ① 4 3 2 1 ② ④ ③ 5 6 Q4: { 1 , 5 , 2 } Q3: { 1 , 5 , 4} Q2: { 2 , 3 , 6 } 单树支割集（基本割集） ① 4 3 2 1 ② ④ ③ 5 6 ① 4 3 2 1 ② ④ ③ 5 6 ① 4 3 2 1 ② ④ ③ 5 6 Q3: { 1 , 5 ,3 , 6 } Q2: { 3 , 5 , 4} Q1: { 2 , 3 , 6 } 单树支割集 独立割集 单树支割集 独立割集 1 2 3 4 {1，2，3，4} 割集 三个分离部分 1 2 3 4 {1，2，3，4} 割集 4 保留4支路，图不连通的。 ① 4 3 2 1 ② ④ ③ 5 6 基本回路 基本割集 {1，2，3，4} {1，4，5} {1，2，6} {3，4，5} {2，3，6} {1，5，3，6} 基本回路和基本割集关系 对同一个树 1. 由某个树支bt确定的基本割集应包含那些连支，每个这种连支构成的单连支回路中包含该树支bt 。　 2. 由某个连支bl确定的单连支回路应包含那些树支，每个这种树支所构成的基本割集中含有bl 。 ① 4 3 2 1 ② ④ ③ 5 6 基本回路 基本割集 {1，2，3，4} {1，4，5} {1，2，6} {3，4，5} {2，3，6} {1，5，3，6} ① 4 3 2 1 ② ④ ③ 5 6 基本回路 基本割集 {1，2，3，4} {1，4，5} {1，2，6} {3，4，5} {2，3，6} {1，5，3，6} § 3 图的矩阵表示 一.关联矩阵A 用矩阵形式描述节点和支路的关联性质 aij aij = 1 有向支路 j 背离 i 节点 aij= -1 有向支路 j 指向 i 节点 aij =0 i节点与 j 支路无关 关联矩阵 Aa={aij}n ? b 节点数 支路数 6 4 5 3 2 1 ① ② ④ ③ Aa= 1 2 3 4 1 2 3 4 5 6 支 节 1 0 0 -1 0 1 -1 -1 0 0 1 0 0 1 1 0 0 -1 0 0 -1 1 -1 0 Aa= 1 2 3 4 1 2 3 4 5 6 支 节 1 -1 0 0 0 -1 1 0 0 0 1 -1 -1 0 0 1 0 1 0 -1 1 0 -1 0 设④为参考节点 -1 -1 0 0 1 0 A= 1 2 3 1