《现代网络分析》PPT课件.ppt

1 第一章网络图论 网络分析主要问题 1 选择独立变量2 列写网络方程3 网络方程求解 拓扑学理论 矩阵代数方程 计算机应用 2 1 1基本定义和概念 一 网络拓扑图1 支路 Branch 每个元件代表一条支路 用线段表示 2 节点 Node 每一条支路的端点 3 图 Graph 支路与节点的集合 连通图非连通图 有向图无向图 平面图非平面图 孤立节点自环 子图母图 3 二 树 回路 割集1 树 Tree 连通图G的一个子图 满足 1 连通图 例 2 5 6 1 3 4 1 2 5 6 1 3 4 5 2 含有G全部节点 3 无回路 树支 构成树的所有支路树支数 n 1n 节点数连支 不属于树的支路 树余 连支数 b n 1 b 支路数 4 2 回路 Loop 基本回路 单连支回路 连支方向为回路方向 回路是连通图G的一个子图 满足 1 连通图2 每个节点仅关联两条支路3 移去任一支路 则无闭合路径 例 选树 2 5 6 基本回路 1 2 5 6 3 2 5 4 5 6 例 回路 4 5 6 1 3 6 3 2 5 1 4 5 3 5 3 割集 Cut 基本割集 单树支割集 树支方向为割集方向 割集是连通图G的一些支路的集合 满足 1 移去该支路集合 则图恰好分成两部分 2 少移一条支路 则图连通 例 割集 1 2 5 2 4 5 3 5 6 1 2 5 6 例 选树 2 5 6 基本割集 2 3 1 5 3 1 4 6 4 1 6 1 2节点关联矩阵 1 增广关联矩阵Aa 行 代表节点序号列 代表支路序号 矩阵元素取值 同向关联 支路j与节点i关联 支路j方向离开节点i 反向关联 支路j与节点i关联 支路j方向指向节点i 无关联 支路j与节点i没有关联 7 举例 写出右图的节点关联矩阵 增广关联矩阵Aa 2 降阶关联矩阵A 从增广关联矩阵Aa中去掉任意一行 所得到的 n 1 xb阶矩阵A 该A矩阵的秩为n 1 8 3 节点关联矩阵性质 1 节点数为n的连通图G 其全节点关联矩阵Aa的秩等于n 1 2 节点关联矩阵A中的任意阶方块子矩阵行列式的值不外乎等于0 1或 1 具有这种性质的矩阵叫做单模矩阵 简称E矩阵 3 若L为连通图G的任意一个回路 则在Aa中 由L的各支路所对应的各列必定线性相关 4 基本关联矩阵A的任意一个n 1阶行列式不等于零的充分必要条件是 该行列式各列所对应的支路构成图G的树 4 基尔藿夫第一定律的矩阵形式 或 9 1 3回路关联矩阵 3 1 2 1 回路关联矩阵B行 代表回路序号列 代表支路序号 矩阵元素取值 反向关联 支路j与回路i关联 支路j方向与回路i方向相反 无关联 支路j与回路i没有关联 同向关联 支路j与回路i关联 支路j方向与回路i方向一致 10 举例 写出所示图的基本回路关联矩阵 选一棵树 写基本回路与支路的关联矩阵Bf 注意 基本回路方向为单连支的方向 2 基本回路关联矩阵Bf 网孔回路关联矩阵M回路方向习惯取顺时针 写关联矩阵 1 2 3 11 3 回路关联矩阵性质 1 节点数为n 支路数为b的连通图G 全回路关联矩阵Ba的秩等于L b n 1 2 回路关联矩阵B中的任意阶方块子矩阵行列式的值不外乎等于0 1或 1 具有这种性质的矩阵叫做单模矩阵 简称E矩阵 3 设同一连通图G的矩阵A和Bf的列具有相同的支路排列顺序 则 4 基尔藿夫第二定律的矩阵形式 则 或 4 若连通图G已选定树 对应此树的的矩阵A和Bf均按先连支后树支的顺序排其列 即 12 1 4割集关联矩阵 1 割集关联矩阵C行 代表割集序号列 代表支路序号 矩阵元素取值 反向关联 支路j与割集i关联 支路j方向与割集i方向相反 无关联 支路j与割集i没有关联 同向关联 支路j与割集i关联 支路j方向与割集i方向一致 13 举例 写出所示图的基本割集关联矩阵 选一棵树 写基本割集与支路的关联矩阵Cf 注意 基本割集方向为单树支的方向 2 基本割集关联矩阵Cf 14 3 割集关联矩阵性质 1 节点数为n的连通图G 全割集关联矩阵Ca的秩等于n 1 2 割集关联矩阵C中的任意阶方块子矩阵行列式的值不外乎等于0 1或 1 具有这种性质的矩阵叫做单模矩阵 简称E矩阵 3 设同一连通图G的矩阵Cf和Bf的列具有相同的排列顺序 则 4 基尔藿夫第一定律应用于割集的矩阵形式 或 或 15 对于一个有向图 选一棵树 支路编号先树支后连支 则有 或 故有 5 A Bf Cf关系 16 习题 求Bf Cf 树支 1 2 3 5 9 1 1 100100000010 10010000011 10001000 100100001000100 10000100 1 101000001 10000 100100010001 1 10 110010010 100100010011 1000000100001 1 17 1 5网络分析中的独立变量组 一 连支电流 网孔电流 意义 可以将L b n 1个连支电流作为一组独立变量 又 可得 对于一个有向图 选一棵树 支路编号先树支后连支 则有 网络树支电流可用连支电流表示 对于平面网络 可将L b n 1个网孔电流作独立变量 18 二 树支电压 节点电位 意义 可以将n 1个树支电压作为一组独立变量 又 可得 对于一个有向图 选一棵树 支路编号先树支后连支 则有 网络连支电压可用树支电压表示 对于节点电位 可将n 1个节点电位作独立变量 19 1 6非基本关联矩阵 一 非基本回路矩阵 所取独立变量是支路变量的线性组合 如何取 一般有如下步骤 1 任选一棵树 2 把i用连支电流表示 3 把i代入 4 iL能作独立变量的唯一要求 若iL能作独立变量 则 B 称为非基本回路矩阵 20 解 选一棵树 4 5 6 第一组变量能作独立变量 例 对于图示图形 可否用下列变量作为独立变量 第二组变量不能作独立变量 21 二 非基本割集矩阵 所取独立变量是支路变量的线性组合 如何取 一般有如下步骤 1 任选一棵树 2 把U用树支电压表示 3 把U代入 4 UC能作独立变量的唯一要求 若UC能作独立变量 则 C 称为非基本割集矩阵 22 解 由所给变量 有 例1 对于图示图形 可否用下列变量作为独立变量 选一棵树 4 5 6 故所给变量能作独立变量 且 其非基本割集矩阵为 23 解 由所给变量 有 例2 对于图示图形 试求以下列变量作为独立变量的非基本割集矩阵 选一棵树 1 2 4 其非基本割集矩阵为 24 1 7图形的树数 一 Binet Cauchu定理 设有两矩阵 且m n 则方阵 所对应的行列式等于P的最高阶子行列式与对应Q的最高阶子行列式的乘积的代数和 即 P与Q对应的最高阶子行列式乘积 二 图形的树数 矩阵A Bf Cf M中 每个矩阵的不等于零的最高阶子行列式的数目都等于图形的树数 1 由关联矩阵求图形的树数 25 例1 求图示图形的树数 1 2 3 4 5 解 选一棵树 1 2 3 26 例2 求图示图形的树数 解 选一棵树 1 2 4 选一棵树 1 2 3 27 2 由非关联矩阵求图形的树数 例2 对于图示图形 其非基本割集矩阵为 不是树数 从C可知 支路 1 3 5 可构成一个树 取非基本割集矩阵的1 3 5列 16 28 1 8求图形的全部树 一 用多项式表示图设用多项式 其中 bi是图G的支路编号 ai取1或0 当支路bi包含在子图Gs中时 ai 1 当支路bi不含在子图Gs中时 ai 0 表示图G的子图Gs G1 G2 二 子图多项式运算规则 1 加法 bi bi 0 当i j时 bi不能与bj相加 2 乘法 bibi 0 bibjbk bkbjbi 0 例 29 三 求图形的全部树 1 从图G中任选一个树 得到一组基本割集 2 对应该组割集可得一组多项式 3 计算该多项式为基底的乘积 4 利用图形多项式加法和乘法规则 得到图形的全部树 例 求图所示的图形全部树 解 选一个树 1 3 5 可得基本割集多项式 计算该多项式为基底的乘积 所以 该图形全部树有16棵 30 四 求图形的全部连支集 1 从图G中任选一个树 得到一组基本回路 2 对应该组回路可得一组多项式 3 计算该多项式为基底的乘积 4 利用图形多项式加法和乘法规则 得到图形的全部连支集 例 求图所示的图形全部连支集 解 选一个树 1 3 5 可得基本回路多项式 计