第2章图论.ppt

矩阵A、Bf和Qf的关系 关于独立变量 扩展矩阵 ，或 ，或 关联矩阵与回路矩阵，以及割集矩阵与回路矩阵并不是独立的，存在如下关系： 设连通图G，按先树支后连支顺序编号，各矩阵可分解成相应的子矩阵，即 则可得 或： 又 于是矩阵Bf和Qf均可由关联矩阵A获得，即 : 连枝电流可作为电路的独立电流变量，此时独立电流源支路（电流是独立的）应该作为连枝 ； 树枝电压可作为电路的独立电压变量，此时独立电压源支路（电压是独立的）应该作为树枝 。 因为设树支电流向量为it ，连支电流向量为il ，利用割集矩阵有 同理：设树支电压向量和连支电压向量分别为ut和ul ，利用回路矩阵有 （1）将独立电压源作为树枝，独立电流源作为连枝； （2）按树的规则完成一个树的选择； （3）先从独立电压源支路开始，完成对树枝的编号； （4）再对连枝进行编号，其中将电流源支路的编号放在最后. 一般原则如下： 按照以上规则列写的矩阵称为扩展的矩阵并用下标“a”表示。 Aa Ba Qa * * 第二章 网络图论 图论是工程数学的分支，在许多其他领域均有应用。 如：城市规划，交通，系统工程，物流，医学等 第一节 网络与图 第二节 图的基本概念 第三节 关联矩阵、回路矩阵、割集矩阵 第四节 路径矩阵 第五节 矩阵A、B和Q的关系 第一节 网络与图 图 —— 点和线的集合（二元关系）； 反映网络的拓扑结构，与元件无关。 1、 KCL：在节点上的支路，KVL：回路上的支路； 2、方向：信号的转移。 电路图 Fig. 1 6 5 4 3 2 o ③ ② ① 有向图G 第二节 图的基本概念 一、图与子图 图 G =（V，E） 支路连接两个节点： 相邻 两节点（同类）， 节点与支路关联（非同类） a b 1 自环： a 图G的一个子图Gs ,Gs ? G , GS中节点VS与支路ES均属于G中的一部分，分别是V，E的子集。 若 VS = V，GS称为G的生成子图。 孤立节点 二、全通图、连通图及分离图 全通图：G中任意两节点均有支路. 孤立节点也是图的一部分 连通图：任意两节点间均至少有一条路径（支路序列）. 0 3 2 1 3 2 1 2 2 分离图： 0 3 1 3 1 三、平面图、有向图及无向图 平面图：可使各支路不相交；否则为非平面图 有向图：各支路标有方向图 无向图： 各支路无方向图 四、断点与可断图 G中任一节点移去时，与之相连的所有支路必须同时移去， 由此所得的子图不再连通了，该点就称为断点。 具有断点的图称为可断图。 断点 断点 断点 五、路径、树和树支、连支和补树、林 路径：两节点的通路，有始端点和终端点，各节点和支路只能出现一次； 有向图与无向图有差别，有向图不能逆向走。 林：分离图G的各部分子图的树构成林；K个分离部分构成K个树的林。 树和树支：连接所有节点，但不构成回路的最少支路集合； 至少有两个悬挂节点，树中支路称树支,树支数=n-1。 连支和补（余）树：G中除去树支以外的支路为连支，连支数=b-(n-1); 连支的集合称为补（余）树。 0 3 2 1 3 2 1 六、 单连支回路（基本回路）和单树支割集（基本割集） l1 l3 l2 c1 c2 c3 2 3 6 1 5 4 树支: 1、2、 3; 连支：4、5、6 单连支回路: l1(1、2、4) ， l2(2、3、5)， l3(1、3、6) 单树支割集: c1(1、4、6)， c2(2、4、5)， c3(3、5、6) 若按2、4、5为树支，1、3、6为连支，情况如何？ 一、 关联矩阵 图G的节点与支路的关系数字化，用矩阵的形式表示。 第三节 关联矩阵、回路矩阵、割集矩阵 节点和支路关联性 图的拓扑结构用n?b的矩阵描述 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 = 1 支路k与结点j 关联，方向背离节点; -1 支路k与结点j 关联，方向指向节点; 0 支路k与结点j无关. 参考结点 1 ２ ３ ６ ５ ４ ① ② ④ ③ A为降阶