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

题目

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

在这里插入图片描述

知识点

关于匈牙利算法:

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

相关推荐

  1. 软件项目管理---胡乱复习

    2023-12-30 15:08:05       49 阅读
  2. 二分 染色法 + 匈牙利算法

    2023-12-30 15:08:05       49 阅读
  3. 算法设计与分析(期末复习4完结

    2023-12-30 15:08:05       20 阅读
  4. 算法设计与分析(期末复习3)

    2023-12-30 15:08:05       26 阅读
  5. 及其应用的一些论断---选择题

    2023-12-30 15:08:05       52 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-30 15:08:05       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-30 15:08:05       100 阅读
  3. 在Django里面运行非项目文件

    2023-12-30 15:08:05       82 阅读
  4. Python语言-面向对象

    2023-12-30 15:08:05       91 阅读

热门阅读

  1. AJAX:整理1: 了解AJAX的相关知识

    2023-12-30 15:08:05       59 阅读
  2. Vue3.2 自定义指令详解与实战

    2023-12-30 15:08:05       63 阅读
  3. 猴子摘香蕉python

    2023-12-30 15:08:05       59 阅读
  4. 80 BFS和DFS两种方式解岛屿数量

    2023-12-30 15:08:05       59 阅读
  5. HTML5简介与基础骨架

    2023-12-30 15:08:05       61 阅读
  6. numpy数组追加元素

    2023-12-30 15:08:05       61 阅读
  7. Linux 命令 ifconfig 全面解析!

    2023-12-30 15:08:05       88 阅读
  8. git、gitee、github、gitlab 区别以及功能

    2023-12-30 15:08:05       69 阅读
  9. 一些与漏洞相关的面试题

    2023-12-30 15:08:05       47 阅读
  10. 服务器故障重启可以解决大部分问题

    2023-12-30 15:08:05       58 阅读
  11. 81 使用DFS和BFS解机器人的运动范围

    2023-12-30 15:08:05       60 阅读
  12. U-net

    2023-12-30 15:08:05       66 阅读
  13. 力扣热题100道-普通数组篇

    2023-12-30 15:08:05       49 阅读
  14. mysql5.7 数据库主从同步实现

    2023-12-30 15:08:05       55 阅读