Les graphes
![]() |
|
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
- 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
- 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
- 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-régulier, graphe complet, arc
Vous devez être authentifiés pour avoir accès à l'éditeur des exercices de programmation.