A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B and a cycle C in B is called conformal if B-V(C) has a perfect matching. We show that there do not exist two disjoint alternating paths that form a cross over a conformal cycle C in a brace B if and only if one can reduce B, by an application of a matching theoretic analogue of small clique sums, to a planar brace H in which C bounds a face. We then utilise this result and provide a polynomial time algorithm which solves the 2-linkage problem for alternating paths in bipartite graphs with perfect matchings.
翻译:双部分图B 如果连接在一起,且B中最多两个大小的每个匹配都包含在B和B的一个周期C的完美匹配中,如果B-V(C)有一个完美的匹配,则B和B的周期C就被称为匹配。我们证明,在牙套B中,不存在两个不相连的交替路径,在符合C的周期中形成十字交叉,如果而且只有在能够将B与一个小球形的相匹配的理论类比应用到一个圆形的平板支部H,从而将脸标定在C。我们然后利用这一结果,提供一种多元时间算法,用完美匹配的两部分图解交替路径的2个链接问题。