Názov projektu: A-tokovo kritické grafy
Meno študenta: Gergő Varga
Kontakt na študenta: varga241@uniba.sk
Meno školiteľa: doc. RNDr. Robert Lukoťka, PhD.
Kontakt na školiteľa: lukotka@dcs.fmph.uniba.sk
Opis projektu:
Nech A je abelovská grupa. Nikde nulový A-tok je priradenie orientácie a nenulových hodnôt z grupy A hranám grafu tak, aby v každom vrchole platilo, že súčet hodnôt na hranách vchádzajúcich do vrchola sa rovná súčtu hodnôt na hranách z vrchola vychádzajúcich.
Graf je A-tokovo kritický, ak nemá nikde nulový A-tok, ale po identifikovaní ľubovoľných dvoch vrcholov bude mať nikde nulový A-tok.
Ciele projektu:
- V zimnom semestri je cieľom vytvoriť jednoduchý algoritmus na zistenie, či je daný graf tokovo A-kritický.
- V letnom semestri sa pokúsime tento algoritmus vylepšiť pomocou SAT solverov a zmiešaného lineárneho programovania.