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

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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。