Théorie des graphes 1

  • ECTS

    2 crédits

  • Composante

    Collège Sciences et Technologies pour l’Energie et l’Environnement (STEE)

  • Volume horaire

    19,5h

Description

L’UE est découpée en 2 parties.

La 1ère partie est dédiée à un court historique, associé aux premières définitions (sommets, arêtes ou arcs, avec notamment les premiers théorèmes liés aux degrés des sommets). Nombreux exemples en TD, où il s’agit de modéliser sous forme graphique. On apprend à représenter les graphes grâce aux matrices d’adjacence (avec application en TP, à l’existence de chemin, ou de connexité), ou aux matrices d’incidence (avec application en TP, au calcul de cycles indépendants ou du nombre de composantes connexes), ou aux listes de successeurs, ou prédécesseurs (avec application en TP, au calcul d’arbres en profondeur).

La 2ème partie est liée aux cheminements (chaînes, chemins, cycles, circuits). Plusieurs algorithmes permettent de déterminer les composantes connexes, ou fortement connexes, en utilisant les arbres en profondeur, ou le calcul explicite des fermetures transitives. Les chaînes ou chemins eulériens sont évoqués, et cette partie s’achève sur des propriétés des graphes planaires.

Lire plus

Objectifs

  • Modéliser sous forme graphique un problème (sommet, arc ou arête), et lister les principales propriétés du graphe
  • Identifier le problème à résoudre, à partir du modèle graphique, et l’associer à des grandes classes de problèmes de la théorie de graphes.
  • Représenter le graphe par matrice d’adjacence, d’incidence, ou listes ce graphe
  • Mettre en place des algorithmes permettant de parcourir de manière arborescente en profondeur ces graphes, d’ajouter des numérotations préfixes ou suffixes, de trouver des forêts en profondeur
  • Mettre en place des algorithmes permettant de trouver des composantes fortement connexes : exploitant les arbres de successeurs ou prédécesseurs, ou exploitant la numérotation suffixe, ou exploitant la fermeture transitive.
Lire plus

Heures d'enseignement

  • Théorie des graphes 1 - CMCours Magistral7,5h
  • Théorie des graphes 1 - TDTravaux Dirigés7,5h
  • Théorie des graphes 1 - TPTravaux Pratique4,5h

Pré-requis nécessaires

Algèbre linéaire

Lire plus

Contrôle des connaissances

Évaluation continue intégrale (ECI) 100%

Lire plus

Compétences visées

Bloc 1 

C1.2 Concevoir des algorithmes pour la résolution de problèmes

Débutant

Bloc 2

C2.1 Concevoir des structures de données

Débutant

C2.5 Découvrir, représenter et exploiter des connaissances.

Débutant

Bloc 5

C5.2 Formuler et modéliser des problèmes de systèmes complexes

 

Débutant

Lire plus