maximum matching of a graph
[card,match] = best_match(g)
:a graph (see graph_data_structure).
integer
integer row vector
A matching on a graph is a set of edges such that no two of them share a node in common. The largest possible matching on a graph with n nodes consists of n/2 edges, and such a matching is called a perfect matching. Although not all graphs have perfect matchings, a maximum matching exists for each graph.
best_match
finds an maximum matching for the
graph g
. The output are card
and the
vector match
. card
is the
cardinality of an optimal matching. match(i)
is the
node adjacent to node i
in the maximum matching or 0 if
i
is unmatched.
//create the graph ta=[27 27 3 12 11 12 27 26 26 25 25 24 23 23 21 22 21 20 19 18 18]; ta=[ta 16 15 15 14 12 9 10 6 9 17 8 17 10 20 11 23 23 12 18 28]; he=[ 1 2 2 4 5 11 13 1 25 22 24 22 22 19 13 13 14 16 16 9 16]; he=[he 10 10 11 12 2 6 5 5 7 8 7 9 6 11 4 18 13 3 28 17]; n=28; g=make_graph('foo',0,n,ta,he); // Graph display xx=[46 120 207 286 366 453 543 544 473 387 300 206 136 250 346 408]; g.nodes.graphics.x=[xx 527 443 306 326 196 139 264 55 58 46 118 513]; yy=[36 34 37 40 38 40 35 102 102 98 93 96 167 172 101 179]; g.nodes.graphics.y=[yy 198 252 183 148 172 256 259 258 167 109 104 253]; g.nodes.graphics.display='name'; show_graph(g); [card,match] = best_match(g); mprintf("number of edge in matching=%d number of nodes=%d\n",card,node_number(g)) // compute the edge number of the matching v=index_from_tail_head(g,1:n,match) //show the matching edges hilite_edges(v); // // WITH A LARGER GRAPH g=load_graph(metanet_module_path()+'/demos/mesh1000.graph'); g.directed=0; ta=g.edges.tail;he=g.edges.head;n=node_number(g); show_graph(g,'new',1/2,[1000,400]); [card,match] = best_match(g); hilite_edges(index_from_tail_head(g,1:n,match)); | ![]() | ![]() |
Micali, S. and Vazirani, V. V.,"An O(square root of V * E) Algorithm for Finding Maximum Matching in General Graphs", Proc. 21st Annual Symposium on Foundation of Computer Science, IEEE, 1980, pp. 17-27.
Lovász, L. and Plummer, M. D. Matching Theory. Amsterdam, Netherlands: North-Holland, 1986.