算法合集之《偶图的算法及应用》
偶图的算法及应用
偶图的算法及应用
南京师范大学附属中学 孙方成
【摘要】
本文首先介绍了匹配这种无向图中特殊的关系，以及偶图这种特殊图的定义。然后将两者结合起来，介绍了偶图的最大基数匹配和最佳匹配的有效算法。同时通过给出有关偶图的最大匹配数和最小覆盖数间的数量关系，说明了和一般图相比，偶图所具有的独特优势。
【关键词】
偶图 匹配 增广路 覆盖集 算法复杂度
一、 前言
偶图是一种特殊的图。偶图的结点总是被分成两个互补的部分，这两部分常常用来分别表示两类不同的事物。而两类事物间的最基本的关系，就是匹配的关系。如果能根据具体的情况，将偶图和匹配结合起来，则可以在很大程度上打开思路，优化算法。总之，偶图这种特殊的图，在程序设计中有着广泛的应用。它的高效性有助于对某些复杂问题的较特殊情况，给出完美的解。
二、 匹配的概念
定义1 设图G V G ,E G ，而M是E G 的一个子集，如果M中的任两条边均不邻接，则称M是G的一个匹配。M中的一条边的两个端点叫做在M下是配对的。
若匹配M中的某条边与顶点v关联，则称M饱和顶点v，并称v是M饱和的。
设M是图G的一个匹配，若G中存在一条基本路径R，路径的边是由属于M的匹配边和不属于M的非匹配边交替出现组成，则称R为交替路。若R的两个端点都是M的非饱和点，则称这条交替路为可增广路。
设图G V G ,E G ，V G 被分成两个非空的互补顶点子集X和Y，若图G的一个匹配M E G 能饱和X中的每个顶点，换言之，X中的全部顶点和Y中的一个子集的顶点之间确定一个一一对应关系，则称M是图G的一个完
你可能喜欢
- 算法竞赛
- 算法研究
- 动态规划
- 算法报告
- 算法题目
- 算法设计
- 算法代码
- 算法竞赛入门经典15页
- 算法竞赛入门经典笔记3页
- 算法竞赛入门经典各章习题答案15页
- 第二届SHU算法应用竞赛15页
- 算法竞赛入门经典第二章习题编程C#3页
- 算法与信心学竞赛部分习题提示和答案11页
- TERCOM算法研究11页
- 适合云计算平台的规划算法研究8页
- 硕士论文 WDM网络中组播传送的几种优化算法研究67页
- 一种基于密度的K_means算法研究4页
- 对排序算法的一点研究3页
- svm算法研究2页
- 第4章 动态规划53页
- 5 动态规划47页
- 动态规划技术11页
- 第6-7章 动态规划、动态规划应用45页
- 动态规划求解方法的Matlab实现及应用[1]7页
- 动态规划6页
- flooding算法报告2页
- 算法设计实验报告三2页
- 算法设计实验报告六2页
- 算法设计实验报告二2页
- 算法设计实验报告一2页
- 回溯算法的实验报告.doc6页
- 算法设计题目2页
- 算法案例--题目15页
- Java面试中遇到的一些经典算法题目2页
- JAVA经典算法题目26页
- 算法实训题目17页
- 算法分析复习题目及答案13页
- 算法分析与设计28页
- 经典算法设计方法大杂烩17页
- 第三章 程序的简单算法设计15页
- 计算机算法设计与分析实验指导书8页
- 算法设计与分析 实验报告11页
- 算法设计基础出的题目1页
- 免疫算法C代码4页
- java排序算法代码11页
- Dijkstra算法C代码4页
- 蚁群算法简单代码2页
- 常见算法代码总结4页
- C语言二分法查找算法代码2页
