| 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$.
|
|---|