偶图的算法及应用

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

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

偶图范畴有很多应用。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

图和子图 图和简单图图 G = (V, E)V ---顶点集，ν---顶点数12ε E ---边集， ε---边数例。

左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。

真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。

不过今后对两者将经常不加以区别。

称 边 ad 与顶点 a (及d) 相关联。

也称 顶点 b(及 f) 与边 bf 相关联。

称顶点a 与e 相邻。

称有公共端点的一些边彼此相邻，例如p 与af 。

环（loop ，selfloop ）：如边 l 。

棱（link ）：如边ae 。

重边：如边p 及边q 。

简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。

一条边的端点：它的两个顶点。

记号：νε()(),()().G V G G E G ==。

习题1.1.1 若G 为简单图，则εν≤⎛⎝ ⎫⎭⎪2 。

1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。

同构在下图中， 图G 恒等于图H , 记为 G = H ⇔ VG)=V(H), E(G)=E(H)。

图G 同构于图F ⇔ V(G)与V(F), E(G)与E(F)之间 各 存在一一对应关系，且这二对应关系保持关联关系。

记为 G ≅F。

注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。

de f G = (V , E )yz w cG =(V , E )w cyz H =(V ’, E ’)’a ’c ’y ’e ’z ’F =(V ’’, E ’’)注 判定两个图是否同构是NP-hard 问题。

完全图(complete graph) Kn空图（empty g.） ⇔ E = ∅ 。

V’ ( ⊆ V) 为独立集 ⇔ V’中任二顶点都互不相邻。

偶图的算法及应用南京师范大学附属中学 孙方成【摘要】本文首先介绍了匹配这种无向图中特殊的关系，以及偶图这种特殊图的定义。

然后将两者结合起来，介绍了偶图的最大基数匹配和最佳匹配的有效算法。

同时通过给出有关偶图的最大匹配数和最小覆盖数间的数量关系，说明了和一般图相比，偶图所具有的独特优势。

【关键词】偶图 匹配 增广路 覆盖集 算法复杂度一、 前言偶图是一种特殊的图。

偶图的结点总是被分成两个互补的部分，这两部分常常用来分别表示两类不同的事物。

而两类事物间的最基本的关系，就是匹配的关系。

如果能根据具体的情况，将偶图和匹配结合起来，则可以在很大程度上打开思路，优化算法。

总之，偶图这种特殊的图，在程序设计中有着广泛的应用。

它的高效性有助于对某些复杂问题的较特殊情况，给出完美的解。

二、 匹配的概念定义1 设图()()(),G V G E G =，而M 是()E G 的一个子集，如果M 中的任两条边均不邻接，则称M 是G 的一个匹配。

M 中的一条边的两个端点叫做在M 下是配对的。

若匹配M 中的某条边与顶点v 关联，则称M 饱和顶点v ，并称v 是M 饱和的。

设M 是图G 的一个匹配，若G 中存在一条基本路径R ，路径的边是由属于M 的匹配边和不属于M 的非匹配边交替出现组成，则称R 为交替路。

若R 的两个端点都是M 的非饱和点，则称这条交替路为可增广路。

设图()()(),G V G E G =，()V G 被分成两个非空的互补顶点子集X 和Y ，若图G 的一个匹配()M E G ⊆能饱和X 中的每个顶点，换言之，X 中的全部顶点和Y 中的一个子集的顶点之间确定一个一一对应关系，则称M 是图G 的一个完备匹配。

在大多数情况下，如果直接从可增广路的角度求一个图的最大（最佳）匹配，其算法效率较低。

所以，对于一般图的匹配算法同时还要涉及到花苞1的定义即处理。

但由于本文主要考虑偶图的匹配问题，所以对这些内容不进行展开。

三、 偶图的定义和判定定义2 设图),(E V G =，若能把V 分成两个集合1V 和2V ，使得E 中的每条边的两个端点，一个在1V 中，另一个在2V 中，这样的图称为偶图，也叫二分图，或是二部图。

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

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

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

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

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

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

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