Course 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 Entry Requirements:

Linear Algebra

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

Teaching methods:

Lecture, conversation, exemplification.

Learning outcomes:

Modelling and solving some medium complexity level problems, using the mathematical and computer sciences knoweledges.

Learning outcomes verification and assessment criteria:

Written paper 50%; mid-term test 30%; seminar activities 20%.

Recommended reading:

-, • Gross, J.L., Yellen, J., Graph Theory and its Applications, CRC Press LLC, 1998, -, -, -, -.
-, • Diestel R., Graph Theory, Springer-Verlag, 1997, -, -, -, -.
-, • Diestel R., Graph Theory, Springer-Verlag, 1997, -, -, -, -.