Dans cette section, nous allons examiner un autre problème
algorithmique, celui de la connexité. On souhaite un
algorithme qui, étant donné un graphe quelconque , réponde ``oui''
si et seulement si
est connexe et ``non'' dans la cas contraire.
Une idée simple est d'utiliser directement la
définition 5.6 et de vérifier
si pour toute paire de sommets et
, il existe une chaîne entre
et
. Examinons cette
solution.
L'algorithme serait donc (pour les deux types abstraits) :
Remarquons que cet algorithme utilise une opération non
élémentaire : ``vérifier s'il existe une chaîne entre à
''.
Cela ne pose pas de problèmes, autres que :
Attaquons-nous au problème de trouver une chaîne entre deux
sommets quelconques et
. L'algorithme dépend du type
abstrait.
Au préalable, il nous faut une définition supplémentaire :
Cette définition nous dit que si deux sommets de la chaîne, aux places
respectives et
sont identiques,
alors les deux places
et
sont aussi les mêmes.
Autrement dit ``un sommet figure au plus une fois dans la chaîne'' ou
encore, pour qu'une chaîne soit simple, elle ne peut pas passer deux
fois par le même sommet. Cependant on permet que le sommet du début
et le sommet de la fin soient les mêmes. Dans ce cas, la chaîne est
un cycle.
Nous allons utiliser cette définition pour prouver un théorème qui va nous aider dans la recherche d'une chaîne entre deux sommets d'un graphe.
Preuve :Soit
la chaîne
entre les deux sommets
et
. Si la chaîne
est déjà simple, alors il existe trivialement une chaîne simple entre
et
. Sinon, par la définition 9.2, il y a
deux sommets
et
tels que
, pour
lesquels
et
ou bien deux sommets
et
tels que
, pour lesquels
et
. En supposant que
(sinon
on renverse les rôles de
et
), on peut alors écrire
de la
manière suivante :
.
À partir de cette chaîne, nous allons construire une chaîne plus
courte dans laquelle, le nombre d'occurrences du sommet
est
inférieur à celui du nombre d'occurrences du sommet
dans
en supprimant de
la partie
. On obtient
.
Que soit plus courte que
est évident. Que le
nombre d'occurrences de
ait diminué est évident aussi. Mais
comment pouvons-nous être sûr que
est une chaîne ? Pour
cela, il faut encore examiner la définition 5.5. Dans
cette définition est imposé
que chaque arête de la chaîne soit entourée de ses deux extrémités.
Dans
c'est évident pour toutes les arêtes sauf
qui n'a plus
le sommet
à sa gauche. Heureusement,
, ce qui
règle le problème.
Maintenant, il suffit de répéter cette méthode de contraction jusqu'à ce que la chaîne soit simple. height4pt width4pt
Cette preuve est particulière, car non seulement elle nous dit qu'il existe une chaîne simple, mais elle nous dit aussi comment la construire à partir d'une chaîne non simple. Une telle preuve (qui non seulement donne l'existence d'un objet, mais qui nous donne aussi une méthode pour le trouver) est appelée une preuve constructive. Une telle preuve est toujours plus appréciée par un informaticien qu'une preuve qui indique seulement qu'un objet existe. La raison est que l'informaticien peut souvent convertir une preuve constructive en un algorithme pour trouver l'objet. De manière générale, une preuve constructive est toujours plus convaincante qu'une preuve d'existence.
Nous allons nous servir de ce résultat pour obtenir un algorithme capable de trouver une chaîne simple à la place d'une chaîne quelconque. L'algorithme de recherche d'une chaîne simple est non seulement plus rapide mais aussi plus simple.
Mais avant d'attaquer l'algorithme proprement dit, nous avons besoin d'un autre théorème. Pour préparer ce théorème, il nous faut d'abord une définition supplémentaire :
Preuve :Ce théorème est un peu compliqué à prouver. D'abord, il y a la phrase ``si et seulement si''. Il faut alors prouver à la fois ``si'' et ``seulement si''. D'habitude on les prouve séparément.
Partie ``si'' : Il faut alors prouver que si, soit , soit il
existe une chaîne simple entre un voisin
de
et
ne contenant pas
, alors il existe une chaîne simple entre
et
. Si
,
il existe trivialement une chaîne simple entre
et
: la chaîne
. S'il existe une chaîne simple entre un voisin
de
et
ne
contenant pas
, alors nous pouvons écrire cette chaîne de la manière
suivante :
. Soit
une arête (il peut y en avoir
plusieurs) ayant
et
comme extrémités. Par la définition 9.3,
nous savons qu'une telle arête existe. À partir de
,
et
, nous pouvons construire
.
est une chaîne puisque la restriction sur les extrémités est respectée. De
plus
est simple, car
est simple et
ne figure pas dans
. Finalement,
est bien une chaîne entre
et
. Cette
partie de la preuve est donc terminée.
Partie ``seulement si'' : Il faut alors prouver que s'il existe une
chaîne simple entre deux sommets et
, alors soit
, soit
il existe une chaîne simple entre un voisin
de
et
ne contenant
pas
. Pour cela, on examine la longueur de la chaîne qui existe (selon
les prémisses) entre
et
. Si cette chaîne contient un
seul sommet, à savoir
, par la définition 5.5,
. Sinon (si la chaîne contient plus d'un sommet), on peut
l'écrire
(avec éventuellement
). Ici,
est une chaîne simple entre
et
. Par les
définitions 5.5 et 9.3,
et
sont
forcément voisins. Cette partie de la preuve est alors terminée.
Les deux parties ``si'' ``seulement si'' étant toutes les deux prouvées, la preuve est terminée. height4pt width4pt
Maintenant, nous pouvons commencer à réfléchir à un algorithme
pour trouver une chaîne entre deux sommets et
. Voici
une tentative :
Cet algorithme est beaucoup plus compliqué que ceux que nous avons examinés jusque là. D'abord, il est récursif, à savoir, dans l'algorithme pour vérifier si une chaîne existe, on se sert de ce même algorithme pour vérifier si une autre chaîne existe. Il faut alors faire attention à ce que l'exécution de l'algorithme se termine toujours (sinon selon la section 8.1 ce n'est pas un algorithme). Mais, ici nous n'allons pas prouver la terminaison de cet algorithme.
Dans cet algorithme, nous avons caché une petite difficulté. Il est
écrit dans l'algorithme : ``Pour chaque voisin de
faire''.
Mais ceci n'est pas si simple à réaliser. Avec le type abstrait centré-arêtes, nous n'avons pas accès immédiat aux voisins d'un sommet. Pour
ce type abstrait, il faut alors écrire quelque chose comme ceci :
Par contre, si l'on utilise le type abstrait centré-sommets, l'algorithme est plus simple et plus rapide :
En ce qui concerne la complexité asymptotique de ces algorithmes,
examinons seulement le cas du type abstrait centré-arêtes
(algorithme 9.5).
Le temps d'exécution dépend du nombre de sommets dans une chaîne simple
entre et
.
Même si on donne systématiquement des chaîne très
courtes, l'algorithme doit alors parcourir toutes les arêtes du
graphe.
Le temps d'exécution est donc certainement au moins
proportionnel au nombre d'arêtes du graphe, soit
.
Or, en général, il est encore plus élevé.
Examinons maintenant l'algorithme 9.3 pour vérifier
la connexité du graphe. Il contient deux boucles imbriquées, chaque
boucle étant exécutée pour chaque sommet du graphe. À chaque exécution
du corps de la boucle interne, on appelle
l'algorithme 9.5
ou 9.6 pour trouver une
chaîne simple. La complexité totale de cet algorithme devient alors
au moins
.
Autrement dit, le temps d'exécution
est proportionnel au carré du nombre de sommets multiplié par le
nombre d'arêtes. Ceci n'est pas très bon. Une compagnie de
télécommunications, par exemple, peut facilement avoir un million
d'abonnés (sommets), et un million de possibilités pour un abonné d'en
appeler un autre (arêtes). Cela donne un nombre d'opérations
élémentaires à exécuter de
. Même en supposant qu'un
ordinateur soit capable d'exécuter une opération en un cycle d'horloge
(peu probable) et que l'ordinateur effectue
cycles par seconde
(vitesse normale d'un PC moderne), vérifier si
chaque abonné peut appeler tout autre abonné nécessiterait pour
la compagnie
secondes.
Étant donné qu'une année contient environ
secondes, cela correspond à environ
ans de calcul. Le vrai valeur
est certainement plus élevée encore.
Il est donc hors de question de proposer un tel algorithme à une compagnie de télécommunications. Mais que faire ?
La réponse se trouve encore dans un résultat théorique sur les graphes. En fait, le problème est que nous avons appliqué plus ou moins directement la définition 5.6. Nous allons maintenant prouver un résultat nous permettant de faire beaucoup mieux.
Preuve :Partie ``si'' : il faut prouver que si à partir de n'importe quel
sommet du graphe, il existe une chaîne
vers tous les sommets du
graphe, alors, le graphe est connexe. D'abord rappelons que la
définition 5.6 exige que
, il existe une chaîne entre
et
. La question est
donc : Est-ce que, si à partir de n'importe quel sommet
du graphe,
il existe une chaîne entre
et chaque autre sommet du graphe, alors,
, il existe une chaîne entre
et
?
Ici nous allons utiliser la technique de preuve par contradiction, à
savoir nous allons supposer qu'à partir de n'importe quel sommet
du graphe, il existe une chaîne de
vers tous les sommets du graphe,
mais,
, sans chaîne entre
à
,
puis montrer que cela nous donne un résultat absurde.
Notre supposition nous dit qu'il existe et
sans chaîne entre
à
. L'avantage d'une preuve par
contradiction est qu'il suffit d'examiner un seule couple de ce
type. Nous savons qu'il existe une chaîne de
vers tous les sommets du
graphe, en particulier de
à
et de
à
. Appelons ces
deux chaînes
et
. Nous
allons d'abord regarder la chaîne inverse de
,
.
est bien une chaîne de
à
. Puis nous allons
examiner la concaténation entre
et
, à savoir
. Cette chaîne est bien une
chaîne entre
et
, ce qui contredit la supposition qu'aucune telle
chaîne n'existe. Ceci termine la partie ``si'' de la preuve.
Partie ``seulement si'' : il faut prouver que si un graphe est
connexe, alors à partir de n'importe quel sommet du graphe, il
existe une chaîne de
vers tous les sommets du graphe. Cette partie est
triviale, car par la définition 5.6, il existe une telle
chaîne de n'importe quel sommet à n'importe quel sommet du graphe, et
donc en particulier de
à n'importe quel sommet du graphe.
Les deux parties ``si'' et ``seulement si'' étant prouvées, la preuve est terminée. height4pt width4pt
Avec ce résultat, l'algorithme 9.3 peut être amélioré de la manière suivante :
La boucle imbriquée de l'algorithme 9.3 a été
remplacé par une seule opération pour récupérer le sommet numéro
du graphe. Pour un graphe avec
sommets, nous avons alors gagné
un facteur
de temps d'exécution. Si pour un problème donné, le
temps d'exécution de l'algorithme 9.3 est
ans
(soit environ
secondes), celui de l'algorithme 9.7
sera alors environ
secondes, ou environ
minutes.
Ceci représente une amélioration spectaculaire. mais il est possible de faire encore mieux.
Pour cela, on observe que si l'algorithme 9.7
parcourt le graphe à partir du sommet dans la
figure 9.1 alors il va
parcourir les sommets entre
et
, puis ceux entre
et
, refaisant alors le parcours entre
et
,
puis ceux entre
et
, refaisant alors le parcours
entre
et
, refaisant alors le parcours entre
et
, etc.
Afin d'éviter ces multiples parcours, on peut utiliser le fait que
s'il existe une chaîne de à
passant par
et une chaîne
de
à
, alors il existe une chaîne de
à
. Au lieu de
chercher une chaîne à partir du même sommet
à chaque itération,
on peut chercher à partir d'un sommet ayant une chaîne depuis
.
Nous allons montrer cet algorithme uniquement pour le type abstrait
centré-sommets.
Maintenant, il faut définir la fonction mark_from.
C'est simplement un autre algorithme qui prend en entrée
un sommet et dont le but est de marquer tous les sommets
tels qu'il existe une chaîne entre
et
.
Examinons la complexité asymptotique de cet algorithme. Chaque sommet est examiné au plus deux fois (une fois pour le marquer et une fois pour constater qu'il est déjà marqué). Chaque arête est visitée au plus deux fois (une fois après avoir constaté que son extrémité n'est pas marquée, et éventuellement une deuxième fois s'il s'agit d'une boucle).
Cela donne une complexité
, à savoir que le
temps d'exécution est proportionnel à la somme du nombre de sommets et
du nombre d'arêtes du graphe. Cela représente certainement un facteur
d'amélioration par rapport à l'algorithme 9.7
pour l'exemple donné. Si donc l'algorithme 9.7 est
capable de donner la réponse à notre
compagnie de télécommunication en
minutes (
secondes)
environ, l'algorithme 9.8 est capable de faire la
même chose en
secondes, soit en
millisecondes. Par
rapport à notre algorithme initial, dont le temps d'exécution était au
moins
ans, c'est une amélioration cette fois-ci plus que
considérable.
Les améliorations de complexité citées ci-dessus peuvent paraître trop spectaculaires pour être réalistes. Cependant, on constate régulièrement de telles améliorations pratiquement aussi spectaculaires entre de mauvais et de bons algorithmes. Dans un cas devenu célèbre, un membre du laboratoire de recherche des auteurs de ce livre a pu faire passer le temps d'exécution d'un algorithme utilisé par une entreprise, d'environ une semaine à quelques secondes pour un problème de taille réaliste.
En fait, il est courant que des programmeurs sans formation théorique développent des solutions peu performantes pour un problème car ils n'ont pas les connaissances en informatique théorique qui leur permettraient de trouver une solution efficace. Le résultat est alors souvent médiocre, souvent avec des millions d'Euros de perte.