Scilab function
Last update : 16/06/2004

perfect_match - appariement parfait de coût minimum

### Calling Sequence

  `[cst,nmatch] = perfect_match(g,arcost)`

### Parameters

- `g` : graphe (liste)
- `arcost` : vecteur ligne d'entiers
- `cst` : entier
- `nmatch` : vecteur ligne d'entiers

### Description

`perfect_match` trouve un appariement parfait de coût minimum pour le graphe `g`. `g` doit être un graphe non-orienté avec un nombre pair de sommets. `arcost` est le vecteur des coût (entiers) des arcs (la dimension de `arcost` est le double du nombre d'arêtes du graphe). Les sorties sont le vecteur `nmatch` de l'appariement parfait et le coût correspondant `cst`.

### Examples

    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);
    xx=[46 120 207 286 366 453 543 544 473 387 300 206 136 250 346 408];
    g('node_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('node_y')=[yy 198 252 183 148 172 256 259 258 167 109 104 253];
    show_graph(g);m2=2*size(ta,2);
    arcost=round(100.*rand(1,m2));
    [cst,nmatch] = perfect_match(g,arcost);
    sp=sparse([ta' he'],[1:size(ta,2)]',[n,n]);
    sp1=sparse([[1:n]' nmatch'],ones(1,size(nmatch,2))',[n,n]);
    [ij,v,mn]=spget(sp.*sp1);
    show_arcs(v');

### See Also

`best_match`,