doc/images/bipartite_matching.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 11 Aug 2009 20:55:40 +0200
changeset 765 3b544a9c92db
permissions -rw-r--r--
Add Karp algorithm class (#179)
based on the MinMeanCycle implementation in SVN -r3436.
The interface is reworked to be the same as Howard's interface.
     1 %!PS-Adobe-3.0 EPSF-3.0
     2 %%BoundingBox: 15 18 829 570
     3 %%HiResBoundingBox: 15.1913 18.4493 828.078 569.438
     4 %%Creator: Karbon14 EPS Exportfilter 0.5
     5 %%CreationDate: (04/15/06 15:20:26)
     6 %%For: (Balazs Dezso) ()
     7 %%Title: ()
     8 
     9 /N {newpath} def
    10 /C {closepath} def
    11 /m {moveto} def
    12 /c {curveto} def
    13 /l {lineto} def
    14 /s {stroke} def
    15 /f {fill} def
    16 /w {setlinewidth} def
    17 /d {setdash} def
    18 /r {setrgbcolor} def
    19 /S {gsave} def
    20 /R {grestore} def
    21 
    22 N
    23 251.402 32.047 m
    24 532.945 293.946 814.484 555.844 814.484 555.844 c
    25 [] 0 d 1 0 0 r 3.92814 w s
    26 
    27 N
    28 749.012 32.047 m
    29 742.465 293.946 735.918 555.844 735.918 555.844 c
    30 [] 0 d 0 0 0 r 1.96407 w s
    31 
    32 N
    33 539.492 32.047 m
    34 637.703 293.946 735.918 555.844 735.918 555.844 c
    35 [] 0 d 0 0 0 r 1.96407 w s
    36 
    37 N
    38 172.832 32.047 m
    39 454.375 293.946 735.918 555.844 735.918 555.844 c
    40 [] 0 d 0 0 0 r 1.96407 w s
    41 
    42 N
    43 107.355 32.047 m
    44 421.637 293.946 735.918 555.844 735.918 555.844 c
    45 [] 0 d 1 0 0 r 3.92814 w s
    46 
    47 N
    48 644.25 555.844 m
    49 696.633 293.946 749.012 32.047 749.012 32.047 c
    50 [] 0 d 0 0 0 r 1.96407 w s
    51 
    52 N
    53 474.016 555.844 m
    54 611.516 293.946 749.012 32.047 749.012 32.047 c
    55 [] 0 d 1 0 0 r 3.92814 w s
    56 
    57 N
    58 683.535 32.047 m
    59 663.894 293.946 644.25 555.844 644.25 555.844 c
    60 [] 0 d 0 0 0 r 1.96407 w s
    61 
    62 N
    63 120.453 555.844 m
    64 401.992 293.946 683.535 32.047 683.535 32.047 c
    65 [] 0 d 0 0 0 r 1.96407 w s
    66 
    67 N
    68 28.7853 555.844 m
    69 356.16 293.946 683.535 32.047 683.535 32.047 c
    70 [] 0 d 1 0 0 r 3.92814 w s
    71 
    72 N
    73 539.492 32.047 m
    74 546.039 293.946 552.586 555.844 552.586 555.844 c
    75 [] 0 d 1 0 0 r 3.92814 w s
    76 
    77 N
    78 316.875 32.047 m
    79 349.613 293.946 382.351 555.844 382.351 555.844 c
    80 [] 0 d 1 0 0 r 3.92814 w s
    81 
    82 N
    83 107.355 32.047 m
    84 244.855 293.946 382.351 555.844 382.351 555.844 c
    85 [] 0 d 0 0 0 r 1.96407 w s
    86 
    87 N
    88 290.687 555.844 m
    89 375.805 293.946 460.922 32.047 460.922 32.047 c
    90 [] 0 d 1 0 0 r 3.92814 w s
    91 
    92 N
    93 120.453 555.844 m
    94 290.687 293.946 460.922 32.047 460.922 32.047 c
    95 [] 0 d 0 0 0 r 1.96407 w s
    96 
    97 N
    98 172.832 32.047 m
    99 146.64 293.946 120.453 555.844 120.453 555.844 c
   100 [] 0 d 1 0 0 r 3.92814 w s
   101 
   102 N
   103 15.6913 555.844 m
   104 15.6913 555.844 l
   105 15.6913 548.614 21.5553 542.75 28.7853 542.75 c
   106 36.0163 542.75 41.8833 548.614 41.8833 555.844 c
   107 41.8833 563.075 36.0163 568.938 28.7853 568.938 c
   108 21.5553 568.938 15.6913 563.075 15.6913 555.844 c
   109 15.6913 555.844 l
   110 C
   111 S 0 0 0 r f R
   112 
   113 N
   114 16.8833 555.844 m
   115 16.8833 555.844 l
   116 16.8833 549.27 22.2113 543.942 28.7853 543.942 c
   117 35.3593 543.942 40.6913 549.27 40.6913 555.844 c
   118 40.6913 562.418 35.3593 567.747 28.7853 567.747 c
   119 22.2113 567.747 16.8833 562.418 16.8833 555.844 c
   120 16.8833 555.844 l
   121 C
   122 S 1 0.5 1 r f R
   123 
   124 N
   125 107.355 555.844 m
   126 107.355 555.844 l
   127 107.355 548.614 113.223 542.75 120.453 542.75 c
   128 127.683 542.75 133.547 548.614 133.547 555.844 c
   129 133.547 563.075 127.683 568.938 120.453 568.938 c
   130 113.223 568.938 107.355 563.075 107.355 555.844 c
   131 107.355 555.844 l
   132 C
   133 S 0 0 0 r f R
   134 
   135 N
   136 108.547 555.844 m
   137 108.547 555.844 l
   138 108.547 549.27 113.879 543.942 120.453 543.942 c
   139 127.027 543.942 132.355 549.27 132.355 555.844 c
   140 132.355 562.418 127.027 567.747 120.453 567.747 c
   141 113.879 567.747 108.547 562.418 108.547 555.844 c
   142 108.547 555.844 l
   143 C
   144 S 1 0 1 r f R
   145 
   146 N
   147 199.019 555.844 m
   148 199.019 555.844 l
   149 199.019 548.614 204.887 542.75 212.117 542.75 c
   150 219.348 542.75 225.211 548.614 225.211 555.844 c
   151 225.211 563.075 219.348 568.938 212.117 568.938 c
   152 204.887 568.938 199.019 563.075 199.019 555.844 c
   153 199.019 555.844 l
   154 C
   155 S 0 0 0 r f R
   156 
   157 N
   158 200.211 555.844 m
   159 200.211 555.844 l
   160 200.211 549.27 205.543 543.942 212.117 543.942 c
   161 218.691 543.942 224.019 549.27 224.019 555.844 c
   162 224.019 562.418 218.691 567.747 212.117 567.747 c
   163 205.543 567.747 200.211 562.418 200.211 555.844 c
   164 200.211 555.844 l
   165 C
   166 S 1 0.5 1 r f R
   167 
   168 N
   169 277.59 555.844 m
   170 277.59 555.844 l
   171 277.59 548.614 283.457 542.75 290.687 542.75 c
   172 297.918 542.75 303.781 548.614 303.781 555.844 c
   173 303.781 563.075 297.918 568.938 290.687 568.938 c
   174 283.457 568.938 277.59 563.075 277.59 555.844 c
   175 277.59 555.844 l
   176 C
   177 S 0 0 0 r f R
   178 
   179 N
   180 278.781 555.844 m
   181 278.781 555.844 l
   182 278.781 549.27 284.113 543.942 290.687 543.942 c
   183 297.262 543.942 302.59 549.27 302.59 555.844 c
   184 302.59 562.418 297.262 567.747 290.687 567.747 c
   185 284.113 567.747 278.781 562.418 278.781 555.844 c
   186 278.781 555.844 l
   187 C
   188 S 1 0 1 r f R
   189 
   190 N
   191 369.258 555.844 m
   192 369.258 555.844 l
   193 369.258 548.614 375.121 542.75 382.351 542.75 c
   194 389.582 542.75 395.445 548.614 395.445 555.844 c
   195 395.445 563.075 389.582 568.938 382.351 568.938 c
   196 375.121 568.938 369.258 563.075 369.258 555.844 c
   197 369.258 555.844 l
   198 C
   199 S 0 0 0 r f R
   200 
   201 N
   202 370.445 555.844 m
   203 370.445 555.844 l
   204 370.445 549.27 375.777 543.942 382.351 543.942 c
   205 388.926 543.942 394.258 549.27 394.258 555.844 c
   206 394.258 562.418 388.926 567.747 382.351 567.747 c
   207 375.777 567.747 370.445 562.418 370.445 555.844 c
   208 370.445 555.844 l
   209 C
   210 S 1 0 1 r f R
   211 
   212 N
   213 460.922 555.844 m
   214 460.922 555.844 l
   215 460.922 548.614 466.785 542.75 474.016 542.75 c
   216 481.246 542.75 487.109 548.614 487.109 555.844 c
   217 487.109 563.075 481.246 568.938 474.016 568.938 c
   218 466.785 568.938 460.922 563.075 460.922 555.844 c
   219 460.922 555.844 l
   220 C
   221 S 0 0 0 r f R
   222 
   223 N
   224 462.113 555.844 m
   225 462.113 555.844 l
   226 462.113 549.27 467.441 543.942 474.016 543.942 c
   227 480.59 543.942 485.922 549.27 485.922 555.844 c
   228 485.922 562.418 480.59 567.747 474.016 567.747 c
   229 467.441 567.747 462.113 562.418 462.113 555.844 c
   230 462.113 555.844 l
   231 C
   232 S 1 0.5 1 r f R
   233 
   234 N
   235 539.492 555.844 m
   236 539.492 555.844 l
   237 539.492 548.614 545.355 542.75 552.586 542.75 c
   238 559.816 542.75 565.68 548.614 565.68 555.844 c
   239 565.68 563.075 559.816 568.938 552.586 568.938 c
   240 545.355 568.938 539.492 563.075 539.492 555.844 c
   241 539.492 555.844 l
   242 C
   243 S 0 0 0 r f R
   244 
   245 N
   246 540.683 555.844 m
   247 540.683 555.844 l
   248 540.683 549.27 546.012 543.942 552.586 543.942 c
   249 559.16 543.942 564.492 549.27 564.492 555.844 c
   250 564.492 562.418 559.16 567.747 552.586 567.747 c
   251 546.012 567.747 540.683 562.418 540.683 555.844 c
   252 540.683 555.844 l
   253 C
   254 S 1 0 1 r f R
   255 
   256 N
   257 631.156 555.844 m
   258 631.156 555.844 l
   259 631.156 548.614 637.019 542.75 644.25 542.75 c
   260 651.48 542.75 657.348 548.614 657.348 555.844 c
   261 657.348 563.075 651.48 568.938 644.25 568.938 c
   262 637.019 568.938 631.156 563.075 631.156 555.844 c
   263 631.156 555.844 l
   264 C
   265 S 0 0 0 r f R
   266 
   267 N
   268 632.348 555.844 m
   269 632.348 555.844 l
   270 632.348 549.27 637.676 543.942 644.25 543.942 c
   271 650.824 543.942 656.156 549.27 656.156 555.844 c
   272 656.156 562.418 650.824 567.747 644.25 567.747 c
   273 637.676 567.747 632.348 562.418 632.348 555.844 c
   274 632.348 555.844 l
   275 C
   276 S 1 0.5 1 r f R
   277 
   278 N
   279 722.82 555.844 m
   280 722.82 555.844 l
   281 722.82 548.614 728.687 542.75 735.918 542.75 c
   282 743.149 542.75 749.012 548.614 749.012 555.844 c
   283 749.012 563.075 743.149 568.938 735.918 568.938 c
   284 728.687 568.938 722.82 563.075 722.82 555.844 c
   285 722.82 555.844 l
   286 C
   287 S 0 0 0 r f R
   288 
   289 N
   290 724.012 555.844 m
   291 724.012 555.844 l
   292 724.012 549.27 729.344 543.942 735.918 543.942 c
   293 742.492 543.942 747.82 549.27 747.82 555.844 c
   294 747.82 562.418 742.492 567.747 735.918 567.747 c
   295 729.344 567.747 724.012 562.418 724.012 555.844 c
   296 724.012 555.844 l
   297 C
   298 S 1 0 1 r f R
   299 
   300 N
   301 801.391 555.844 m
   302 801.391 555.844 l
   303 801.391 548.614 807.254 542.75 814.484 542.75 c
   304 821.715 542.75 827.578 548.614 827.578 555.844 c
   305 827.578 563.075 821.715 568.938 814.484 568.938 c
   306 807.254 568.938 801.391 563.075 801.391 555.844 c
   307 801.391 555.844 l
   308 C
   309 S 0 0 0 r f R
   310 
   311 N
   312 802.582 555.844 m
   313 802.582 555.844 l
   314 802.582 549.27 807.91 543.942 814.484 543.942 c
   315 821.059 543.942 826.387 549.27 826.387 555.844 c
   316 826.387 562.418 821.059 567.747 814.484 567.747 c
   317 807.91 567.747 802.582 562.418 802.582 555.844 c
   318 802.582 555.844 l
   319 C
   320 S 1 0 1 r f R
   321 
   322 N
   323 15.6913 32.047 m
   324 15.6913 32.047 l
   325 15.6913 24.8165 21.5553 18.9493 28.7853 18.9493 c
   326 36.0163 18.9493 41.8833 24.8165 41.8833 32.047 c
   327 41.8833 39.2775 36.0163 45.1407 28.7853 45.1407 c
   328 21.5553 45.1407 15.6913 39.2775 15.6913 32.047 c
   329 15.6913 32.047 l
   330 C
   331 S 0 0 0 r f R
   332 
   333 N
   334 16.8833 32.047 m
   335 16.8833 32.047 l
   336 16.8833 25.4728 22.2113 20.1407 28.7853 20.1407 c
   337 35.3593 20.1407 40.6913 25.4728 40.6913 32.047 c
   338 40.6913 38.6212 35.3593 43.9493 28.7853 43.9493 c
   339 22.2113 43.9493 16.8833 38.6212 16.8833 32.047 c
   340 16.8833 32.047 l
   341 C
   342 S 0.5 0.5 1 r f R
   343 
   344 N
   345 94.2623 32.047 m
   346 94.2623 32.047 l
   347 94.2623 24.8165 100.125 18.9493 107.355 18.9493 c
   348 114.586 18.9493 120.453 24.8165 120.453 32.047 c
   349 120.453 39.2775 114.586 45.1407 107.355 45.1407 c
   350 100.125 45.1407 94.2623 39.2775 94.2623 32.047 c
   351 94.2623 32.047 l
   352 C
   353 S 0 0 0 r f R
   354 
   355 N
   356 95.4533 32.047 m
   357 95.4533 32.047 l
   358 95.4533 25.4728 100.781 20.1407 107.355 20.1407 c
   359 113.93 20.1407 119.262 25.4728 119.262 32.047 c
   360 119.262 38.6212 113.93 43.9493 107.355 43.9493 c
   361 100.781 43.9493 95.4533 38.6212 95.4533 32.047 c
   362 95.4533 32.047 l
   363 C
   364 S 0.5 0.5 1 r f R
   365 
   366 N
   367 159.734 32.047 m
   368 159.734 32.047 l
   369 159.734 24.8165 165.601 18.9493 172.832 18.9493 c
   370 180.062 18.9493 185.926 24.8165 185.926 32.047 c
   371 185.926 39.2775 180.062 45.1407 172.832 45.1407 c
   372 165.601 45.1407 159.734 39.2775 159.734 32.047 c
   373 159.734 32.047 l
   374 C
   375 S 0 0 0 r f R
   376 
   377 N
   378 160.926 32.047 m
   379 160.926 32.047 l
   380 160.926 25.4728 166.258 20.1407 172.832 20.1407 c
   381 179.406 20.1407 184.734 25.4728 184.734 32.047 c
   382 184.734 38.6212 179.406 43.9493 172.832 43.9493 c
   383 166.258 43.9493 160.926 38.6212 160.926 32.047 c
   384 160.926 32.047 l
   385 C
   386 S 0.5 0.5 1 r f R
   387 
   388 N
   389 238.305 32.047 m
   390 238.305 32.047 l
   391 238.305 24.8165 244.172 18.9493 251.402 18.9493 c
   392 258.633 18.9493 264.496 24.8165 264.496 32.047 c
   393 264.496 39.2775 258.633 45.1407 251.402 45.1407 c
   394 244.172 45.1407 238.305 39.2775 238.305 32.047 c
   395 238.305 32.047 l
   396 C
   397 S 0 0 0 r f R
   398 
   399 N
   400 239.496 32.047 m
   401 239.496 32.047 l
   402 239.496 25.4728 244.828 20.1407 251.402 20.1407 c
   403 257.976 20.1407 263.305 25.4728 263.305 32.047 c
   404 263.305 38.6212 257.976 43.9493 251.402 43.9493 c
   405 244.828 43.9493 239.496 38.6212 239.496 32.047 c
   406 239.496 32.047 l
   407 C
   408 S 0.5 0.5 1 r f R
   409 
   410 N
   411 303.781 32.047 m
   412 303.781 32.047 l
   413 303.781 24.8165 309.644 18.9493 316.875 18.9493 c
   414 324.105 18.9493 329.973 24.8165 329.973 32.047 c
   415 329.973 39.2775 324.105 45.1407 316.875 45.1407 c
   416 309.644 45.1407 303.781 39.2775 303.781 32.047 c
   417 303.781 32.047 l
   418 C
   419 S 0 0 0 r f R
   420 
   421 N
   422 304.973 32.047 m
   423 304.973 32.047 l
   424 304.973 25.4728 310.301 20.1407 316.875 20.1407 c
   425 323.449 20.1407 328.781 25.4728 328.781 32.047 c
   426 328.781 38.6212 323.449 43.9493 316.875 43.9493 c
   427 310.301 43.9493 304.973 38.6212 304.973 32.047 c
   428 304.973 32.047 l
   429 C
   430 S 0.5 0.5 1 r f R
   431 
   432 N
   433 382.351 32.047 m
   434 382.351 32.047 l
   435 382.351 24.8165 388.215 18.9493 395.445 18.9493 c
   436 402.676 18.9493 408.543 24.8165 408.543 32.047 c
   437 408.543 39.2775 402.676 45.1407 395.445 45.1407 c
   438 388.215 45.1407 382.351 39.2775 382.351 32.047 c
   439 382.351 32.047 l
   440 C
   441 S 0 0 0 r f R
   442 
   443 N
   444 383.543 32.047 m
   445 383.543 32.047 l
   446 383.543 25.4728 388.871 20.1407 395.445 20.1407 c
   447 402.019 20.1407 407.351 25.4728 407.351 32.047 c
   448 407.351 38.6212 402.019 43.9493 395.445 43.9493 c
   449 388.871 43.9493 383.543 38.6212 383.543 32.047 c
   450 383.543 32.047 l
   451 C
   452 S 0.5 0.5 1 r f R
   453 
   454 N
   455 447.828 32.047 m
   456 447.828 32.047 l
   457 447.828 24.8165 453.691 18.9493 460.922 18.9493 c
   458 468.152 18.9493 474.016 24.8165 474.016 32.047 c
   459 474.016 39.2775 468.152 45.1407 460.922 45.1407 c
   460 453.691 45.1407 447.828 39.2775 447.828 32.047 c
   461 447.828 32.047 l
   462 C
   463 S 0 0 0 r f R
   464 
   465 N
   466 449.016 32.047 m
   467 449.016 32.047 l
   468 449.016 25.4728 454.348 20.1407 460.922 20.1407 c
   469 467.496 20.1407 472.824 25.4728 472.824 32.047 c
   470 472.824 38.6212 467.496 43.9493 460.922 43.9493 c
   471 454.348 43.9493 449.016 38.6212 449.016 32.047 c
   472 449.016 32.047 l
   473 C
   474 S 0.5 0.5 1 r f R
   475 
   476 N
   477 526.394 32.047 m
   478 526.394 32.047 l
   479 526.394 24.8165 532.262 18.9493 539.492 18.9493 c
   480 546.723 18.9493 552.586 24.8165 552.586 32.047 c
   481 552.586 39.2775 546.723 45.1407 539.492 45.1407 c
   482 532.262 45.1407 526.394 39.2775 526.394 32.047 c
   483 526.394 32.047 l
   484 C
   485 S 0 0 0 r f R
   486 
   487 N
   488 527.586 32.047 m
   489 527.586 32.047 l
   490 527.586 25.4728 532.918 20.1407 539.492 20.1407 c
   491 546.066 20.1407 551.394 25.4728 551.394 32.047 c
   492 551.394 38.6212 546.066 43.9493 539.492 43.9493 c
   493 532.918 43.9493 527.586 38.6212 527.586 32.047 c
   494 527.586 32.047 l
   495 C
   496 S 0.5 0.5 1 r f R
   497 
   498 N
   499 591.871 32.047 m
   500 591.871 32.047 l
   501 591.871 24.8165 597.734 18.9493 604.965 18.9493 c
   502 612.195 18.9493 618.062 24.8165 618.062 32.047 c
   503 618.062 39.2775 612.195 45.1407 604.965 45.1407 c
   504 597.734 45.1407 591.871 39.2775 591.871 32.047 c
   505 591.871 32.047 l
   506 C
   507 S 0 0 0 r f R
   508 
   509 N
   510 593.062 32.047 m
   511 593.062 32.047 l
   512 593.062 25.4728 598.39 20.1407 604.965 20.1407 c
   513 611.539 20.1407 616.871 25.4728 616.871 32.047 c
   514 616.871 38.6212 611.539 43.9493 604.965 43.9493 c
   515 598.39 43.9493 593.062 38.6212 593.062 32.047 c
   516 593.062 32.047 l
   517 C
   518 S 0.5 0.5 1 r f R
   519 
   520 N
   521 670.441 32.047 m
   522 670.441 32.047 l
   523 670.441 24.8165 676.305 18.9493 683.535 18.9493 c
   524 690.766 18.9493 696.633 24.8165 696.633 32.047 c
   525 696.633 39.2775 690.766 45.1407 683.535 45.1407 c
   526 676.305 45.1407 670.441 39.2775 670.441 32.047 c
   527 670.441 32.047 l
   528 C
   529 S 0 0 0 r f R
   530 
   531 N
   532 671.633 32.047 m
   533 671.633 32.047 l
   534 671.633 25.4728 676.961 20.1407 683.535 20.1407 c
   535 690.109 20.1407 695.441 25.4728 695.441 32.047 c
   536 695.441 38.6212 690.109 43.9493 683.535 43.9493 c
   537 676.961 43.9493 671.633 38.6212 671.633 32.047 c
   538 671.633 32.047 l
   539 C
   540 S 0 0 1 r f R
   541 
   542 N
   543 735.918 32.047 m
   544 735.918 32.047 l
   545 735.918 24.8165 741.781 18.9493 749.012 18.9493 c
   546 756.242 18.9493 762.106 24.8165 762.106 32.047 c
   547 762.106 39.2775 756.242 45.1407 749.012 45.1407 c
   548 741.781 45.1407 735.918 39.2775 735.918 32.047 c
   549 735.918 32.047 l
   550 C
   551 S 0 0 0 r f R
   552 
   553 N
   554 737.105 32.047 m
   555 737.105 32.047 l
   556 737.105 25.4728 742.437 20.1407 749.012 20.1407 c
   557 755.586 20.1407 760.914 25.4728 760.914 32.047 c
   558 760.914 38.6212 755.586 43.9493 749.012 43.9493 c
   559 742.437 43.9493 737.105 38.6212 737.105 32.047 c
   560 737.105 32.047 l
   561 C
   562 S 0 0 1 r f R
   563 
   564 N
   565 801.391 32.047 m
   566 801.391 32.047 l
   567 801.391 24.8165 807.254 18.9493 814.484 18.9493 c
   568 821.715 18.9493 827.578 24.8165 827.578 32.047 c
   569 827.578 39.2775 821.715 45.1407 814.484 45.1407 c
   570 807.254 45.1407 801.391 39.2775 801.391 32.047 c
   571 801.391 32.047 l
   572 C
   573 S 0 0 0 r f R
   574 
   575 N
   576 802.582 32.047 m
   577 802.582 32.047 l
   578 802.582 25.4728 807.91 20.1407 814.484 20.1407 c
   579 821.059 20.1407 826.387 25.4728 826.387 32.047 c
   580 826.387 38.6212 821.059 43.9493 814.484 43.9493 c
   581 807.91 43.9493 802.582 38.6212 802.582 32.047 c
   582 802.582 32.047 l
   583 C
   584 S 0.5 0.5 1 r f R
   585 
   586 %%EOF