LES GRAPHES

Un graphe est en ensemble de noeuds relies par des liens. Ce n'est plus un arbre des qu'il existe deux parcours differents pour aller d'au moins un noeud a un autre. Un graphe est connexe lorsqu'il est possible de trouver au moins un parcours permettant de relier les noeuds deux a deux (un arbre est un graphe connexe, deux arbres forment un graphe non connexe). Un graphe est dit pondere lorsqu'a chaque lien est associee une valeur (appelee poids). On utilisera un graphe pondere par exemple pour gerer des itineraires routiers (quelle est la route la plus courte pour aller d'un noeud a un autre), pour gerer des fluides (noeud relies par des tuyauteries de diametre different) ou pour des simulations de trafic routier, pour simuler un circuit electrique, pour prevoir un ordonnancement dans le temps de taches... Un graphe est dit oriente lorsque les liens sont unidirectionnels. Nous ne traiterons pas ici en detail les algorithmes associes aux graphes, mais nous aborderons quelques problemes rencontres.

On peut representer un graphe de maniere dynamique, comme les arbres (le nombre de liens par noeud est souvent variable). Une autre solution est de numeroter les N sommets, et d'utiliser une matrice carree NxN, avec en ligne i et colonne j un 0 si les noeuds i et j ne sont pas relies, ou le poids de la liaison sinon (1 pour les graphes non ponderes). Pour des graphes non orientes, la matrice est symetrique (par rapport a la diagonale), ce qui permet d'economiser de la memoire mais peut compliquer les programmes (c'est la technique employee pour les elements finis). Une representation par matrice est surtout interessante lorsqu'il y a beaucoup de liens (graphe presque complet), la representation a l'aide de pointeurs etant moins gourmande en memoire pour les graphes comportant peu de liens par noeud.

Un probleme important est le parcours d'un graphe : il faut eviter les boucles infinies, c'est a dire retourner sur un noeud deja visite et repartir dans la meme direction. On utilise par exemple des indicateurs de passage (booleens), ou une methode a jetons (on place des "jetons" dans differents noeuds bien choisis et on les fait suivre les liens). Une methode souvent utilisee est de rechercher avant tout (et une seule fois) l'arbre recouvrant : c'est un arbre permettant de visiter tous les noeuds, n'utilisant que des liens existants dans le graphe (mais pas tous). Cet arbre recouvrant n'est evidement pas unique. En cas de graphe non connexe, il faut rechercher plusieurs arbres recouvrants.

On peut remarquer qu'un arbre recouvrant d'un graphe connexe a N sommets aura necessairement N-1 liens. Pour les graphes ponderes, on peut rechercher l'arbre recouvrant de poids minimum (somme des poids des liens minimale). Differents algorithmes existent pour traiter ce probleme.