| Meno: | Samuel |
|---|---|
| Priezvisko: | Vavrek |
| Názov: | Algoritmus na určenie cirkulárneho tokového čísla |
| Vedúci: | doc. RNDr. Robert Lukoťka, PhD |
| Rok: | 2023 |
| Kľúčové slová: | cirkulárne tokové číslo, branch and bound |
| Abstrakt: | Cirkulárny nikde nulový r-tok je priradenie orientácií a reálnych čísel z intervalu < 1, r − 1 > hranám grafu bez mostov tak, že pre každý vrchol je súčet vtekajúcich hodnôt rovný súčtu vytekajúcich hodnôt. Cirkulárne tokové číslo je infimum všetkých hodnôt r, pre ktoré má graf nikde nulový r-tok. Je známe, že pre toto infimum s graf má nikde nulový s-tok a s je racionálne. V tejto práci navrhneme a implementujeme Branch and Bound algoritmus hľadajúci cirkulárne tokové číslo ľubovoľného bezmos- tového grafu, ktorý vnútorne pracuje s celými číslami a jeho výstup je v tvare zlomku, čoho výhodou je numerická stabilita a presnosť. Korektnosť algoritmu budeme testo- vať na grafoch so známymi hodnotami cirkulárneho tokového čísla. Rýchlosť algoritmu budeme porovnávať so zmiešaným lineárnym programom. Na základe výsledkov experi- mentov sa môžeme domnievať, že ďalšou optimalizáciou algoritmu dosiahneme rýchlejší algoritmus ako s použitím solvera pre zmiešané lineárne programovanie. |
Súbory bakalárskej práce:
Autor nedal súhlas so zverejnením svojej bakalárskej práce.
Súbory prezentácie na obhajobe:
| vavrek_obhajoba.pdf |