کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427002 | 686420 | 2016 | 4 صفحه PDF | دانلود رایگان |
• We have presented an extension of Hall's theorem in partitioned bipartite graph G.
• We have proved a necessary and sufficient condition for the existence of specific matching in G.
• We have showed that this matching can be computed in polynomial time.
Let G=(X,Y,E)G=(X,Y,E) be a bipartite graph with bipartition X and Y and edge set E such that X is partitioned into a set of k pairwise disjoint subsets X1,X2,…,XkX1,X2,…,Xk. For any sequence n1,n2,…,nkn1,n2,…,nk of natural numbers with ni≤|Xi|ni≤|Xi| for all i, we prove a necessary and sufficient condition for the existence of a semi-perfect matching in G, a matching that includes, for each i , at least nini edges that are incident to vertices from XiXi. Clearly, this is equivalent to Hall's theorem in the case where ni=|Xi|ni=|Xi| for all i.
Journal: Information Processing Letters - Volume 116, Issue 11, November 2016, Pages 706–709