Teorie grafů

Garant předmětu:

Jiří Demel

Přednášející:

Jiří Demel

Cvičící:

Jiří Demel

Předmět zajišťuje:

katedra inženýrské informatiky

Anotace:

Teorie grafů - základní pojmy, formulace grafových úloh, základní algoritmy řešení se zřetelem na efektivnost výpočtu.

Požadavky:

Nejsou

Osnova přednášek:

Základní pojmy, sled, tah, cesta,

grafové modely reálných problémů, eulerovské tahy,

algoritmy prohledávání do šířky a do hloubky,

souvislost, silná souvislost,

acyklické grafy, topologické uspořádání,

stromy a kořenové stromy,

úloha o minimální kostře,

nejkratší cesty,

toky v sítích,

párování, přiřazovací úloha,

hamiltonovské cesty a kružnice,

nazávislost, barevnost, kliky,

rovinné grafy.

Osnova cvičení:

Základní pojmy, sled, tah, cesta,

grafové modely reálných problémů, eulerovské tahy,

algoritmy prohledávání do šířky a do hloubky,

souvislost, silná souvislost,

acyklické grafy, topologické uspořádání,

stromy a kořenové stromy,

úloha o minimální kostře,

nejkratší cesty,

toky v sítích,

párování, přiřazovací úloha,

hamiltonovské cesty a kružnice,

nazávislost, barevnost, kliky,

rovinné grafy.

Cíle studia:

Schopnost používat graf jako vyjadřovací prostředek k modelování reálných situací, schopnost řešit základní grafové úlohy.

Studijní materiály:

!Demel, J.: Grafy a jejich aplikace, 2002, Academia Praha, ISBN 80-200-0990-6; 2. vydání vlastním nákladem 2015, ISBN 80-260-7684-1

Poznámka:

Rozvrh na zimní semestr 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost TH:B-476 14:00–15:50 (přednášková par. 1) Thákurova 7 (budova FSv) B476místnost TH:B-476 16:00–17:50 (přednášková par. 1 paralelka 101) Thákurova 7 (budova FSv) B476
Út
St
Čt
Pá

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Geodézie a kartografie, specializace Geomatika (povinně volitelný předmět)