Matchings in bipartite graphs
We illustrate the use of bipmatch to find maximum matchings in bipartite graphs.
We begin with a 3-by-5 grid graph.
g = graph; grid(g,3,5); p = bipartition(g); % find the bipartion of the graph m = bipmatch(g,p); disp(m)
1 2 3 6 5 4 7 8 9 12 11 10 13 14
We create a function edraw to draw a graph with a selected set of edges solid and the remaining edges dotted.
The code for edraw is in the file edraw.m and is not part of that standard Matgraph distribution. The code is repeated here:
% function edraw(g,elist) % n = nv(g); % h = graph(n); % create a graph with same number of vertices as g % add(h,elist); % add edges in elist to h % embed(h, getxy(g)); % copy g's embedding % draw(g,':'); % draw g with dotted lines % draw(h); % overdraw h with solid lines % free(h); % release h clf;edraw(g,m);
random_tree(g,25); distxy(g); p = bipartition(g); m = bipmatch(g,p); clf;edraw(g,m);
Optimization terminated: relative function value changing by less than OPTIONS.TolFun. Embedding score = 26.8465 Elapsed time is 3.617853 seconds.
random_bipartite(g,8,10,.4); p = bipartition(g); m = bipmatch(g,p); clf;edraw(g,m);