Page 220 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

a(4，7)=42； a(5，6)=70；
[i，j，b]=find(a)；

data=[i’；j’；b’]；index=data(1：2，：)；
loop=max(size(a))-1；
result=[]；
while length(result)<loop

temp=min(data(3，：))；
flag=find(data(3，：)==temp)；

flag=flag(1)；
v1=index(1，flag)；v2=index(2，flag)；
if v1~=v2

result=[result，data(：，flag)]；
end
index(find(index==v2))=v1；

data(：，flag)=[]；
index(：，flag)=[]；
end
result

第五节 匹配问题的解决

定义 若 ， ， 无公共端点（i ≠ j ）则称 M 为图
G 中的一个对集；M 中的一条边的两个端点叫做在对集 M 中相配；M 中的端点
称为被 M 许配；G 中每个顶点皆被 M 许配时，M 称为完美对集；G 中已无使

的对集 M'，则 M 称为最大对集；若 G 中有一轨，其边交替地在对集
M 内外出现，则称此轨为 M 的交错轨，交错轨的起止顶点都未被许配时，此交

错轨称为可增广轨。
若把可增广轨上在 M 外的边纳入对集，把 M 内的边从对集中删除，则被许
配的顶点数增加 2，对集中的“对儿”增加一个。

210