Matchings in bipartite graphs
We illustrate the use of bipmatch to find maximum matchings in bipartite graphs.
Contents
Grid graph
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
Draw the result
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);

A random tree
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.

A random bipartite graph
random_bipartite(g,8,10,.4); p = bipartition(g); m = bipmatch(g,p); clf;edraw(g,m);

Release storage
free(g)