有源网络“有向根树法”的研究及应用

《有源网络“有向根树法”的研究及应用》由会员分享，可在线阅读，更多相关《有源网络“有向根树法”的研究及应用（42页珍藏版）》请在金锄头文库上搜索。

1、河北工业大学硕士学位论文 1 第一章第一章 绪论绪论 1- 1 图论概述图论概述 1- 1- 1 图论的基本思想图论的基本思想 无论是在自然界中，还是在日常生活、社会生活和工业生产活动中，用图形来描述对象或事物之间的某些特定关系常常感到特别方便。 例如， 用工艺流程图来描述某项工程中各工序之间的先后关系，用竞赛图来描述某循环比赛中各选手之间的胜负关系，用网络图来描述某通讯系统各小通讯站之间信息传递关系，用交通图来描述某地区内各城市之间的铁路连接关系，用原理电路图来描述某电器内各元件导线连接关系等等。 上述流程图、竞赛图、网络图、交通图等图形的点表示对象（如工序、选手、通讯站等） ，两点之间的有

2、向或无向连线表示两对象之间具有某种特定的关系（如先后关系、胜负关系、传递关系、连接关系等） 。点和线组成的图，是从实际物理系统模拟、抽象、简化得到的数学模型。根据图的性质分析和研究实际系统，可以简化分析的过程，得到更优的结果。这就是图论的基本思想。 1- 1- 2 图论的起源图论的起源 图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如图 1.1.1 所示。图中 A、B、C，D 表示陆地。七桥问题是：如何从这四块陆地中任何一块开始，经过每一座桥正好一次，再回到起点。 很长的一段时间，七桥问题都没有得到成功解决。1736 年，瑞士数学家欧拉对七桥问

3、题进行了研究。他用抽象分析法将七桥问题简化为一个图：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个图（如图 1.1.2） 。欧拉对这个简易的图进行严格的数学论证，证明七桥问题没有解。在论证过程中，欧拉给出了对于一个给定的图可以某种方式走遍的判定法则，即图中每个节点连接的边数必须是偶数个的法则。欧拉用简易的图对七桥问题的研究，揭开了图论及拓扑学研究的序幕。自此，很多数学家尝试用图去分析和解决一些实际的问题，图论也图 1.1.1 示意图 图 1.1.2 模拟图 图 1.1 哥尼斯堡七桥 Fig. 1.1 Koenigsberg 7 bridge B A

4、 D C A B D C 有源网络“有向根树法”的研究及应用 2 因此得以发展和广泛应用。 1859 年，英国数学家哈密顿发明了周游世界的游戏：一个规则的实心十二面体，在它的 20 个顶点标出世界著名的 20 个城市， 要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路， 即绕行世界。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，使得这一游戏问题引起了广泛的注意和研究。 另外一个非常著名的图论问题是“四色猜想” 。这个猜想的内容是：在一个平面或球面上，任何地图都能只用四种颜色来着色

5、，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。根据图论思想对地图进行抽象：每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。四色猜想是图论中的一个有趣的问题。对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。 1- 1- 3 图论的定义及应用图论的定义及应用 简单的讲，图论Graph Theory是以图为研究对象的一门学科，是拓扑学的一个分支。图是指由若干给定的点及连接两点的线所构成的图形。这种图形中，通常用点表示事物、用连接两点的线表示相应两个事物间某种

6、特定关系5，8，12。图论的实质是通过由点和线组成的图形，构成模拟物理系统的数学模型，并根据图的性质进行分析，提供研究各种系统的巧妙方法。 研究图的基本概念和性质、图的理论及其应用，构成了图论的主要内容14 。任何一个包含了某种二元关系的系统都可以用图论的方法分析，而且它往往还有形象直观的特点。事实上，我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否甚为重要，而连接线的曲直长短则无关紧要。由此数学抽象产生了图的概念。 图论中应用的线形图与几何图不同，每条边均可赋以权(Weight)，组成加权图，用来研究系统特性、进行决策分析、确定最优设计、调整经济管理等等。这个“权”可取为

7、一个正的数值，用以表示距离、流量、费用。通过加权图可以研究电网络、运输网络、通讯网络以及运筹学中的一些重要课题。 图论在运输网络、 线性规划以及运筹学中的应用是非常引人注目的。 L.R.Ford 与 D.R Fulkerson早在 1962 年写了一本研究网络流的专著。涉及通讯网络的问题主要是系统的可靠性，连通性；而运输系统则是最短路径，最少费用与最优定址等问题。 一方面，图论应用日益广泛，并不断开拓富有潜力的新领域。随着计算机功能的愈益增加，它的应用将得到更大的推动，其应用范围也将更加扩大。同时也会使得其相关理论的研究有了越来越大的发展空间。另一方面，能用二元关系描述的一些实际问题，也需要图

8、论的相关理论不断发展，以得到更优的解决方案。至今为止,拟阵理论、超图理论、极图理论、代数图论、拓扑图论等仍然是图论相关理论研究的重要内容。图论理论研究不断深入，在应用方面必将取得愈来愈多的丰硕成果。在应用空间的不断拓展和实际需求的双重推动下，图论研究迅速发展和深入。 河北工业大学硕士学位论文 3 1- 2 图论在电网络理论中的应用图论在电网络理论中的应用 电网络理论是电气工程及电子工程的重要理论基础。图论在电网络理论中的应用是其在电气电子领域中最主要的应用之一。 基尔霍夫（KIRCHHOFF）首先对电网络问题进行了全面的研究，证明了电阻性网络解的存在，但忽略了位的概念。麦克斯韦（MAXWELL

9、）指出了这个问题，提出两个对解决网络问题非常有效的方法麦克斯韦的网孔和节点对解法，从而弥补了基尔霍夫系统阐述的缺陷。麦克斯韦提出的节点对解法是节点导纳矩阵形式的解法，是拓扑分析的出发点6，7，11，13，对于电网络分析的发展具有非常重要的意义。 基尔霍夫和麦克斯韦开创了网络拓扑分析方法之后一个长时期内，拓扑分析进展一直很迟缓。直到本世纪五十年代，拓扑分析的研究才重新活跃起来。1965 年 W.K.Chen（陈惠开）提出了用有向图与有向 k-树分析有源网络的一般方法。在这个方法基础上，S.P.Chan（陈树柏）和 W.R.Dunn 等在拓扑分析上取得了一些新的进展，提出诸如 k-树组法等优化改进

10、形式。 随着研究的深入，图论这一富有趣味的学科在电网络分析方面的应用更加广泛，如建立对暂态分析及非线性、时变网络分析十分有效的状态方程，网络的稳定性、灵敏度分析，尤其 k-树方法不仅可用于网络分析，也可应用于网络综合。这些应用大大提高了人们对电网络的分析能力。 20 世纪后，图论渗透应用到了诸多领域，在电气及电子工程领域的应用更为突出。主要表现在两个方面： 1印制电路与集成电路的制造领域 印制电路与集成电路的制造限于平面图或平面子图的组合，因此平面性判定与平面子图的抽取、印制电路和集成电路的走线与元件布局是非常重要的研究课题。1961 年，C.Y.Lee 提出用计算机处理互连问题的方法，包括排

11、除障碍及导线长度优化。B.S.Ting 与 E.S.Kuh 推广 Lee 的方法来解决多层线路的走线问题。1974 年，D.A.Mlynski 著文阐述了图论方法解决集成电路布局问题的优缺点。K.Zibert与 R.Sael 提出平面化与布局的有效方法。S.Goto（后藤敏）与 E.S.Kuh 以线性布局为基础解决最短路长的二维布局问题。此外 Y.S.Huang（黄炎松）与 S.P.Chan 近年来也发表了数篇有关集成电路布局的论文。印制电路与集成电路的另一问题就是网络的自动故障诊断。近几年来，W.Mayeda，S.Shinoda，K.Onaga（翁田健治） ，Y.Kajitani，R.W.C

12、hen（陈润吾） ，S.P.Chan，E.S.Kuh 等在网络诊断和印制电路与集成电路布线方面取得了新成果。 2通讯网络领域 通讯系统含有两种不同功能的网络：即传输信息的流量网络与起控制作用的开关网络。流量网络与网络中各点之间的信息传输有关，能用以模拟多种其他类型的流量问题，例如公路交通运输或铁路货物运输。 开关网络讨论开关元件的连接问题。开关网络研究工作是 C.Y.Lee，S.Seshu 等人开始的。O.Wing引进了路径矩阵，导出开关函数与网络拓扑关系，还讨论了从路径矩阵综合开关网络问题。也有专门有源网络“有向根树法”的研究及应用 4 讨论多级开关网络的阻塞概率，抗损开关网络等问题。W.M

13、ayeda 曾讨论了双向支路、导出端点容量矩阵和支路容量矩阵，并说明如何利用这两种矩阵的关系实现网络综合。他还研究了抗损网络，对某个边如果失效时，流通可靠性的变化作了研究，还提出最大可靠性定理。 近年来，随着电工技术，特别是电子科学与计算机科学的飞速发展，引发了电网络理论相关的一系列新的课题，使得电网络理论这一古老的工程学科充满了勃勃生机。 1- 3 本课题的选题意义及研究内容本课题的选题意义及研究内容 在分析有向图、有向 k-树以及一些相关的电网络分析方法（如双树法，完全树法，矩阵法）的基础上1519。为了有效的分析有源网络，包括元件模型的建立以及拓扑分析的优化设计，本课题基于根树法，对有向

14、根树法在有源网络中的应用作了深入分析和研究。论文主要研究内容如下： 1. 研究有源网络元件模型的伴随有向图的生成方法。有向图是很重要的一种分析电网络的工具，是应用根树法分析电网络的基础。基于这种分析方法，如何生成电网络元件的伴随有向图是最为关键的问题。本课题研究了包括 VCCS、VCVS 等有源元件的伴随有向图模型，并且根据约束网络法及不定导纳矩阵形式，提出了含理想运算放大器的有源网络的伴随有向图模型。 2. 有向图的根树法分析。本课题对生成的有向图应用比较方便的根树法进行分析，基于 Minty算法思路，改进了 Mayeda- Seshu 算法并将其应用到有向图中，求解全部有向树、全部有向 2

15、-树。 3. 设计计算机软件。 通过计算机编程实现了上述两方面的算法， 并且实现了窗口模式的人机交互 界面，使输入更简洁，结果输出更直观。 河北工业大学硕士学位论文 5 第二章第二章 电路元件的模型化电路元件的模型化 电网络分析时，可以将网络抽象化。网络中的每个元件用线段代替，每个连接点用节点代替。经过这样处理后，我们就可以利用图论的方法来研究电网络。 2- 1 电路的图电路的图 2- 1- 1 电路的图的定义电路的图的定义 任何电路中，电压及电流不仅与元件性质有关，而且与元件的连接关系有关。可以用图来反映电路元件的连接关系。若元件的连接点用顶点表示，元件用边表示，电路可抽象成一个图，如图 2

16、.1所示。 图是由顶点与边组成的，用边来反映顶点间的某种联系，例如，图 2.1.2 中边 4 表示原电路 b、d节点间有元件连接。 一个图 G 定义为一个偶对(V，E)，记作 G=（V，E） ，其中 （1）V 是一个集合，其中的元素称为顶点； （2）E 是一个集合，其元素称为边，边为顶点的序对； 例如，图 2.1.2 中的图 G 可写成 V=a，b，c，d，E=1，2，3，4，5，l=（a，b） ，2=（b，c)， 3= (a，d)，4= (b，d)，5= (c，d)。 若有边 ek= （vi，vj） ，vi，vjV，顶点 vi，vj称为边的端点。边 ek又称为与顶点 vi，vj关联。如果 （vi,vj)（vj,vi） ，表明顶点对有序，它代表的边有方向。否则，边无向。相应地，图可分为有向图与无向图。 图 G=（V，E）的某节点 v 所关联的边数称为该节点的度，用 d(v)表示。如果 v 带有自环，则自环对 d(v)的贡献为 2。因本课题为电路分析，电路支路不会产生