Matfiz : Diskrétní Zadání

Toto je stará verze stránky DiskrétníZadání z 2007-01-15 17:17:59..

Nějaké příklady zadání zkoušek pro ty, které diskrétka teprve čeká.

Jinak zkouška probíhá v klidu a míru – dostanete zadání, bez časového presu si řešíte a když si myslíte, že máte hotovo, Valtr přijde a příklady proberete. Pokud se objeví nějaká nejasnost, dostanete čas si věc znova promyslet a až si budete myslet, že už víte, Valtr přijde znova.

Formální oblečení není vůbec potřeba, i Valtr sám přišel tak, jak chodí na přednášky.

Zadání 1

1) Definice:

a) Tranzitivní relace. Definovat, zjistit jestli jsou následující 3 relace tranzitivní: xR1y <=> y=x+1 ; xR2y <=> x-y je sudé číslo ; xR3y <=> x>y/2
b) Kostra grafu. Definovat, nakreslit graf, který má právě 6 koster.
c) 2-souvislost. Definovat, popsat důsledky, předvést rozdíl hranové a vrcholové 2-souvislosti.

2) Problém minimální kostry, popsat a předvést 1 algoritmus bez důkazu správnosti.
3) Kolik existuje neizomorfních grafů na 8 vrcholech, které mají skóre jen z 1 a 2.
4) Nakresli všechny vzájemně neizomorfní grafy se skóre (3,3,3,3,3,3) (+ samozřejmě důkaz že jich víc není. )

Zadání 2

1) Definice:

a) Definujte permutaci na množině X. Dále X = Z (množina celých čísel), rozhodněte zda jsou (a -->> -a), (a -->> a+1) a (a -->> 5a) permutace.
b) Podejte dvě definice stromu. Dokažte, nebo vyvraťte: každý indukovaný podgraf stromu je strom.
c) Definujte souvislý graf. Dokažte, nebo vyvraťte: doplněk každého nesouvislého grafu je souvislý graf.

2) Charakterizujte skóre, podle kterého lze sestrojit graf.
3) Kolik je permutací množiny {1, ..., n} s právě jedním pevným bodem?
4) Charakterizujte grafy, které neobsahují cestu délky tři jako podgraf.

Klíč:
1) Definice neopisuju, ostatní:

a) Potřeba ověřit prostotu a “na”, odpovědi jsou ano, ano, ne (není “na”).
b) Ne (stačí protipříklad).
c) Jo. Ukáže se třeba tak, že nesouvislý graf má nutně dvě komponenty a doplněk je tedy úplný bipartitní graf plus nějaké další hrany. Nebo taky jinak.

2) Věta o skóre tak, jak jsme ji brali. Nakonec chtěl i důkaz.
3) Vyhovujících permutací je n * šatnářka(n-1).
4) Jsou to grafy, kde každá komponenta je «hvězda» v intuitivním slova smyslu plus každá hvězda může mít hrany na svém obvodu (protože kružnice délky tři není cesta délky tři), ale pouze střídavě.