二部图的匹配、独力集 例16： 判断下图的匹配 最大匹配 非完美匹配
完美匹配
二部图的匹配、独力集
定义5 若图 G的一个顶点子集中的任意两个点都互不相 邻, 则称该顶点子集为为G的一个点独立集。图G的独 立数为G的最大点独力集所含的点数，记为 (G)
定义6 若图 G的一个顶点子集K称为G的一个点覆盖子集， 如果G中的任意一条边都至少有一个顶点包含在G中. 图G 的覆盖数为G的最小点覆盖集中所含的点数，记为 (G) 若G中任一个顶点都是图G的边集S中一条边的顶点， 则称S为G的一个边覆盖集。含边数最少的边覆盖集中的 边数称为图G的边覆盖数。
二部图的匹配、独力集-相关定理
定理 1
(G) (G) | V(G) |
定 理 2 若 图 G没有孤立 顶点 ， 即顶 点 的最小 度 > 0 ， 则
' (G) ' (G) | V(G) |
定理3 对 于二分 图 G ， 有
' (G) (G)
二部图的匹配、独力集
定 义2 设 图G V, E, M E , 若M中 任 意 两 条 边 在G中 均 不 邻 接 ， 则 称 是G的 一 个 匹 配 。 M
二部图的匹配、独力集
定义3 若匹配M的某条边与点v关联, 则称M饱和 点v, 并且称v是M的饱和点, 否则称v是M的非饱 和点.
定义4 设M是图G的一个匹配, 如果G的每一个点 都是M的饱和点, 则称M是完美匹配；如果G中 没有另外的匹配M0, 使 | M0 |＞| M |, 则称M是最 大匹配. 含边数最多的最大匹配中所含的边数称为 图G的边独立数，记为 ' (G) 每个完美匹配都是最大匹配, 反之不一定成立.
i 1
min( Maxl (Ci ) Minl (Ci )) 目标2：
1i 3 1i 3
• 限制条件
V (C ) V(G)
i i 1
3
第一问目标简化： 多目标
Min(Max1i3l (Ci ))
单目标
分组： 方法很多。可以给定一个初始分组， 然后基于上述单目标进行调整。
问题2： 最小组数问题。（问题3也涉及） 分析： 求r组多旅行商路线，在满足题目要求 限制条件下，使得每个路线都包含县城， 且总体能覆盖V。并证明r-1组不可能。
引理1 设G = ( X, Y, E )为二部图, 则① G存在 饱和X的每个点的匹配的充要条件是 对任意S X,有 | N (S ) | ≥ | S | . 其中, N (S ) = {v | u∈S, v与u相邻}. ② G存在完美匹配的充要条件是 对任意S X 或S Y有 | N (S ) | ≥ | S | .
分析： 6 种 高度 5 个 槽 的钥匙 最多 可能有 65 7776 ， 通 过排 列组 合 ， 除 去不 满足 条件 的各种 情 况， 可 以 算 出一批 锁具 的总数为 5880件
• 由于两个 锁具 对应 的 5 个 槽 高 中有 4 个 相 同 ， 另一 个 只相 差 1， 被视 为互 开 ， 那 么它们 各 自 槽 高 之 和必为 一个 奇数 、 一个 偶数． 另外 ， 槽 高 之和为 奇数 和偶数 的锁 具 可 以 一 一对 应 ， 因 而各 占一 半 ： 2 9 4 0件 ， 槽 高 之和为奇数 ( 或偶数) 的两锁具之间不可能互 开 ， 所 以若 6 O个装一箱 ， 2 9 4 0个锁具可 以装 4 9箱 ， 4 9箱槽高之和为奇数或偶数的锁具 ， 肯定不能互开． 现在的问题是 4 9 箱是不是最 大可能的?
最佳推销员回路问题可转化为最佳 H 圈问题．方法是由给 定的图 G=(V,E)构造一个以 V 为顶点集的完备图 G’=(V,E’)， E’ 的每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权．即：
x,y E’, w(x,y)=mindG(x,y)
定理２ 加权图 G 的最佳推销员回路的权与 G’的最佳 H 圈的权相同．
问题3：最短时间及最优巡视方案
• 最短时间： 县城到最远乡镇的距离。不难 确定。最优巡视方案？？？ • 可以按照问题2的模型确定组数。答案为22. • 但是如何证明21不行？ 思考题？
问题4：组数已定，讨论T,t,V的改变对 最佳巡视路线的影响
• 要尽快完成巡视,就得要求每组完成巡视时 问尽量均衡,因为总的完成巡视时间按最长 的完成巡视时间计算。 现在讨论在均衡度 允许的范围内已分成n组后，改变T, t, V对 最佳巡视路线的影响。显然在分组不变的 情况下,无论如何改变分组后，对每组内的 最沈 封丛 视路线是没有影响的，但可能会 影响各组 间的均衡性 因此该问题实际上是 讨论T, t, V对分组的影响,即在不破坏原来分 组均衡的条件下,T 、t ,V允许的最大变化范
B题 灾情巡视路线 下图为某县的乡（镇）、村公路网示意图， 公路边的数字为该路段的公里数。 今年夏天该县遭受水灾。为考察灾情、组 织自救，县领导决定，带领有关部门负责人到 全县各乡（镇）、村巡视。灾情巡视路线指从 县政府所在地出发，走遍各乡（镇）、村，又 回到县政府所在地的路线。 若分三组（路）巡视，试设计总路程最短 且各组尽可能均衡的灾情巡视路线。
推销员问题-定义
流动推销员需要访问某地区的所有城镇，最 后回到出发点．问如何安排旅行路线使总行程最 小．这就是推销员问题． 若用顶点表示城镇，边表示连接两城镇的 路，边上的权表示距离（或时间、费用），于 是推销员问题就成为在加权图中寻找一条经过 每个顶点至少一次的最短闭通路问题．
定义 在加权图G=(V,E)中， （１）权最小的哈密尔顿圈称为最佳H圈． （２）经过每个顶点至少一次的权最小的闭通路称 为最佳推销员回路．
二部图的匹配、独力集
定义1 设X , Y都是非空有限顶点集, 且X Y = Φ ,
E xy x X , y Y
称G = ( X, Y, E )为二部图. 如果X中的每个点都与Y中的 每个点邻接, 则称G = ( X, Y, E )为完备二部图. 若 F：E →R +, 则称G = ( X, Y, E, F )为二部赋权图.
一般说来，最佳哈密尔顿圈不一定是最佳推销员回路， 同样最佳推销员回路也不一定是最佳哈密尔顿圈．
H回路，长22
最佳推销员回路，长4
定理１
在加权图 G=(V,E)中，若对任意 x,y,z V，
z x,z y,都有 w(x,y) w(x,z)+w(z,y)，则图 G 的最佳 H 圈也是最佳推销员回路．
将锁具的互开关系用图表示，锁具集合用V V1 V2 表示， 其 中 V 1和 V 分别表示槽高之和为奇数和偶数的锁具集合。 若 2 vi V1 , v j V2 , 能 够互 开， 则 两 点 连 一 边。 • 对 问题 1 构 造 的二分 图 ， 由于奇数 类锁 具 与偶 数类 锁 具 的对 称 性 ， 引理 1 满 足 ， 所 以存 在饱 • 和 V1 的每个顶点的匹配，而 V1 的顶 点互不 相邻 ， 因此
３）对 C 重复步骤（２） ，直到条件不满足为止，最后得到 的 C 即为所求．
分析： 灾情巡 视路 线 问题 是一个 寻求最佳多旅行商回路的问题 。
• 1、多旅行商问题 跟单旅行商问题的区别。单旅行商问题 可以转化为加权图的最优H圈问题。多旅行 商问题怎么办？ 2、第一问目标：总路程最短且尽可能均衡。 3 如何表述。目标1：Min( l (Ci ))
假定巡视人员在各乡（镇）停留时间T=2小时，在 各村停留时间t=1小时，汽车行驶速度V=35公里/小时。 要24小时内完成巡视，至少应分几组；给出这种分组 下你认为最佳的灾情巡视路线。 在上述关于T , t和V的假定下，如果巡视人员足 够多，完成巡视的最短时间是多少；给出在这种最短 时间完成巡视的要求下，你认为最佳的灾情巡视路线。 若巡视组数已定(如三组），要求尽快完成巡视， 讨论T，t和V改变对最佳灾情巡视路线的影响。
§1 引言
图论是应用十分广泛的运筹学分支，它已广泛 地应用在物理学、化学、控制论、信息论、科学管 理、电子计算机等各个领域。
在实际生活、生产和科学研究中，有许多问题 都可以用图论的理论和方法来解决。例如，完成工 程任务的时间最少；运输距离最短；工程所用费用 最少……等等。
1998年全国大学生数学建模竞赛题目
旅行商问题（TSP－traveling salesman problem）
一名推销员准备前往若干城市推销产品。如何为他 （她）设计一条最短的旅行路线（从驻地出发，经过每个城 市恰好一次，最后返回驻地）？这一问题的研究历史十分悠 久，通常称之为旅行商(推销员）问题。
哈 密 尔 顿 图
1859年，数学家哈密尔顿发明了一种周游世界的游 戏：在一个12面体的每个角点代表一个城市，问能否从某 城市出发，沿12面体的棱行走，经过每个城市一且仅一次， 最后回到出发地。
1994全国大学生数学建模竞赛题目
B题 锁具装箱
某厂生产一种弹子锁具, 每个锁具的钥匙有5个槽, 每个槽的高度
从{1,2,3,4,5,6}6个数(单位略)中任取一数。 由于工艺及其它原因,
制造锁具时对5个槽的高度还有两个限制: 至少有3个不同的数; 相 邻两槽高度之差不能为5。 满足以上条件制造出来的所有互不相同
的锁具称为一批。 出来的所有互不相同的锁具称为一批。 从顾客
的利益出发, 自然希望在每批锁具中"一把钥匙开一把锁"。 但是在 当前工艺条件下, 对于同一批中两个锁具是否能够互开, 有以下试
验结果: 若二者相对应的5个槽的高度中有4个相同, 另一个的高度
差为1, 则可能互开; 在其它情形下, 不可能互开。 原来, 销售部 门在一批锁具中随意地取每60个装一箱出售。 团体顾客往往购买几
箱到几十箱, 他们抱怨购得的锁具会出现互相开的情形。 现聘聘请
你为顾问, 回答并解决以下问题:
• 每一批锁具有多少个, 装多少箱。 • 为销售部门提供一种方案, 包括如何装箱(仍 是60个锁具一箱), 如何给箱子以标志, 出售 时如何利用这些标志, 使团体顾客不再或减 少抱怨。 • 采取你提出的方案, 团体顾客的购买量不超 过多少箱, 就可以保证一定不会出现互开。 • 按照原来的装箱办法, 如何定量地衡量团体 顾客抱怨互开的程度(试对购买一、二箱者 给出具体结果)。