Graphes (UGA)

Les graphes

Modélisation à l'aide des graphes Notions de base sur les graphes Représentations des graphes Quelques graphes célèbres

• Compétences

  1. Modélisation à l'aide de graphe
  

  • Reconnaitre un problème pratique qui peut être modélisé à l'aide de graphe
  • Modéliser un problème pratique à l'aide d'un graphe

  2. Notions de base sur les graphes
  

  • Identifier et décrire un isomorphisme 
  • Reconnaitre les principales variantes aux graphes simples : boucle, graphe orienté, mutigraphe, étiquetage 
  • Ecrire des preuves simples sur des propriétés des degrés 

  3. Représentation des graphes
  

  • Présenter un graphe dans différentes représentation : graphique, matrice d'adjacence, matrice d'incidence, liste d'adjacence 
  • Décrire un algorithme pour passer d'une représentation machine (matrice ou liste) à l'autre 
  • Choisir la représentation la plus adaptée (coût temps et espace) à un problème 

  4. Implémentation d'algorithme simples sur les graphes
  

  • Comprendre le fonctionnement de la classe Graphe.java
  • Implémenter quelques manipulations des graphes en java 

  
  Vocabulaire :  graphe, sommets, arêtes, ordre, complémentaire, auto-complémentaire, extrémité d'une arête, arête incidente à un sommet, sommets voisins, sommet isolé, voisinage d'un sommet, degré d'un sommet, graphe $k$-régulier, graphe complet, arc

  Notations : $G, V, E, n, m, d(v), N(v), K_n$

  ---

• Transparents d'introduction sur les graphes File
• Feuille d'exercices File
• ---

• Vous devez être authentifiés pour avoir accès à l'éditeur des exercices de programmation.
  

• Test sur les graphes Quiz
• Prise en main de la classe Graphe (listes d'adjacence) - Java Virtual programming lab
• Javadoc de Graphe.java File
• Prise en main de la classe Graphe (matrice d'adjacence) - Java Virtual programming lab