| Academic year 2026/2027 |
| Supervisor: | doc. Ing. Jakub Kůdela, Ph.D. | |||
| Supervising institute: | ÚAI | |||
| Teaching language: | Czech or English | |||
| Aims of the course unit: | ||||
The course aims to acquaint the students with the graph theory and graph-based algorithms that extend the knowledge acquired in subjects courses focused on artificial intelligence, operations research, project management and computer networks and are commonly used to solve problems in engineering and other areas. |
||||
| Learning outcomes and competences: | ||||
|   | ||||
| Prerequisites: | ||||
|   | ||||
| Course contents: | ||||
|   | ||||
| Teaching methods and criteria: | ||||
|   | ||||
| Assesment methods and criteria linked to learning outcomes: | ||||
|   | ||||
| Controlled participation in lessons: | ||||
|   | ||||
| Type of course unit: | ||||
| Lecture | 10 × 2 hrs. | optionally | ||
| Course curriculum: | ||||
| Lecture | 1. Definition of a graph and basic terms. 2. Computer representation of a graph. 3. Time and space complexity of algorithms. 4. Graph searching, backtracking, branch and bound method. 5. Applications of path problems, shortest paths, network graphs. 6. Eulerian trails, Hamiltonian paths and circles. 7. Connected components, trees and spanning trees. 8. Steiner trees. 9. Voronoi diagrams, Delaunay triangulation. 10. Graph colouring, cliques. 11.-12. Network flows. 13. Graph matching. |
|||
| Literature - fundamental: | ||||
| 1. Chartrand, G. and Oellermann, O.R.: Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993. | ||||
| 2. Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.: Introduction to Algorithms. MIT Press, 2001. | ||||
| 3. Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004. | ||||
| 4. Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998. | ||||
| Literature - recommended: | ||||
| 5. Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp. | ||||
| 6. Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991. | ||||
| 7. Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms. Addison Wesley, New York, 2002. | ||||
| The study programmes with the given course: | |||||||||
| Programme | Study form | Branch | Spec. | Final classification | Course-unit credits | Obligation | Level | Year | Semester |
| D-APM-P | full-time study | --- | -- | DrEx | 0 | Compulsory-optional | 3 | 1 | S |
Faculty of Mechanical Engineering
Brno University of Technology
Technická 2896/2
616 69 Brno
Czech Republic
+420 541 14n nnn
+420 726 81n nnn – GSM Telef. O2
+420 604 07n nnn – GSM T-mobile
Operator: nnnn = 1111