At the end of this course, the students; 1) Learn the basic concepts and techniques of graph theory. 2) Select appropriate models and algorithms of graph theory to solve the problems arising in computer science, engineering and operations research. 3) Learn Euler circuits and related application problems, solve them using algorithms. 4) Have theoretical knowledge on Hamilton circuits. Gain an understanding of the challenges arising in solving the traveling salesman problem. 5) Learn algorithms used for solution of the shortest path problem and compare their computational complexity. 6) Solve the problem of maximum flow. Implement the algorithms for matching and assignment problems. 7) Solve problems by applying the tree algorithms.
MODE OF DELIVERY
Face to face
PRE-REQUISITES OF THE COURSE
No
RECOMMENDED OPTIONAL PROGRAMME COMPONENT
None
COURSE DEFINITION
Graphs and graph models, connected graphs. Multigraphs and digraphs. Isomorphic graphs. Trees, the minimum spanning tree problem. Connectivity. Eulerian graphs. Hamiltonian graphs. Matchings and factorization. Planarity and planar graphs. Coloring graphs, the four color problem. Vertex coloring, edge coloring. Matrices and graph algorithms. Flows and cuts, constructing maximal flows.
COURSE CONTENTS
WEEK
TOPICS
1st Week
Graphs and graph models, connected graphs.
2nd Week
Multigraphs and digraphs.
3rd Week
Isomorphic graphs.
4th Week
Trees, the minimum spanning tree problem.
5th Week
Connectivity. Eulerian graphs.
6th Week
Hamiltonian graphs.
7th Week
Matchings and factorization.
8th Week
Mid-term
9th Week
Planarity and planar graphs.
10th Week
Coloring graphs, the four color problem.
11th Week
Vertex coloring, edge coloring.
12th Week
Matrices and graph algorithms.
13th Week
Flows and cuts, constructing maximal flows.
14th Week
Flows and cuts, constructing maximal flows.
RECOMENDED OR REQUIRED READING
1. Buckley F., Lewinter M., Friendly introduction to Graph Theory, Prentice Hall, 2003 2. Grimaldi R.P., Discrete and Combinatorial Mathematics, 5/E, Addison Wesley, 2003 3. Rosen K.H., Discrete Mathematics and Its Applications, 6/E, McGraw-Hill, 2007
