[critor]

Beaucoup de problèmes de mathématiques et de sciences reviennent à l'étude de graphes, que l'on associe en mathématiques à des matrices dites d'adjacence. Selon le contexte, ces graphes peuvent être pondérés ou non, orientés ou non.

On peut citer par exemple les probabilités conditionnelles, dont les problèmes se résolvent usuellement en traçant des arbres binaires pondérés, cas particuliers de graphes pondérés que l'on représente usuellement en traçant une arborescence ou une étoile en partant de la racine.
Les participants à notre Grand Prix de Programmation 2014 nous ont sorti de très beaux programmes à ce sujet.

Lorsque nous avons affaire à des graphes non arborescents (présentant des cycles) pas trop complexes, une méthode de représentation consiste à répartir équitablement les sommets sur un cercle. Le programme à compléter dans le cadre de notre concours de chasse au Wumpus incluait un tel traceur.



Dans le contexte qui nous intéresse aujourd'hui, ce traceur de graphes quelconques présentait plusieurs inconvénients:

• non utilisable de façon indépendante du programme du Wumpus
• ne gère pas les graphes pondérés ou orientés
• ne respecte pas exactement les conventions de représentation des graphes

Mais heureusement, Levak nous sort aujourd'hui un traceur de graphes exploitant le même algorithme, et palliant à tous ces inconvénients :

• gestion des graphes pondérés et non pondérés
• gestion des graphes orientés et non orientés
• respect des conventions des représentation des graphes

Il vous suffira donc de saisir la matrice associée à votre graphe, et ce dernier sera automatiquement dessiné - une fonctionnalité pouvant être fort utile au secondaire aux Terminales ES spécialité Mathématiques !

Toutefois, il manquera encore nombre de fonctions à inclure avant de parfaitement répondre aux attentes de ce public. Entre autres, possibilité de demander :

• l'ordre du graphe
• le type du graphe (simple, orienté, pondéré, arbre, complet, connexe...)
• le degré d'un sommet
• l'existence de chaînes et cycles eulériens ou hamiltonniens
• le plus court chemin entre deux sommets
• des informations sur le nombre chromatique
• à partir d'un état initial :
  
  • l'état de rang n donné
  • l'état stable si existant
• ...

Outre le codage de tous ces 'petits' algorithmes il faudrait également inclure une interface d'édition de graphes, car il est assez rare que les sujets de BAC commencent par donner la matrice d'adjacence - le plus souvent c'est au candidat de la trouver à partir du graphe représenté sur le sujet.


Mais cela reste quand même une grande avancée, qui on l'espère saura évoluer d'ici le BAC ES 2015 - merci Levak !


Téléchargement : archives_voir.php?id=83718