Zkouska 24.6. Valtr

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
MJS
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 22. 1. 2008 20:08
Typ studia: Matematika Bc.

Zkouska 24.6. Valtr

Příspěvek od MJS »

1. Dokazte nebo vyvratte: Necht T je strom na alespon 3 vrcholech nemajici zadny vrchol stupne 2 a necht C je kruznice prochazejici vsemi listy stromu T (a nemajici zadny dalsi vrchol). Potom pridanim hran kruznice C ke stromu T vznikne 3-souvisly graf.

Pry to jde nejak jakkoliv ukopat.

2. Dokazte nebo vyvratte:
a) Ma-li G HK, potom jeho vrch. souvislost je >=2.
b) Ma-li G dve navzajem hran. disj. HK, potom je 3-souvisly.
c) Ma-li G vsechny stupne sude a > nez 2, potom ma HK.

a) Ano, jednoduche, b) ne, staci najit protipriklad c) ne: staci napr, vzit dvakrat K4,4, coz je nesouvisle a tudiz nema HK

3. Max. tok. na oboustranne zorientovanem K_8 s kapacitami 12.

Jasne = 84

4. Hallova veta + dukaz.

Vsechno za 6 bodu, body ? : >17 >14 >11
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“