Graph Theory and Applications

DEPARTMENT OF MATHEMATICS

15101177 GRAPH THEORY AND APPLICATIONS (3ο semester) 5 ECTS

Definitions: graphs, subgraphs, elementary results, trees, enumeration, shortest paths, spanning trees. Paths, Eulerian cycles, Hamiltonian cycles. Matchings, theorem of Hall, theorem of Tutte, augmenting paths, Kuratowski theorem, vertex colourings, the 4-colors theorem, chromatic polynomials. Linear structure of graphs, vector spaces, bases of subspaces, graph matrices, dual graphs, flows. Implementation of algorithms: algorithms of Dijkstra and Prim. Algorithms for the problems on connectivity, trees, planarity, maximum matchings, Chinese postman, chromatic polynomials, and flows.

No textbooks.