| Abstrakt: | Témou tejto diplomovej práce je problém nájdenia zmyslu pre orientáciu v grafe, kde počet značiek priradených hranám grafu je čo najmenší. Práca skúma topológie hyperkociek a zovšeobecnených Petersenových grafov. Na týchto topológiách sa zameriava na chordálny zmysel pre orientáciu. Hľadajú sa podtriedy týchto grafov, na ktorých existuje minimálny chordálny zmysel pre orientáciu, čím sa vylúčia tie, v ktorých neexistuje a následne sa určujú horné a spodné ohraničenia pre počet značiek. V práci dokazujeme, že hyperkocky nemajú minimálny chordálny zmysel pre orientáciu a určujeme ohraničenia najmenšieho počtu značiek pre dosiahnutie chordálneho zmyslu pre orientáciu. V triede zovšeobecnených Petersenových grafov nachádzame niekoľko podtried a určujeme ich najmenší zmysel pre orientáciu, resp. ohraničenia. V malom rozsahu sa venujeme aj výpočtovým metódam, ktoré, hoci málo úspešné, dávajú podnety na ďalšie skúmanie problematiky.
|
|---|