Teória grafov

Matematicko-počítačové modelovanie


  1. Základy kombinatoriky. Sčítavací princíp, permutácie, variácie a kombinácie, faktoriály, Stirlingova formula, kombinačné čísla, binomická veta, princíp inklúzie a exklúzie, Dirichletov princíp.

  2. Grafy. Definícia, spôsoby zadania grafu, grafové matice, vzdialenosti v grafe, prehľadávanie do šírky a do hĺbky, stromy.

  3. Prechádzky. Eulerove ťahy, Eulerova veta, Hamiltonovské kružnice, Oreho veta, bloky grafu, nájdenie blokov grafu pomocou prehľadávania do šírky.

  4. Toky a súvislosť. Sieť, tok, úloha o maximálnom toku, Ford-Fulkersonova veta, algoritmus hľadajúci maximálny tok, súvislosť, Mengerova veta.

  5. Rezy a cykly. Priestory rezov z cyklov, bázové rezy a cykly, vetvy, chordy, princíp duality, matice rezov a cyklov, nenulové k-toky, počet kostier grafu.

  6. Matroidy. Úloha o minimovej kostre, Pažravý algoritmus, matroidy, nezávislé množiny, kružnice, rang matroidu, prienik matroidov.

  7. Transverzály. Hallova veta, zovšeobecnená Hallova veta, párovania v párnych grafoch, permanenty.

  8. Párovania. Petersenova veta, Konigova veta, priraďovací problém, párovania vo všeobecnom grafe, Tuttova veta, alternujúce cesty.

  9. Vrcholové farbenia. Definícia, Brooksova veta, Hadwigerova hypotéza, chromatický polynóm, rovinné grafy, Eulerova formula, Kuratowského veta, farebnosť rovinných grafov.

  10. Rozklady grafov. Chromatický index, Vizingova veta, Ramseyove čísla, Erdosova veta, Ramseyova veta.

  11. Zložitosť algoritmov. Deterministický a nedeterministický algoritmus, triedy P a NP, polynomiálna redukcia, niektoré NP-úplné problémy.

  12. Opakovanie.

  13. Opakovanie.

Kľúčové slová: Kombinatorika, graf, strom, Eulerovský ťah, Hamiltonovská kružnica, toky, súvislosť, rezy, cykly, nenulové k-toky, počet kostier grafu, Pažravý algoritmus, matroidy, transverzály, párovania, Hallova veta, permanenty, Petersenova veta, Konigova veta, priraďovací problém, párovania vo všeobecnom grafe, chromatické číslo, chromatický polynóm, farbenia rovinných grafov, chromatický index, Ramseyove čísla, Ramseyova veta, Erdosova veta, zložitosť algoritmov.