Přeskočit na hlavní obsah
Přeskočit hlavičku
Platnost příspěvku skončila 31. 10. 2014!

DiMaS - Jiří Fiala: Hledání Hamiltonovských cest v intervalových grafech

 30. 10. 2014, 12:30 - 13:30
 EC3
30.10.2014

V přednášce se budeme zabývat problémem, zdali lze množinu reálných intervalů uspořádat do posloupnosti tak, že každé dva po sobě následující intervaly mají neprázdný průnik. Pro tento problém bude představen algoritmus a s jeho pomocí se ukáže, že jistá zřejmá nutná podmínka pro existenci takového uspořádání je zároveň i postačující.

Jinými slovy, buď daná posloupnost existuje, pak ji lze nalézt a ověřit patřičné vlastnosti; nebo neexistuje a i v tomto případě lze relativně snadno nalézt argument proč ani existovat nemůže. To je jeden z mála případů, kdy má obecně výpočetně těžký problém stručné důkazy pro případy kladných i záporných odpovědí.

Přednáška je určená široké veřejnosti, žádné odborné znalosti z kombinatoriky ani výpočetní složitosti nejsou nutné k porozumění tématu.

Vloženo: 29. 10. 2014
Kategorie:  Chystané akce
Útvar: 470 - Katedra aplikované matematiky
Kontaktní osoby:  doc. Mgr. Petr Kovář, Ph.D.
Zpět