Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:holmesr:section_3.4 [2018/02/06 02:42] – holmesr | courses:cs211:winter2018:journals:holmesr:section_3.4 [2018/02/06 03:57] (current) – holmesr | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Section 3.4 Testing Bipartiteness: | ====== Section 3.4 Testing Bipartiteness: | ||
| + | A bipartite graph is one that can be separated into two sets such that every edge has one edge in X and the other in Y. This can be represented by a BFS tree by labelling all the odd layers as the layers which contain nodes in the X partition and the even layers contain nodes in the Y partition. Then it is easy to see that there can not be an edge that begins and ends in the same layer, and by the definition of a BFS, there can not be an edge that spans more than one layer difference from the layer in which it has one end. It follows from this then that a bipartite graph can not contain any odd cycles, since an odd cycle must contain an edge that begins and ends in the same layer of the BFS tree. | ||
| + | |||
| + | This lays down the basis for a very easy addition to be made to the BSF algorithm that will help determine whether a graph is bipartite or not. Simply add an array of size n called Partition and assign all the nodes //n// in an odd layer to be Partition[n] = X and all the nodes in even layers to be Partition[n] = Y. If any edge has both ends being Partition[n] = X or Partition[n] = Y, then the graph is bipartite. Since this all occurs in constant time, it does not bump up the O(n+m) running time of BFS. | ||
| + | |||
| + | This section was fascinating in that it demonstrated that determining bipartiteness of a graph is reliant on the same algorithmic skeleton as the BFS algorithm. | ||
