当前位置：文档之家 › 偶图的算法及应用

偶图的算法及应用

  • 格式：ppt
  • 大小：150.00 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

图论重要结论

图论重要结论

定理1： 图G= (V, E)中所有顶点的度的和等于边数m 的2倍，即：推论1 在任何图中，奇点个数为偶数。

推论2 正则图的阶数和度数不同时为奇数 。

定理2 若n 阶简单图G 不包含Kl+1，则G 度弱于某个完全 l 部图 H ，且若G 具有与 H 相同的度序列，则: 定理3设T 是(n, m)树，则：偶图判定定理: 定理4图G 是偶图当且仅当G 中没有奇回路。

敏格尔定理: 定理5 (1) 设x 与y 是图G 中的两个不相邻点，则G 中分离点x 与y 的最小点数等于独立的(x, y)路的最大数目； (2)设x 与y 是图G 中的两个不相邻点，则G 中分离点x 与y 的最小边数等于G 中边不重的(x, y)路的最大数目。

欧拉图、欧拉迹的判定: 定理6 下列陈述对于非平凡连通图G 是等价的：(1) G 是欧拉图；(2) G 的顶点度数为偶数； (3) G 的边集合能划分为圈。

推论： 连通非欧拉图G 存在欧拉迹当且仅当G 中只有两个顶点度数为奇数。

H 图的判定: 定理H 图，则对V(G)的任一非空顶点子集S定理8 (充分条件) 对于n ≧3的单图G ，如果G 定理9 (充分条件) 对于n ≧3的单图G ，如果G 中的任意两个不相邻顶点u 与v ，有：定理10 (帮迪——闭包定理) 图G 是H 图当且仅当它的闭包是H 图。

定理11(Chv átal ——度序列判定法) 设简单图G 的度序列是(d1,d2,…,dn), 这里，d1≦d2≦…≦m<n/2,或者 dm>m,或者dn-m ≧ n-m,则定理12 设G 是n 阶单图。

若n ≧3且则G 是H 图；并且，具有n 个顶点 条边的非H 图只有C1,n 以及C2,5.定理13 (Hall G 存在饱和X 每个顶推论：若G 是k (k>0)正则偶图，则G 存在完美匹配。

定理14 (哥尼，1931) 在偶图中，最大匹配的边数等于最小覆盖的顶点数。

离散数学PPT课件10着色与对偶图(ppt文档)

离散数学PPT课件10着色与对偶图(ppt文档)






不同颜色.
四. 图G的正常着色(简称着色):
1. 对G的每个结点指定一种颜色,使得相邻接的两个结点
着不同颜色. 如果G着色用了n种颜色,称G是 n-色的.
2.对G着色时,需要的最少颜色数,称为G的着色数,记作
x(G) .
3.对G着色方法:(下面介绍韦尔奇.鲍威尔法)
3.对G着色方法:(介绍韦尔奇.鲍威尔法 Welch.Powell) ⑴将G中的结点按照度数递减次序排序,(此排序可能不唯 一,因为可能有些结点的度数相同) ⑵用第一种颜色对第一个结点着色,并按照排序,对与前面 着色点不邻接的每一个点着上相同颜色. ⑶用另一种颜色对尚未着色的点, 重复执行⑵和⑶,直到
⑶当且仅当ek只是一个面Fi的边界时, vi*上有一个环ek* 与ek相交.
v3*
则称图G*是G的对偶图.
v5
F1 v1*
F3
可见G*中的结点数等于
F2 v2*
G中的面数.
二. 自对偶图:如果图G对偶图G*与G同构,则称G是自对偶
图. (如下图) 三.对偶图与平面图着色的关系:

对平面图面相邻面用不同颜 色的着色问题,可以归结到对 其对偶图的相邻接的结点着
有共同的学生在读, 就在两门课程之间连一直线.得到图:
结点度数递减排序:
A
B,C,D,G,A,E,F 对图正常着色后, 标有同一种颜色的 G
课,可以同时考试.安排考试日程: 周一: A 周二: B,F 周三:C,E 周四: D,G
F E
作业 P189 – 8.16 8.17
B C
D
所有结点都着上颜色为止.
B C
例如:结点排序:A,B,E,F,H,D,G,C A

图论偶图与匹配

图论偶图与匹配

由(2)可知G’的任一结点的次数或者是0，不然就是1 或2，因此G’的每个连通分支或者是由M’和M的边交替 出现构成的回路，或者是由M’和M的边交替出现构成 的交替路，由于G’中M’的边多于M的边，因此必有一 条交替路P始干M‘的边且终止子M’的边，这条交替路 的两个端点对M’是饱和点，对M则是非饱和点，因此 P是G的一条可M增广路。
证明 树至多有一个完美匹配
证明：
若树T存在两个互异的完美匹配M和M’ ，则 M ⊕ M ' ≠ φ, M这与T是树矛盾。
5.1.1证明 k-方体有完美匹配
证明： k-方体的顶点坐标为 ( x1 , x2 ,..., xk ), xk ∈ {0,1} 取顶点 ( x1 , x2 ,..., xk −1 , 0) 和顶点 ( x1 , x2 ,..., xk −1 ,1) 之间 的边的全体构成的集合为M,显然M中顶点均不相 邻，所以 M 是一个匹配， | M |= 2k−1 ， 且k-方体的 顶点数为 2k ，M中每一个顶点均是M饱和的，所以 M是k-方体的完美匹配。
V1={1,3} V2={2,4}?,
V1={1,3,4}?
定理 G=<V,E>是偶图 当且仅当它的所有回路的长度都是偶 数. 证明:必要性: 假设G是个以V1,V2为互补的结点子集的二 部图, 设任意长度为n的回路: vi0vi1vi2,…,vin-1vi0, 假设 vi0vi2vi4,…,vin-2∈V1, vi1vi3vi5,…,vin-1∈V2 , 可见n-1是奇数, 所以n是偶数. 充分性: 设G的每个回路长度均为偶数, a)设G是连通的. 定义结点集合: V1= {vi | vi和某个固定结点v之间的距离为偶数} V2=V- V1={vi | vi和某个固定结点v之间的距离为奇数} 下面证明E中任何边, 其端点分别属于V1和V2. (用反证法)假设有一条边(vi, vj)∈E, 使得vi∈V1 , vj∈V1

对偶公式离散数学

对偶公式离散数学

对偶公式离散数学对偶公式是离散数学中的一种重要概念，它与图形的对称性有关，可以帮助我们更好地理解图形的结构特征和性质。

在本文中，我将讨论对偶公式的定义、证明、应用等方面，以帮助读者更好地理解这一概念。

对偶公式的定义对偶公式是指将一个平面图形的所有面和所有点互换得到的另一个平面图形，两个图形互为对偶关系。

具体来说，对于一个给定的平面图形G=(V，E)，我们可以定义它的对偶图G某=(V某，E某)，使得G和G某满足以下两个条件：1.G和G某的所有面和所有点一一对应。

2.对于G中的任意两个面，它们相邻当且仅当它们对应的点在G某中相邻；对于G某中的任意两个面，它们相邻当且仅当它们对应的点在G中相邻。

对偶公式的证明对于平面图形G=(V，E)，我们可以通过以下步骤来证明它的对偶图G 某=(V某，E某)存在：1.根据欧拉公式，我们有：，V，-，E，+，F，=2，其中，V，E，F，分别表示G中的点数、边数和面数。

2.我们将G中的每一个面向外“翻面”，得到一个新图形G'，它的每个面都是由原来的面与周围的边所围成的一块区域。

3.我们将G'中的每个交点都插入一个新的点，得到一个新图形H。

4.我们将H中每个面都向外“翻面”，得到一个新图形H'，它的每个面都是由原来的面与周围的点所围成的一块区域。

5.我们可以发现，H'中的每个面都对应着G中的一个点，且H'中的每个点都对应着G中的一个面。

因此，我们可以定义G某=(V某，E某)，其中V某为H'中的点集，E某为H'中的边集，且G某为G的对偶图。

通过上述证明，我们可以看出，对偶公式的存在并不依赖于G是否为平面图形，而只与G中的面、点、边之间的关系有关。

对偶公式的应用对偶公式在离散数学中有着广泛的应用，包括图论、拓扑学、计算几何等领域。

以下是一些典型的应用场景：1. 图论中常常使用对偶公式来证明定理或推导算法。

例如，通过对偶公式可以证明Planar Graph的最大独立集大小小于等于4/3 某最小顶点覆盖大小。

偶图及匹配

偶图及匹配

例如: a与e之间的最短路：ace，afe.
d(a,e)=2, d(a,h)=
6
集合论 与图论
偶图的判别定理
定理1 图G为偶图的充分必要条件是它的所有圈的长度 都是偶数.
证: 必要性
设P=u1u2u3...um-1umu1是G的一个长为m的圈。 因为G=(V, E)是一个偶图，则V存在一个二划分 {V1,V2}，对于任意{u,v}E，uV1，vV2， 的在圈P中，若设u1V1，那么所有圈上奇数下标
2个问题最终都抽象成偶图的完全匹配是否存在
的问题！
14
集合论 与图论
Hall定理（相异性条件）
许多问题提出了偶图的完全匹配的存在性问题.
定理3(Hall定理, 1935年) 设G=(V1∪V2，E)是一个 偶图，|V1|≤|V2|. G中存在从V1到V2的完全匹配 充分必要条件是V1中任意k个顶点(k=1, 2, …, |V1|) 至少与V2中的k个顶点相连接.
对这个问题，若把姑娘和小伙
子用点来表示，若某位姑娘能
接受某个小伙子，则在相应点
间连一条线，则可以得到一个
无向图G.
2
集合论 与图论
工作安排问题
工作安排问题：一个车间有m个工人和n件不同的工 作，每件工作只需一位工人干，而每位工人仅能熟 练地干其中的几件工作. 问在什么条件下车间主任 能为每位工人分配一件他能胜任的工作呢？
称Y为G的一个匹配. (显然，若Y是图G的一个匹配，则任意的v∈V，
v至多与Y 中的一条边关联.)
(3)设Y是图G的一个匹配，若对G的任一匹配Y ´， 恒有|Y ´|≤|Y |，则称Y是图G的一个最大匹配.
11
集合论 与图论
匹配
定义4 设G=(V,E)是一个偶图且V=V1∪V2，对 任意x∈E，x是连接V1的一个顶点与V2的一个顶 点的边，则若存在一个 匹配Y使得

偶图范畴的规范描述

偶图范畴的规范描述

偶图范畴的规范描述
在计算机科学中，偶图范畴是一种通用模型，用于抽象地表达和描述事件和条件之间的关系。

它是一种独特的、分割的数学结构，由两个或多个有限集合组成，它们之间的关系可以表示成一组有向边的集合，这组有向边的集合可以详细描述事件和条件之间的关系。

偶图范畴有很多应用。

它可以用来表示语言、社会和文化间的关系，也可以用来抽象地表达和描述系统中复杂的事件和条件之间的关系。

例如，偶图范畴可以用来分析社会政策和多样性的关系。

此外，它也可以用来分析科学和研究中的问题，以及一些复杂的组织结构。

偶图范畴由三个基本要素组成：一个有限的、非空的集合G，一个集合F，以及一组映射的关系R。

G集是一个有限的、非空的集合，它提供了一个定义范围。

F集则提供了一组元素，它们可以用来描述对象间的关系。

最后，R集提供了一组映射关系，它们可以用来描述一组元素之间的关系，以及它们与其他元素的关系。

偶图范畴的主要性质有三种：闭合性、可靠性和可视性。

闭合性表示偶图范畴中的元素可以彼此之间建立关联。

可靠性表示偶图范畴中的元素和关系是可靠的，具有良好的可重复性。

最后，可视性表示偶图范畴中的元素和关系可以以图形形式表示，以便于研究者可以更好地理解并分析其构造和性质。

因此，偶图范畴是一种十分有用的模型，它可以用来抽象地表达和描述各种不同类型的事件和条件之间的关系。

它具有易于使用、可靠性高、可视性强等优点，因此，它可以被广泛应用于不同的领域，
比如语言学、社会学、文化学和社会政策研究等。

因此，偶图范畴的规范描述对于更好地理解、分析和发现各种事件和条件之间的关系具有重要意义。

完全偶图的定向图

山东科学ＳＨＡＮＤＯＮＧＳＣＩＥＮＣＥ第２６卷　第３期　２０１３年６月出版Ｖｏｌ．２６Ｎｏ．３Ｊｕｎ．２０１３收稿日期：２０１２ １２ １５基金项目：国家自然科学基金（６１０７０２２９）；教育部博士点基金（博导类）（２０１１１４０１１１０００５）作者简介：张雪飞（１９８９－），女，硕士研究生，研究方向为图论及其应用。

通讯作者，王世英（１９６１－），男，博士，教授，博士生导师。

Ｅｍａｉｌ：ｓｈｉｙｉｎｇ＠ｓｘｕ．ｅｄｕ．ｃｎＤＯＩ：１０．３９７６／ｊ．ｉｓｓｎ．１００２－４０２６．２０１３．０３．００１完全偶图的定向图张雪飞，王世英（山西大学数学科学学院，山西太原０３０００６）摘要：完全偶图是具有二分类（Ｘ，Ｙ）的简单偶图，其中Ｘ的每个顶点与Ｙ的每个顶点相连，若｜Ｘ｜＝ｍ，｜Ｙ｜＝ｎ，则这样的图记为Ｋｍ，ｎ。

本文主要研究了Ｋｎ，ｎ的定向图。

证明了如下结论：对于非负整数ａ和ｂ，若存在满足每个顶点的入度是ａ或者是ｂ的一个Ｋｎ，ｎ的定向图，则存在非负整数ｓ和ｔ满足方程ｓ＋ｔ＝２ｎ和ａｓ＋ｂｔ＝ｎ２。

进一步，对于满足特定条件的非负整数ａ，ｂ和ｎ，存在Ｋｎ，ｎ的定向图使得每个顶点的入度非ａ即ｂ。

关键词：二部图；定向；入度中图分类号：Ｏ１５７．６ 文献标识码：Ａ 文章编号：１００２ ４０２６（２０１３）０３ ０００１ ０４ＡｎｏｒｉｅｎｔｅｄｇｒａｐｈｏｆａｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈＺＨＡＮＧＸｕｅ ｆｅｉ，ＷＡＮＧＳｈｉ ｙｉｎｇ（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｈａｎｘｉＵｎｉｖｅｒｓｉｔｙ，Ｔａｉｙｕａｎ０３０００６，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ∶Ａｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｉｓａｓｉｍｐｌｅｂｉｐａｒｔｉｔｅｗｉｔｈｂｉｐａｒｔｉｔｉｏｎ（Ｘ，Ｙ）ｉｆｅａｃｈｖｅｒｔｅｘｉｎＸｉｓｃｏｎｎｅｃｔｅｄｗｉｔｈｅａｃｈｖｅｒｔｅｘｉｎＹ．ＡｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｉｓｄｅｎｏｔｅｄａｓＫｍ，ｎｉｆ｜Ｘ｜＝ｍａｎｄ｜Ｙ｜＝ｎ．ＴｈｉｓｐａｐｅｒａｄｄｒｅｓｓｅｓｔｈｅｏｒｉｅｎｔｅｄｇｒａｐｈｓｏｆＫｍ，ｎ，ａｎｄｐｒｏｖｅｓｔｈａｔｔｈｅｒｅｅｘｉｓｔｔｗｏｎｏｎ ｎｅｇａｔｉｖｅｉｎｔｅｇｅｒｓｓａｎｄｔｓａｔｉｓｆｙｉｎｇｔｈｅｅｑｕａｔｉｏｎｓｓ＋ｔ＝２ｎａｎｄａｓ＋ｂｔ＝ｎ２ｉｆｔｈｅｉｎ ｄｅｇｒｅｅｏｆｅａｃｈｖｅｒｔｅｘｉｎａｎｏｒｉｅｎｔｅｄｇｒａｐｈｏｆＫｎ，ｎｉｓａｏｒｂ（ａａｎｄｂａｒｅｔｗｏｎｏｎ ｎｅｇａｔｉｖｅｉｎｔｅｇｅｒｓ）．Ｍｏｒｅｏｖｅｒ，ｔｈｅｒｅｅｘｉｓｔｓａｎｏｒｉｅｎｔｅｄｇｒａｐｈｏｆＫｎ，ｎｔｈａｔｍａｋｅｓｔｈｅｉｎ ｄｅｇｒｅｅｏｆｅａｃｈｖｅｒｔｅｘｔｏｂｅｅｉｔｈｅｒａｏｒｂｆｏｒｔｈｅｎｏｎ ｎｅｇａｔｉｖｅｉｎｔｅｇｅｒｓａ，ｂａｎｄｎｓａｔｉｓｆｙｉｎｇｓｏｍｅｓｐｅｃｉａｌｃｏｎｄｉｔｉｏｎｓ．Ｋｅｙｗｏｒｄｓ∶ｂｉｐａｒｔｉｔｅｇｒａｐｈ；ｏｒｉｅｎｔａｔｉｏｎ；ｉｎ ｄｅｇｒｅｅ１　引言给定任意图Ｇ，对于它的每条边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图。

图论及其应用(16)

另一方面，对于X的任一非空子集S, 设E1与E2分别是与S 和N(S)关联的边集，显然有： E1 E2 即：
E1 k S E2 k N (S )
由Hall定理，存在由X到Y的匹配.又|X| = |Y|，所以G存在 完美匹配。 16
例2 (1) 证明：每个k方体都有完美匹配(k大于等于2) (2) 求K2n和Kn,n中不同的完美匹配的个数。 (1) 证明一：证明每个k方体都是k正则偶图。 事实上，由k方体的构造：k方体有2k个顶点，每个顶点可 以用长度为k的二进制码来表示，两个顶点连线当且仅当代 表两个顶点的二进制码只有一位坐标不同。 如果我们划分k方体的2k个顶点，把坐标之和为偶数的顶 点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点 也如此。所以k方体是偶图。 又不难知道k方体的每个顶点度数为k,所以k方体是k正则 偶图。
2
v k 2v 1k
显然，P中M中的边比非M中的边少一条。于是作新 的匹配M1,它当中的边由P中非M中边组成。M1中边比 M中多一条，这与M是G的最大匹配矛盾。 “充分性” 若不然，设M1是G的一个最大匹配，则|M1|>|M|。
6
令H = M1ΔM。 容易知道：G[H]的每个分支或者是由M1与M中边交 替组成的偶圈，或者是由M1与M中边交替组成的路。 在每个偶圈中，M1与M中边数相等；但因|M1|>|M|， 所以，至少有一条路P，其起点和终点都是M非饱和点， 于是，它是G的一条M可扩路。这与条件矛盾。 注：贝尔热定理给我们提供了扩充G的匹配的思路。 贝尔热(1926---2002) 法国著名数学家。他的《无限图 理论及其应用》(1958) 是继哥尼之后的图论历史上的第 二本图论专著。他不仅在图论领域做出了许多贡献，而 且四处奔波传播图论，推动了图论的普及和发展。

对偶原理在几何中的应用

对偶原理在几何中的应用1. 什么是对偶原理对偶原理是一种广泛应用于数学和逻辑推理的原理。

它通过交换命题中的主语与谓语，可以得到另一个等价的命题。

在几何中，对偶原理可以用来描述平面上的点和线之间的关系。

通过对图形的对偶操作，可以得到一个与原始图形相对应的对偶图形，这种对偶图形与原始图形具有一定的对应关系，且具有相似的性质和结构。

2. 对偶原理的基本规则对于几何中的对偶操作，有以下基本规则：•点的对偶：平面上任意一个点都对应着一条直线，这条直线是过这个点的所有直线的对偶。

•直线的对偶：平面上任意一条直线都对应着一个点，这个点是包含这条直线的所有点集合的对偶。

•包含关系的对偶：如果一条直线包含一个点，那么这个点的对偶是包含直线的所有点的对偶。

同样，如果一个点被一条直线所包含，那么这个直线的对偶是包含这个点的所有直线的对偶。

通过上述对偶规则，我们可以在平面几何中进行对偶操作，得到与原始图形相对应的对偶图形。

3. 对偶原理在几何中的应用对偶原理在几何中有许多应用。

下面将介绍其中几个主要的应用：3.1 平行关系的对偶在平面几何中，两个平行线之间的关系可以通过对偶原理进行描述。

对于两条平行线l和m，它们之间的对偶关系是l包含m的所有点的对偶等于m包含l的所有直线的对偶。

也就是说，如果一条直线包含了两个平行线被包含的所有点，那么这条直线的对偶就是包含这两条平行线的所有直线的对偶。

3.2 垂直关系的对偶对于平面上的两条垂直线，它们之间的对偶关系是一条直线包含另一条直线的对偶等于另一条直线包含一条直线的对偶。

这就是说，如果一条直线包含了两条垂直线中的一条，那么这条直线的对偶就是包含另一条直线的对偶。

3.3 垂直平分线和角平分线的对偶关系在平面几何中，垂直平分线和角平分线有着特殊的对偶关系。

对于一个角的垂直平分线，它的对偶是这个角的角平分线。

同样，对于一个角的角平分线，它的对偶是这个角的垂直平分线。

3.4 定理的对偶在几何中，对偶原理还可以应用于证明定理。

图论


定理5 若|V(G)|≧3,则G是块，当且仅当G无环且任意两顶点位于 同一圈上。
k (G )点 (G )边 (G ) （取等条件） n 当 (G ) 时， (G ) (G ) 2
1 x 2 3 5 (10 x) 2 12
13:27:10
18
定义 无圈图称为森林。
注：(1) 树与森林都是简单图;
(2) 树与森林都是偶图。
(3) 在一棵树中，度数为1的顶点称为树叶，度数大于1 的顶点称为分支点。
例 画出所有不同构的6阶树。 解 按树中存在的最长路进行枚举。
13:27:10
11
定义3 如果在一个n个点的完全 l 部图G中有：
n kl r , 0 r l
V1 V2 Vr k 1 Vr 1 Vr 2 Vl k
则称G为n阶完全 l 几乎等部图，记为T l, n |V1| = |V2| = … = |Vl | 的完全 l 几乎等部图称为完 全 l 等部图。 定理1： 连通偶图的2部划分是唯一的。 证明 设连通偶图G的2部划分为V1∪V2 =V 。
9
(2) 若G是连通的，对于i ≠j , vi和vj间距离是使An的 aij (n)≠0的最小整数。
2、图的关联矩阵
(1) 若G是(n, m) 图。定义l , vi与e j关联的次数(0,1,或2(环）) 例如：
e1 v1 e5 e6 v4 e4 v3 v2 e2 e7 e3
1 1 M (G ) 0 0
1 1 0 0
0 1 1 0
0 0 1 1
1 0 0 1
0 0 0 2
1 0 1 0
10
13:27:10 2) 关联矩阵的每列和为2；每行的和为对应顶点度数；
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

A
6
偶图的最大匹配
Edmonds于1965年提出了解决偶图的最大匹配的匈牙利算法：
(1) 从 G中 取 一 个 初 始 匹 配 M 。
(2) 若X中的顶皆为M中边的端点，止，M 即为完
备 匹 配 ； 否 则 ， 取 X 中 不 与 M 中 边 关 联 的 顶 u， 记
S {u},T 。
(3) 若 P S T， 止 ， 无 完 备 匹 配 ， 否 则 ， 取
修改顶标的方法，使新的相等子图的最大匹配逐渐
扩大，最后出现相等子图的完备匹配。 这就是KM算
法。
A
11
KM算法
(1) 选 定 初 始 可 行 顶 标 l， 在 G l上 选 取 一 个 初 始 匹 配 M 。
( 2 ) 若 V1中 的 顶 皆 为 M 中 边 的 端 点 ， 止 ， M 即 为 最 佳 匹 配 ；
偶图的算法及应用
南京师范大学附属中学 孙方成
A
1
目录
匹配的概念 偶图的定义和判定 偶图的最大匹配 偶图的最小覆盖问题 偶图的最佳匹配问题 小结
A
2
匹配的概念(1)
定 义 1 设 图 GVG,EG， 而 M是 EG的 一 个
子 集 ， 如 果 M中 的 任 两 条 边 均 不 邻 接 ， 则 称 M是 G的 一 个 匹 配 。 M中 的 一 条 边 的 两 个 端 点 叫 做 在 M下 是 配 对 的 。
否
则
，
取
G
中
l
不
与
M
中
边
关联的源自顶u，记S
{u},T
。
(3) 若 P S T , 转 (4 )； 若 P S T ， 取
al
m in
xS , yT
l x l y w xy
l v al,v S，
l
v
l
v
al
,
v
T
，
l
v
,
其它。
l
l, G l
G
l
。
(4) 选 P S T 中 的 一 点 y， 若 y是 M 中 边 的 端 点 ， 且 yz M ，
设图GVG,EG，VG被分成两个非空的
互补顶点子集X和Y，若图G的一个匹配MEG能饱
和X中的每个顶点，换言之，X中的全部顶点和Y中的
一个子集的顶点之间确定一个一一对应关系，则称M
是图G的一个完备匹配。
A
4
偶图的定义
定义2 设图G(V,E)，若能把V分成两个集合V1和 V2，使得E中的每条边的两个端点，一个在V1中，另 一个在V2中，这样的图称为偶图，也叫二分图，或 是二部图。偶图也可表示为G(V1,V2;E)。
则S S
{z},T T
{
y }，
转
( 3 )；
否
则
，
取
G
中
l
M
可
增
广
路
径 R u , y ， 令 M M E ( R )，A 转 ( 2 )。
12
一个例题
某公司有工作人员x1,x2,…,xn ，他们去 做工作y1,y2,…,yn ，每个人都能做其中的几 项工作，并且对每一项工作都有一个固定 的效率。问能否找到一种合适的工作分配 方案，使得总的效率最高。要求一个人只 能参与一项工作，同时一项工作也必须由 一个人独立完成。不要求所有的人都有工 作。
对于顶点集V V1，用PV表示V2中所有和V相
连的顶点的集合。
定 义 3 如 果 偶 图 G 的 互 补 结 点 子 集 V 1 中 的 每 一 结 点 都 与 V 2 中 的 所 有 结 点 邻 接 ， 则 称 G 为 完 全 偶 图 。
A
5
偶图的判定
定 理 1 当 且 仅 当 无 向 图 G 的 每 一 个 回 路 的 次 数 均 为 偶 数 时 ， G 才 是 一 个 偶 图 。 如 果 无 回 路 ， 相 当 于 任 一 回 路 的 次 数 为 0,0视 为 偶 数 。
A
10
KM算法前的准备
在介绍求最佳匹配的KM算法前，首先介绍一些 相关的概念：
定义 5 映射l:VGR满足xV1，yV2，成立 lxlywxy，则称 lv是偶图 G的可行顶标；令
El xy|xyEG,lxlywxy
称以El为边集的生成子图为“相等子图”，记做Gl。
可以证明，Gl的完备匹配即为G的最佳匹配。 以此为基础，1955年Kuhn，1957年Munkres给出
但是，如果问题可以抽象成偶图的最小覆 盖问题，结局就不一样了。由于偶图的特殊性， 偶图的最小覆盖问题存在多项式算法。
A
8
最大匹配与最小覆盖的关系
在证明这个定理的过程中，要用到Hall婚姻定理： 设 G是 一 个 偶 图 ， 顶 集 划 分 成 V1和 V2， G 中 存 在
对 于 V1的 完 备 匹 配 的 充 要 条 件 是 ， 对 于 一 切 SV1，
V2y1,y2,...,yn， 权 wxiyj 0。 如 果 有 一 完 备 匹 配 M，
对 所 有 完 备 匹 配 M， 都 有 WMWM， 则 称 M为 偶 图
G的 最 佳 匹 配 。
由于引入了权，所以最佳匹配不能直接套用最大匹 配算法进行求解。同时，由于对最佳匹配的定义是建 立在完全加权偶图的基础上的，对于不完全图，可以 通过引入权为0（或是其他不影响最终结果的值），使 得偶图称为完全偶图，从而使用最佳匹配算法来解决。
都 有 SPS。
1931年König给出最大匹配与最小覆盖的关系定理如下：
在 偶 图 G 中 ， 若 M *是 最 大 匹 配 ， K *是 最 小 覆 盖 集 ， 则 M *＝ K *。
A
9
偶图的最佳匹配问题
定 义 4 GV1,V2;E是 加 权 完 全 偶 图 ， V1x1,x2,...,xn，
y P S T。
(4) 若 y是 M 中 边 的 端 点 ， 设 yz M ， 令
S S {z}, T T { y}， 转 (3)； 否 则 ， 取 可 增 广
路 径 R u , y ， 令 M M E ( R )， 转 (2)。
A
7
偶图的最小覆盖问题
一般图的最小覆盖问题是一个已被证明的 NPC问题。换一句话说，一般图的最小覆盖问 题，是没有有效算法的图论模型。所以，将一 个实际问题抽象成最小覆盖问题，是没有任何 意义和价值的。
若 匹 配 M 中 的 某 条 边 与 定 点 v 关 联 ， 则 称 M 饱 和 顶 点 v ， 并 称 v 是 M 饱 和 的 。
A
3
匹配的概念(2)
设 M是 图 G的 一 个 匹 配 ， 若 G中 存 在 一 条 基 本 路 径 R， 路 径 的 边 是 由 属 于 M的 匹 配 边 和 不 属 于 M的 非 匹 配 边 交 替 出 现 组 成 ， 则 称 R为 交 替 路 。 若 R的 两 个 端 点 都 是 M 的 非 饱 和 点 ， 则 称 这 条 交 替 路 为 可 增 广 路 。