Graph Theory

The course is an introduction to a fundamental branch of mathematics, graph theory. Its aim is to provide students with essential knowledge of graphs, enabling the seamless use of theoretical concepts and methodologies in practical problems and applications within computer science, information systems, and human-centered applications.

The syllabus is designed to introduce students to the basic concepts and key results of graph theory, while familiarizing them with a wide range of related notions through everyday examples. At the same time, through exercises and practical assignments, students will be encouraged to explore essential graph analysis tools that are available online.

By the end of the course, students are expected to have acquired the fundamental knowledge of graph theory, to be able to recognize when and how these concepts can be applied in various applications, and to make effective use of available tools, validating the results against the corresponding theoretical expectations.

The course covers the fundamental concepts and definitions of graphs as mathematical objects. It introduces a wide range of topics such as connectivity, cycles and paths, cuts, planarity, graph coloring, random walks, and node clustering. In each thematic area, the basic definitions of the key notions are presented, each problem is formally defined (e.g., graph coloring, finding an Eulerian cycle, etc.), and important theorems and algorithms are introduced. These serve as useful tools for students in subsequent courses in the Department of Informatics.

At the level of weekly teaching organization, the content is structured as follows:

Week 1:
Basic definitions: graphs, subgraphs, etc.

Week 2:
Basic definitions: paths & cycles

Week 3:
Trees – Graph connectivity (graph traversal, flows, and cuts)

Week 4:
Distances and routes in graphs

Week 5:
Eulerian and Hamiltonian graphs

Week 6:
Planar graphs

Week 7:
Graph coverings

Week 8:
Algebraic graph theory: adjacency matrix, Laplacian matrix, eigenvalues and eigenvectors of the adjacency matrix

Week 9:
Graph coloring

Week 10:
Perfect matchings in graphs

Week 11:
Random walks on graphs

Week 12:
Clustering in graphs

Week 13:
Review and practice with sample exercises

1. Θεωρία και Αλγόριθμοι Γράφων, Ιωάννης Μανωλόπουλος, Απόστολος Παπαδόπουλος, Κωνσταντίνος Τσίχλας.
2. ΑΛΓΟΡΙΘΜΙΚΗ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ, ΣΤΑΥΡΟΣ ΝΙΚΟΛΟΠΟΥΛΟΣ, ΓΕΩΡΓΙΑΔΗΣ ΛΟΥΚΑΣ, ΠΑΛΗΟΣ ΛΕΩΝΙΔΑΣ
3. Graph Theory [electronic resource], Reinhard Diestel

Class lectures + problem set examples

• Use of electronic notes
• Teaching support through the e-class online platform

Final written exam + problem sets