### Course Syllabus

### Title

Graph Theory and Algorithms

### Teacher(s)

Prof. Gianluca della Vedova

Prof. Marco Viviani

### Language

English

### Short description

The course is an introduction to Graph Theory, without a specific application in mind.

Lecture plan:

- Introduction to Graph Theory: What is a graph? Basic concepts. Connectivity (connected components, reachability, biconnected components, spanning trees, bipartite graphs)
- Walks, Paths, Trials, Cycles (Hamiltonian cycles, Eulerian cycles, TSP)
- Graph Matching (perfect matching, algorithm on bipartite graphs)
- Graph Decomposition (Modular decomposition, cographs)
- Graph Coloring (perfect graphs). Treewidth, pathwidth, Twin-width
- Graph Compression
- Graph Embedding and Hyperbolicity
- Graph Mining (Intro & Graph Indexing)
- Graph Mining (Graph Summarization & Graph Classification)
- Graph Partitioning (and Clustering) & Complex Networks (graphs to represent complex systems and networks, small-world)

### CFU / Hours

2.5 credits/20 hours

### Teaching period

May 2021