Grafy a kombinatorika

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Předmět si klade za cíl seznámit studenta s nejdůležitějšími partiemi teorie grafů, kombinatorických principů a struktur, diskrétních modelů a algoritmů. Kromě pochopení teoretických principů bude kladen důraz i na aplikaci poznatků při řešení úloh a navrhování algoritmů. Mezi probíraná témata patří technika generujících funkcí, vybrané partie z barevnosti grafů a hypergrafů, Ramseyovské věty, úvod do pravděpodobnostních technik a studium vlastností různých speciálních tříd grafů a kombinatorických struktur.

Požadavky:

Předpokládají se znalosti srovnatelné s obsahem předmětů Algoritmy a grafy I. a II. (BI-AG1 a BI-AG2).

Osnova přednášek:

1. Generující funkce.

2. Generující funkce a barevnost.

3. Perfektní grafy.

4. Úvod do Ramseyovy teorie.

5. Ramseyova teorie, Tutteova věta a Edmondsův algoritmus.

6. Počet koster: Lineární algebra v kombinatorice.

7. Extremální věty.

8. Pravděpodobnostní metoda.

9. Pravděpodobnostní metoda.

10. Kuratowského věta.

11. Kreslení grafu na plochách.

12. Vybíravost a hranová barevnost.

Osnova cvičení:

1. Opakování pojmů z teorie grafů a kombinatoriky

2. Generující funkce.

3. Barevnost kombinatorických struktur.

4. Lineární algebra v kombinatorice: věta o počtu koster.

5. Úvod do Ramseyovy teorie.

6. Jazyky a grafy; Rauzyho graf.

7. Úvod do pravděpodobnostní metody.

8. Lovaszovo lokalní lemma a aplikace.

9. Extremalní teorie grafů.

10. Kuratowského věta a další otázky rovinnosti grafů.

11. Tutteova věta a Edmondsův algoritmus.

12. Perfektní grafy a chordalní grafy.

13. Teorie nestranných kombinatorických her.

14. Grafové algoritmy v kombinatorice na slovech a bioinformatice.

Cíle studia:

Předmět si klade za cíl seznámit studenta s nejdůležitějšími partiemi teorie grafů, kombinatorických principů a struktur, diskrétních modelů a algoritmů. Kromě pochopení teoretických principů bude kladen důraz i na aplikaci poznatků při řešení úloh a navrhování algoritmů. Mezi probíraná témata patří technika generujících funkcí, vybrané partie z barevnosti grafů a hypergrafů, Ramseyovské věty, úvod do pravděpodobnostních technik a studium vlastností různých speciálních tříd grafů a kombinatorických struktur.

Studijní materiály:

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

2. Valla, T. - Matoušek, J. : Kombinatorika a grafy. ITI Series, 2005.

3. Bollobas, B. : Modern Graph Theory. Springer, 1998. ISBN 0-387-98488-7.

4. Graham, R. L. - Knuth, D. - Patashnik, O. : Concrete Mathematics. Addison-Wesley, 1994. ISBN 978-0-201-55802-9.

Poznámka:

Předmět je vyučován v češtině.

Další informace:

https://courses.fit.cvut.cz/NI-GAK/

Pro tento předmět se rozvrh nepřipravuje

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

• Mgr. specializace Počítačová bezpečnost, 2026 (VO)
• Mgr. specializace Počítačové systémy a sítě, 2026 (VO)
• Mgr. specializace Teoretická informatika, 2026 (PS)
• Mgr. specializace Programovací jazyky, 2026 (VO)
• Mgr. specializace Umělá inteligence, 2026 (VO)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2026 a vyšší (VO)
• Master programme, for the phase of study without specialisation, ver. for 2026 and higher (VO)