第七部分图论方法(356KB).pptVIP

* * * * * * * * * * * * * * * 5.人员分配问题 6.稳定匹配问题 假设有一百个男人和一百个女人, 每个男人都凭自己好恶给每个女人打分, 我最爱a, 其次爱b, 再次爱c(假定没有相同的)... 每个女人也同样给每个男人打分. 然后就是求婚过程.直到最后大家都订了婚, 便一起结婚.  6.稳定匹配问题 设简单偶图G=(X,Y,E)中，男孩集X，女孩集Y，每边xy表示男孩x与女孩y彼此认识。今假设每个男孩x对他所认识的所有女孩有一个倾向度排序，每个女孩y对他所认识的所有男孩也有一个倾向度排序，对G上任意给定的一个倾向度分派，称G的一个匹配M为稳定匹配，如果对G中任一条非M边xy,以下两个条件至少有一个成立： M中存在这样一条边xy’（即x是M饱和的），使x倾向于y’胜过y； M中存在这样一条边x’y（即y是M饱和的），使y倾向于x’胜过x； 6.稳定匹配问题 数学上可以证明:在任给定的一个倾向度分派下，任一偶图中，都可找到一稳定匹配，且为一X－最优稳定匹配M*，即对G中的任一稳定匹配M及任一顶点x ? X，若xy ? M，则存在xy* ? M*，使y=y*；或x倾向于y*胜过y。 6.稳定匹配问题 第一, 这个过程会中止, 也就是说, 总有大家都订了婚的一天,不可能无限循环. 第二, 中止后所有的婚姻是稳定婚姻. 所谓不稳定婚姻是说, 比如说有两对夫妇M1, F1和M2, F2, M1的老婆是F1, 但他更爱F2;而F2的老公虽说是M2. 但她更爱M1(注意是更爱,不是最爱), 这样的婚姻就是不稳定婚姻,因为M1和F2理应结合, 他们现在各自的婚姻都是错误. 我们能证明的是, 通过上面那个求婚过程, 所有的婚姻都是稳定的, 没有人犯错误. 7.竞赛图 几支球队参加单循环比赛，各队两两交锋，每场比赛无平局，必分输赢。如何排列各队的名次，成为比赛组织者和各参赛队关心的问题。 7.竞赛图 2个队相应的竞赛图可归纳为一种. 3个顶点的竞赛图可归为两种情况. 7.竞赛图 4个顶点的竞赛图 7.竞赛图 对于任何一对顶点，存在两条有向路径，使两顶点可以相互连通，这种有向图称为双向连通的。 令表示第i个队的得分，则称n维向量S=(s1,s2,…,s n)T为得分向量. S=Ae, e=(1,1, …,1)T S(k)=AS(k-1)=Ake, k=1,2, … * * * * * * * * * * * * * * * * * * * * * * * 第七部分 图论方法 第十二章 图论方法 1. 图的基本概念 图是一个有序对V，E，V是结点集，E是边集； 无向边，与无序结点对(v, u)相关联的边； 有向边，与有序结点对v, u相关联的边； 无向图，每条边都是无向边的图； 有向图，每条边都是有向边的图. 图的基本概念 混合图，既有有向边，也有无向边的图. 平凡图，仅有一个结点的图； 零图，边集为空集的图V, ?，即仅有结点的图. 自回路(环)，关联于同一个结点的边. 无向平行边，联结相同两个结点的多于1条的无向边； 有向平行边，联结两个结点之间的多于1条且方向相同的有向边； 简单图，不含平行边和自回路的图. 图的基本概念 在有向图D＝V,E中，以v(?V)为起点的边之条数为出度deg＋(v)；以v(?V)为终点的边之条数为入度deg－(v). 在无向图G＝V,E中，与结点v(?V)关联的边数，即为结点度数deg(v)或d(v)；在有向图中，结点v的出度和入度之和为度数. 最大度数，?(G)＝max{deg(v)?v?V}；最小度数，?(G)=min{deg(v)?v?V} 图的基本概念 有n个结点的且每对结点都有边相连的无向简单图，称为无向完全图；有n个结点的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图。 设G＝V,E, V，E的子集V?,E?构成的图G?=V?,E?是图G的子图；若G??G且G??G，(V??V或E??E)，G?是G的真子图. 生成子图，设图G＝V,E, 若E??E, 则图V,E?是图V,E的生成子图，即结点与原图G相同的子图. 2. 哥尼斯堡七桥问题 2. 哥尼斯堡七桥问题 2. 哥尼斯堡七桥问题 2. 哥尼斯堡七桥问题 通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路； 通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路； 具有欧拉回路的图称为欧拉图； 具有欧拉通路但无欧拉回路的图称为半欧拉图。 2. 哥尼斯堡七桥问题 判别方法： (1) 无向连通图是欧拉图当且仅当其所有顶点的度数都是偶数； (2) 无向连通图是半欧拉图当且仅当其奇点数为2； 2. 哥尼斯堡七桥问题 Fleury算法： 任取v0∈V(G)，令P0=