Matematické Fórum

Chtel bych upresnit, zda jsem to vubec pochopil spravne.
Zadani zni nasledujicim zpusobem:
Mejme graf G, kde V (G) = (X choose 3) (mnozina vsech triprvkovych podmnozin mnoziny X) a X = [1; 12],
pricemz vrcholy u a v jsou sousedn prave tehdy, kdyz u a v reprezentuji disjunktni mnoziny. Urcete
stupne vsech vrcholu. Muze byt graf G nesouvisly? Sve tvrzeni zduvodnete!

Chapu to tak, ze
a) mam tolik vrcholu, kolik je (12 choose 3), neboli 220.
b) kazdemu vrcholu priradim unikantni oznaceni, ktere je prave mnozinou tri cisel, vybranych z mnoziny X. Tim padem kazdy z 220 vrcholu bude mit svoji jednoznacnou mnozinu cisel.
c) propojim ty vrcholy, ktere maji disjunktni mnoziny, tj. propojim napr. vrcholy {1, 2, 3} a {4, 5, 6}, ale nepropojim {1, 2, 3} a {4, 3, 5}.

Tim padem kazdy vrchol ma stupen (N-3 choose 3), kde N je kardinalita mnoziny X. (Odecteme 3 cisla, ktere patri urcitemu vrcholu a spocitame, kolik mame vrcholu neobsahujicich tyto tri cisla).

Nesouvislost jeste neresim, zatim chci aspon vedet, zda chapu spravne zadani.

Dekuji predem!