Sa consideram secvente de grafuri neorientate de tipurile urmatoare:

* Tipul $A$

Tipul $A$

Secventa grafurilor de tip $A$ se construieste in modul ce se poate deduce din exemplele urmatoare:
     $A1$        $A2$       $A3$            $A4$        $A5$

!problema/perfect?poza1.jpg!

Observati ca graful $An$ are $2n$ varfuri.

* Tipul $B$

 
Tipul $B$

Secventa grafurilor de tip $B$ se construieste dupa modelul urmator:
     $B1$        $B2$       $B3$            $B4$

!problema/perfect?poza2.jpg!

* Tipul $C$

 
Tipul $C$

Secventa grafurilor de tip $C$ se construieste dupa modelul urmator:

     $C1$     $C2$         $C3$            $C4$

  $C1$     $C2$         $C3$            $C4$
 

!problema/perfect?poza3.jpg!
Se numeste cuplaj perfect in graf o modalitate de a alege muchii ale grafului astfel incat oricare varf din graf sa fie incident cu exact o muchie aleasa. Doua cuplaje sunt distincte daca exista o muchie care apartine unui cuplaj, dar nu apartine celuilalt.

Cele $5$ cuplaje perfecte ale grafului $A4$ sunt:

!problema/perfect?exp1.jpg!

img 1

Cele $4$ cuplaje perfecte ale grafului $B2$ sunt:

!problema/perfect?exp2.jpg!

img 2

Cele $8$ cuplaje perfecte ale grafului $C2$ sunt:

!problema/perfect?exp3.jpg!

img 3

== include(page="template/taskfooter" task_id="perfect") ==

3135