|
|
Petersenovské obarvení a jeho varianty
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Petersenovské obarvení 3-regulárního grafu G je ekvivalentní tzv. normálnímu obarvení za použití pěti barev. Normální obarvení je dobré hranové obarvení ta- kové, že každá hrana je spolu se svými čtyřmi sousedy obarvena dohromady třemi nebo pěti různými barvami. Podle Jaegerovy hypotézy lze každý 3-regulární graf bez mostů petersenovsky obarvit. Platnost hypotézy by dokázala další zajímavá tvrzení pro 3-regulární grafy. V tomto textu se budeme zabývat normálním obar- vením pro větší počet barev. Z Jaegerovy věty o nenulovém Z2 3 -toku plyne, že každý graf bez mostů lze normálně obarvit sedmi barvami. Zde dokážeme exis- tenci obarvení devíti barvami pro grafy s mostem, s řezem velikosti dva nebo s trojúhelníkem nezávisle na Jaegerově větě. Důkaz využívá myšlenku Andersenova důkazu existence silného hranového obarvení 3-regulárních grafů deseti barvami. V závěru řekneme, jak by mohl jít důkaz dokončit pro zbylé třídy 3-regulárních grafů. 1
|
|
|
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)
|
|
|
Petersenovské obarvení a jeho varianty
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Petersenovské obarvení 3-regulárního grafu G je ekvivalentní tzv. normálnímu obarvení za použití pěti barev. Normální obarvení je dobré hranové obarvení ta- kové, že každá hrana je spolu se svými čtyřmi sousedy obarvena dohromady třemi nebo pěti různými barvami. Podle Jaegerovy hypotézy lze každý 3-regulární graf bez mostů petersenovsky obarvit. Platnost hypotézy by dokázala další zajímavá tvrzení pro 3-regulární grafy. V tomto textu se budeme zabývat normálním obar- vením pro větší počet barev. Z Jaegerovy věty o nenulovém Z2 3 -toku plyne, že každý graf bez mostů lze normálně obarvit sedmi barvami. Zde dokážeme exis- tenci obarvení devíti barvami pro grafy s mostem, s řezem velikosti dva nebo s trojúhelníkem nezávisle na Jaegerově větě. Důkaz využívá myšlenku Andersenova důkazu existence silného hranového obarvení 3-regulárních grafů deseti barvami. V závěru řekneme, jak by mohl jít důkaz dokončit pro zbylé třídy 3-regulárních grafů. 1
|
host ::
RSS.