3.2 Par cours des graphes
73
© Dunod – Toute reproduction non autorisée est un délit.
Un par cours peut se résu mer, d’une part par les deux ordres d’ouver ture (on dit
aussi de prévisite) et de fer me ture (on dit aussi de postvisite) des som mets du graphe,
et, d’autre part, par la forêt cou vrante (une forêt est un graphe dont chaque compo sante
connexe est une arbo res cence) défi nie par l’ensemble des arcs (x, y) telle que l’ouver -
ture du som met y s’est effec tuée au cours de la visite du som met x ; elle « couvre » tous
les som mets. Dans cet exemple ces deux ordres sont, en par tie, arbi traires. Ce ne sera
plus le cas pour les par cours en lar geur ou en pro fon deur qui sont décrits plus loin.
Début de la première passe
on a ouvert A
puis on a ouvert B
puis on a ouvert I
Figure 3.13
73
© Dunod – Toute reproduction non autorisée est un délit.
Un par cours peut se résu mer, d’une part par les deux ordres d’ouver ture (on dit
aussi de prévisite) et de fer me ture (on dit aussi de postvisite) des som mets du graphe,
et, d’autre part, par la forêt cou vrante (une forêt est un graphe dont chaque compo sante
connexe est une arbo res cence) défi nie par l’ensemble des arcs (x, y) telle que l’ouver -
ture du som met y s’est effec tuée au cours de la visite du som met x ; elle « couvre » tous
les som mets. Dans cet exemple ces deux ordres sont, en par tie, arbi traires. Ce ne sera
plus le cas pour les par cours en lar geur ou en pro fon deur qui sont décrits plus loin.
Début de la première passe
on a ouvert A
puis on a ouvert B
puis on a ouvert I
Figure 3.13