因为理论物理学研究的需要,所以在这个学科内不止一次地发现过图论。乌伦伯克(uhlenbeck)在统计力学的研究中用点来代表分子,两个点的邻接表示存在某种物理形式的最邻近的相互作用,如磁的吸力或斥力。在李政道和杨振宁的类似解释中,点代表欧几里得空间的小立方体,其中每一个立方体可能被一个分子占有或者不被分子占有。于是,两个点邻接就表示两个空间都被占有。另外,物理学还用图论来作为一种图形的表示方法。在范曼(Fevnmanon)提出的图解中,点代表物理粒子,线代表粒子碰撞后的路线。
在概率论中,马尔可夫链的研究引进了有向图,它的意思是:点代表事件,一条从一个点到另外一个点的有向线表示这两个事件直接相继有正的概率。研究中,直接定义一个马尔可夫链是一个网络,其中从每一个点出发的所有有向线的值的和是1。有向图有一种类似的表示法出现在数值分析的矩阵求逆和特征值计算的部分中,瓦尔加(Varga)给出了一些例子。对于一个给定的矩阵,特别是“稀疏的”矩阵,可以用如下的方式构成一个有向图:用点来代表给定的矩阵的行与列的指标,当矩阵的i、j元非零时有一条从点f到点.,的有向线。这种方法与处理马尔可夫链的方法有相似性。
线性规划与运筹学的领域里也利用图论的方法研究网络上的流的形式。一个图的点表示某种货物可以储藏或装船的实际位置,从一处到另一处的一条有向线和记在这条线上的一个正数代表一条运输货物的水道和它的能力,这个能力给出可以同时通过的最大允许数量。
科技的迅猛发展向图论提出了越来越多的需要解决的问题,使图论在科学界非常活跃。尤其是计算机科学的快速发展,为图论及其算法的实现提供了强大的计算与证明的手段,有力地推动了图论的发展,而图论在开关理论、数据结构、操作系统、形式语言、计算机网络、编译程序、人工智能等方面亦有显著贡献。
目前,图论领域形成了两个研究方向:一个是以研究图的性质为主,称之为抽象图论;另一个是以研究图的算法为主,称之为算法图论,也称为网络最优化。本书中不仅介绍了图论的基本原理,还介绍了图论算法及其应用。
……
展开