文档介绍:维普资讯
鲁 东 大 学 学 报 自然 科 学 版
,:—
二 部 图最 和� 的� 个邻接点 ����≤ � ≤ � ��,则 ��就 是 ��的 匹配 ,�
诱 导子 图都 是零 图 ,则 称 �为二部 图或偶 图 .� ��������: ��.否则 ,�������������。为 ��的�
二部 图 �最 大 匹配 算 法 的核 心 思 想是 在 一� 邻接点�,��������:��.���� �������,���力 ��
条边 的两个邻 接 点 中,避 免 度 数小 的顶 点 因度 数� �.从 �中删 除所有与 ��和 ��邻接 的非 匹配边 ,相�
大的顶 点 已经产 生 匹 配 而失 配 ,每 次 都 是 度数 小� 应邻接 点的度数减 �,转 ����.��� 算 法结束 .�
的顶 点优 先 产 生 匹配 .具 体方 法 是 ,如果 � 中存� 例 如 ,图 �所 示 的二部 图 ��,� � ���,��,��,�
在度 数不 为零 的顶 点 ,则 从 �,中选择 一个 度数 最� ��,��,���,� � ���,���,���,���,���,����,��� ��,�
小 的顶点�,再从� 的邻 接点 中选 择 度数最小 的顶�
�,�,�,�,��,��: ��,�,�,�,�,��.二 部 图 ��最�
点 �作 为� 的匹配 ,从 �中删 除所 有与�和 �邻接�
大匹配 的求解 过程 如下 .�
的全 部非 匹配 边 ,被 删 除边 的两 邻 接点 度 数 均减�
从 ��中选择 �����,它 对应 �。的度 ,因其 度�
�;从� 中删 除�顶点 ,从� 中删 除 �顶点 .重复上�
数 为 �,直 接形成 ��的匹 配 ,��������:� �.从 ���
述 过程 ,直到� 为空或� 中顶点 的度数 全 为零 时�