Arbres et arborescences
171
La procédure sur ce graphe simple a été quelque peu longue, à cause de l'équivalence de
deux circuits
6 .
Cet exemple ayant été traité, nous pouvons passer à un court exposé sur les procédures
d'exploration arborescente en général.
7.4.2. Les procédures de recherche arborescente
7.4.2.1. Principes généraux.
Comme nous l'avons déjà dit, ces procédures sont censées répondre au problème très
général suivant :
soit un ensemble , fini ou non, et une fonction
qui, à tout élément
, fait
correspondre
Il s'agit de trouver un élément
tel que
ou encore plus simplement : trouver le minimum de sur
6 On peut éviter cet inconvénient en ajoutant au début des calculs une quantité
très petite sur
l'un des deux arcs joignant deux sommets.
48
52
H
H1
H2
AE
AE
52
H3
H4
EA
EA
56
52
H5 55
H6 52
H7
H8 52
H9
H10 54
H11
55
H12
52
H13
H14
54
H15
H16
54
AD
CB
BE
AD
CB
BE
DA
BC
CD
DA
BC
CD