§2-4 图论模型
图论产生于哥尼斯堡（Konigsberg）七桥问题，原德国（现立陶宛）哥尼斯堡（现加里宁格勒），那里有一条河，称为普雷格尔（Pregel）河，河上有七座桥。当地人们试图沿河上每一座桥走一遍，且每一座桥只走一次再返回原出发地，但没有人能够成功。这就是被称为哥尼斯堡七桥问题的一个难题。著名数学家 Enler 将其转化为图（1736年），从而，哥尼斯堡七桥问题转化为图论上的一笔画问题。
1、基本概念及几个问题：
在图论中,由顶点集V(G) (Vertex) 以及边 E(G)(Edge),顶点之间的连线,组成的图形称为图（Graph）
图上顶点与顶点间可能有边，也可能无边，我们称为有、无关系。
图2-18
借用代数中的“关系”概念：设有
二个集合A、B，A与B的乘积为A×B=｛(x,y)∣x∈A, y∈B｝， A×B 的子集R?A×B称为 A与B的一个关系。 例如： 同学关系；师生关系 ；父子关系等。 特殊的关系有：等价关系R，满足 1. 自反性（(x,x)?R）；2. 对称性（(x,y)?R则 (y,x)?R）3. 传递性（(x,y)?R,(y,z)?R则 (x,z)?R）。
图可以表示为G(V , E)或 (V(G) , E(G) )=G或G(V , R) (R是V与V的一个关系)。
图分为有向图，对应边有方向，从而，对应的关系不满足对称性；无向图，对应边无方向。
如：集合A=｛北京、天津、上海、重庆 ｝以及二地之间的航线可得一图（图2-19）。按水路则可得另一图。
７８
图2-19
图是由顶点与部分顶点间连线组成。
例 集A=｛张三（A）、 李四（B）、王五（C）、赵六（D）｝, 张三是李四、王五的老师，赵六是李四的老师，李四是王五的学生。用图表示即图2-20。 这是一个有向图, 对应的关系R=｛(A,B), (A,C), (D,B), (B,C)｝. 图的边可用 uv （u、v 为端点）或e表示； 顶点相邻：如果二个顶点与同一条边相邻； 环边：如果一条边的二个端点重合, 图2-21中的e2；
重边：端点重合的二条边如图2-21中e3,e4； 轨道：由顶点到边到顶点┅┅最后到顶点组成的图。如v0e1v1e 2 …vn-1 en 是一个轨道； 迹（链）：边不重的轨道 （顶点可能重合）；
简单图：没有环边也没有重边的图 路（轨）：顶不重的轨道。闭合路或迹叫圈。
对于图我们只关心有、无边、是否相邻，不关心形状，即同一图可以有不同的形状，如图2-22的(a),(b)表示同一个图。
子图： 设图G1=(V(G1), E(G1 ) ) ，G2 = (V(G2) , E(G2) )，G1称为G2的子图，如果 V(G1)?V(G2) , E(G1)?E(G2)。
偶度点： 与偶数条边相邻的点；奇度点： 与奇数条边相邻的点。 2、几个问题：
1） Euler
圈
(环游)： 自图的任一点出发，每条边经过且仅经过一次再回到出发点的图；Euler图（途径）（或一笔画）：从图的任一点出发，每条边经过且仅经过一次的图；E图：每一顶点为偶点的图； E链：经过每一边的链；M图：仅有二
个奇点的图（与E链的区别：M图必有二个奇点，E链未必）。 问：Euler 圈，E图，M图是否存在？如何求出？
７９
图2-20
图2-21
图2-22
2） Hamilton 路：包含图的所有顶点的路；
Hamilton 回路（圈）： 包含图的所有顶点的圈。
3) 中国邮路问题：一邮递员从邮局出发去各街道投递信件，然后再回到邮局，每条街道至少经过一次，求一条路使其走过的路线最短。
本问题在1962年由山东大学管梅谷先生提出，所以称为中国邮路问题。 4) 货郎担问题(又名旅行售货商问题)：一货郎挑着担子走村串巷卖东西, 求一
条经过每一村的最短的路。
5） 平面图：能画在平面上且相异边不相交的图，典型的例子是房屋和井（见图2-29）。
6） 偶图与对集：二个点集，以及边是由分别与另一个集合中点相连的图。 7） 四色问题：任何一张地图，都可以用不超过四种颜色涂色使之任意相邻区
域为不同颜色。
8）最小生成树
下边分段介绍这些问题。 3、Enler图与中国邮路问题
定理2-1：图G为Euler环游（或Euler 图）的充分必要条件是连通图G中任一顶点全为偶度点。
证明：必要性：不妨设W为G的Euler环游，则每一顶点v的度数k必为偶数（Euler环游为圈）
充分性：分三步1. 若对于图G的任一顶点v， d(v)≥2 则G至少含有一个圈。
2. G由n个无公共边的圈组成
由1. G至少有一圈 K0 ， 我们从G中删去 K0 (若顶点v的度数为2，则此顶点被删去，否则不删去)， 剩下的图仍满足定理条件，故可重复上述步骤有限次，如 n-1次，则剩下一个圈Kn ,从而G由一些圈组成且每条边仅属于一个圈。
3. G为Euler 环游
设G为G1,G2?Gn 的并 （Gi由2.得到的圈）， Gi无公共边。只要证明：?1?k?n, 存在闭路w恰含k个圈。
用归纳法 若k=1 明显为Euler环游，取w=G1即可。
设 1≤k≤n时G为Euler环游，即存在闭途径w?包含k个圈。由于G为连通图，故在剩余的n-k个圈中必含有一个圈C, 与w?有公共顶点（否则将不连通），不妨设有相同的起点（且为终点），于是 w=w?∪C 恰含{Gi} 中k+1个圈。
推论：（一笔画定理） 一个连通图G为Euler途径（即一笔画成）的充要条件是它
８０
图2-23
至多含有二个奇度点。
证明：充分性 若去掉二个奇度点间的一条路经（如图2-24）则图为Euler环游，不妨设该环游从其中一个奇度点出发且回到该奇度点，再沿去掉的一条边到另一个奇度点，即知该图为Euler途径。
必要性 若G为Euler环游，则由定理知每个顶点为偶度点。否则，设u0, v0为Euler途径的起止点，则G+u0v0有Euler 途径，从而仅有u0, v0为奇度点。
例7：七桥问题
可化为图2-18，由于A,B,C,D皆为奇度点，故不能一笔画成。
另外图2-25中的（a）,(c)是Euler途径，(b)不是Euler途径
定理2-2： 若图G有2k个奇度点，则该图可以用k笔画成。
例8在一个晚会上握过奇数次手的人的个数是偶数。
以人为顶点，握过手则在这二个顶点（人）间联一条边。显然，该图的奇度点个数为偶数个。
例9 图2-26有8个奇度点，故需4笔画成。 例10 中国邮路问题
一邮递员从邮局出发去各街道投递信件，然后再回到邮局，每条街道至少经过一次，求一条路使其走过的路线最短。
若所研究的问题为Euler环游，则问题显然，且Euler环游为最佳路线。否则以如下问题（如图2-27，非E图）为例说明中国邮路问题的解法：
第一步，将图变为Euler环游。 （由于 v2, v3, v6, v7为奇度点，故非E图）。 首先，增加边使每一奇度点变为偶度点；
其次，若某二点间重边数多于一条，则去掉偶数条；最后检查含有重边的圈： a）若各圈长度＞2重边长，则方案最优，否则b)调整，将原来重复的边去掉，没有重复的边加上边（变成重边）。
８１
图2-24
图2-25
图2-26 图2-27
如此可将问题转化为Euler环游问题。
第二步，对于G为Euler环游情况，求出Euler回路。 Fleury算法——求Euler环游的算法 1． 2．
取v0 ∈V(G), 记w0=v0；
设Wi=v0e1v1e2 ? eivi 已选定，则从E－{e1?
ei}中选取一条边ei?1 使 a) ei?1与ei相邻 ； b)除非不得已，ei?1不是G－{e1?ei}的桥（桥：e称为图G的桥，如果e不在G的任一圈（或去掉e，图不连通）； 3．
重复2）直到不能进行，即得一条Euler环游。
图2-28
第三步，求图的Euler途径。
定理2-3 若G是Euler环游，则Fleary算法终止时即得到Euler回路。
例11扫雪问题（AMCM-90B美国数学建模竞赛90B题）是考虑二辆扫雪车清扫路面积雪问题。
图2-29
地图(图2-29)中的实线表示马里兰州威考密科县中扫雪区域中的二车道马路，虚线表示州属高速公路。一场雪后，从位于*标记地点以西4公里的二处车库派出二辆扫雪车。求用二辆扫雪车清扫路面上的雪的有效的方法，扫雪车可以利用高速公路进入扫雪区。
假设扫雪车既不会发生故障也不停顿，在交叉路口不需要特别的扫雪方法。 大致做法：
８２