Teorie grafů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh

Kód	Zakončení	Kredity	Rozsah	Jazyk výuky
11Y1TG	KZ	2	2P+0C	česky

Garant předmětu:

Lucie Kárná

Přednášející:

Lucie Kárná

Cvičící:

Lucie Kárná

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

Základní grafové pojmy, formalizace popisu grafů, způsoby reprezentace grafu. Úlohy teorie grafů, instance, zadání. Prohledávání grafu, minimální kostra grafu, stromy, nejkratší dráha, Eulerovské tahy, párování v bipartitních grafech, toky v sítích, cirkulace, kritická cesta, úloha obchodního cestujícího. Algoritmy řešení existenčních a optimalizačních úloh. Výpočetní složitost, přístup k řešení NP-těžkých úloh, heuristické postupy.

Požadavky:

Znalost základních pojmů z teorie grafů.

Osnova přednášek:

Osnova cvičení:

Cíle studia:

Student prohloubí své znalosti z teorie grafů. Seznámí se se základními pojmy a problémy z oblasti algoritmizace úloh. Setká se s klasickými úlohami teorie grafů a algoritmy pro jejich řešení. Nahlédne do problematiky časové náročnosti a efektivity algoritmů.

Studijní materiály:

Demel, J: Grafy a jejich aplikace, Praha, Academia, 2002

Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Praha, Karolinum, 2009

Poznámka:

Rozvrh na zimní semestr 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

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

2.bl.bak.prez.DS 09/10začátek (povinně volitelný předmět)
2.bl.bak.prez.ME 09/10začátek (povinně volitelný předmět)
2.bl.bak.prez.AI 09/10začátek (povinně volitelný předmět)
2.bl.bak.prez.LD 09/10 (povinně volitelný předmět)
2.bl.bak.prez.DS 05/06 začátek (povinně volitelný předmět)
2.bl.bak.prez.ME 05/06 začátek (povinně volitelný předmět)
2.bl.bak.prez.AI 05/06 začátek (povinně volitelný předmět)
2.bl.bak.prez.LD 05/06začátek (povinně volitelný předmět)
2.bl.bak.prez.DS 06/07 začátek (povinně volitelný předmět)
2.bl.bak.prez.ME 06/07 začátek (povinně volitelný předmět)
2.bl.bak.prez.AI 06/07 začátek (povinně volitelný předmět)
2.bl.bak.prez.LD 06/07 začátek (povinně volitelný předmět)
2.bl.bak.prez.DS 07/08začátek (povinně volitelný předmět)
2.bl.bak.prez.AI 07/08začátek (povinně volitelný předmět)
2.bl.bak.prez.ME 07/08začátek (povinně volitelný předmět)
2.bl.bak.prez.LD 07/08začátek (povinně volitelný předmět)
2.bl.bak.prez.DS 08/09začátek (povinně volitelný předmět)
2.bl.bak.prez.AI 08/09začátek (povinně volitelný předmět)
2.bl.bak.prez.LD 08/09začátek (povinně volitelný předmět)
2.bl.bak.prez.ME 08/09začátek (povinně volitelný předmět)
2.bl.bak.prez.DS 10/11začátek (povinně volitelný předmět)
2.bl.bak.prez.ME 10/11začátek (povinně volitelný předmět)
2.bl.bak.prez.AI 10/11začátek (povinně volitelný předmět)
2.bl.bak.prez.LD 10/11 (povinně volitelný předmět)
2.bl.bak.pres.DS (povinně volitelný předmět)
2.bl.bak.prez.AI (povinně volitelný předmět)
2.bl.bak.prez.LD (povinně volitelný předmět)
2.bl.bak.prez.ME (povinně volitelný předmět)
AUT bak.prez.11/12 (povinně volitelný předmět)
DOS bak.prez.11/12 (povinně volitelný předmět)
ITS bak.prez.11/12 (povinně volitelný předmět)
LED bak.prez.11/12 (povinně volitelný předmět)
MED bak.prez.11/12 (povinně volitelný předmět)
AUT bak. prez.12/13 (povinně volitelný předmět)
DOS bak.prez.12/13 (povinně volitelný předmět)
MED bak.prez.12/13 (povinně volitelný předmět)
ITS bak.prez.12/13 (povinně volitelný předmět)
LED bak.prez.12/13 (povinně volitelný předmět)
AUT bak.prez.13/14 (povinně volitelný předmět)
DOS bak.prez.13/14 (povinně volitelný předmět)
ITS bak.prez.13/14 (povinně volitelný předmět)
LED bak.prez.13/14 (povinně volitelný předmět)
MED bak.prez.13/14 (povinně volitelný předmět)
DOS bak.prez.13/14 (SKOK) (povinně volitelný předmět)
LED bak.prez.13/14 (SKOK) (povinně volitelný předmět)
MED bak.prez.13/14 (SKOK) (povinně volitelný předmět)
DOS bak.prez.14/15 (povinně volitelný předmět)
MED bak.prez.14/15 (povinně volitelný předmět)
AUT bak.prez.14/15 (povinně volitelný předmět)
ITS bak.prez.14/15 (povinně volitelný předmět)
LED bak.prez.14/15 (povinně volitelný předmět)
DOS bak.prez.15/16 (povinně volitelný předmět)
MED bak.prez.15/16 (povinně volitelný předmět)
AUT bak.prez.15/16 (povinně volitelný předmět)
ITS bak.prez.15/16 (povinně volitelný předmět)
LED bak.prez.15/16 (povinně volitelný předmět)
BEZ bak.prez.15/16 (povinně volitelný předmět)
DOS bak.prez.16/17 (povinně volitelný předmět)
LOG bak.prez.16/17 (povinně volitelný předmět)
ITS bak.prez.16/17 (povinně volitelný předmět)
LED bak.prez.16/17 (povinně volitelný předmět)
BEZ bak.prez.16/17 (povinně volitelný předmět)
DOS bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
DOS bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
LOG bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
LOG bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
ITS bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
ITS bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
LED bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
LED bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
BEZ bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (povinně volitelný předmět)
BEZ bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (povinně volitelný předmět)
LOG bak.prez.17/18 - včetně 11FYZ v 3.s. (povinně volitelný předmět)
LED bak.prez.17/18 - včetně 11FYZ v 3.s. (povinně volitelný předmět)
DOS bak.prez.18/19 (povinně volitelný předmět)
LOG bak.prez.18/19 (povinně volitelný předmět)
ITS bak.prez.18/19 (povinně volitelný předmět)
LED bak.prez.18/19 (povinně volitelný předmět)
DOS bak.prez.18/19 (skok do 3.r.) (povinně volitelný předmět)
CŽV pro LED bak.prez. v 18/19 (povinně volitelný předmět)
LOG bak.prez.18/19 (skok do 3.r.) (povinně volitelný předmět)
ITS bak.prez.18/19 (skok do 3.r.) (povinně volitelný předmět)
LED bak.prez.18/19 - skok z 2.r.do 3.r. (povinně volitelný předmět)
LED bak.prez.19/20 angličtina (povinně volitelný předmět)
DOS bak.prez.19/20 (povinně volitelný předmět)
LOG bak.prez.19/20 (povinně volitelný předmět)
ITS bak.prez.19/20 (povinně volitelný předmět)
LED bak.prez.19/20 (povinně volitelný předmět)
ITS bak.prez.19/20 (skok do 3.r.) (povinně volitelný předmět)
DOS bak.prez.19/20 (skok do 3.r.) (povinně volitelný předmět)
LED bak.prez.19/20 (skok do 3.r.) (povinně volitelný předmět)
LED bak.prez.20/21 angličtina (povinně volitelný předmět)
DOS bak.prez.20/21 (povinně volitelný předmět)
LOG bak.prez.20/21 (povinně volitelný předmět)
LOG bak.prez.20/21 (skok do 3.r.) (povinně volitelný předmět)
ITS bak.prez.20/21 (povinně volitelný předmět)
ITS bak.prez.20/21 (skok do 3.r.) (povinně volitelný předmět)
LED bak.prez.20/21 (povinně volitelný předmět)
LED bak.prez.20/21 (skok do 3.r.) (povinně volitelný předmět)
LED bak.prez.21/22 (skok do 3.r.) (povinně volitelný předmět)
DOS bak.prez.21/22 (skok do 3.r.) (povinně volitelný předmět)
LOG (obor) bak.prez.21/22 (skok do 3.r.) (povinně volitelný předmět)
ITS bak.prez.21/22 (skok do 3.r.) (povinně volitelný předmět)
DOS bak.prez.21/22 (povinně volitelný předmět)
ITS bak.prez.21/22 (povinně volitelný předmět)
LED bak.prez.21/22 (povinně volitelný předmět)