Logo ČVUT
Loading...
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2011/2012

Teorie grafů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah
PI-TGR ZK 4 0+3
Přednášející:
Jan Kratochvíl (gar.), Jan Kratochvíl (gar.)
Cvičící:
Jan Kratochvíl (gar.), Jan Kratochvíl (gar.)
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Studovány budou jak strukturální otázky tak otázky algoritmizace a složitosti základních optimalizačních úloh na speciálních třídách grafu. Z hlediska výpočetní složitosti bude pozornost věnována hranici mezi polynomiální řešitelností a NP-težkostí jednotlivých variant studovaných úloh.

Požadavky:

Vseobecné znalosti z diskretni matematiky a teorie algoritmu pokryte prednaskami Zaklady diskretni matematiky (BI-ZDM) a Efektivni algoritmy (BI-EFA).

Osnova přednášek:

1. Speciální trídy grafu a algoritmy na nich. Pro mnohé speciální trídy grafu jsou nekteré obecne tezké (NP-tezké) úlohy resitelné v polynomiálním case. Zmíneny budou intervalové, chordální a perfektní grafy a dalsí grafy s geometrickymi reprezentacemi.

2. Stromové struktury. Rada optimalizacních úloh resitelnych v polynomiálním case pro stromy je resitelná i pro grafy, jejichz struktury se stromum v jistém smyslu blízí (stromovy zdvih, cestny zdvih, klikovy zdvih). Téz obecné metody vypoctu na grafech omezeného zdvihu.

3. Pokrocilá témata z oblasti barevnosti. Barevnost patrí k základním invariantum grafu. Probrány budou moderní koncepty jako je seznamová barevnost, vybíravost, hranová barevnost. Pozornost bude venována i tzv. Problému pridelování frekvencí, ktery motivoval zavedení ruznych vzdálenostne omazujících typu barvení grafu.

4. Toky a rezy. Teorie toku v sítích, minimaxové vety, aplikace na mnozinové systémy (Hallova veta), souvislost grafu a sítí.

5. Náhodné grafy. Modely náhodnych grafu, jejich vlastnosti a vyvoj. Pravdepodobnostní dukazy a algoritmy. Pseudonáhodné grafy. Vlastnosti tzv. webového grafu.

6. Vizualizace grafu. Prístupy a metody pouzívané v oblasti „Graph Drawing“ - rovinné grafy, kreslení grafu s predem povolenymi prusecíky, kreslení grafu na malou mrízku. Vizualizace a prohledávání velkych grafu.

Osnova cvičení:
Cíle studia:

Cílem předmětu je podat přehled o moderních metodách teorie grafů.

Studijní materiály:

1.R. Diestel, Graph Theory, 3rd edition, Springer, 2005.

2.M.C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Freeman, New York 1980.

3.L. Kucera: Kombinatorické algoritmy, SNTL, 1989.

4.Schrijver: Combinatorial Optimization, Springer, 2003.

Poznámka:
Rozvrh na zimní semestr 2011/2012:
Rozvrh není připraven
Rozvrh na letní semestr 2011/2012:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 9. 7. 2012
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1602206.html