edge weight of bipartite graph

Question

I have difficulties in understanding certain logic. I have a bi-partite graph as below.

I wish to find the optimal match for all the vertices in left side (Viz,A1,A2,A3,A4). I got a suggestion from my friend that the summation of edge weight can be used to solve this problem. However, I am not sure, how summation of edge weight will help in this case. For example, for A1 I can say AL2 is the best match and so on. However, my friend suggested that edge weight is much more optimal solution to this problem. I am not able to understand how it can be a optimal solution. His idea was that, all of (A1,A2,A3,A4) will be connected to all of (AL1,AL2,..,AL6) and for each edge we will calculate the summation of edge weights. Can someone please help me understand what he actually means?

EDIT: I think this might not be a case of perfect matching in bipartite graphs as the nodes in left side should equal the nodes in the right side.

Answer 1

A maximum weighted bipartite matching can be efficiently computed in polynomial time using a max-flow algorithm, which is a special case of a linear program. There are several relationships between bipartite matchings, max-flow, and linear programs, but the Hopkroft-Karp algorithm is the most concise expression of an algorithm for solving this specific problem.

Maximum matchings for non-bipartite graphs can also be computed efficiently.

(All the algorithms above have weighted versions.)

EDIT: It was unclear from your comments whether you have a slightly different problem. If there can be a one-to-many mapping from left to right, but right nodes can only map to one left node, you effectively have a max-flow problem where the left nodes have infinite-capacity inflow and the right nodes have an outflow capacity of one. Consult max-flow algorithms for different solution methods.