Zkouška 5.2.2007 - Kráľ

Xerxes
Matfyz(ák|ačka) level I
Příspěvky: 37
Registrován: 23. 1. 2007 16:32
Typ studia: Informatika Bc.
Bydliště: Zlínský kraj / Kolej 17. listopadu
Kontaktovat uživatele:

Zkouška 5.2.2007 - Kráľ

Příspěvek od Xerxes »

1. Definujte pojem třídy ekvivalence. Rozhodněte, zdali je následující relace R ekvivalencí na množině celých čísel a pokud ano, popište její třídy ekvivalence:

xRy <=> 3 dělí (x + 2y)

2. Popište problém minimální kostry, algoritmus pro jeho řešení a dokažte jeho správnost.

3. Ukažte, že následující graf G = (V, E) není rovinný, kde V = {1, 2, ..., 15}, E = {{i, j}: i - j je sudé a |i - j| >= 4}.

4. Mohou mít dva garfy G<sub>1</sub> a G<sub>2</sub> stejné skóre, jestliže:

(a) G<sub>1</sub> je 2-souvislý, G<sub>2</sub> není souvislý,
(b) G<sub>1</sub> je strom, G<sub>2</sub> je 2-souvislý,
(c) G<sub>1</sub> není rovinný, G<sub>2</sub> je kružnice,
(d) G<sub>1</sub> není rovinný, G<sub>2</sub> je strom?

Řešení, koho by zajímalo:

1. Po ověření všech tří axiomů vyjde, že jde o ekvivalenci, která rozloží množinu celých čísel do tří tříd ekvivalence podle zbytku po dělení třemi.

2. Bez komentáře.

3. Nejprve je nutné si uvědomit, které vrcholy jsou vlastně spojené hranou. Jde o takové vrcholy, jejichž čísla mají sudý rozdíl alespoň 4. V zadaném grafu jsou tedy hranou spojeny ty vrcholy, které mají rozdíl čísel 4, 6, 8, 10, 12 nebo 14.

Graf není rovinný, protože obsahuje K<sub>3,3</sub> jako podgraf. Například vrcholy 1, 3, 5 tvoří první partitu a 11, 13, 15 druhou. Je snadné ověřit, že rozdíl čísel každých dvou vrcholů z různých partit je sudý a alespoň 4, vrcholy jsou tedy spojeny hranou.

4. Je nutné buď najít příklad, kdy mají oba grafy stejné skóre, nebo dokázat, že ho nemůžou mít stejné nikdy.

(a) Ano. Například C<sub>6</sub> je 2-souvislý, graf tvořený dvěma oddělenými C<sub>3</sub> je nesouvislý a oba mají skóre (2,2,2,2,2,2).

(b) Ne. Strom obsahuje alespoň dva vrcholy stupně 1. 2-souvislý graf ale nemůže obsahovat žádný vrchol stupně 1, protože po odebrání jeho jediného souseda by se ocitl ve své vlastní komponentě, což by byl spor.

(c) Ne. Nerovinný graf musí obsahovat dělení K<sub>3,3</sub> nebo K<sub>5</sub> jako podgraf. V prvním případě by obsahoval vrchol stupně alespoň 3, ve druhém dokonce 4. Na druhou stranu kružnice má pouze stupně 2.

(d) Ano. Například K<sub>3,3</sub> a vedle něj 4 samostatné úsečky P<sub>1</sub> je graf jistě nerovinný (i když nesouvislý). Má skóre (3,3,3,3,3,3,1,1,1,1,1,1,1,1). Strom s takovým skóre je snadné sestrojit. Stačí vzít úsečku, na oba konce připojit po dvou dalších a na jejich konce zase po dvou na každou.

Snad nemám nikde chybu, když tak mi řekněte.
Odpovědět

Zpět na „2006“