English
Docent Tomáš Kaiser, pracovník Fakulty aplikovaných věd Západočeské univerzity v Plzni, obhájil před komisí Matematické struktury disertaci „Circuits and Matchings in Graphs“ a získal vědecký titul „doktor fyzikálně-matematických věd“. Disertace je komentovaným souborem 16 prací publikovaných v mezinárodních časopisech a zaměřených na hamiltonovskou teorii grafů a strukturu párování v grafech.
Kontext disertace vymezují dva hluboké otevřené problémy teorie grafů. Prvním z nich je hypotéza C. Thomassena o hamiltonovských kružnicích v hranových grafech, formulovaná v roce 1986. Hypotéza souvisí s obecnou otázkou, zda graf s dostatečně vysokou souvislostí musí obsahovat hamiltonovskou kružnici (kružnici procházející všemi vrcholy). Pro takto položenou otázku není obtížné najít příklady grafů, pro které je odpověď záporná. Pokud se nicméně omezíme na třídu tzv. hranových grafů, situace se změní a Thomassenova hypotéza tvrdí, že již 4-souvislé hranové grafy (tedy souvislé hranové grafy, které zůstanou souvislé i při odstranění libovolné množiny nejvýše tří vrcholů) obsahují hamiltonovskou kružnici.
Druhou motivaci disertační práce představuje tzv. Berge-Fulkersonova hypotéza, kterou poprvé publikoval D. R. Fulkerson v roce 1971. Týká se tzv. kubických grafů (tedy grafů, v nichž z každého vrcholu vycházejí tři hrany), a to konkrétně takových, které se nedají rozdělit na dvě navzájem nepropojené komponenty odstraněním jediné hrany (grafy „bez mostů“). Již od konce 19. století je známo, že takové grafy obsahují perfektní párování, tedy množinu hran pokrývající každý vrchol právě jednou. Ekvivalentní verze slavné věty o čtyřech barvách (dokázané v roce 1976 za významné pomoci počítače) říká, že každý kubický graf bez mostů, který se dá nakreslit v rovině bez křížení hran, je možné rozdělit na tři perfektní párování. Pro nerovinné grafy – tedy pro ty, pro něž takové nakreslení neexistuje – nemusí existovat ani zmíněné rozdělení na perfektní párování. Berge-Fulkersonova hypotéza nicméně tvrdí, že v libovolném takovém grafu existuje šest perfektních párování, která pokrývají každou hranu právě dvakrát.
V práci zkoumám obě uvedené hypotézy z různých úhlů. Ve vztahu k Thomassenově hypotéze je do disertace zařazen zejména společný článek s Petrem Vránou (kolegou ze Západočeské univerzity v Plzni), kde se ukazuje, že 5-souvislé hranové grafy, ve kterých z každého vrcholu vychází alespoň šestihran, obsahují hamiltonovskou kružnici. Jde o nejlepší známý výsledek ve směru Thomassenovy hypotézy a pro jeho odvození bylo potřeba problém reformulovat v řeči tzv. hypergrafů. Hledání korektní formulace důkazu si vyžádalo několik let soustředěného úsilí. Další výsledky (získané společně s různými spoluautory) se týkají například tzv. dominujících kružnic v grafech typu snark nebo hamiltonovských kružnic v intervalových grafech.
Z Berge-Fulkersonovy hypotézy snadno vyplývá, že hrany každého kubického grafu bez mostů se dají pokrýt pěti perfektními párováními. I tento důsledek je dosud otevřeným problémem; jeden z výsledků zahrnutých v disertaci se vztahuje k otázce, jakou maximální část množiny hran je možné v takových grafech pokrýt pomocí dvou nebo tří perfektních párování. Část práce věnovaná struktuře párování zahrnuje také výsledky týkající se tzv. Fan-Raspaudovy hypotézy nebo cirkulárního hranového barvení.
TOMÁŠ KAISER,
Západočeská univerzita v Plzni