1
$\begingroup$

I am looking for concrete and simple problems that may be solved using bipartite graphs or bipartite graph properties. Any idea along with explanations are welcome.

$\endgroup$
3
  • $\begingroup$ What do you mean by problem? Do you want a real-life application? $\endgroup$ Apr 23, 2014 at 19:48
  • $\begingroup$ Yes, preferably $\endgroup$
    – Laurent
    Apr 23, 2014 at 19:50
  • 1
    $\begingroup$ Hello, and welcome to Computer Science StackExchange! Unfortunately, in its current form, this question is overly broad; it would be too hard to judge one answer more or less right than another, and I can imagine (maybe short) books being written on this subject. Please try to narrow the scope, at which point the question may be reopened. Thanks for your participation, and again, welcome! $\endgroup$
    – Patrick87
    Apr 24, 2014 at 17:38

2 Answers 2

3
$\begingroup$

Assignment Problem would be one such example:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.

Hall's Marriage Theorem would be another:

Imagine two groups; one of n men, and one of n women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.

The Mutilated Chessboard Problem can be solved using The Hall's Theorem:

Suppose a standard 8x8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2x1 so as to cover all of these squares?

$\endgroup$
1
$\begingroup$

There are loads conceptually simple and interesting such problems here: http://uva.onlinejudge.org/

I don't remember the actual problem numbers, though, but you can search the forum for bipartite graph problems.

$\endgroup$
2
  • $\begingroup$ Thank you for the pointer but it seems there is only one problem about bipartite numbers which is not what I am looking for :( $\endgroup$
    – Laurent
    Apr 24, 2014 at 6:33
  • $\begingroup$ I know I have solved more than one bipartite graph problem there. Probably 2-3, so there are more than that. But perhaps those problems are not identified as bipartite graph problems, and/or can be solved in another way. A quick search in the forum seems to give tens of problems that involve bipartite graphs. $\endgroup$
    – Tommy L
    Apr 28, 2014 at 7:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.