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.

!problema/perfect?exp3.jpg!
== include(page="template/taskfooter" task_id="perfect") ==

3135