Skúška - Kráľ

Vinc at 2007-01-12 17:10:06

Bolo by skvelé, ak by sem každý napísal svoje zadanie zo skúšky... Začínam ja ;)

(1) Definujte, kedy je relácia ekvivalentná. Ktoré z nasledujúcich 3 relácií R_1, R_2, R_3 na množine nenulových celých čísel {..., -2, -1, 1, 2, ...} sú ekvivalencie. (Zdôvodnite)
a) (x,y) patrí R_1 <=> x|y
b) (x,y) patrí R_2 <=> x.y>=0
c) (x,y) patrí R_3 <=> x-y je násobok 7

(2) Sformulujte Spernerovu vetu o maximálnej veľkosti systému nezávislých podmnožín n-prvkovej množiny

(3) Koľko je vzájomne neizomorfných grafov s 9 vrcholmi, ktorých každý vrchol má stupeň 0 alebo 2?

(4) Dokážte, že farebnosť vonkajšieho (český ekvivalent je "vnejškově") rovinného grafu je najviac 3.[/list][/code]