Page 222 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

型是：在人员分派问题的模型中，图 G 的每边加了权 表示 xi 干 y j
工作的效益，求加权图 G 上的权最大的完美对集。

解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要
引入可行顶点标号与相等子图的概念。

定义 若映射

则称 l 是二分图 G 的可行顶点标号。令

称以 El 为边集的 G 的生成子图为相等子图，记作 Gl 。

可行顶点标号是存在的。例如

第六节 Euler 图与 Hamilton 图的应用

一、基本概念

定义 经过 G 的每条边的迹叫做 G 的 Euler 迹；闭的 Euler 迹叫做 Euler 回路
或 E 回路；含 Euler 回路的图叫做 Euler 图。
Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重

复地行遍所有的边再回到出发点。
定理 6
1.G 是 Euler 图的充分必要条件是 G 连通且每顶点皆偶次。

2. G 是 Euler 图的充分必要条件是 G 连通且 是圈。

3.G 中有 Euler 迹的充要条件是 G 连通且至多有两个奇次点。
定义 包含 G 的每个顶点的轨叫做 Hamilton( 哈密顿 ) 轨；闭的 Hamilton 轨

叫做 Hamilton 圈或 H 圈；含 Hamilton 圈的图叫做 Hamilton 图。
直观地讲，Hamilton 图就是从一顶点出发每顶点恰通过一次能回到出发点的
那种图，即不重复地行遍所有的顶点再回到出发点。

212