Overview
Aims
Our aims in this course are twofold. First, to discuss some of the major results of graph theory, and to provide an introduction to the language, methods and terminology of the subject
Second, to emphasize various approaches (algorithmic, probabilistic, etc.) that have proved fruitful in modern graph theory: these modes of thinking about the subject have also proved successful in areas of informatics.
-..
Course contents
1. Preliminaries. General notions. 2. Basic concepts in Graph Theory. Cyclomatic number 3. Graph traversal. Breadth First Traversal. Depth First Traversal 4. Minimum distances in graphs 5. Connected components 6. Bipartite graphs. Maximum matching problem in a bipartite graph 7. Hamiltonian paths and circuits . Chen algorithm. Foulkes algorithm. Kaufmann algorithm 8. Flow networks. Bellman-Kalaba algorithm. Ford algorithm. Dijkstra algorithm 9. Maximum flow in transport networks 10. Trees. Deffinitions and theorems. 11. Traversal of a dirrected tree 12. Trees of minimum values. Kruskal algorithm. Sollin algorithm 13. Binary trees 14. Structural trees
Learning outcomes
Modelling and solving some medium complexity level problems, using the mathematical and computer sciences knoweledges.
Assessment
Written paper 50%; mid-term test 30%; seminar activities 20%.