<?xml version="1.0" encoding="ISO-8859-1" standalone="no"?> 
<!DOCTYPE MAN SYSTEM "../../manrev.dtd">
<MAN>
  <LANGUAGE>fr</LANGUAGE>
  <TITLE>perfect_match  </TITLE>
  <TYPE>Scilab function  </TYPE>
  <DATE>September 1996  </DATE>
  <SHORT_DESCRIPTION name="perfect_match"> appariement parfait de coût minimum  </SHORT_DESCRIPTION>
  <CALLING_SEQUENCE>
  <CALLING_SEQUENCE_ITEM>[cst,nmatch] = perfect_match(g,arcost)  </CALLING_SEQUENCE_ITEM>
  </CALLING_SEQUENCE>
  <PARAM>
 <PARAM_INDENT>
  <PARAM_ITEM>
  <PARAM_NAME>g  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : graphe (liste) 
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>arcost  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : vecteur ligne d&apos;entiers
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>cst  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : entier 
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>nmatch  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : vecteur ligne d&apos;entiers 
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
 </PARAM_INDENT>
  </PARAM>
  <DESCRIPTION>
  <P>
    <VERB>perfect_match</VERB> trouve un appariement parfait de coût minimum pour le graphe <VERB>g</VERB>.
    <VERB>g</VERB> doit être un graphe non-orienté avec un nombre pair de sommets.
    <VERB>arcost</VERB> est le vecteur des coût (entiers) des arcs (la dimension
    de <VERB>arcost</VERB> est le double du nombre d&apos;arêtes du graphe). 
    Les sorties sont le vecteur <VERB>nmatch</VERB> de l&apos;appariement parfait et le coût
    correspondant <VERB>cst</VERB>.
  </P>
  </DESCRIPTION>
  <EXAMPLE><![CDATA[
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');
 ]]></EXAMPLE>
  <SEE_ALSO>
    <SEE_ALSO_ITEM> <LINK>best_match</LINK> </SEE_ALSO_ITEM>
  </SEE_ALSO>
</MAN>
