图论及其应用(匈牙利算法)---期末胡乱复习版

2023-12-29 21:27:13

题目

T1:从下图中给定的 M = {x1y4,x2y2,x3y1,x4y5},用 Hungariam算法【匈牙利算法】 求出图中的完美匹配,并写出步骤。

在这里插入图片描述

知识点

关于匈牙利算法:

  • 需要注意的是,匈牙利算法仅适用于二分图,并且能够找到完美匹配。
  • 什么是交替路?从一个未匹配点出发,依次经过非匹配边–匹配边–非匹配边…形成的路径。
  • 什么是增广路?从一个未匹配点出发,走交替路,若能到达另一个未匹配点,则这条交替路叫增广路。
  • 算法流程:【给出初试匹配—从非饱和点出发找增广路—边交换。】
    (1)任给初始匹配M【一些边的集合】。
    (2)若

文章来源:https://blog.csdn.net/weixin_45880844/article/details/135283058
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。