Bipartite Graphs
(Page 1 of 4 )
The economic crisis is upon us. You hear from radio, newspaper and television that we need to hold the line. You can no longer waste any of your time and money, because otherwise, the bankruptcy of your company is almost certain. In these harsh times, every little cent you can save is worth a fortune. If you have a company with various employees that can work in multiple places, but their production depends on what they are doing, and you want to maximize the company's productivity, you've come to the right place. This is the conclusion of a thirteen-part series that shows you how to use graphs and algorithms to solve everyday problems.
Although at first glance the bipartite trait of graphs has nothing at common with your problem, if you think about it, you will discover otherwise. All we need to do is rephrase the input data a little to get closer to your issue. So, let there be n workers that can work in a given number of machines/places.
Of course, based on your experience, you know that each worker provides different levels of efficiency on each job. Therefore, it is crucial for you to make the assignments in a fashion such that your productivity will reach its maximum with your current team.
Now consider that vertexes represent every job. We will name this group A. The assembly of the employees we will represent via nodes, and name them group B. A connection between these two groups matches the productivity of one with one assignment. Now, translating the problem to graph language will mean finding the maximum pairing (edges) that will result in n pairs.
Of course, you may have more than n jobs or less than n employees. In this case, only the number of vertexes in each group will differ; the problem remains the same. Here it is a prime example of this:
Image Courtesy of Grapy Theory Algorithms, Kátai Zoltán
The first connection group (represented by the bold edges) offers two pairings, while the second is a little more efficient, offering three as the maximum. Now that you understand the issue before you, to venture any further I need to clarify what you must know to understand this article.
This is part of a larger series about graphs; you will find all of the other articles here on the ASP Free web site. If you are not familiar with any of the concepts I'm about to enumerate, just search for the articles; you can even click on my name to find them all. Come back later, after you have read the articles explaining the concepts. You should understand how to represent graphs in memory, the breadth-first search and the Ford-Fulkerson Algorithm for network flows.
Next: The Problem >>
More Code Examples Articles
More By Gabor Bernat
