Arbres et arborescences
161
7.4.1. Un exemple d'exploration arborescente : le problème du voyageur de
commerce
Pour faire comprendre facilement ce qu'est une exploration arborescente, nous allons
prendre un exemple très simple :
Soit villes
reliées entre elles par des routes à double sens, suivant le schéma
ci-dessous :
Les distances entre les villes sont indiquées sur les arêtes.
Un voyageur de commerce se pose la question suivante : il voudrait passer une fois et
une seule fois dans chacune des villes et revenir à son point de départ de telle façon que
la distance parcourue soit la plus faible possible.
En termes de graphe, le problème se pose de la façon suivante : il s'agit de trouver un
cycle hamiltonien (cycle qui passe en une fois et une seule en chacun des sommets) de
valeur totale minimale. Dans le cadre des graphes orientés, on peut aussi remplacer
chaque arête par deux arcs orientés en sens contraire et de même valeur (dans d'autres
graphes, les valeurs peuvent évidemment être différentes) :
Il s'agit alors de trouver dans ce nouveau graphe le circuit hamiltonien de valeur
minimale.
C'est sur le concept orienté que nous allons raisonner en nous basant sur un algorithme
permettant de résoudre ce problème, l'algorithme de Little.
1) Evaluation par défaut minimale
Ecrivons la matrice des valeurs des arcs entre les différents sommets, en remplissant la
diagonale de
et en posant égale à
la valeur d'un arc qui n'existe pas.
15
6
12
13
11
16
10
17
9
A
B
E
D
C
A
B
15
15
161
7.4.1. Un exemple d'exploration arborescente : le problème du voyageur de
commerce
Pour faire comprendre facilement ce qu'est une exploration arborescente, nous allons
prendre un exemple très simple :
Soit villes
reliées entre elles par des routes à double sens, suivant le schéma
ci-dessous :
Les distances entre les villes sont indiquées sur les arêtes.
Un voyageur de commerce se pose la question suivante : il voudrait passer une fois et
une seule fois dans chacune des villes et revenir à son point de départ de telle façon que
la distance parcourue soit la plus faible possible.
En termes de graphe, le problème se pose de la façon suivante : il s'agit de trouver un
cycle hamiltonien (cycle qui passe en une fois et une seule en chacun des sommets) de
valeur totale minimale. Dans le cadre des graphes orientés, on peut aussi remplacer
chaque arête par deux arcs orientés en sens contraire et de même valeur (dans d'autres
graphes, les valeurs peuvent évidemment être différentes) :
Il s'agit alors de trouver dans ce nouveau graphe le circuit hamiltonien de valeur
minimale.
C'est sur le concept orienté que nous allons raisonner en nous basant sur un algorithme
permettant de résoudre ce problème, l'algorithme de Little.
1) Evaluation par défaut minimale
Ecrivons la matrice des valeurs des arcs entre les différents sommets, en remplissant la
diagonale de
et en posant égale à
la valeur d'un arc qui n'existe pas.
15
6
12
13
11
16
10
17
9
A
B
E
D
C
A
B
15
15