Ects : 5

Volume horaire : 18

Volume horaire : 18

Description du contenu de l'enseignement :

Presentation and study of some of some structures and graph problems which have important applications in practice.

Basic notions (handshake lemma, examples of graphs, trees, Connectivity (Menger's theorem), Euler's Tours and Hamilton cycles. Euler's theorem, Dirac's and Ore's theorem)

Cocycles, cocircuits, planar graphs, eccentricity, radius and diameter estimation for very large graphs, vertex cover, independent set

Graph coloring: Definition of node and edge coloring, properties and algorithms for minimum coloring. Relation with stability and clique numbers