Anda ülevaade graafiteooria olemusest ja peamistest tulemustest.

To give an overview on the basic notions and main results of Graph Theory.

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.

Students who pass the course will be able to:
1. understand research papers that contain graph theoretical notions;
2. use graph-theoretical language their own research;
3. recognise classical hard graph-theoretical problems;
4. recognise the graph theoretical problems that are efficiently solvable and are able to solve them algorithmically.

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.

Notion of a graph and its representations. Subgraphs, induced subgraphs. Bipartite graphs. Paths and connectivity. Shortest path. Trees. Labelled trees. Euler cycle/path problem. Hamiltonian cycle/path problem. Travelling salesman problem. Minimum spanning tree problem. Introduction to matroids. Flows in oriented graphs. Max flow min cut theorem. Edge covering problems. Matchings. Berge's theorem. Hall's marriage theorem. König's theorem. Cliques and independent sets. Introduction to Ramsey theory. Edge coloring problems. Vizing's theorem. Planar graphs. Definition of planarity. Euler's formula. Planarity criteria (Kuratowski, Wagner). Vertex coloring. Vertex coloring of planar graphs. Four-color theorem. Chromatic polynomial. Random graphs. Theorems on almost all finite graphs. Countably infinite random graphs. Erdös-Renyi theorem.

Teadmiste kontroll toimub eksami. Eksamile pääsemiseks peavad olema 2 kodutööd arvestatud ja kontrolltöö tehtud vähemalt hindele "kasin" (E, 1).

Examination. To be admitted to the examination, 2 pieces of homework must be passed and a mark of at least “poor” (E, 1) obtained for the test.

32 tundi loenguid + 32 tundi harjutusi + 92 tundi iseseisvat tööd = 156 tundi õppimist.

32 h of lectures + 32 h of practical work + 92 h of independent work = 156 h of study.

Vajalik

-