县区工会网站建设方案icp备案域名购买

当前位置： 首页 > news >正文

县区工会网站建设方案,icp备案域名购买,郑州专业网站建设在哪里,创建站怎么上传网站怎么办学习不是为了竞争和战胜他人#xff0c;而是为了更好地了解自己和世界。 - 达赖喇嘛 文章目录 图的相关概念涂色问题基础涂色方法#xff08;贪婪算法#xff09;证明 二分图匹配问题应用#xff1a;稳定婚烟问题算法性质及其证明 图的相关概念 图的定义#xff1a;一组而是为了更好地了解自己和世界。 - 达赖喇嘛 文章目录 图的相关概念涂色问题基础涂色方法贪婪算法证明 二分图匹配问题应用稳定婚烟问题算法性质及其证明 图的相关概念 图的定义一组VE对。V一个点集的集合。E边集呈现形式为V上的一个关系。什么是关系 V的一个例子为{x1x2x3}E的一个例子为{x1x2x2x3}也可写成{x1-x2x2-x3}。 相邻点如果两个点之间有边那么这两个点就是相邻的。映射如果x1x2是E的一个元素那么E映射到x1E也映射到x2。度数边集映射到x1的次数称为x1的度数。环起点和终点都是同一个点的边称为环。重边两个起点和终点完全相同的边称为重边。简单图没有环或者重边的图称作简单图。 涂色问题 给定一个图如果最少能用K种颜色为图涂色使相邻点拥有不同颜色那么K称为该图的色度。 基础涂色方法贪婪算法 步骤 将点标号为x1x2…xn。将颜色标号为c1c2…cn。每次用标号最小的合法颜色涂标号最小的尚未上色的点。 易证使用这种算法如果图中度数最多的点有d度那么最多使用d1种颜色。 证明 可以用归纳法证明设Pn表示有n个点的图满足命题 基础步骤n1时d0用一种颜色P1T。归纳步骤假设PnT考虑有n1个点的图该图中的点最多拥有d度。若在该图中取走一个点那么剩下的n点图中的点也最多拥有d度且一定满足Pn。再加回该点即使该点拥有d度且相连的d个点颜色都不同该点也可以使用第d1种颜色因此n1点图的色度d 1Pn1T。□ 二分图 如果一个图可以分成左右两个集合集合内部的点都不相邻分属于两个集合的部分点有相邻关系那么这个图称为二分图。不难看出二分图色度为2。 匹配问题 匹配给定一个图这个图的一个所有点都有且只有1度的子图称作该图的一个匹配。例如
对于这个图{x1-x5x2-x8x3-x6x4-x7}是该图的一个匹配。注意{x1-x5}也是该图的一个匹配。 如果一个匹配包括原图的所有点那么这个匹配是一个完美匹配。对于带权图来说一个匹配的权重是匹配中所有边的权重之和。此时完美匹配需满足两个条件包括所有点且该匹配拥有最小权重。我们也称此时的完美匹配为最小权重匹配。 应用稳定婚烟问题 看下面的图假定A,B是男生C,D是女生。边的权重值越小代表该男生、女生越喜欢ta的该相邻点
我们可以看出A更喜欢DB更喜欢C…假定如果A和C结婚B和D结婚那么比起伴侣A和D都更喜欢对方那么他们可能发生出轨行为导致婚烟不稳定。反之如果A和D结婚B和C结婚那么婚烟是稳定的因为即使C更喜欢A但A更喜欢他的伴侣D因此他不愿意和C出轨。 那么对于一个带权图怎么找到它的稳定婚烟匹配呢 算法 首先明确一点只有二分图才有稳定婚烟匹配因此如果混入了gay或……那么不存在稳定婚烟匹配。另外男女生数量必须相同这点很好理解。我们可以通过一个称作TMA的算法找到一个图的一种稳定婚烟匹配。TMA步骤如下 每个男生去找他最喜欢的女生示爱。如果女生发现有多个男生来找她她查看自己的权重并找到她最喜欢的拒绝其他男生。注意这并不代表留下的这个男生就是她的最终伴侣。被拒绝的男生将这个女生从他的权重名单里划掉然后顺位去找下一个女生示爱。重复第二步和第三步直到每个女生面前有且只有一位男生示爱算法结束找到稳定婚烟匹配。 举个例子说明。假定对于每个男生和女生他们的权重名单如下这里跳过图阶段而直接抽象出信息最左边的是最喜欢的最右边的是最不喜欢的 男生按照权重名单去找相对应的女生。 在A面前有三个男生根据名单她留下5剩下的2 4两男生划掉A分别去找下一个女生 C查看名单留下41划掉C去找B B查看名单留下21划掉B去找E
至此所有女生面前有且仅有一个男生算法结束。 经过检验感兴趣的读者可以自行尝试一下这个算法是有效的。接下来我们对其性质进行证明。 性质及其证明 性质1这个算法会在不多于n21个周期内结束。这个性质很好理解n个男生n个女生男生的名单最多划n2次除了第一个回合外每个回合至少有一个男生的名单会被划因此算法最多执行n21个周期。性质2如果一个女生拒绝了一个男生那么从她拒绝的那一天开始到算法结束她身边一定有一个她更喜欢的示爱者。这个性质可以用归纳法来形式化的证明但直观上也很好理解假若女孩A拒绝男孩3在某一天那么当天她留下的那个一定是更喜欢的未来的某一天她即使拒绝了之前留下的也说明有更更喜欢的示爱者来了根据传递性该性质正确。性质3每个人经过该算法的匹配后都有一个伴侣这点不需证明。性质4TMA产生一个稳定婚烟匹配。如果一个男生和女生没能结婚那么有两种可能女生拒绝了男生根据性质2女生一定更喜欢现在的伴侣不会产生出轨男生没来找过女生此时男生一定更喜欢他现在的伴侣因此也不会产生出轨。性质5证明较复杂参考知乎文章稳定婚烟问题TMA算法中男生能找到保证稳定婚烟下的最佳情侣。用算法进行的轮数来归纳证明 首先定义如果A和B是合适的那么存在一种稳定婚烟匹配中A和B配对。 基础步骤利用归谬法证明在第1轮结束时没有男生被合适的女生拒绝即如果一个男生被女生拒绝那么他们一定是不合适的。设女生A在第1轮拒绝1而选择了2那么假设在某一个稳定匹配中A和1结婚那么A更喜欢2而2最喜欢A所以会发生出轨则这个婚烟是不稳定的出现矛盾假设不成立证明完成。 归纳步骤如果在第n轮结束时依然没有男生被合适的女生拒绝则证明在n1轮时依然不会有。设在第n1轮女生A拒绝1而选择了2假设A和1在某个稳定匹配中结婚那么A更喜欢2对2来说在TMA算法中拒绝他的女生都是不合适的即不可能在任何稳定匹配中出现2与她们结婚的情况因此在假想的稳定匹配中他的最终伴侣一定差于A那么2也更喜欢A所以发生出轨出现矛盾。因此一旦女生对男生合适那么她就不会拒绝这个男生又因为男生是按照他的喜好顺序求爱的因此最后找到的一定是他的稳定最佳情侣。□ 性质6TMA算法中女生总会找到稳定最差情侣。依然用归谬法证明假设存在一个稳定匹配该匹配中有一个女生G匹配到比TMA匹配中更差的情侣B’那么她更喜欢在TMA算法中匹配到的男生B对于B来说由于性质5他也一定更喜欢在TMA算法中匹配到的稳定最佳情侣G所以出现出轨产生矛盾命题得证。□ 我是霜_哀在算法之路上努力前行的一位萌新感谢你的阅读如果觉得好的话可以关注一下我会在将来带来更多更全面的知识讲解