Co by studenti a studentky měli znát a umět? Ve zkratce: znát pojmy z přednášek a jejich definice, umět s danými pojmy pracovat. Znát a umět použít algoritmy probrané na přednáškách. Znát základní výsledky z přednášek a umět je využít. Umět sestrojit graf se zadanými vlastnostmi (a případně být schopni rozhodnout, že takový graf neexistuje). Explicitně:
Znát různé definice pojmu (neorientovaného) grafu a chápat, v čem se liší. Umět sestrojit graf s požadovanou strukturou (počet vrcholů a hran).
Znát pojem podgrafu, faktoru, podgrafu indukovaného množinou vrcholů. Chápat, v čem se dané pojmy liší, umět je využívat.
Znát pojem stupně vrcholu v grafu, handshaking lemma, požadavky na počet vrcholů lichého stupně v grafu. Umět sestrojit jednoduché instance grafů s požadovanou strukturou (předepsané stupně vrcholů).
Znát pojem isomorfismu grafů. Umět u jednoduchých instancí rozhodnout, zda jsou grafy isomorfní či nikoli. Umět sestrojit několik neisomorfních grafů s požadovanou strukturou.
Znát pojem kružnice, umět rozhodnout, zda zadaný graf obsahuje kružnici.
Znát pojmy sled, tah, cesta. Umět rozhodnout, zda je něco sled, tah, cesta.
Znát pojem souvislosti grafu. Umět rozhodnout, zda je zadaný graf souvislý.
Znát pojem komponenty souvislosti. Umět sestrojit graf s požadovaným počtem komponent souvislosti (a dalšími omezeními).
Znát pojem vzdálenosti dvou vrcholů. Umět sestrojit graf se zadanými omezeními na vzdálenosti vrcholů.
Znát pojem eulerovského grafu. Umět sestrojit eulerovský/neeulerovský graf (s danými vlastnostmi), umět o zadaném grafu rozhodnout, zda je či není eulerovský.
Znát definici stromu, znát vlastnosti stromů. Umět rozhodnout, zda je zadaný graf stromem či nikoli. Umět sestrojit strom o daných vlastnostech (počet listů, vrcholů daného stupně apod.).
Znát pojem kostry grafu. Umět rozhodnout, zda zadaný graf má kostru či nikoli, umět kostru grafu sestrojit.
Znát pojem minimální kostry ohodnoceného grafu. (Znát pojem ohodnoceného grafu.) Umět nalézt minimální kostru ohodnoceného grafu.
Znát pojem obarvení grafu, k *barevnosti, barevnosti grafu. Umět u jednoduchých příkladů rozhodnout o barevnosti grafu. Umět sestrojit graf s danou barevností a dalšími omezeními (jednoduché příklady). Znát a umět použít algoritmus sekvenčního barvení, znát jeho vlastnosti.
Znát pojem nezávislé množiny v grafu. Znát pojem nezávislosti grafu a základní vlastnosti nezávislosti. Umět najít nezávislost grafu (pro jednoduché příklady), rozhodnout, zda je daná množina vrcholů nezávislá. Umět sestrojit graf s danou nezávislostí (a dalšími omezeními).
Znát pojem kliky a klikovosti. Umět pro jednoduché příklady grafů nalézt jejich klikovost. Umět nalézt v grafu kliky. Umět sestrojit graf s danou klikovostí a dalšími omezeními (jednoduché příklady).
Znát různé definice pojmu orientovaného grafu a chápat, v čem se liší. Umět sestrojit orientovaný graf s požadovanou strukturou (počet vrcholů a hran).
Znát pojem vstupního a výstupního stupně vrcholu v orientovaném grafu. Umět sestrojit orientovaný graf s danou strukturou stupňů vrcholů. Vědět, jak struktura stupňů vrcholů ovlivňuje vlastnosti orientovaného grafu.
Znát pojem orientovaného sledu, tahu, cesty. Znát pojem cyklu, chápat rozdíl mezi kružnicí a cyklem. Znát pojem orientované dostupnosti.
Znát pojem silné souvislosti. Znát pojem silně souvislé komponenty. Umět sestrojit graf se zadanými vlastnostmi týkajícími se orientované dostupnosti (např. graf s daným počtem silně souvislých komponent, který splňuje další vlastnosti). Umět pro jednoduché instance nalézt silně souvislé komponenty orientovaného grafu.
Znát pojem kondensace orientovaného grafu. Umět pro jednoduché instance zkonstruovat kondensaci zadaného orientovaného grafu.
Znát pojem kořene orientovaného grafu. Znát pojem kořenového stromu. Umět zakořenit neorientovaný strom, umět zkonstruovat orientovaný kořenový strom s danými vlastnostmi.
Znát pojem acyklického grafu. Znát základní vlastnosti acyklických grafů, umět sestrojit acyklický graf s danými vlastnostmi. Znát pojem topologického očíslování. Umět nalézt topologické očíslování zadaného grafu.
Umět v jednoduchých případech kombinovat znalosti a schopnosti zmíněné výše.
Umět v jednoduchých případech rozhodnout, zda graf se zadanými vlastnostmi vůbec sestrojit lze.