Písemná část zkoušky bude obsahovat následující úlohy,
přičemž nejvyšší možný zisk bude 100 bodů, z nichž je třeba
získat alespoň polovinu:


Použít algoritmus na daném grafu (2x10 bodů):
  Dijkstrův algoritmus,
  nalezení vzdáleností všech dvojic vrcholů,
  určení počtu sledů dané délky,
  počítání pravděpodobnosti v markovském řetězci,
  hledání největších toků (algoritmus Edmondse a Karpa),
  hledání největšího párování,
  hledání koster nejmenší váhy,
  počítání chromatického polynomu.

Dát příklad grafu daných vlastností nebo zdůvodnit jeho neexistenci
(3x5 bodů).

Dát příklad grafu s daným skóre, který má danou vlastnost (2x5 bodů).

Najít všechny vzájemně neizomorfní grafy daných vlastností (10 bodů).

Určit, zda jsou dané dva grafy izomorfní, nebo zda je jeden
podgrafem (případně indukovaným podgrafem) druhého (8 bodů).

Rozhodnout o rovinnosti daného grafu a případně jej doplnit
na maximální rovinný graf (7 bodů).

Pro každý graf z dané nekonečné třídy určit hranovou a vrcholovou
souvislost, hranové a vrcholové chromatické číslo a zda je
eulerovský či hamiltonovský (10 bodů).

Formulovat požadovanou definici (5 bodů).

Formulovat požadované tvrzení (5 bodů).

Dokázat jednoduché tvrzení (10 bodů).


Ke zvládnutí úloh o vlastnostech grafů bude třeba ovládat
následující pojmy a základní tvrzení o nich:
podgraf, indukovaný podgraf,
stupeň vrcholu, regularita, sled, tah, cesta, kružnice,
bipartitní graf, eulerovský graf, hamiltonovský graf,
hranová a vrcholová souvislost, most, bod artikulace,
blok, blokový strom, hranové a vrcholové chromatické číslo,
rovinný graf, stěna.