Bipartite Graphs - The Problem
(Page 2 of 4 )
The first and most important question is, how do we divide a given graph into two individual sets? We could also write a program that will ask for the data from two different files, or ask for the vertexes one after another and only then add the edges.
However, this is a time-intensive job, and we will decrease the re-usability of the program. Any little modification would mean a major modification in the code. We want to make it as user-friendly as possible, so whoever adds the data in the input file should only add the edges representing the efficiency.
The issue, translated again into the language of graphs, is to find out if the graph is bipartite, and if so, make the split into set A and set B. A pair graph is one within which the edges are not directed, and can be split in two individual sets where every edge has one end in the first set and the other end in the second set.
When can any kind of graph be split into two types of sets? This can be done only if all of the basic circle system's components have a length that is also a pair number. Now again, if you are not familiar with the statement of circle systems, you can just read my article entitled Circles and Connectivity in Graphs.
Before you jump in to see if this is correct, there is a shorter solution. It is possible with the Breadth-First Search. This search visits the edges by level. First, it drops by the root. It then visits all of the direct neighbors (also called children). It next visits the children of all the children of the root (of course skipping the ones that were already touched). Repeat these steps until you have no more edges to visit.
If we follow this idea we can add all the odd numbered edges (in the parent tree) to set one and the others to set B. To determine invalid graph input, it is only a matter of testing to see if the bottom-most leaf in the tree and the root have the same color.
This process is also called coloring of the graph's nodes with two colors. Therefore, we will refer to this as the colorizing process. However, assume that we have the correct input. With this search, we can count how many nodes we added to which color and return the number of the color which is less used, to make it clear which one of them has more elements. This can save us an extra iteration.
Next: The Colorize Code Source >>
More Code Examples Articles
More By Gabor Bernat
