Bipartite graph example ppt

bipartite graph perfect matching and bipartite graph partitioning and data clustering
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
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 © 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 bipartite