1. Úvodné pojmy teórie grafov: pojem grafu, podgrafy, významné triedy grafov, sledy, ťahy a cesty, súvislosť, postupnosti stupňov v grafoch. 2. Stromy: charakterizácia stromov, kostra grafu a problém minimálnej kostry. 3. Eulerovké a Hamiltonovské grafy: Eulerovské grafy a ich charakterizácia, postačujúce podmienky pre Hamiltonovské grafy. 4. Farbenia grafov: vrcholové farbenie, hranové farbenie, zovšeobecnené farbenia, známe odhady pre chromatické invarianty grafov. 5. Planárne grafy: Eulerov vzorec a jeho dôsledky, Platónske telesá, charakterizácia planárnych grafov, vrcholové farbenie planárnych grafov. 6. Orientované grafy: orientované sledy, ťahy, cesty a kružnice, silná, unilaterálna a slabá súvislosť, turnaje, acyklické orientované grafy. 7. Problém najkratšej cesty v orientovaných grafoch: Dijkstrov algoritmus. 8. Vybrané problémy teórie grafov: spárenia v bipartitných grafoch, extremálna kombinatorika, Ramseyho čísla a ich odhady.
|
-
Demel, Jiří. (2002). Grafy a jejich aplikace. Academia.
-
Diestel, Reinhard. (2017). Graph Theory 5th ed.
-
Chartrand G., Zhang. P. (2012). A First Course in Graph Theory. Dover Publications.
-
J.A. Bondy, U.S.R. Murty. (2008). Graph Theory. Springer.
-
Jiří Matoušek, Jaroslav Nešetřil. (2000). Kapitoly z diskrétní matematiky. Praha.
|