| Meno: | Filip
|
|---|
| Priezvisko: | Novák
|
|---|
| Názov: | Hľadanie perfektných párení
|
|---|
| Vedúci: | RNDr. Ján Mazák, PhD.
|
|---|
| Rok: | 2020
|
|---|
| Kľúčové slová: | perfektné párenie, kubický graf, snark, algoritmus, AllSAT solver
|
|---|
| Abstrakt: | Získali sme prehlad o rôznych algoritmoch, ktoré hladajú perfektné párenia vo všeobecných
grafoch. Niektoré z nich sme implementovali a testovali sme ich rýchlost na
kubických grafoch. Najspolahlivejší a najrýchlejší algoritmus sme vybrali a použili vo
vlastnej implementácii algoritmu, ktorý hladá všetky perfektné párenia v grafe. Pomocou
vybratého algoritmu sa nám podarila zefektívnit naša implementácia algorimtu,
ktorý sme testovali na kubických grafoch. Výsledný algoritmus sme testovali na snarkoch
s rôznymi vlastnostami a porovnávali s rýchlostou AllSAT solvera.
|
|---|