Obiettivi Formativi

Il modulo si pone tre obiettivi principali: - introdurre lo studente allo sviluppo di metodologie strutturare per modelizzare varie situazioni in termini di grafi - mostrare una serie di soluzioni di problemi tipiche della teoria dei grafi - migliorare le competenze dello studente in termini di analisi e codifica di algoritmi

Learning Goals

The module has three main goals: - introduce the student to the employment of structured methodologies to model various situations in terms of graphs - show a series of solutions to problems typical of the graph theory - increase the proficiencies of the student in terms of both analysis and coding of algorithms

Metodi didattici

Lezioni frontali, svolgimento di esercitazioni in aula e a casa

Teaching Methods

Frontal lectures, discussions of exercises, homeworks

Prerequisiti

Lo studente deve conoscere i fondamenti della programmazione e del corso di Algoritmi (o equivalente)

Prerequisites

The student must know the basics of Programming and Algorithms (or equivalent)

Verifiche dell'apprendimento

L'apprendimento verrà verificato mediante la valutazione di una serie di esercizi da svolgere individualmente a casa e un progetto finale da discutere durante l'esame orale.

Assessment

Learning will be verified through the evaluation of homework exercises and a final project to be discussed during the oral examination.

Programma del Corso

Elementary graph algorithms Representation of graphs Breadth-first search Depth-first search Topological sort Strongly connected components Minimum spanning tree Growing a minimum spanning tree The algorithms of Kruskal and Prim Single-source shortest paths The Bellman-Ford algorithm Single-source shortest paths in directed acyclic graphs Dijkstra's algorithm Difference constraints and shortest paths Proofs of shortest-paths properties All-pairs shortest paths Shortes paths and matrix multiplication The Floyd-Warshall algorithm Johnson's algorithm for sparse graphs Maximum flow Flow networks The Ford-Fulkerson method Maximum bipartite matching Push-relabel algorithms The relabel-to-front algorithm

Course Syllabus

Elementary graph algorithms Representation of graphs Breadth-first search Depth-first search Topological sort Strongly connected components Minimum spanning tree Growing a minimum spanning tree The algorithms of Kruskal and Prim Single-source shortest paths The Bellman-Ford algorithm Single-source shortest paths in directed acyclic graphs Dijkstra's algorithm Difference constraints and shortest paths Proofs of shortest-paths properties All-pairs shortest paths Shortes paths and matrix multiplication The Floyd-Warshall algorithm Johnson's algorithm for sparse graphs Maximum flow Flow networks The Ford-Fulkerson method Maximum bipartite matching Push-relabel algorithms The relabel-to-front algorithm