#### GRAPHS ALGORITHMS

###### Domain: Computer Science • Field of study: Computer Science
 Type of course: Compulsory Language of instruction: Romanian Erasmus Language of instruction: English Name of lecturer: Pax Dorin Wainberg-Drăghiciu Seminar tutor: Pax Dorin Wainberg-Drăghiciu Form of education Full-time
 Form of instruction: Class Number of teaching hours per semester: 56 Number of teaching hours per week: 4 Semester: Summer Form of receiving a credit for a course: Grade Number of ECTS credits allocated 7

#### 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.
-..

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%.