Graafi mõiste ja esitused. Alamgraafid ja indutseeritud alamgraafid. Kahealuselised graafid. Teed ja sidusus. Lühim tee. Puud. Märgendatud puud. Euleri ahelad/tsükklid. Hamiltoni ahelad/tsüklid. Rändkaupmehe ülesanne. Minimaalse aluspuu leidmine. Sissejuhatus matroididesse. Vood suunatud graafis. Maksimaalse voo teoreem. Servakatte probleem. Kooskõlad. Berge'i teoreem. Halli abieluteoreem. Königi teoreem. Klikid ja sõltumatud hulgad. Sissejuhatus Ramsey teooriasse. Servade värvimisega seotud probleemid. Vizingi teoreem. Tasandilised graafid. Tasandilisuse definitsioon. Euleri valem. Tasandilisuse tunnused (Kuratowski, Wagner). Tippude värvimine. tasandilise graafi tippude värvimine. Nelja värvi probleem. Kromaatiline polünoom. Juhuslikud graafid. Teoreemid peaaegu kõikidest lõplikest graafidest. Loenduvalt lõpmatud juhuslikud graafid. Erdös-Renyi teoreem.
Kursuse edukalt läbinud üliõpilane
1. suudab lugeda graafiteooria mõisteid ja valemeid sisaldavaid artikleid ning saab nendest aru;
2. oskab kasutada graafiteooriat enda uurimustöödes ja töös;
3. tunneb graafiteooria klassikalisi ja keerulisi probleeme;
4. tunneb graafiteooria hästi lahenduvaid probleeme ja oskab neid algoritmiliselt lahendada.
26. jaanuar - 11. mai 2021
Teisipäeviti 8.15-11.30, Akadeemia tee 15a, ruum ICT-A1
Ainekaardi link
Jälgi meid sotsiaalmeedias: