Meno:Ján
Priezvisko:Kováč
Názov:Rozšíriteľnosť párení na grafoch
Vedúci:Michal Kotrbčík, Martin Škoviera
Rok:2012
Blok:INF
Kľúčové slová:equimatchable graf, rozšíriteľnosť párení, karteziánsky súčin grafov, chordálny graf, prienikový graf fundamentálnych cyklov
Abstrakt:V našej práci sa zaoberáme rozšíriteľnosťou párení na grafoch. V prvej časti skúmame štruktúru equimatchable grafov, teda grafov v ktorých každé nerozšíriteľné párenie je aj najväčšie, pričom naše hlavné výsledky sú nasledujúce tvrdenia. Uvádzame charakterizáciu grafov $H$, pre ktoré platí, že $H\#T$ je equimatchable pre každú kostru $T$ grafu $H$, kde $H\#T$ označuje prienikový graf fundamentálnych cyklov. Ukázali sme, že pre každý equimatchable chordálny graf $G$, ktorý nie je faktorovo kritický, existuje graf $H$ taký, že $H\#T$ je izomorfný s $G$ pre každú kostru $T$ grafu $H$. Pre karteziánske súčiny grafov sme dokázali, že ak $G$ a $H$ sú súvislé grafy s aspoň dvomi vrcholmi, tak karteziánsky súčin $G$ a $H$ je equimatchable práve vtedy, keď $G$ aj $H$ sú izomorfné s $K_2$. Ďalej sme ukázali, že ak $H_1$ a $H_2$ sú ľubovoľné faktorovo kritické grafy s rovnakým počtom vrcholov, tak pre ľubovoľný graf $G$ platí, že najväčšie párenie grafu $G \Box H_1$ má rovnakú mohutnosť ako najväčšie párenie grafu $G \Box H_2$. V druhej časti zavádzame nový koncept rozšíriteľnosti párení: graf $G$ patrí do triedy $\Delta_n$ práve vtedy, ak rozdiel mohutností ľubovoľných dvoch nerozšíriteľných párení grafu $G$ je najviac $n$. Naše hlavné výsledky v tejto časti sú nasledovné tvrdenia. Popisujeme štruktúru grafov z triedy $\Delta_n$ a presne charakterizujeme triedu $\Delta_1$. Zostrojili sme deterministický polynomiálny algoritmus, ktorý pre pevne zvolené $n$ a $k$ overí, či graf s deficienciou najviac $k$ patrí do triedy $\Delta_n$. Uvádzame algoritmus, ktorý v deterministickom polynomiálnom čase rozhodne, či daný graf patrí do triedy $\Delta_1$.

Súbory diplomovej práce:

uvod.pdf