Question? Leave a message!




Bipartite Graphs

Bipartite Graphs
ECE 250 Algorithms and Data Structures Bipartite Graphs Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Identifying bipartite graphs 2 Outline This topic looks at another problem solved by breadth-first traversals – Determining if a graph is bipartite – Definition of a bipartite graph – The algorithm – An exampleIdentifying bipartite graphs 3 Definition Definition – A bipartite graph is a graph where the vertices V can be divided into two disjoint sets V and V such that every edge has one vertex in V and 1 2 1 the other in V 2Identifying bipartite graphs 4 Bipartite Graphs Consider this graph: is it bipartite?Identifying bipartite graphs 5 Bipartite Graphs Yes: With a little work, it is possible to determine that we can decompose the vertices into two disjoint sets Identifying bipartite graphs 6 Bipartite Graphs Is this graph bipartite?Identifying bipartite graphs 7 Bipartite Graphs In this case, it is not a bipartite graph – Can we find a traversal that will determine if a graph is bipartite?Identifying bipartite graphs 8 Bipartite Graphs Consider using a breadth-first traversal for a connected graph: – Choose a vertex, mark it belonging to V and push it onto a queue 1 – While the queue is not empty, pop the front vertex v and • Any adjacent vertices that are already marked must belong to the set not containing v, otherwise, the graph is not bipartite (we are done); while • Any unmarked adjacent vertices are marked as belonging to the other set and they are pushed onto the queue – If the queue is empty, the graph is bipartiteIdentifying bipartite graphs 9 Bipartite Graphs With the first graph, we can start with any vertex – We will use colours to distinguish the two setsIdentifying bipartite graphs 10 Bipartite Graphs Push A onto the queue and colour it red AIdentifying bipartite graphs 11 Bipartite Graphs Pop A and its two neighbours are not marked: – Mark them as blue and push them onto the queue B FIdentifying bipartite graphs 12 Bipartite Graphs Pop B—it is blue: – Its one marked neighbour, A, is red – Its other neighbours G and H are not marked: mark them red and push them onto the queue F G HIdentifying bipartite graphs 13 Bipartite Graphs Pop F—it is blue: – Its two marked neighbours, A and G, are red – Its neighbour E is not marked: mark it red and pus it onto the queue G H EIdentifying bipartite graphs 14 Bipartite Graphs Pop G—it is red: – Its two marked neighbours, B and F, are blue H EIdentifying bipartite graphs 15 Bipartite Graphs Pop H—it is red: – Its marked neighbours, B, is blue – It has two unmarked neighbours, C and I; mark them blue and push them onto the queue E C IIdentifying bipartite graphs 16 Bipartite Graphs Pop E—it is red: – Its marked neighbours, F and I, are blue C IIdentifying bipartite graphs 17 Bipartite Graphs Pop C—it is blue: – Its marked neighbour, H, is red – Mark D as red and push it onto the queue I DIdentifying bipartite graphs 18 Bipartite Graphs Pop I—it is blue: – Its marked neighbours, H, D and E, are all red DIdentifying bipartite graphs 19 Bipartite Graphs Pop D—it is red: – Its marked neighbours, C and I, are both blueIdentifying bipartite graphs 20 Bipartite Graphs The queue is empty, the graph is bipartiteIdentifying bipartite graphs 21 Bipartite Graphs Consider the other graph which was claimed to be not bipartiteIdentifying bipartite graphs 22 Bipartite Graphs Push A onto the queue and colour it red AIdentifying bipartite graphs 23 Bipartite Graphs Pop A off the queue: – Its neighbours are unmarked: colour them blue and push them onto the queue B FIdentifying bipartite graphs 24 Bipartite Graphs Pop B off the queue: – Its one neighbour, A, is red – The other neighbour, H, is unmarked: colour it red and push it onto the queue F HIdentifying bipartite graphs 25 Bipartite Graphs Pop F off the queue: – Its one neighbour, A, is red – The other neighbours, E and G, are unmarked: colour them red and push it onto the queue H E GIdentifying bipartite graphs 26 Bipartite Graphs Pop H off the queue—it is red: – Its one neighbour, G, is already red – The graph is not bipartite E GIdentifying bipartite graphs 27 Bipartite Graphs Definition Cycles that contains either an even number or an odd number of vertices are said to be even cycles and odd cycles, respectively Theorem A graph is bipartite if and only if it does not contain any odd cycles Reference: Kleinberg and TardosIdentifying bipartite graphs 28 Sumary This topic looked at identifying bipartite graphs – Perform a breadth-first traversal – Each vertex is given one of two identifiers (we used color) – The first vertex is identified as one color and pushed onto the queue – When a vertex is popped: • Each unvisited neighbor is pushed onto the tree with the opposite color • Each visited neighbor must be the opposite color – If one is not, the graph is not bipartiteIdentifying bipartite graphs 29 References Wikipedia, http://en.wikipedia.org/wiki/Breadth-first_searchTesting_bipartiteness http://en.wikipedia.org/wiki/Breadth-first_search http://en.wikipedia.org/wiki/Bipartite_graph 1 Jon Kleinberg and Éva Tardos, Algorithm Design, Addison Wesley, 2006, §§3.2-5, pp.78-99. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W.Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment