Matfiz : Diskrétní Zadání

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

Nějaké příklady zadání zkoušek pro představu 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.

Malá poznámka: zadání se zřejmě opakují, na zkoušce v podnělí 17.1. jsem dostal naprosto stejné zadání jako Martin Ziegler, který (jak soudím dle data zápisu do wiki) dělal zkoušku už v pátek 15.1.

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.

Pokud se chcete k tomuhle zadání něco zeptat, klidně mi napište: MartinZiegler?.

Tak sem taky nejake zadani pridam:

Zadání 3

1) a) Definujte ekvivalenci na mnozine X. Jsou nasledujici relace ekvivalence? X = Z \ {0}: (x|y; xy>=0; x-y je nasobek 7).
{PS, na to co byla ekvivalence, tak se jeste priptal, kolik to ma trid ekvivalence}
b) Definujte permutaci na mnozine X. Pro X = {1,2,3,4,5,6,7} urcete kolik je permutaci suda na suda a zaroven licha cisla na licha.
Kolik je permutaci suda na licha a licha na suda?
c) Definujte indukovany podgraf. Najdete graf na 6 vrcholech jehoz vsechny podgrafy jsou indukovane.
2) Princip inkluze a exkluze. (Asi i dukaz, ja jsem to teda i dokazovala)
3) Qn = (V,E). Vrcholy jsou n-prvkove posloupnosti nul a jednicek. Mezi dvema vrcholy vede hrana, prave tehdy, lisi-li se prave v jedne
souradnici. Rozhodnete pro ktera n se da nakreslit 1 tahem bez opakovani hran. (U tohoto prikladu jsem rikala i nastin dukazu, kdy je graf Eulerovsky)
4) (2,3,3,3,3,3..) {n-1 trojek} Rozhodnete pro ktera n je to skore grafu.

Pokud chcete neco vedet k tomuhle zadani, tak mi klidne napiste: KateřinaBöhmová.

Zadání 4

1. a) Definujte skóre grafu. Jakou nejvyšší sumu skóre lze získat? Vyjádřete pomocí n.
b) Definujte zobrazení. Jsou následující relace zobrazením (množiny X a Y jsou s přirozenými čísly)?
i) xRy právě tehdy když x dělí y
ii) xRy právě tehdy když x^4 – y^2 = 0
iii) xRy právě tehdy když x+1-y^2 = 0
c) Definujte eulerovský graf. Jaké existují bipartitní eulerovské grafy Km,n ?
2. Zformulujte a dokažte (a zdůvodněte) princip inkluze a exkluze (původně Spernerova věta – nebude vyžadovat – nebrali jsme).
3. Spočtěte SUMA (k přes 0 do n) ( 2n nad 2k )
4. Najděte rovinný graf, který má nejvíce stěn + zdůvodnění a vyjádření pomocí n.

Pokud chcete neco vedet k tomuhle zadani, tak mi klidne napiste: KarelVandas.