2. Diplômes
3. Licence informatique
4. Licence 3
5. Semestre 5
6. TC
7. Theorie-des-graphes
8. Structure de graphes

Structure de graphes

Objectifs

L'objectif de ce cours est de se familiariser avec  la notion de graphes.

Lors de ce cour seront vus des concepts utiles et fondamentaux
en théorie des graphes. Le point de vue adopté sera combinatoire
et algorithmique.

 

 

Plan du cours

 

1. Définitions et Notations
2. Graphes Eulériens
   1. Définition.
   2. Décomposition en cycles (Théorème de Veblen).
   3. Condition nécéssaire et Suffisante.
   4. Algorithme de Fleury.
3. Parcours de graphes
   1. Parcours générique
   2. Parcours en Largeur
      1. Applications au plus courts chemins dans les graphes univalués.
      2. Reconnaissance des graphes bipartis.
   3. Parcours en Profondeur
      1. Tri topologique
      2. Composantes fortements connexes
      3. Graphes 2-connexes et décomposition en blocs

Description des TP

Prise en main de la plateforme SageMath

Implémantations des algorithmes de parcours.

 

Connaissances requises

Méthodes Discrètes / Logique; N2 Informatique.

RSE (Responsabilité Sociale et Environnementale)

Bibliographie

A remplir