Elementary Introduction to Graph Theory

poslední změna: 18-10-2017

Synopsis

The course provides an explanation of basics graph theory followed by a survey of common graph algorithms.

Source Materials

Final exam

  • Format: Written exam. You will be given 6 questions (usually 2 theoretic and 4 algorithmic).

  • Type: Open book, i.e. you can bring any written material you want (e.g. lecture notes, printouts, books), but it is strictly forbidden to use any electronic devices.

Detailed outline

date lecture
6.10. Graph. Isomorphism. Degree (minimal and maximal). Handshaking lemma. Graphic sequence. Characterization of graphic sequences (Havel's theorem).
13.10. Walk, path, closed walk, cycle. Connected graphs. Adjacency matrix. Graph traversal: Tarry and Trémaux's algorithms.