Un traceur de graphes pour TI-Nspire et Terminales ES Spé

[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

[Levak]

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.

Ce classeur n'est pas fait pour les élèves de terminale mais pour les études supérieures.
Par ailleurs, bien que le nom n'est pas le même que tu as donné, il y a le plus court chemin avec http://fr.wikipedia.org/wiki/Algorithme_de_Balas-Hammer et une méthode matricielle dont je ne me souviens plus du nom puisque c'était l'année dernière.
Ensuite, quand on modifie graph.a dans le classeur, ça calcule automatiquement graph.i, sauf que je sais plus non plus à quoi ça correspond.

[critor]

C'est bien ce que je dis et ça reste donc à forker et à adapter à notre public.
Nulle intention pour moi toutefois, d'insinuer que c'est toi qui dois te le taper.

Quant au plus court chemin, ce n'est pas le bon algorithme pour des Terminale.
Il faut prendre Dijkstra.

[critor]

Commencé à regarder quelles fonctions utiles rajouter pour les Terminales ES Spé Maths et Terminales S Spé ISN (même si il n'y a pas d'examen terminal écrit dans ce dernier cas).

Déjà, ai simplifié le traceur pour alléger la sortie écran dans le cas d'arêtes non orientées (aller et retour de même pondération).
Dans ce cas-là, la pondération n'est affichée qu'une seule fois, et les flèches ne sont pas dessinées.

Fonctions rajoutées pour tous les graphes:

• test si le graphe est orienté
• test si le graphe est pondéré
• degré d'un sommet

Même si c'est limite hors programme, dans le cas des graphes orientés possibilité avec un paramètre de distinguer les degrés entrant et sortant - le degré d'un sommet étant alors défini comme la somme des deux.


Il manque encore nombre de choses, ainsi qu'une interface pour rendre le tout facile d'accès - mais c'est ce qui sera fait en dernier.

[Hayleia]

Pas mal déjà
Juste une question cependant, les sommets sont placés sur un polygone régulier à chaque fois où ils sont placés plus intelligemment en fonction des arêtes ? Et s'ils sont placés sur un polygone régulier, est-ce que le placement intelligent est prévu pour une future mise à jour (même en bas de la todo list) ?

[critor]

Pour l'instant, ce sera toujours un polygone régulier.
C'est d'ailleurs la méthode de tracé utilisée dans une majorité de sujets de BAC ES Spé Maths.

Le dessin 'intelligent' d'un graphe est un problème complexe qui fait l'objet de plusieurs thèses.

[Hayleia]

Ah c'est donc pour ça que je n'avais pas réussi à trouver d'idée pour l'implémenter quand j'en avais besoin et que j'ai moi aussi dû me "restreindre" aux polygones réguliers
En fait je demandais pour savoir si je pouvais jeter un oeil au code si c'était intelligent, mais bon

[Levak]

Ah c'est donc pour ça que je n'avais pas réussi à trouver d'idée pour l'implémenter quand j'en avais besoin et que j'ai moi aussi dû me "restreindre" aux polygones réguliers
En fait je demandais pour savoir si je pouvais jeter un oeil au code si c'était intelligent, mais bon

En o(n⁴) tu as un algo minimaliste, sur la base du polygône régulier, en inversant simplement des sommets suivant leur meilleure position sur ce dernier (minimisant les intersections d'arêtes). C'est jouable pour une dizaine de noeuds grand maxi.

[critor]

On continue:


Au programme:

• précise si le graphe non orienté est connexe
• précise si le graphe orienté est faiblement ou fortement connexe
  (hors programme Spé ES)
• précise si le graphe est simple (sans boucle)
• précise si le graphe est un arbre (non orienté sans cycle)
• dans le cas des graphes non orientés, signale la présence ou l'abscence d'un cycle eulérien ou à défaut d'une chaîne eulérienne
• dans le cas des graphes orientés, signale la présence ou l'abscence d'un circuit eulérien ou à défaut d'un chemin eulérien
  (hors programme Spé ES)

Comme en Spé ES on voit à la fois les graphes orientés et non orientés, je n'ai pas le choix que de gérer les deux cas si je veux faire les choses proprement.
Les parties hors programme viennent du fait que le programme de la Spécialité ES s'intéresse à la résolution de questions complètement différentes selon que l'on est sur un graphe orienté ou non orienté.


Manquent à ce jour pour la Spé ES:

• cas non orienté:
  
  • nombre chromatique
  • plus court chemin selon Dijkstra
• cas orienté:
  
  • état de rang n donné
  • recherche d'un état stable

[critor]

Le script Lua dispose maintenant d'une interface pour justifier la présence ou l'absence de chaîne/chemin/cycle/circuit eulérien :