Page 73 - Textos de Matemática Vol. 39

ALGORITHM FOR K-MATCHINGS IN BIPARTITE GRAPHS 63
in Ek := {e1,...,ek} ⊂ E such that Ek covers 2k vertices in G. That is, no two edges in Ek have a common vertex. It is straightforward to show that permk B(G) is the number of k-matching in G.
More generally, let B = [b ] ∈ Rm×n, R := [0, ∞) be an m×n nonnega- ij + +
tive matrix. We associate with B the following bipartite graph
G(B) = (V1(B) ∪ V2(B), E(B)). Identify V1(B), V2(B) with ⟨m⟩, ⟨n⟩ respec-
tively. Then for i ∈ ⟨m⟩,j ∈ ⟨n⟩ the edge (i,j) is in E(B) if and only if bij > 0.
Let Gw := (V1(B) ∪ V2(B),Ew(B)) be the weighted graph corresponding to
B. I.e., the weight of the edge (i,j) ∈ E(B) is bij > 0. Hence B(Gw), the
representation matrix of the weighted bipartite graph Gw, is equal to B. Let
M ∈ Mk(G(B)). Then (i,j)∈M bij is the weight of the matching M in Gw.
In particular, permk B is the total weight of weighted k-matchings of Gw. The
weighted matching polynomial corresponding to B ∈ Rm×n, or G induced by
B, is defined as:
Φ(x,B):=
k=0
Φ(x, B) can be viewed as the grand partition function for the monomer-dimer
model in statistical mechanics [6]. (See §3 for the case of a nonbipartite graph.) In particular, all roots of Φ(x, B) are negative.
Theorem 2.1. Let B ∈ Rm×n and k ∈ ⟨min(m, n)⟩. Let +
min(m,n)
k+0
perm Bxk, B∈Rm×n, perm B:=0.
B ∈ R(m+n−k)×(m+n−k) be the following 2 × 2 block matrix
k+
Bk := B
1m,m−k , where 1p,q is a p × q matrix whose all entries are 0
1n−k,n equal to 1. Then
(2.1)
perm B= permBk
k (m−k)!(n−k)!
.
+w
Proof. For simplicity of the exposition we assume that k < min(m,n). (In the case that k = min(m, n) then Bk has one of the following block structure: 1 × 1, 1 × 2, 2 × 1.) Let Gw = (V1(B) ∪ V2(B),Ew(B)),Gw,k = (V1(Bk) ∪ V2(B),Ew(Bk)) be the weighted graphs corresponding to B,Bk respectively. Note that Gw is a weighted subgraph of Gw,k induced by V1(B) = ⟨m⟩ ⊂ ⟨m + n − k⟩ = V1(Bk),V2(B) = ⟨n⟩ ⊂ ⟨n + m − k⟩ = V2(Bk). Furthermore, each vertex in V1(Bk)\V1(B) is connected exactly to each vertex in V2(B), and each vertex in V2(Bk)\V2(B) is connected exactly to each vertex in V1(B). The weights of each of these edges is 1. These are all edges in G(Bk). A perfect match in G(Bk) correspond to:
• An n − k match between the set of vertices V1(Bk)\V1(B) and the set of vertices β′ ∈ Qn−k,n, viewed as a subset of V2(B).