Oprava 3. zápočtové písemky z Matematiky III. (17. 12. 2007).
Téma: Teorie grafů, [čas 50 minut + dle potřeby]
Jméno a příjmení UČO 1. 2. 3. 4. 5. 6. E
1. [2 body] Následující maticí sousednosti je zadán orientovaný ohodnocený graf:
(
- 8 - 14 - 15 - - ^
- - 1 7 8 - - - -
- - - 1 3 - - 6
- - 7 - 18 5 - 7
17
9 -
- - 7 - - - 20
v /
Nakreslete ho (návod dle tabule) a určete (s použitím Ford-Fulkersonova algoritmu)
maximální tok. Poté určete minimální řez této sítě (tj. nejmenší
množinu hran, po jejímž odebrání oddělíme zdroj od stoku mající tu vlastnost,
že součet kapacit (ne tokových ohodnocení!) těchto odebraných hran je
minimální.) Tuto množinu hran v obrázku jasně vyznačte.
2. [1 bod] Graf z předchozího příkladu si znovu překreslete (tentokrát jako neorientovaný!)
a pomocí vhodného algoritmu určete jeho minimální kostru a v
obrázku jasně vyznačte!
3. [3 body] Nakreslete souvislý graf s 8 vrcholy, který
a) není roviny, není eulerovský, ale je hamiltonovský.
b) není roviny, není hamiltonovský, ale je eulerovský.
c) je hranově 3-souvislý a má jednu artikulace.
4. [2 body] Napište definici izomorfismu grafů G\ a G2. Poté nakreslete takové
grafy G\ a G2, které mají stejné skóre a nejsou izomorfní.
5. [2 body] Dokažte, že existuje (neexistuje) graf o skóre (6,5, 5, 5, 3, 3, 3). Pokud
existuje, tak nějaký s tímto skóre nakreslete. Nakonec rozhodněte (a odůvodněte),
zda existuje roviny graf se zadaným skóre.
6. [Prémie (1 bod)] Je dán graf bez mostů s 21 vrcholy. Určete maximální počet
artikulací, který tento graf může mít. (Zdůvodněte, jak jste k tomuto číslu
došli.)