Matfiz : DiskrétníZadání

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 pondě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.

Zadání 5

1. Definujte isomorfismus grafů. Nakresli všechny neisomorfní grafy na třech vrcholech. Nakresli všechny neisomorfní stromy na pěti vrcholech.
2. Definujte transitivitu relace. Jsou následující relace transitivní? x R₁ y <=> x > y⁴, x R₂ y <=> x různé od y, x R₃ y <=> x² > y.
3. Kolik je zobrazení z {1, 2, 3, 5} do {4, 5, 6, 8}? Kolik z toho bijekcí?
Binomická věta (bez důkazu).
Kolik je podgrafů C₅?
Dokažte větu o čtyřech barvách pro rovinné grafy, které neobsahují K₃ jako podgraf. Využijte libovolná tvrzení a věty z přednášky, třeba, že rovinný graf bez K₃ nemá příliš mnoho hran a proto má vrcholy malého stupně, postupujte podobně jako u důkazu věty o pěti barvách.

Všechno jsem měl správně, ale pak se mě zeptal ještě, co vím o počtu hran v grafu bez C₄ (nanejvýš 1/2*(n^2/3 + n) ). K tomuhle ze mě dostal už jen, že se to dokazuje pomocí Cauchy-Schwarzovy nerovnosti, tak mě nechal předvést ještě (celý) důkaz Cayleyho formule.

Na stejném termínu byl ještě jeden člověk (nebudu jmenovat) se stejným zadáním, kterého se neptal vůbec na nic >:-o. Pokud se chcete k tomuhle zadání na něco zeptat, rozhodně mi nepište: Adam

Zadání 6

Definujte částečné uspořádání. Máme 3 relace: xR1y <=> x-y je dělitelné pěti; xR2y <=> x=y nebo x-y>3; xR3y <=> x.y>0. Jsou tyto relace částečné uspořádání?
Definujte graf. Kolik existuje grafů na n vrcholech?
Definujte Eulerovský graf. Při jakých hodnotách m,n lze nakreslit úplný bipartitní Eulerovský graf?

Jak vzniknou všechny 2-souvislé grafy?

Odvoďte pomocí Cayleyho formule vzorec pro výpočet všech možných koster úplného grafu s odebráním jedné hrany. (G=Km,n – e a chtěl normální vzoreček,ne žádnou sumu nebo něco podobnýho)

Kolik různých grafů na 9 vrcholech existuje, přičemž každý vrchol má stupen 2 nebo 0?