下载文档原格式
浅谈稳定完备婚姻的算法及推广话说在1962年，两个数学家David Gale 和Lloyd Shapely 提出了下面的问题：给定若干个男生和同样多的女生，他们每个人都对所有的异性有一个心理的偏好次序。
是否存在一种男女配对组合构成一种稳定的组合关系？这里稳定组合的意思是说，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。
（可以理解，这样的异性太容易红杏出墙了，所以是某种不稳定因素。
）进一步的问题是，在已知每个人对异性的偏好顺序的情况下，怎样求出这种稳定组合方式（如果它存在的话）？你可以理解为这是数学家们替月老问的问题：给定一群孤男寡女，寻找一种牵红线的方式，以确保把红杏扼杀在摇篮里。
1、稳定完备婚姻上面这一问题被称为稳定婚姻问题。
它有很多种可能的解法。
为了让大家相信数学家不是真得如此无聊，我要指出它确确实实是一个地道的组合数学问题，有其特定的数学价值。
当然啦，它也有很多别的背景和应用，比如用来在若干个公司和应聘者之间进行招聘中介……但是数学家们怎么会放过如此八卦的一个名字呢？我们看下面的例题： 某社团中有n 位女士和m 位男士。
假定每位女士按照其对每位男士作为配偶的偏爱程度排名次，无并列。
也就是说，这种排列是纯顺序的，每位女士将这些男士的排列成顺序 1,2,3,… ,n ，类似的,每位男士也对这些女士排列成顺序1，2，3,…，n,我们知道，在这个社团里配对成完备婚姻的方式有n!种。
假定某种婚姻匹配中存在女士A 和 B 及两位男士a 和b,使得i) A 和a 结婚；ii) B 和b 结婚；iii) A 更偏爱b （名次更优先）而非a ；iv) B 更偏爱A 而非B 。
那么，我们认为该完备婚姻是不稳定的。
因为在这种假设下，A 和b 可能会背着别人相伴逃跑，他们都认为，与当前配偶相比每个都更偏爱自己的新伴侣。
如果完备婚姻不是不稳定的，我们则称其为稳定的完备婚姻。
2、稳定完备婚姻的算法2.1 建立模型用二分图来为这个问题建立数学模型。
1999年吉 林 工 业 大 学 自 然 科 学 学 报Vol.29第1期JOURNAL OF J IL IN UNIV ERSITY OF TECHNOLO GY (NATURAL SCIENCES )总第93期收稿日期:1998-07-06毕双艳,女,1944年9月生,副教授两类联图的优美性 毕双艳 唐永林 路 线 李松涛 (长春邮电学院计算机系) (吉林职业师范学院) (吉林工业大学理学院)摘 要 给出了两类联图P 1∨(P 1∨2P n )及st (n )∨T ,论证了这两类图都是优美图,由此推出一些有意义的结论。
关键词 简单图 优美图 联图中图分类号 O15719本文讨论的是简单无向图G (V ,E )。
V (G )和E (G )分别表示图G 的顶点集和边集,|E (G )|表示图G 的边数。
有关术语见文献〔1〕。
定义1〔1〕 对于一个图G (V ,E ),如果对每一个顶点v ∈V ,都存在一个非负整数θ(v )(称为顶点v 的标号),使满足(1)Πu ,v ∈V ,若u ≠v ,则θ(u )≠θ(v )(2)max {θ(v )|v ∈V }=|E |(3)Πe 1,e 2∈E ,若e 1≠e 2,则θ′(e 1)≠θ′(e 2)其中θ′(e )=|θ(u )-θ(v )|,e =uv ,则称G 为优美图(graceful graph )。
θ为G 的优美值(graceful value )或优美标号(graceful labeling )。
定义2〔2〕 设图G 1和G 2不相交,在G 1∪G 2中,把G 1的每一个顶点和G 2的每一个顶点连接起来所得到的图叫做G 1和G 2的联图(join graph ),记作G 1∨G 2。
关于联图的一些研究进展情况见文献〔2〕。
设P n 表示n (n 为自然数)个顶点的简单通路,P 1表示一个顶点的平凡图;把P 1上的顶点与P n 上每一个顶点都通过长度为2的通路连接起来而得到的图记作P 1∨2P n 。
完全图知识点总结一、完全图的基本概念完全图是图论中的一个重要概念，它是一种特殊的图，具有很多独特的性质和特点。
完全图由n个顶点组成，其中任意两个顶点之间都有一条边相连。
完全图通常用Kn来表示，其中n代表顶点的个数。
完全图是一种特殊的简单图，因为任意两个顶点之间都有边，所以在完全图中不存在孤立的顶点或者度为0的顶点。
二、完全图的性质1. 完全图的边数在完全图中，任意两个顶点之间都有边相连，因此完全图的边数可以通过组合数学的知识计算得到。
对于n个顶点的完全图Kn，它的边数可以表示为C(n, 2)，即n个顶点中任取两个顶点相连，共有C(n, 2)条边。
2. 完全图的度完全图中每个顶点的度都是相同的，为n-1。
这是因为在完全图中，任意两个顶点之间都有边相连，所以每个顶点都与其他所有的顶点相邻，因此它的度为n-1。
3. 完全图的邻接矩阵和度矩阵完全图的邻接矩阵是一个n×n的矩阵，其中第i行第j列的元素表示第i个顶点和第j个顶点之间是否有边相连。
在完全图中，邻接矩阵是一个对称矩阵，对角线元素为0，非对角线元素为1。
完全图的度矩阵是一个n×n的矩阵，其中对角线元素为每个顶点的度，非对角线元素为0。
4. 完全图的生成对于完全图Kn，可以使用不同的方法进行生成。
一种方法是从n个顶点开始，逐个添加边直到所有的顶点之间都有边相连。
另一种方法是从n个顶点开始，对于每一对顶点，都添加一条边相连。
5. 完全图的应用完全图在实际生活中有很多应用，例如通信网络中的数据传输、交通规划中的道路建设、社交网络中的人际关系等。
在这些应用中，完全图可以帮助分析网络的拓扑结构、寻找最短路径、评估网络的稳定性等。
三、完全图的相关问题1. 完全图的最大团和最大独立集在完全图中，由于任意两个顶点都相连，因此最大团的大小为n，即完全图本身就是一个最大团。
最大独立集的大小为1，即每个顶点都是一个独立集。
2. 完全图的哈密顿回路和欧拉回路在完全图中，哈密顿回路是指通过所有顶点恰好一次的回路，而欧拉回路是指通过所有边恰好一次的回路。
二分图：二分图是这样的一个图，它的顶点可以分为两个集合X和Y。
所有的边关联的两个顶点中，恰好一个属于集合X，一个属于集合Y。
二分图的匹配：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
二分图的最大匹配:二分图的所有匹配中包含边数最多的匹配称为图的最大匹配。
完美（完备）匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。
最佳匹配：如果边上带权的话，找出权和最大的匹配叫做求最佳匹配。
增广路径：也称增广轨或交错轨。
若P是图G中一条连通两个未匹配顶点的路径，并且属最大匹配边集M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广轨。
定义总是抽象的下面通过图来理解它。
图中的线段（2->3, 3->1, 1->4）便是上面所说的p路径，我们假定边（1,3）是以匹配的边，（2,3）（1,4）是未匹配的边，则边（4,1）边（1,3）和边（3,2）在路径p上交替的出现啦，那么p就是相对于M的一条增广轨，这样我们就可以用边1,4 和边2,3 来替换边1,3 那么以匹配的边集数量就可以加1,。
下面给出关于二分图最大匹配的三个定理1:最大匹配数+ 最大独立集= n + m2:二分图的最小覆盖数= 最大匹配数3:最小路径覆盖= 最大独立集最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。
最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。
最小路径覆盖是指一个不含圈的有向图G 中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P 中的某一条路径。
路径可以从任意结点开始和结束，且长度也为任意值，包括0.1求解二分图最大匹配的方法：●匈牙利算法（时间复杂度O(nm)）其思想是是通过不断的寻找增广轨实现最大匹配。
●转化为单位容量简单网络的最大流问题(本文不介绍)在二分图的基础上，加入源点s和汇点t，让s与每个X结点连一条边，每个Y结点和t连一条边，所有弧的容量为1。
⼆分图概念及性质 段段续续的看⼆分图已经有些时⽇了。
现在借着周末整理⼀下这么多天对⼆分图的掌握程度。
也好对⼆分图有个整体的认知。
另外，此⽂只针对与⼆分图的⼀些概念和性质，不涉及求最⼤匹配的算法。
好吧，切⼊正题： ⾸先我们抛开⼆分图严谨准确的定义，从⼀个感性的⾓度来认识⼀下什么是⼆分图。
所谓⼆分图，就是能够把图中的定点分成两个X，Y两部分；并且整个图的边只存在于X与Y之间。
就是说，X与Y的内部是不存在边的，否则的话就不是⼆分图了。
举个例⼦：如果把整个⼈类中的男⼈和⼥⼈看成顶点，⼈与⼈之间的恋爱关系（这⾥只讨论异性之间的正常恋爱，同性恋是不被承认的）为边来建⽴图模型的话。
那么这其实就是⼀个⼆分图，其中的男⼈为X部分，⼥⼈为Y部分。
好了，现在我们给出⼆分图严谨的科学定义： 假设图G=（V，E）是⼀个⽆向图，若顶点集 V 可以分解成两个互不相交的⼦集（A，B），并且图中的所有边（i，j）的端点 i，j 分别属于⼦集 A，B 中的元素，则称图 G 是⼀个⼆分图。
为了更好的叙述下⽂，先让我们清楚⼀个概念： 匹配：⽆公共点的边集合。
（形象点就是 X与Y之间的边的个数） 匹配数：边集中边的个数。
最⼤匹配：匹配数最⼤的匹配。
边独⽴集：指图中边集的⼀个⼦集，且该⼦集中的任意两条边之间没有公共点。
（对⽐匹配的概念我们发现，其实边独⽴集和匹配是⼀个概念） 最⼤边独⽴集：包含边数最多的边独⽴集。
（其实就是最⼤匹配，为了⽅便，以后统称最⼤匹配）图1如图1，如果<1,4>是⼀个合法匹配，那么<1,5>就不是⼀个合法的匹配，因为它们有公共点1 。
同样的如果<2,5>是⼀个合法的匹配，那么<2,6>和<3,5>就不是⼀个合法的匹配。
不难看出，其中最⼤匹配是边集：{1， 4， 5}，最⼤匹配数为3 。
独⽴集： 是指图的顶点集的⼀个⼦集，且该⼦集中的任意两个顶点之间不存在边。
