第六章 图论_原创文档.pdfVIP

第六章图论

§8.1图论发展史

第一阶段：瑞士数学家欧拉（E.Euler）在1736年发表了一篇题为“依据几何位置的解

题方法”的论文，有效地解决了哥尼斯城堡“七桥难题”，从此开创了图论的历史新纪元；所

谓“七桥难题”是指：18世纪的哥尼斯堡城中流过一条河，河上有七座桥连接着河的两岸和

河中的两个小岛，如图8-1所示：一个游者怎样才能一次连续走过这七座桥而每座桥只走一

次，回到原出发点；没有人想出这种走法，又无法说明走法不存在。欧拉将这个问题归结为

如图8-2所示的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七

桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且仅一次，再回到原点？欧拉证

明了这样的走法不存在，并给出了这类问题的一般结论。

图8-1图8-2

第二阶段：1847年，数学家基尔霍夫（Kirchhoff）运用图论解决了电路理论中的求解

联立方程的问题，他引入了“树”的概念，可惜由于他的思想超出了时代的发展而长期未被

重视；到1857年，英国数学家凯莱（Cayley）又从化学的角度进一步扩展了“树”的概念，

从此图论又有了新的发展。

第三阶段：1857年，英国数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实

心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任

一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅

行”问题。要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。

第四个阶段：20世纪以后，随着计算机的不断发展，图论也有了突飞猛进的进展，广

泛应用于各科领域：如物理、化学、信息论，博弈论，计算机网络，等等；目前图论已经发

展成完整的一个数学分支，并且越来越多的数学爱好者倾向于研究图论。

§8.2图与网络的基本概念

一、图与网络的基本概念

1、图的相关概念及其分类

引例：在一次聚会中有五位代表其中与，与，

与，与，与是朋友，则我们可以用一个带有五个顶点、五条边的图形来

表示这五位代表之间的朋友关系（图8-3）：

图8-3

定义1、设是一个非空有限集合，

是与不相交的有限集合，一个图是指一个有序二元组，其中称

为图的顶点集，称为的边集；，.

如引例中五位代表之间的朋友关系可以用图来表示，，

，其中：，，，，

.

定义2、两个端点重合的边称为环；两点之间多于一条边的，称为多重边；

不含有环和多重边的图称为简单图。

定义3、任意两个顶点之间都有边相连的无向简单图称为完全图，有个顶点的完全图。

定义4、图的点集可以分为两个非空子集即：

，使得中每一条边的两个端点必有一个端点属于，另一个端点

属于，则称为二部图（偶图），记作：。

2、顶点的次

定义5、以点为端点的边数叫做顶点的次（度），记作:。

例如上述引例图中：。

定理1、任何图中顶点次数的总和等于边数的2