各种图论模型及其解答
摘要：
本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。
符号约定：
Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。
一、引言
图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。整个求解过程如下：
原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解 整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。存在以下两种情况： ①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图
②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图 如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。
综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。
例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友
M：点表示人，连线表示当且仅当该两个人是朋友 A：问题转化为任何一个图一定存在两个顶点的度相等
二、图论模型
接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。 2.1 偶图模型
凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这
类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。 (1) 仓库与销售间
M：点代表仓库或销售点，连线代表仓库与销售店间的关联 (2) 上课安排问题
Q：学校有6位教师将开设6门课程。六位教师的代号是Xi（i=1,2,3,4,5,6)，六门课程代号是Yi （i=1,2,3,4,5,6)。已知，教师X1能够胜任课程Y2和Y3；教师X2能够胜任课程Y4和Y5；教师X3能够胜任课程Y2；教师X4能够胜任课程Y6和Y3；教师Y5能够胜任课程Y1和Y6；教师X6能够胜任课程Y5和Y6。
M：点表示教师或者课程，连线表示当且仅当该教师能胜任该课程 2.2 最短路模型
凡涉及到最小状态转换问题，均可转化为最短路模型。点表示允许的状态，连线表示状态的转换（可逆与不可逆分别对应于无向图、有向图）。 (1) 最短航线
M：点表示城市，连线表示当且仅当两城市有直达航线，并在该线上注明两城市的距离，即权值
A：问题转化为求两点间的最短路径 (2) 状态转换
Q：某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升。求最少的操作次数能均分酒。
M：设x1,x2,x3分别表示8,5,3升酒壶中的酒量，则
点表示组合(x1,x2,x3) ,连线表示当且仅当可通过倒酒的方式相互变换
A：问题转化为在该图中求点(8,0,0)到点(4,4,0)的一条最短路 (3) 狼羊菜渡河
Q：在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河去，由于船太小，每次只能载一样东西。由于狼羊，羊卷心菜不能单独相处。问摆渡人至少要多少次才能将其渡过河？
M：但是以下组合不能允许出现：狼羊菜，羊菜，狼羊，人，人狼，人菜，共6种。岸上只能允许出现10种组合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。
点表示可允许的组合，连线当且仅当两种情况可用载人(或加一物)的渡船相互转变。
A：问题转化为求由顶点“人狼羊菜”到顶点“空”的一条最短路。 2.3 最小生成树模型 道路铺设
Q：道路铺设，使得任意两个地方均可达，并且费用最小
M：点表示工厂(假设是工厂)，任意两点连线，并标出铺设需要的费用 A：问题转化为求该图的最小生成树 2.4 欧拉图模型
通俗地讲，G是欧拉图当且仅当G存在经过每条边恰好一次，并且回到起始点的迹。
(1) 哥尼斯堡七桥问题
Q：能否从一点出发，走遍7座桥，且通过每座桥恰好一次，最后仍回到起始地点
M：点表示陆地，连线表示桥 A：问题转化为G是否存在E图 (2) 中国邮递员问题
Q：邮递员必须走过他投递范围内的每一条街道至少一次，选择一条尽可能短的路线
M：点表示路口，连线表示当且仅当两路口有直达街道
A：若G是E图，通过Fleury算法构造Euler环游，即为所求。否则，按一定规则添加重复边，再用Fleury算法构造Euler环游。 2.5 哈密尔顿圈模型 (1) 旅行售货员问题——TSP
一售货员要到若干城市去售货，每座城市只经历一次，问如何安排行走路线，使其行走的总路程最短。 例子：
Q：一电脑代理商要从她所在城市出发，乘飞机去六个城市，然后回到出发点，如果要求每个城市只经历一次，能否办到？给出行走方案。
M：点表示城市，连线表示两城市有直达航线 A：该图是否存在H圈 (2) 圆桌会议座位安排
Q：若干人围圆周开会，每个人会不同的语言，如何安排座位，使得每个人能够和他身边的交流
M：点表示人，连线表示当且仅当两个人能交流，即至少会同一种语言。(可能你一下子想到的偶图模型，的确该问题可以抽象成偶图模型，但很难转化为图论问题)
A：给出该图的一个H圈 2.6 匹配模型 (1) 旅游座位安排
Q：有一个旅行团要组织一批人去旅游，其中一些人是朋友他们要乘坐公共汽车去，而车上的位子是成对的。因此为了让大家旅途更愉快，旅行团负责人需要将成对的朋友安排在一起。给出一种安排方案。
M：点表示旅行团的人，连线表示当且仅当两人是朋友 A：求该图的最大匹配 (2) 研究生找工作
Q：学生能找到理想工作吗？
M：点表示研究生或者工作，连线表示当且仅当学生申请了该工作 A：问题转化为求饱和每个顶点的一个匹配，即完美匹配 (3) 最优分派问题
M：点表示工作或者人员，构造完全偶图，边的权值表示该工人做此份工作的效率
A：问题转化为求该图的最优匹配 2.7 平面图模型
平面模型可以这样理解，交通网络，使得不交叉，且无需修高架桥、隧道（这里的隧道显然跟山洞不同） (1) 电路板设计问题
Q: 连接电路元件间的导线间不能交叉。否则，当绝缘层破损时，会出现短路故障。
M；点表示电路元器件，连线表示元器件间的连接 A；该图是否可平面 (2) 景区空调管道的设计
M：点表示景区，连线表示当且仅当两景点间要铺设空调管道 A：能否把上图画在平面上，使得边不会相互交叉？ (3) 3间房子和3种设施问题
Q：要求把3种公用设施(煤气，水和电)分别用煤气管道、水管和电线连接到3间房子里，要求任何一根线或管道不与另外的线或管道相交，能否办到？
M：点表示公用设施或者房子，连线表示该类公用设施连接到该房子 A：抽象出来的图是否可平面嵌入 2.8 着色模型
点着色问题对应于顶点集合的一种划分方式，对应于分类问题。边着色对应于边集合的一种划分方式，也对应于分类问题。区分点着色模型和边着色模型，主要在于抽象出来的模型，是相邻的顶点还是相邻的边不能着同一种颜色。 (1) 点着色模型
① 考试时间安排
Q：使得学生们不会有相互冲突的考试，最小安排数
M：点表示待考的课程，连线表示至少有一个学生同时选择这两门课 A：问题转化为求该图的点色数(把互不冲突的课程、考试安排在同一个时间段完成)
② 课程安排问题
Q: 学生选择课程中，使得学生选课不会发生冲突，如何制订一张课时数尽可能小少的课表
M：点表示课程，连线表示当且仅当有某个学生同时选了这两门课程 A：问题转化为求该图的点色数 ③ 交通灯的相位设置问题
Q：为了(最终)让所有的车辆都能够安全通过路口，对于交通灯来说，所需要的相位的最小数是多少
M：点表示车道，连线当且仅当两个车道上的车不能同时安全地进入路口 A：问题转化为求该图的点色数 (2)边着色模型 ① 排课表问题
Q：设有m位教师，n个班级，其中教师xi要给班级yj上pij节课。求如何在最少节次排完所有课。
M：令X=｛x1,x2,?,xm｝, Y=｛y1,y2,?,yn｝,xi与yj间连pij条边，得偶图G=(X, Y)。
A：问题转化为求该图的边着色数 (2) 比赛安排问题
Q：最少天完成比赛
M：点表示参赛人，连线当且仅当两人有比赛
A:问题转化为求一种最优边着色，即用最少色数进行正常边着色 2.9 覆盖模型
覆盖模型，对应于控制问题，通俗地讲点覆盖对应于用最少的点来控制所有边(即任一边至少有一个顶点在点独立集中)，边覆盖对应于用最少的边控制所有的点。均对应于控制问题。 (1) 哨站设计
Q：城市设置哨岗，使得哨兵能监管所有街道的最少哨岗数 M：点表示交叉口，连线表示存在直达街道