Description:

Fundamentals of graph theory. Emphasis is laid on basic concepts, applications and algorithms. From the contents: connectivity, strong conectivity, trees, shortest
paths, flows in networks, Eulerian and Hamiltonian
paths, colorings, independent sets, planar graphs.

Contents:

Basic notions (graphs, vertices, edges, degrees, paths, cycles, etc.).
Applications of path problems.
Searching algorithms (labeling, breath first search, depth first search).
Notions based on undirected paths (connected components, trees, minimal spanning trees).
Notions based on directed paths (strongly connected components, topological sorting, rooted trees, transitive closure).
Shortest path.
Problems related to shortest paths.
Flows in networks.
Application of network flow problems.
Matchings, Assignment problem.
Eulerian graphs, Chinese postman problem.
Hamiltonian paths and cycles. Travelling salesman problem.
Colorings, independent sets and cliques.
Planar graphs.

Seminar contents:

Basic notions (graphs, vertices, edges, degrees, paths, cycles, etc.).
Applications of path problems.
Searching algorithms (labeling, breath first search, depth first search).
Notions based on undirected paths (connected components, trees, minimal spanning trees).
Notions based on directed paths (strongly connected components, topological sorting, rooted trees, transitive closure).
Shortest path.
Problems related to shortest paths.
Flows in networks.
Application of network flow problems.
Matchings, Assignment problem.
Eulerian graphs, Chinese postman problem.
Hamiltonian paths and cycles. Travelling salesman problem.
Colorings, independent sets and cliques.
Planar graphs.

Recommended literature:

Diestel, R.: Graph Theory, Springer, 1996,
Swamy, M., N., S., Thulasiraman, K., Graphs, Networks and Algorithms. New York, John Wiley&Sons, Inc., 1981.
Demel, J.: Graphs and their Applications, (internal material).

Keywords:

Oriented graph, non-oriented graph, graph model.

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar