Streda - Akvarium IX - 9:00-9:45 (3iai)
Streda - Akvarium XI - 12:20-13:05 (3it)
Konzultacne hodiny:
po dohode.
Informacie:
Pisomka, ktora mala byt sucastou cviceni sa presuva na skusku. Skuska sa
bude skladat s troch casti - domace ulohy, priklady, teoria (ustne).
Domace ulohy
DU1: Komplement jednoducheho grafu G je graf, ktory ma rovnake vrcholy ako graf G,
avsak hrany ma prave tie, ktore graf G nema. Graf G nazveme autokomplementarny, ak
je jeho komplement izomorfny s G. Zistite, na akom pocte vrcholov existuju
samokomplementarne grafy. Ak sa vam nepodari vyriesit problem vseobecne, vyrieste ho aspon
pre mensie pocty vrcholov.
DU2: Dokazte alebo vyvratte: Z kazdeho stromu vieme urobit bipartitny graf s rovnako
velkymi particiami iba zmazanim niekolkych jeho listov.
DU3:
Zistie, pre ktore k platia nasledovne tvrdenia:
Ak k>=2, potom pre kazdy vrcholovo k-suvisly graf plati, ze lubovolnych k vrcholov lezi na spolocnej kruznici.
Ak k>=2, potom pre kazdy hranovo k-suvisly graf plati, ze lubovolnych k vrcholov lezi na spolocnej kruznici.
DU4:
Nech G je Cayleyho graf/vrcholovo tranzitivny graf/hranovo tranzitivny (arc-transitive) graf stupna d. Zistite, ci je tento graf
d-vrcholovo-suvisly/d-hranovo suvisly.
Rozhodnite o vsetkych 6 tvrdeniech, ci su pravdive.
Dalej zistite, ci je kazdy Cayleyho graf hranovo tranzitivny.
DU5:
Urcte chromaticky index kompletneho k-partitneho grafu, ktoreho kazda particia ma n vrcholov.
Ak si nebudete vediet rady, sustredte sa najma na pripady
k=1,2,3.
DU6:
Charakterizujte grafy, ktoré sa dajú hranovovo zafarbit dvoma farbami (nie nutne regulárne) tak, že v každom vrchole sú prítomné obe farby.