22
Chapitre 3.Les outils de modélisation et les
méthodes de résolution
Graphe orienté
En théorie des graphes, un graphe orienté C
= (X, A) est défini par la donnée d'un ensemble de
sommets X et d'un ensemble d'arcs A, chaque arc étant un couple
de sommets. Par exemple, si x et y sont des sommets, les
couples (x, y) et (y, x) peuvent être des arcs du
graphe C :
dans ce cas, ils sont notés respectivement xy et
yx.
Chemin
Soit C = (X, U) un graphe,
Un chemin du sommet X0 à Xk dans un
graphe C, est une suite de sommets reliés successi- vement par
des arcs orientés dans le même sens;
On le note : (X0, X1, X2, ...,
Xk)
- Le chemin critique : d'un projet est la plus longue
séquence de tâches qui doit être accomplie pour que le
projet soit terminé à la date due.[3]
Circuit
Le circuit est un chemin simple dont les
extrémités coïncident. (dans les graphes orienté
seulement).
Réseau
Un réseau est un graphe C = (X, U)
muni d'une application d : U R qui à chaque
arc fait correspondre un poids d(u), on note un tel
réseau par R = (X, U, d). On pratique
d(u) peut matérialiser un coût, une distance,
une durée ...etc.
Arbre
Un arbre est un graphe simple connexe ne possédant pas de
cycle. Soit n le nombre de sommets d'un graphe G et m le nombre de ses
arcs:
- Si C est connexe m = n - 1.
- Si C est sans cycles m = n - 1.
Arborescence
Un graphe C = (X, U), avec |X| =
n = 2 sommets est une arborescence de racine s si :
- C est un arbre.
- S est une racine de C.
23
Chapitre 3.Les outils de modélisation et les
méthodes de résolution
Un sommet s d'un graphe G est une racine de
G s'il existe un chemin joignant s à chaque sommet du
graphe G.
Un sommet z d'un graphe G est une
anti-racine de G s'il existe un chemin joignant chaque sommet du
graphe G à z.
Makespan
C'est la date de fin d'exécution de l'ordonnancement
(Cmax).
La mise en ordre d'un graphe (l'ordonnancement d'un
graphe)
Ordonner un graphe revient à disposer dans un certain
ordre ses sommets tels que les arcs soient dans le même sens. On
définit ainsi les différents niveaux des sommets.
L'ordonnancement d'un graphe se traduit par un algorithme.
Recherche du plus court (long) chemin dans un
graphe:
Les problèmes de cheminement dans les graphes (en
particulier la recherche d'un plus court chemin) comptent parmi les
problèmes les plus anciens de la théorie des graphes et les plus
importants par leurs applications.
pour la résolution de ces problèmes,il existe
plusieurs algorithmes qui calcule le plus court (long) chemin,le plus courant
est l'algorithme de Bellman.
L'idée de l'algorithme de Bellman, est de calculer de
proche en proche l'arbores-cence de plus courtes distances, issue du sommet s
à un sommet donné p.
On ne calcule la plus courte distance du sommet s
à y, que si on a déjà calculé les
plus courtes distance du sommet s à tous les
prédécesseurs du sommet y.
3.3.2 Les représentations graphiques
Il y'a principalement deux représentations graphique
d'un projet:
- La représentation AON (Activity-on-Node) ou «
Potentiel-tâches ».
- La représentation AOA (Activity-on-Arrow) ou
«Potentiel-étapes ».
Les abréviations AON et AOA signifient successivement
: Activity On Network et Activity On Arc. Ces deux notions sont
utilisées dans la représentation par le biais d'un réseau
de gestion de projet, à son tour faisant partie d'une branche plus
générale et plus large : La Théorie des Graphes. Cette
dernière est utilisée notamment dans plusieurs domaines comme le
transport, les réseaux neurones ou l'optimisa-tion etc. Ces deux
concepts ont été développés dans les années
50, AON pour établir ce qu'on appelle le chemin critique d'un planning
de projet et AOA dans la méthode
| 
