Chapitre 3 • Éléments de la théorie des graphes
70
Mais un graphe n’est pas tou jours un réseau repré sen tant des cir -
cu la tions quel conques.
Sou vent, une flèche (arc) entre deux points implique seule ment
une rela tion de suc ces sion : par exemple, le graphe (figure 3.10)
peut vou loir dire seule ment que A pré cède B, qui, lui- même, pré -
cède C. Une pro priété évi dente, dans ce cas, est la tran si ti vité. Si A
pré cède B et B pré cède C, alors A pré cède C ; mais on n’a pas besoin
de l’indi quer par une flèche sup plé men taire entre A et C.
Si dans cette inter pré ta tion, on abou tit à une figure (figure 3.11)
compor tant un cir cuit, le pro blème n’est pas cohé rent, car on ne sau -
rait avoir à la fois : A pré cède C (par tran si ti vité) et C pré cède A. Les
graphes des pro blèmes d’ordon nan ce ment pré sen tés plus loin ne sau -
raient compor ter de cir cuit.
On dit qu’un graphe est valué si, à tout arc qui le consti tue, cor -
res pond une valeur numé rique, qu’on écrit seule ment, sur la figure, à
proxi mité de cet arc. Ces valeurs peuvent être des quan ti tés tran spor tées, des débits,
des coûts, des durées, etc.
Signa lons que les graphes per mettent de repré sen ter aisé ment les « sys tèmes » pou -
vant se trou ver dans des « états », les chan ge ments d’états étant des « tran si tions ». Tout
état est alors repré senté par un som met, toute tran si tion par un arc. Nous ren contre rons
plus loin des exemples de sys tèmes états/tran si tions : il s’agira des chaînes de Markov,
puis des pro ces sus de Markov. Un autre exemple en est donné par les réseaux de Petri.
3.2 par cours des graphes
Nous pré sen tons ici une méthode générale appe lée par cours d’un graphe qui, appli -
quée à un graphe orienté ou non orienté, per met la concep tion de toute une famille
d’algo rithmes par ti cu liè re ment effi caces. Ces algo rithmes, appli qués à un graphe
donné, en déter minent des pro prié tés spé ci fiques (par exemple si le graphe est connexe,
ou encore s’il est for te ment connexe) ou bien cal culent des quan ti tés carac té ris tiques
de ce graphe (nombre de compo santes connexes ; lon gueurs de che mins ; etc.). Le
lec teur pourra consta ter tout l’inté rêt de cette méthode au tra vers des exemples
clas siques pré sen tés dans ce sous-cha pitre.
Le prin cipe de la méthode est de par cou rir un graphe, c’est- à-dire l’ensemble de
ses som mets et de ses arcs (ou arêtes). Le par cours du graphe doit se faire en res pec -
tant quelques règles simples assu rant, d’une part, que tout som met et toute arête (ou
arc) ont bien été visi tés et, d’autre part, une complexité mini male de la pro cé dure en
évi tant toute redon dance.
In for mel lement, la pro cé dure de par cours d’un graphe peut s’énon cer de la manière qui suit : on choi sit un som met ini tial que l’on commence à visi ter, la visite
d’un som met étant ter mi née lorsque l’on est allé visi ter tous ses suc ces seurs si le
graphe est orienté (ou tous les som mets qui lui sont adja cents, si le graphe est non
orienté). Ensuite, à chaque étape, on choi sit un som met en cours de visite et on
Figure 3.9
Figure 3.10
Figure 3.11
70
Mais un graphe n’est pas tou jours un réseau repré sen tant des cir -
cu la tions quel conques.
Sou vent, une flèche (arc) entre deux points implique seule ment
une rela tion de suc ces sion : par exemple, le graphe (figure 3.10)
peut vou loir dire seule ment que A pré cède B, qui, lui- même, pré -
cède C. Une pro priété évi dente, dans ce cas, est la tran si ti vité. Si A
pré cède B et B pré cède C, alors A pré cède C ; mais on n’a pas besoin
de l’indi quer par une flèche sup plé men taire entre A et C.
Si dans cette inter pré ta tion, on abou tit à une figure (figure 3.11)
compor tant un cir cuit, le pro blème n’est pas cohé rent, car on ne sau -
rait avoir à la fois : A pré cède C (par tran si ti vité) et C pré cède A. Les
graphes des pro blèmes d’ordon nan ce ment pré sen tés plus loin ne sau -
raient compor ter de cir cuit.
On dit qu’un graphe est valué si, à tout arc qui le consti tue, cor -
res pond une valeur numé rique, qu’on écrit seule ment, sur la figure, à
proxi mité de cet arc. Ces valeurs peuvent être des quan ti tés tran spor tées, des débits,
des coûts, des durées, etc.
Signa lons que les graphes per mettent de repré sen ter aisé ment les « sys tèmes » pou -
vant se trou ver dans des « états », les chan ge ments d’états étant des « tran si tions ». Tout
état est alors repré senté par un som met, toute tran si tion par un arc. Nous ren contre rons
plus loin des exemples de sys tèmes états/tran si tions : il s’agira des chaînes de Markov,
puis des pro ces sus de Markov. Un autre exemple en est donné par les réseaux de Petri.
3.2 par cours des graphes
Nous pré sen tons ici une méthode générale appe lée par cours d’un graphe qui, appli -
quée à un graphe orienté ou non orienté, per met la concep tion de toute une famille
d’algo rithmes par ti cu liè re ment effi caces. Ces algo rithmes, appli qués à un graphe
donné, en déter minent des pro prié tés spé ci fiques (par exemple si le graphe est connexe,
ou encore s’il est for te ment connexe) ou bien cal culent des quan ti tés carac té ris tiques
de ce graphe (nombre de compo santes connexes ; lon gueurs de che mins ; etc.). Le
lec teur pourra consta ter tout l’inté rêt de cette méthode au tra vers des exemples
clas siques pré sen tés dans ce sous-cha pitre.
Le prin cipe de la méthode est de par cou rir un graphe, c’est- à-dire l’ensemble de
ses som mets et de ses arcs (ou arêtes). Le par cours du graphe doit se faire en res pec -
tant quelques règles simples assu rant, d’une part, que tout som met et toute arête (ou
arc) ont bien été visi tés et, d’autre part, une complexité mini male de la pro cé dure en
évi tant toute redon dance.
In for mel lement, la pro cé dure de par cours d’un graphe peut s’énon cer de la manière qui suit : on choi sit un som met ini tial que l’on commence à visi ter, la visite
d’un som met étant ter mi née lorsque l’on est allé visi ter tous ses suc ces seurs si le
graphe est orienté (ou tous les som mets qui lui sont adja cents, si le graphe est non
orienté). Ensuite, à chaque étape, on choi sit un som met en cours de visite et on
Figure 3.9
Figure 3.10
Figure 3.11