CAD01-图论讲诉.ppt

* （2） 矩阵形式 即 或 * 1.4 矩阵分析法 设线性电阻电路有n+1个节点、b条支路；则有 支路电流列向量 支路电压列向量 节点电压列向量 选树后，有树支电压列向量 连支电流列向量 * （1） 节点电位分析 KCL ；KVL 由此可得 设节点电导矩阵 节点独立电流源矩阵 则有 ，其解为 并解得 、 VAR * 例 图示电路中，各电导均为 ， ， 求支路的电流和支路电压列向量。 解 支路电流源列向量 支路电压源列向量 支路电导矩阵 ⑴ 列节点关联矩阵 * 解 ⑵ 计算节点电导矩阵 ⑶ 计算节点电导矩阵的逆矩阵 ⑷ 计算节点独立电流源矩阵 * 解 ⑸ 计算节点电位 ⑹ 计算支路电压、电流 * （2） 基本回路分析 KCL KVL 由此可得 则有 ，其解为 并解得 、 VAR 设回路电阻矩阵 回路独立电压源矩阵 * 例 图示电路中，各电阻均为 ， ， 求支路的电流和支路电压列向量。 解 选树，树支1、 2、4，连支6、3、5 支路电流源列向量 支路电压源列向量 支路电阻矩阵 * 解 ⑴ 列基本回路矩阵 ⑵计算回路电阻矩阵 , * ⑶计算回路电阻矩阵的逆矩阵 ⑷计算回路独立电压源矩阵 ⑸计算回路电流 ⑹计算支路电流、电压 * （3） 基本割集分析 KVL KCL 由此可得 则有 ，其解为 并解得 、 VAR 设割集电导矩阵 割集独立电流源矩阵 * 例 图示电路中，各电导均为 ， ， 求支路的电流和支路电压列向量。 解 支路电压源列向量 支路电导矩阵 支路电流源列向量 选树，树支1、 2、4，连支6、3、5 * 解 ⑴ 列基本割集矩阵 ⑵ 计算割集电导矩阵 , ⑶ 计算割集电导矩阵的逆矩阵 * ⑷ 计算割集独立电流源矩阵 ⑸ 计算树支电压 ⑹ 计算支路电压、电流 * 课堂练习 根据节点电压方程， 试绘制相应的电路。 2. 图中电阻下标取为支路的编号，列出相应的节点关联矩阵、基本割集关联矩阵和基本回路关联矩阵。 * * 1 图-结点和支路的集合； 2 子图-所有结点和支路属于另一图G，为图G的子图； 3 有向图-图G中每条支路均标有方向，为图G的有向图 4 连通图-图中任意二结点之间至少有一条由图中的支路联成的路径，则称之为连通图，否则称为非连通图。 * 1 图-结点和支路的集合； 2 子图-所有结点和支路属于另一图G，为图G的子图； 3 有向图-图G中每条支路均标有方向，为图G的有向图 4 连通图-图中任意二结点之间至少有一条由图中的支路联成的路径，则称之为连通图，否则称为非连通图。 * 1 图-结点和支路的集合； 2 子图-所有结点和支路属于另一图G，为图G的子图； 3 有向图-图G中每条支路均标有方向，为图G的有向图 4 连通图-图中任意二结点之间至少有一条由图中的支路联成的路径，则称之为连通图，否则称为非连通图。 * 1 图-结点和支路的集合； 2 子图-所有结点和支路属于另一图G，为图G的子图； 3 有向图-图G中每条支路均标有方向，为图G的有向图 4 连通图-图中任意二结点之间至少有一条由图中的支路联成的路径，则称之为连通图，否则称为非连通图。 * * 第1章 网络图论基础 1.1 网络图 1.2 关联矩阵 1.3 两种约束关系 1.4 矩阵分析法 * 1 欧拉与哥尼斯堡桥： 有条名叫 Pregel 的河流经哥尼斯堡(现加里宁格勒)，河中有两个岛，把市区分成四块陆地(A,B,C,D)，陆地间有七个桥相通。能否从任一陆地出发，走遍七桥而每桥只走一次？ 哥尼斯堡市区图 图论趣话 * 七桥问题的解决 欧拉规则 (a) 连接奇数个桥的陆地只有一个或超过两个以上时，不能实现一笔画。 (b) 连接奇数个桥的陆地仅有两个时，则从两者中任一陆地出发，可以实现一笔画而停在另一陆地。 (c) 每块陆地都连接有偶数个桥时，则从任一陆地出发都能实现一笔画，而回到出发点。 A B C D 用点表示陆地，用线表示陆地间的桥，便抽象成图。问题变成该图能否实现一笔画？ * 2 环球旅行与哈密顿圈 在一个画在平面上有20个顶点的图中，把所有20个顶点都标上城市名，旅游者从某个城市出发，找一条经过所有城市但只能经过一次的闭合回路。该回路称为哈密顿圈。环球旅行就是寻找哈密顿圈。 * 环球旅行问题的答案： * 3 平面图与非平面图 国王遗嘱大意：把国土分成5块给儿子，规定各块之间都要有边界。儿子又提出在自己分到的领土上都要修一个王宫，并