Domáca úloha č.2

Nech r je realne číslo a G je graf. Cirkulárne hranové $r$-farbenie G je zobrazenie z množiny hrán grafu do prvkov grupy R/rZ (zvyšky modulo r) také, že susedné hrany majú rozdiel farieb aspoň 1. Alternatívne si to môžeme predstaviť ako farbenie používajúce body na kružnici s obvodom r také, že susedné hrany sú ofarbené bodmi vo, ktoré majú na kružnici vzdialenosť aspoň 1. Cirkulárny chromatiský index grafu G je minimálna hodnota r, pre ktorú existuje cirkulárne hranové r-farbenie grafu G.

Vytvorte programy na hľadanie cirkulárneho chromatického indexu kubického grafu. Môžete predpokladať, že cirkulárne chromatické číslo grafu na vstupe je v intervale [3, 3+2/3] (článok). Na testovanie môžete použiť grafy z prvej domácej úlohy. Cirkulárny chromatický index prvého grafu je 3+2/3.

Ako nástroj na výpočet lineárneho programovania a celočíselného lineárneho programovania použite lp_solve. Na uľahčenie práce sme napisali malý wrapper (nemusíte ho použiť, objekt primárne zabaľuje C-čkovský interface, do C++-kovskej triedy). Zoznam funkcií knižnice lpsolve nájdete tu. Naprogramovali sme pre vás malý ukážkový projekt.
  1. Vytvorte funkciu double cchi_ilp(std::vector<std::vector<int>> graph);. Táto funkcia má vytvoriť celočíselný lineárny program a použiť lp_solve na jeho vyriešenie. V komentári, ak to považujete za potrebné, vysvetlite, ako celočíselný lineárny program funguje.
  2. Vytvorte funkciu double cchi_bnb(std::vector<std::vector<int>> graph);. V rámci tejto funkcie vytvoríte vlastný branch and bound algorithmus na riešenie problému cirkulárneho chromatického čísla grafu. Tento algoritmus má byť založený na lineárnom programe z prvej úlohy. Vetviť sa budeme na vhodne zvolených celočíselných premenných. Na získanie dolného odhadu použijeme lineárnu relaxáciu lineárneho programu (samozrejme, pre premenné, pre ktoré sme už urobili voľbu musia byť v lineárnom programe primerane nastavené; btw. medzi prvou a druhou úlohou je prienik, snažte sa namiesto skopírovania identického kódu vytvoriť vhodnú pomocnú funkciu). V komentári vysvetlite, ako funguje vaša heuristika na vetvenie (na ktorom vrchole sa vetviť a ktorou vetvou sa vydať skôr).
Riešenie odovzdajte do 1.5. vrátane (v SEČ) majlom na adresu lukotka.pts@gmail.com. Všetky funkcie odovzdajte v jednom súbore, nazvanom chci.cpp. Tento súbor nemá obsahovať funkciu main. V rámci tohoto súboru sa snažte použit includy v takejto forme: #include "lphelper.hpp", #include <lp_lib.h>. Upozoržnujem, neposielajte 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).