第5章 图与网络分析
图论的根本概念引言瑞士数学欧拉
〔Euler
〕在1736年发表了图论方面的第一篇论文，题为
“依据几何位置的解题方法
〞，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该河上有两个岛，河上有七座桥，如图5-1
〔a〕所示。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。
<Object: word/embeddings/oleObject1.bin>
欧拉用A、B、C、D四点表示河的两岸和小岛，用两点间的联线表示桥，如图5-1
〔b〕，该问题可归结为：能否从任一点出发，通过每条边一次且仅一次，再回到该点？即一笔画问题。欧拉证明了这是不可能的，因为图中每点都只与奇数条线相连。这是古典图论中的一个著名问题。
运筹学中的
“中国邮递员问题
〞：一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个总是就与欧拉回路有密切的关系。
图论的第一本专著是匈牙利数学家
著的“有限图与无限图的理论
〞，发表于1936年。随着科学技术的
开展及电子计算机的出现和广泛应用，图 ...