Discrete mathematics  Graph theory and algorithms
[ LINMA1691 ]
5.0 crédits ECTS
30.0 h + 22.5 h
1q
Teacher(s) 
Delvenne JeanCharles (compensates Blondel Vincent) ;
Blondel Vincent ;

Language 
French

Place of the course 
LouvainlaNeuve

Online resources 
> https://icampus.uclouvain.be/claroline/course/index.php?cid=INMA1691

Main themes 
Introduction to the language and theory of graphs : questions of characterization, isomorphism, existence and enumeration. Properties of directed and undirected graphs such as connectivity, planarity, kcolorability and the property of being Eulerian, perfect, etc. Modelling of practical problems : data structures and algorithms for the exploration of graphs. Basic graph algorithms and an analysis of their complexity.

Aims 
Demonstrate the value of graphs as a modelling tool. Develop the basics of graph theory, the characterisation and enumeration of different classes of graphs, the existence and search for optimal subgraphs, the complexity of calculating certain graph parameters.

Content 
Structure and characterization of graphs  basic concepts  degree, connected components, path, cycle, cut, minor, etc. Classes of graphs and their recognition  perfect, series parallel, planar graphs, acyclic digraphs, etc. Exploration of graphs and tests of their properties  kconnected, eulerian, etc. Flows  theorems of Menger and Hall, maximum flow and minimum cost flow algorithms and their complexity. Problems :finding optimal matchings and stable sets, the travelling salesman problem, cut, graph partitioning and graph colouring problems

Bibliography 

Algorithmic Graph Theory, Alan Gibbons, Cambridge University Press 1985

Introduction to Graph Theory, Douglas West, Prentice Hall 1996.

Combinatorial Optimization, W.R. Cook et al., Wiley 1998. Network Flows, Ahuja et al., Prentice Hall 1993.

Cycle et année d'étude 
> Master [120] in Statistics: General
> Master [120] in Computer Science
> Master [120] in Computer Science and Engineering
> Bachelor in Mathematics
> Bachelor in Engineering
> Master [120] in Mathematical Engineering
> Master [120] in Electrical Engineering

Faculty or entity in charge 
> MAP

<<< Page précédente
