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.