Să considerăm secvenţe de grafuri neorientate de tipurile următoare:
Tipul A
Secvenţa grafurilor de tip A se construieşte în modul ce se poate deduce din exemplele următoare:
Observaţi că graful An are 2n vârfuri.
Tipul B
Secvenţa grafurilor de tip B se construieşte după modelul următor:
Tipul C
Secvenţa grafurilor de tip C se construieşte după modelul următor:
Se numeşte cuplaj perfect în graf o modalitate de a alege muchii ale grafului astfel încât oricare vârf din graf să fie incident cu exact o muchie aleasă. Două cuplaje sunt distincte dacă există o muchie care aparţine unui cuplaj, dar nu aparţine celuilalt.
Cerinţă
Dat fiind un graf de unul dintre tipurile din enunţ, să se determine numărul de cuplaje perfecte distincte ale grafului respectiv.
Date de intrare
Fişierul de intrare perfect.in conţine o singură linie pe care se află un caracter şi un număr natural nenul n, separate printr-un spaţiu. Caracterul poate fi A, B sau C şi indică tipul grafului. Numărul natural n indică numărul de ordine al grafului în secvenţa de grafuri de tipul specificat de caracter.
Date de ieşire
Fişierul de ieşire perfect.out va conţine o singură linie pe care va fi scris numărul de cuplaje perfecte ale grafului din fişierul de intrare.
