[科普中国]-网络图论

应用图论研究网络的几何结构及其基本性质的理论，又称网络拓扑(network topology)。图论是离散数学的一个分支，它的研究对象是从实际问题中抽象出来的，用节点(顶点)和支路(边)构成的线图(graph)，简称为图。

释义应用图论研究网络的几何结构及其基本性质的理论，又称网络拓扑(network topology)。图论是离散数学的一个分支，它的研究对象是从实际问题中抽象出来的，用节点(顶点)和支路(边)构成的线图(graph)，简称为图。例如图1 (a)中的电网络，其几何结构可表示成相应的线图，如图1 (b)。在线图中忽略了电路元件的性质，边的长短与弯曲度都不重要，突出的是节点和支路之间的连接关系。图2是一公路交通网络的线图，含有8个节点(城市)和13条支路(公路)。边上注的字(加权)表示公路长度。用线图表示的这种连接关系以及由此产生的全部几何性质又统称为拓扑性质，故网络图论又称为网络拓扑。

起源图论起源于1736年数学家L.欧拉(L.Euler)求解哥尼斯堡七桥难题。1847年G.R.基尔霍夫(G.R.Kirchhoff)首次用“树”的概念列出电路方程，并为电网络的拓扑分析奠定基础。20世纪中叶以后图论应用日益扩大，涉及网络分析与综合、计算机辅助设计、电路布图、信号流图、电力系统、建筑施工以及最短路径与最大流等方面。随着计算机应用的普及，图的算法设计成为引人入胜的课题。设计有效算法是推广图论应用的关键。衡量算法有效性的主要尺度是运算时间。运算时间可用计算复杂性代替，后者是线图规模(如图的节点数)的函数。

网络拓扑分析从网络的线图和元件参数可直接求各种常见的网络函数，如单口网络的策动点函数和双口网络的转移函数。

1847年G.R.基尔霍夫首先提出一套建立在回路方程基础上的网络拓扑公式。此后，J.C.麦克斯韦(J.C.Maxwell)发展了另一套建立在节点方程基础上的拓扑公式。通常网络函数可通过其节点导纳矩阵行列式△=det Yn和它的代数余子式来表示。上述拓扑公式表明，对于det Yn和其代数余子式的计算可转化为直接求网络对应线图G中全部树的树支导纳乘积之和与相应的二树的树支导纳乘积之和，即

△=det Yn=全部的树支导纳乘积之和

△ij=对应的全部二树的树支导纳乘积之和其中，△ij为△=det Yn中元素(i，j)的余子式，所谓二树是指从G的一个树T中(含n-1个树支)，去掉任一树支而得到的G的一个子图。二树包含G的全部节点，仅有n-2条支路，由两个分离的子图组成，每个子图都不含回路。以上用枚举树以求得网络函数的方法也称为“k树法”。并已推广到含有互感和受控源的有源网络。

信号流图法是在1953年由S.J. 梅森(S.J.Mason)提出的分析线性系统的拓扑方法。流图分析包括两个步骤：先以加权有向图模拟一个线性系统，再用图论方法求对应的路径、回路数，然后进行运算求得增益。这种方法不仅有效地用来分析反馈控制系统，还可用于热传导分析和机械结构分析等。

拓扑分析法的主要优点是计算较为简便，不像解析法那样要展开高阶行列式，可免除或减少对消冗余项，提高计算精度，且用线图模拟系统，形象直观，物理概念明确;但拓扑法的主要缺点是效率低。随着网络规模加大，求树和回路的计算量将急骤增加，因之一般局限于分析小型网络。

网络图论还涉及许多非电网络问题。例如在图2公路交通网络图中，求S到G的最短路径。更有实用意义的是求所有节点对间的最短路径，例如在排定运输调度计划，选择商店、邮局或急救站场址时会用到。这些算法可以方便地编制程序上机运算。

早在1962年L.R.福特(L.R.Ford)与D.R.富尔克森(D.R.Fulkson)就发表了第一本研究网络流的专著。在网络流问题中最有代表性的是求最大流问题，即在给定的运输网络设备条件约束下，可能传输的最大流量。在网络流计算中，有个著名的最大流最小切割定理：在运输网络中，最大流的值等于最小切割的容量。利用这个定理，可方便地求出网络的最大流。1962年L.R.福特与D.R.富尔克森提出的标号算法是计算运输网络中最大流的有效算法。网络流算法在电力系统网络规划、安全分析与状态估计中均得到应用。

网络图论在理论、算法和应用上都存在不少有待解决的问题。特别至今还有许多问题尚未找到有效算法，仍值得进一步研究探讨。1

本词条内容贡献者为:

周敏 - 副教授 - 西南大学