增广轨
(数学术语)
增广轨的定义(也称增广路或交错轨): 若P是图G中一条连通两个未匹配顶点的路径,并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广轨(举例来说,有A、B集合,增广路由A中一个点通向B中一个点,再由B中这个点通向A中一个点……交替进行)。由增广轨的定义可以推出下述三个结论: 1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M。 2-不断寻找增广轨可以得到一个更大的匹配M’,直到找不到更多的增广轨。 3-M为G的最大匹配当且仅当不存在M的增广轨。
用户数据
参数表
继承树
构成树
关注人数:
0
技点进度:
0
/
0
题库进度:
0
/
0
技能进度:
0
/
关注级别:
取消关注
【参数模块正在开发当中】