Testing Bipartiteness An Application of Breadth First Search Section 3 4 Bipartite Graphs p Graph G V E is bipartite if n V can be partitioned into sets X and Y in such a way that every edge has one end point in X and other endpoint in Y 1 PDF created with pdfFactory trial version www pdffactory com Bipartite Graphs p Graph G V E is bipartite if n V can be partitioned into sets X and Y in such a way that every edge has one end point in X and other endpoint in Y Bipartite Graphs p Graph G V E is bipartite if n V can be partitioned into sets X and Y in such a way that every edge has one end point in X and other endpoint in Y 2 PDF created with pdfFactory trial version www pdffactory com Bipartite Graphs Examples X set of students p Y set of classes p Edge u v if and only if student u is enrolled in class v p Bipartite Graphs Examples X set of TA applicants p Y set of classes p Edge u v if and only if applicant u is eligible for teaching class v p 3 PDF created with pdfFactory trial version www pdffactory com Bipartite Graphs Examples X set of TA applicants p Y set of classes p Edge u v if and only if applicant u is eligible for teaching class v p Our graduate secretary handles this graph every semester p Bipartite Graphs X set of red nodes p Y set of blue nodes p Edges are between red and blue nodes p n n No edge between red nodes No edge between blue nodes 4 PDF created with pdfFactory trial version www pdffactory com What graphs are not bipartite What graphs are not bipartite 1 3 2 5 PDF created with pdfFactory trial version www pdffactory com What graphs are not bipartite 1 3 2 What graphs are not bipartite 1 3 2 6 PDF created with pdfFactory trial version www pdffactory com What graphs are not bipartite 1 3 2 What graphs are not bipartite p More generally odd cycles have problems n n n n n n n Consider cycle with nodes 1 2 2k 1 Node 1 red Node 2 blue Node 3 red Node 2k blue Node 2k 1 7 PDF created with pdfFactory trial version www pdffactory com What graphs are not bipartite p 3 14 If a graph G is bipartite then it cannot contain an odd cycle What graphs are not bipartite p 3 14 If a graph G is bipartite then it cannot contain an odd cycle n But is odd cycle the only obstacle 8 PDF created with pdfFactory trial version www pdffactory com What graphs are not bipartite p 3 14 If a graph G is bipartite then it cannot contain an odd cycle n n But is odd cycle the only obstacle If no odd cycle is there a valid red blue coloring of the nodes p i e every edge has a red and blue end point What graphs are not bipartite p 3 14 If a graph G is bipartite then it cannot contain an odd cycle n n But is odd cycle the only obstacle If no odd cycle is there a valid red blue coloring of the nodes p i e every edge has a red and blue end point How can we know if a given graph is bipartite 9 PDF created with pdfFactory trial version www pdffactory com An algorithm for testing bipartiteness Choose a vertex s and color it red p Color neighbors of s blue p Color neighbors of these nodes red p and so on until all nodes are colored p An algorithm for testing bipartiteness Choose a vertex s and color it red p Color neighbors of s blue p Color neighbors of these nodes red p and so on until all nodes are colored p p Do we have a valid coloring n n Yes bipartite No not bipartite 10 PDF created with pdfFactory trial version www pdffactory com BFS Coloring Start exploring from s p Color s red p Color layer L1 blue L2 red and so on p Color odd layers blue and even layers red p Easy to implement on top of BFS p BFS Coloring 11 PDF created with pdfFactory trial version www pdffactory com BFS Coloring Set color v here Analysis of BFS coloring p 3 15 Let G be a connected graph and let L1 L2 be the layers produced by BFS starting at node s Then exactly one of the following two things hold 1 There is no edge of G joining two nodes of the same layer In this case G is a bipartite graph in which the nodes in even numbered layers can be colored red and the nodes in odd numbered layers can be colored blue 2 There is an edge of G joining two nodes of the same layer In this case G contains an odd cycle and so it cannot be bipartite 12 PDF created with pdfFactory trial version www pdffactory com