|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (vedoucí práce) ; Sereni, Jean-Sébastien (oponent)
V práci zkoumáme dva náhodné procesy pro kubické grafy velkého obvodu. První proces nalezne pravděpodobnostní distribuci na hranových řezech takovou, že každá hrana je v náhodně vybraném řezu s pravděpodobností alespoň 0.88672. Jako důsledek odvodíme dolní odhad na velikost největšího řezu pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na váhu nejmenšího zlomkového pokrytí hranovými řezy pro kubické grafy velkého obvodu. Druhý proces nalezne pravděpodobnostní distribuci na nezavislých množinách takovou, že každý vrchol je v nezávislé množině s pravděpodobností alespoň 0.4352. Z toho plyne dolní odhad na velikost největší nezavíslé množiny pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na zlomkovou barevnost pro kubické grafy velkého obvodu.
|
|
|
Structural Graph Theory
Zamora, José ; Loebl, Martin (vedoucí práce) ; Sereni, Jean Sébastien (oponent) ; Fiala, Jiří (oponent)
V práci studujeme čtyři problémy ze strukturální teorie grafů. Nejprve se zabýváme strukturou grafů které mají nikde nenulový 5-tok. Podáme charakteri- zaci takových grafů pomocí existence (1, 2)−faktorů. Ve druhé části zavedeme nový typ dekorace vrcholů grafu, kterému říkáme aditivní barvení. Aditivní barvení je injektivní barvení s omezeními danými grafem. Studujeme strukturu grafů které mají tuto dekoraci, a související algoritmické otázky. Ve třetí časti studujeme hypotézu kterou formuloval před asi dvaceti lety R. Stanley: je pravda, že U-polynom rozlišuje neizomorfní stromy? Dokážeme tuto hypotézu pro stromy- housenky bez vrcholů stupně dva. O tento výsledek se v minulých letech snažila řada vědců, například S. Noble. Ve čtvrté části studujeme strukturu nekonečných grafů které mají uplný graf jako minor nebo topologický minor. Klíčová slova: graf, nikde nenulový tok, faktor grafu, barvení grafů, izomorfismus grafů, strom, U-polynom, minor, topologický minor.
|
|
|
Structural Graph Theory
Zamora, José ; Loebl, Martin (vedoucí práce) ; Sereni, Jean Sébastien (oponent) ; Fiala, Jiří (oponent)
V práci studujeme čtyři problémy ze strukturální teorie grafů. Nejprve se zabýváme strukturou grafů které mají nikde nenulový 5-tok. Podáme charakteri- zaci takových grafů pomocí existence (1, 2)−faktorů. Ve druhé části zavedeme nový typ dekorace vrcholů grafu, kterému říkáme aditivní barvení. Aditivní barvení je injektivní barvení s omezeními danými grafem. Studujeme strukturu grafů které mají tuto dekoraci, a související algoritmické otázky. Ve třetí časti studujeme hypotézu kterou formuloval před asi dvaceti lety R. Stanley: je pravda, že U-polynom rozlišuje neizomorfní stromy? Dokážeme tuto hypotézu pro stromy- housenky bez vrcholů stupně dva. O tento výsledek se v minulých letech snažila řada vědců, například S. Noble. Ve čtvrté části studujeme strukturu nekonečných grafů které mají uplný graf jako minor nebo topologický minor. Klíčová slova: graf, nikde nenulový tok, faktor grafu, barvení grafů, izomorfismus grafů, strom, U-polynom, minor, topologický minor.
|
|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (vedoucí práce) ; Sereni, Jean-Sébastien (oponent)
V práci zkoumáme dva náhodné procesy pro kubické grafy velkého obvodu. První proces nalezne pravděpodobnostní distribuci na hranových řezech takovou, že každá hrana je v náhodně vybraném řezu s pravděpodobností alespoň 0.88672. Jako důsledek odvodíme dolní odhad na velikost největšího řezu pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na váhu nejmenšího zlomkového pokrytí hranovými řezy pro kubické grafy velkého obvodu. Druhý proces nalezne pravděpodobnostní distribuci na nezavislých množinách takovou, že každý vrchol je v nezávislé množině s pravděpodobností alespoň 0.4352. Z toho plyne dolní odhad na velikost největší nezavíslé množiny pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na zlomkovou barevnost pro kubické grafy velkého obvodu.
|
host ::
RSS.