|
|
Minimal counterexamples to flow conjectures
Korcsok, Peter ; Šámal, Robert (vedoucí práce) ; Goodall, Andrew (oponent)
Říkáme, že graf má nikde-nulový k-tok, pokud umíme každé hraně přiradit její směr a přirozené číslo (<k) jako tok tak, aby pro každý vrchol $v$ byl celkový přítok a odtok stejný. Tutte vyslovil v roce 1954 hypotézi, že každý graf bez mostů má nikde-nulový 5-tok, a tato hypotéza je stále otevřená. Kochol v nedávné práci představil výpočetní metodu na dokázání, že minimální protipříklad nemůže obsahovat krátkou kružnici (až do délky 10). V této práci poskytujeme ucelený přehled této metody a protože Kochol nezveřejnil svou implementaci (a pro nezávislé ověrení metody), doplňujeme náš zdrojový kód, ktorý potvrzuje Kocholovy výsledky a rozšiřuje je: dokázali jsme, že minimální protipříklad neobsahuje kružnici kratší než 12. Powered by TCPDF (www.tcpdf.org)
|
|
|
Minimal counterexamples to flow conjectures
Korcsok, Peter ; Šámal, Robert (vedoucí práce) ; Goodall, Andrew (oponent)
Říkáme, že graf má nikde-nulový k-tok, pokud umíme každé hraně přiradit její směr a přirozené číslo (<k) jako tok tak, aby pro každý vrchol $v$ byl celkový přítok a odtok stejný. Tutte vyslovil v roce 1954 hypotézi, že každý graf bez mostů má nikde-nulový 5-tok, a tato hypotéza je stále otevřená. Kochol v nedávné práci představil výpočetní metodu na dokázání, že minimální protipříklad nemůže obsahovat krátkou kružnici (až do délky 10). V této práci poskytujeme ucelený přehled této metody a protože Kochol nezveřejnil svou implementaci (a pro nezávislé ověrení metody), doplňujeme náš zdrojový kód, ktorý potvrzuje Kocholovy výsledky a rozšiřuje je: dokázali jsme, že minimální protipříklad neobsahuje kružnici kratší než 12. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.