Domáca úloha č.1
Nech G je kubický bezmostový graf na m hranách a nech k je prirodzené číslo, 4/3 m <= k <= 212/135 m. Cyklus v grafe je podgraf grafu (nie nutne súvislý), ktorý má všetky vrcholy párneho stupňa (vrchol stupňa 0 je teda povolený).
Naprogramujte funckiu, ktorá overí, či existuje množina troch cyklov taká, že
- každá hrana je v aspoň jednom z cyklov,
- že súčet počtu hrán v jednotlivých cykloch je nanajvýš k.
V jazyku C++ naprogramujte funkcie:
-
bool sccTrivial(std::vector<std::vector<int>> graph, int k). Táto funkcia má obsahovať jednoduchý (neefektívny) algoritmus na riešenie problému.
-
std::vector<std::vector<int>> sccToCNF(std::vector<std::vector<int>> graph, int k). Problém preveďte na problém splniteľnosti konjunktívnej normálnej formy.
Graf je reprezentovaný nasledovne. Graf má graph.size() vrcholov, ktoré sú označené číslami od 0 po graph.size()-1. Hrana medzi vrcholmi i a j existuje práve vtedy, keď graph[i] obsahuje j a graph[j] obsahuje i. Vektory, ktoré graph obsahuje neobsahujú žiadne prvky navyše.
Konjunktívnu normálnu formu reprezentujte ako vektor kláuz, pričom klauzy reprezentujte tak, ako ste to robili na cviku, nedávajte však do vektorov záverečnú 0.
Okrem správnosti riešenia bude udelený počet bodov závisieť najmä od toho ako rýchlo bude bude vedieť SAT solver daný problém vyriešiť pomocou vami vygenerovanej CNF a od jej dĺžky (budem používať miniSAT).
Dajte si pozor na to, aby vaša funkcia na generovanie konjunktívnej normálnej formy zvládla spracovať aj grafy majúce veľa vrcholov (nevadí ak ich SAT solver nebude zvládať spracovať v rozumnom čase).
Vygeneroval som niekoľko vstupných grafov. V tomto súbore ich nájdete spolu s optimálnymi hodnotami pokrytia 3mi cyklami.
Riešenie odovzdajte do 3.4. vrátane (v SEČ) majlom na adresu lukotka.pts@gmail.com.
Všetky funkcie odovzdajte v jednom súbore, nazvanom scc.cpp. Tento súbor nemá obsahovať funkciu main.
Upozorňujem, neposielajte teraz ani v budúcnosti na túto adresu nič iné ako samotné odovzdanie riešenia domácich úloh (na túto adresu sa prihlasujem iba keď sťahujem domáce úlohy a posielam feedback a aj teraz som tam objavil nejaké majly o bakalárkach).