COMBINATORIAL OPTIMIZATION


GENERAL DESCRIPTION OF THE COURSE

During this course the student will acquire fundamental theoretical and practical knowledge of basic graph theory and optimization algorithms.

Many practical engineering problems can be represented by graphs. Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices or nodes which are connected by edges, lines or arcs (i.e. directed lines). In application to real-world systems, the term network is defined to mean a graph or a digraph (i.e. direct graph) in which attributes (values) are associated with the nodes and/or edges. In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. A similar approach can be taken to problems in social media, travel, biology, chemistry, computer chip design, and many other fields. The development of algorithms to handle graphs is therefore one of major interest.

 

COURSE CONTENTS

The course will cover the following topics:

  • basic graph theory (graph, digraph, weighted graph, network, adjacancy matrix and incidence matrix, isomorphic graphs, trees, Eulerian and Hamiltonian graphs, connectivity, planarity, graph colorings, chromatic number and chromatic index)
  • optimization problems (shortest path problem, long path problem, minnimal spaning tree problem, Eulerian-type problems, Hamiltonian-type problems, problems involving the coloring of the vertices and/or edges)
  • application of algorithms (Shortest path algorithm, Dijkstra’s algorithm, Bellman-Ford algorithm, Long path algorithm, Greedy algorithm, Kruskal’s algorithm, Prim’s algorithm, Fleury’s algorithm)
  • case studies (Chinese postman problem, Travelling salesman problem, project optimization, scheduling)
  • computer exercises (Graphs and applications, Springer)

 

STUDY MATERIALS:

  • M. Aldous, R. J. Wilson: Graphs and Applications, An Introductory Approach, Springer 5th printing, London 2006
  • Kreyszig: Advanced Engineering Mathematics, 10th edition, John Willey and Sons, New York 2011