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)
Comment
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 bipartite