next up previous contents index
suivant: Graphe Eulérien monter: Algorithmes sur les graphes précédent: Degré moyen   Table des matières   Index


Connexité

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 $G$, réponde ``oui'' si et seulement si $G$ 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 $s_1$ et $s_2$, il existe une chaîne entre $s_1$ et $s_2$. Examinons cette solution.

L'algorithme serait donc (pour les deux types abstraits) :

Algorithme 9.3    
Entrée : un graphe $G$
Sortie : un booléen indiquant si $G$ est connexe ou non.
Algorithme :
  1. utiliser l'opération NB_NODES(G) pour récupérer le nombre de sommets $\vert V(G)\vert$ de $G$,
  2. pour $i$ de $0$ à $\vert V(G)\vert - 1$ faire :
    1. utiliser l'opération NODE(G, i) pour récupérer le sommet numéro $i$ de $G$ et mettre le résultat dans la variable $s_1$,
    2. pour $j$ de $0$ à $\vert V(G)\vert - 1$ faire :
      1. utiliser l'opération NODE(G, j) pour récupérer le sommet numéro $j$ de $G$ et mettre le résultat dans la variable $s_2$,
      2. vérifier s'il existe une chaîne entre $s_1$ et $s_2$,
      3. si ce n'est pas le cas, renvoyer la valeur ``non'', car dans ce cas, le graphe n'est pas connexe,
  3. renvoyer la valeur ``oui''. (Si on arrive ici sans avoir renvoyé ``non'', c'est qu'il existe une chaîne entre chaque paire de sommets).

Remarquons que cet algorithme utilise une opération non élémentaire : ``vérifier s'il existe une chaîne entre $s_1$ à $s_2$''. Cela ne pose pas de problèmes, autres que :

  1. il faut trouver un algorithme pour cette opération,
  2. il faut faire attention en calculant la complexité de l'algorithme de connexité, car elle doit tenir compte de la complexité de ce sous-algorithme.

Attaquons-nous au problème de trouver une chaîne entre deux sommets quelconques $s_1$ et $s_2$. L'algorithme dépend du type abstrait.

Au préalable, il nous faut une définition supplémentaire :

Définition 9.2   Une chaîne $C = s_1, e_1, s_2, e_2, \ldots, s_n, e_n, s_{n+1}$ est simple si et seulement si $\forall i, j
\in [1, n]$, $s_i = s_j \Rightarrow i = j$ et $\forall i, j
\in [2, n+1]$, $s_i = s_j \Rightarrow i = j$

Cette définition nous dit que si deux sommets de la chaîne, aux places respectives $i$ et $j$ sont identiques, alors les deux places $i$ et $j$ 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.

Théorème 9.1   Dans un graphe $G$, s'il existe une chaîne entre $s \in V(G)$ et $t
\in V(G)$, alors il existe une chaîne simple entre $s$ et $t$.

Preuve :Soit $C = s_1, e_1, s_2, e_2, \ldots, s_n, e_n, s_{n+1}$ la chaîne entre les deux sommets $s = s_1$ et $t = s_{n+1}$. Si la chaîne est déjà simple, alors il existe trivialement une chaîne simple entre $s$ et $t$. Sinon, par la définition 9.2, il y a deux sommets $s_i$ et $s_j$ tels que $i,j \in [1, n]$, pour lesquels $i \not = j$ et $s_i = s_j$ ou bien deux sommets $s_i$ et $s_j$ tels que $i,j \in [2, n+1]$, pour lesquels $i \not = j$ et $s_i = s_j$. En supposant que $i < j$ (sinon on renverse les rôles de $i$ et $j$), on peut alors écrire $C$ de la manière suivante : $C = s_1, e_1, \ldots, s_i, e_i, \ldots, s_j, e_j,
\ldots, s_n, e_n, s_{n+1}$.

À partir de cette chaîne, nous allons construire une chaîne $C'$ plus courte dans laquelle, le nombre d'occurrences du sommet $s_i = s_j$ est inférieur à celui du nombre d'occurrences du sommet $s_i$ dans $C$ en supprimant de $C$ la partie $e_i, \ldots,
s_j$. On obtient
$C' = s_1, e_1, \ldots, s_i, e_j, \ldots, s_n,
e_n, s_{n+1}$.
Que $C'$ soit plus courte que $C$ est évident. Que le nombre d'occurrences de $s_i$ ait diminué est évident aussi. Mais comment pouvons-nous être sûr que $C'$ 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'$ c'est évident pour toutes les arêtes sauf $e_j$ qui n'a plus le sommet $s_j$ à sa gauche. Heureusement, $s_i = s_j$, 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 :

Définition 9.3   Dans un graphe $G$, deux sommets $s$ et $t$ sont voisins si et seulement si $\exists e \in E(G)$ telle que $s$ et $t$ sont les extrémités de $e$. On dit alors que $s$ est un voisin de $t$ et que $t$ est un voisin de $s$.

Théorème 9.2   Il existe une chaîne simple entre deux sommets $s$ et $t$ si et seulement si soit $s = t$, soit il existe une chaîne simple entre un voisin $s'$ et $s$ à $t$ ne contenant pas $s$.

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 $s = t$, soit il existe une chaîne simple entre un voisin $s'$ de $s$ et $t$ ne contenant pas $s$, alors il existe une chaîne simple entre $s$ et $t$. Si $s = t$, il existe trivialement une chaîne simple entre $s$ et $t$ : la chaîne $C =
s$. S'il existe une chaîne simple entre un voisin $s'$ de $s$ et $t$ ne contenant pas $s$, alors nous pouvons écrire cette chaîne de la manière suivante : $C = s', \ldots, t$. Soit $e$ une arête (il peut y en avoir plusieurs) ayant $s$ et $s'$ comme extrémités. Par la définition 9.3, nous savons qu'une telle arête existe. À partir de $C$, $s$ et $e$, nous pouvons construire $C' = s, e, s', \ldots, t$. $C'$ est une chaîne puisque la restriction sur les extrémités est respectée. De plus $C'$ est simple, car $C$ est simple et $s$ ne figure pas dans $C$. Finalement, $C'$ est bien une chaîne entre $s$ et $t$. 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 $s$ et $t$, alors soit $s = t$, soit il existe une chaîne simple entre un voisin $s'$ de $s$ et $t$ ne contenant pas $s$. Pour cela, on examine la longueur de la chaîne qui existe (selon les prémisses) entre $s$ et $t$. Si cette chaîne contient un seul sommet, à savoir $C =
s$, par la définition 5.5, $s = t$. Sinon (si la chaîne contient plus d'un sommet), on peut l'écrire $C = s, e, s', \ldots, t$ (avec éventuellement $s' = t$). Ici, $C' = s', \ldots, t$ est une chaîne simple entre $s'$ et $t$. Par les définitions 5.5 et 9.3, $s$ et $s'$ 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 $s$ et $t$. Voici une tentative :

Algorithme 9.4    
Entrée : Un graphe $G$ et deux sommets $s, t \in V(G)$.
Sortie : Une valeur booléenne indiquant si oui ou non il existe une chaîne simple entre $s$ et $t$.
Algorithme :
  1. si $s = t$ alors renvoyer la valeur ``oui'',
  2. utiliser l'opération MARK_NODE(s) pour marquer le sommet $s$
  3. pour chaque voisin $s'$ de $s$ faire :
    1. utiliser l'opération NODE_MARKED(s') pour déterminer si $s'$ est marqué.
    2. si ce n'est pas le cas :
      1. vérifier s'il existe une chaîne simple entre $s'$ et $t$.
      2. si c'est le cas, alors renvoyer la valeur ``oui''
  4. on arrive ici si on ne peut pas trouver une chaîne simple entre un voisin $s'$ de $s$ et $t$,
  5. utiliser l'opération UNMARK_NODE(s) pour démarquer le sommet $s$,
  6. renvoyer la valeur ``non''.

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 $s'$ de $s$ 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 :

Algorithme 9.5    
Entrée : Un graphe $G$ et deux sommets $s, t \in V(G)$.
Sortie : Une valeur booléenne indiquant si oui ou non il existe une chaîne simple de $s$ à $t$.
Algorithme :
  1. si $s = t$ alors renvoyer la valeur ``oui'',
  2. utiliser l'opération MARK_NODE(s) pour marquer le sommet $s$
  3. utiliser l'opération NB_EDGES(G) pour récupérer le nombre d'arêtes de $G$, $\vert E(G)\vert$,
  4. pour chaque $i, 0 \le i < \vert E(G)\vert$ faire :
    1. utiliser l'opération EDGE(G, i) pour récupérer l'arête numéro $i$ du graphe. Soit $e$ cette arête,
    2. utiliser l'opération EDGE_END(a, j) pour affecter une variable $s'$ (pour voisin) de la manière suivante : si EDGE_END(a, 0) donne $s$ comme résultat, alors donner à $s'$ la valeur de EDGE_END(a, 1). Sinon, si EDGE_END(a, 1) donne $s$ comme résultat, alors donner à $s'$ la valeur de EDGE_END(a, 0). Sinon donner la valeur nil à $s'$.
    3. si $s'$ n'est pas nil :
      1. utiliser l'opération NODE_MARKED(s') pour déterminer si $s'$ est marqué.
      2. si ce n'est pas le cas :
        1. vérifier s'il existe une chaîne simple de $s'$ à $t$.
        2. si c'est le cas, alors renvoyer la valeur ``oui''
  5. on arrive ici si on ne peut pas trouver une chaîne simple d'un voisin $s'$ de $s$ à $t$,
  6. utiliser l'opération UNMARK_NODE(s) pour démarquer le sommet $s$,
  7. renvoyer la valeur ``non''.

Par contre, si l'on utilise le type abstrait centré-sommets, l'algorithme est plus simple et plus rapide :

Algorithme 9.6    
Entrée : Un graphe $G$ et deux sommets $s, t \in V(G)$.
Sortie : Une valeur booléenne indiquant si oui ou non il existe une chaîne simple de $s$ à $t$.
Algorithme :
  1. si $s = t$ alors renvoyer la valeur ``oui'',
  2. utiliser l'opération MARK_NODE(s) pour marquer le sommet $s$
  3. utiliser l'opération NB_EDGES(s) pour récupérer le degré (disons $k$) de $s$,
  4. pour chaque $i, 0 \le i < k$ faire :
    1. utiliser l'opération EDGE(s, i) pour récupérer l'arête numéro $i$ (appelons la $e$) de $s$,
    2. utiliser l'opération FOLLOW_EDGE(s, e) pour récupérer l'autre extrémité (un voisin $s'$) de $s$,
    3. utiliser l'opération NODE_MARKED(s') pour déterminer si $s'$ est marqué.
    4. si ce n'est pas le cas :
      1. vérifier s'il existe une chaîne simple de $s'$ à $t$.
      2. si c'est le cas, alors renvoyer la valeur ``oui''
  5. on arrive ici si on ne peut pas trouver une chaîne simple d'un voisin $s'$ de $s$ à $t$,
  6. utiliser l'opération UNMARK_NODE(s) pour démarquer le sommet $s$,
  7. renvoyer la valeur ``non''.

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 $s$ et $t$. 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 $O(\vert E(G)\vert)$. 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 $O({\vert V(G)\vert}^2 \vert E(G)\vert)$. 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 $10^{18}$. 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 $10^9$ cycles par seconde (vitesse normale d'un PC moderne), vérifier si chaque abonné peut appeler tout autre abonné nécessiterait pour la compagnie $10^9$ secondes. Étant donné qu'une année contient environ $3 \cdot 10^7$ secondes, cela correspond à environ $30$ 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.

Théorème 9.3   Un graphe est connexe si et seulement si à partir de n'importe quel sommet $s$ du graphe, il existe une chaîne de $s$ vers chaque autre sommet du graphe.

Preuve :Partie ``si'' : il faut prouver que si à partir de n'importe quel sommet $s$ du graphe, il existe une chaîne $s$ vers tous les sommets du graphe, alors, le graphe est connexe. D'abord rappelons que la définition 5.6 exige que $\forall s_1, s_2
\in V(G)$, il existe une chaîne entre $s_1$ et $s_2$. La question est donc : Est-ce que, si à partir de n'importe quel sommet $s$ du graphe, il existe une chaîne entre $s$ et chaque autre sommet du graphe, alors, $\forall s_1, s_2
\in V(G)$, il existe une chaîne entre $s_1$ et $s_2$ ?

Ici nous allons utiliser la technique de preuve par contradiction, à savoir nous allons supposer qu'à partir de n'importe quel sommet $s$ du graphe, il existe une chaîne de $s$ vers tous les sommets du graphe, mais, $\exists s_1, s_2 \in V(G)$, sans chaîne entre $s_1$ à $s_2$, puis montrer que cela nous donne un résultat absurde.

Notre supposition nous dit qu'il existe $s_1$ et $s_2$ sans chaîne entre $s_1$ à $s_2$. 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 $s$ vers tous les sommets du graphe, en particulier de $s$ à $s_1$ et de $s$ à $s_2$. Appelons ces deux chaînes $C_1 = s, \ldots, s_1$ et $C_2 = s, \ldots, s_2$. Nous allons d'abord regarder la chaîne inverse de $C_1$, $\overline{C_1} = s_1, \ldots, s$. $\overline{C_1}$ est bien une chaîne de $s_1$ à $s$. Puis nous allons examiner la concaténation entre $\overline{C_1}$ et $C_2$, à savoir $\overline{C_1}C_2 = s_1, \ldots, s, \ldots, s_2$. Cette chaîne est bien une chaîne entre $s_1$ et $s_2$, 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 $s$ du graphe, il existe une chaîne de $s$ 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 $s$ à 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 :

Algorithme 9.7    
Entrée : un graphe $G$
Sortie : un booléen indiquant si $G$ est connexe ou non.
Algorithme :
  1. utiliser l'opération NODE(G, 0) pour récupérer le sommet numéro $0$ (on suppose que le graphe a au moins un sommet) de $G$ et mettre le résultat dans la variable $s$,
  2. utiliser l'opération nb_nodes(G) pour récupérer le nombre de sommets $\vert V(G)\vert$ de $G$,
  3. pour $i$ de $0$ à $\vert V(G)\vert - 1$ faire :
    1. utiliser l'opération NODE(G, i) pour récupérer le sommet numéro $i$ de $G$ et mettre le résultat dans la variable $t$,
    2. vérifier s'il existe une chaîne de $s$ à $t$,
    3. si ce n'est pas le cas, renvoyer la valeur ``non'', car dans ce cas, le graphe n'est pas connexe,
  4. renvoyer la valeur ``oui'', car si on arrive ici sans avoir renvoyé ``non'', il existe une chaîne entre chaque paire de sommets.

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 $0$ du graphe. Pour un graphe avec $10^6$ sommets, nous avons alors gagné un facteur $10^6$ de temps d'exécution. Si pour un problème donné, le temps d'exécution de l'algorithme 9.3 est $30$ ans (soit environ $10^9$ secondes), celui de l'algorithme 9.7 sera alors environ $10^3$ secondes, ou environ $17$ 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 $s_0$ dans la figure 9.1 alors il va parcourir les sommets entre $s_0$ et $s_1$, puis ceux entre $s_0$ et $s_2$, refaisant alors le parcours entre $s_0$ et $s_1$, puis ceux entre $s_0$ et $s_3$, refaisant alors le parcours entre $s_0$ et $s_2$, refaisant alors le parcours entre $s_0$ et $s_1$, etc.

Figure: Parcours pour la connexité
\begin{figure}\begin{center}
\input figalgochemin.pstex_t
\end{center}\end{figure}

Afin d'éviter ces multiples parcours, on peut utiliser le fait que s'il existe une chaîne de $s$ à $u$ passant par $t$ et une chaîne de $t$ à $v$, alors il existe une chaîne de $s$ à $v$. Au lieu de chercher une chaîne à partir du même sommet $s$ à chaque itération, on peut chercher à partir d'un sommet ayant une chaîne depuis $s$. Nous allons montrer cet algorithme uniquement pour le type abstrait centré-sommets.

Algorithme 9.8    
Entrée : Un graphe $G$ avec tous ses sommets démarqués.
Sortie : Une valeur booléenne indiquant si $G$ est connexe.
Effet de bord : Marque tous les sommets $t$ tels qu'il y a une chaîne entre $s$ et $t$.
Algorithme :
  1. utiliser l'opération NODE(G, 0) pour récupérer le sommet numéro $0$ de $G$ (on suppose que le graphe a au moins un sommet),
  2. appeler la fonction mark_from(s) (définie ci-dessous) avec ce sommet $0$ comme argument,
  3. utiliser l'opération NB_NODES(G) pour récupérer le nombre de sommets de $G$ $\vert V(G)\vert$,
  4. pour tout $i, 0 \le i < \vert V(G)\vert$ faire :
    1. utiliser l'opération NODE(G, i) pour récupérer le sommet numéro $i$ (appelons-le $s$),
    2. utiliser l'opération NODE_MARKED(s) pour vérifier si $s$ est marqué.
    3. si ce n'est pas le cas, alors renvoyer la réponse ``non'', sommet,
  5. si on arrive ici, alors tous les sommets du graphe étaient marqués. Renvoyer la réponse ``oui''.

Maintenant, il faut définir la fonction mark_from. C'est simplement un autre algorithme qui prend en entrée un sommet $s$ et dont le but est de marquer tous les sommets $t$ tels qu'il existe une chaîne entre $s$ et $t$.

Algorithme 9.9    
Entrée : Un sommet $s$.
Sortie : Aucune. Effet de bord : Marque tous les sommets ayant une chaîne à partir de $s$.
Algorithme :
  1. si le sommet $s$ est déjà marqué, alors ne rien faire,
  2. sinon, faire :
    1. utiliser l'opération MARK_NODE(s) pour marquer ce sommet,
    2. utiliser l'opération NB_EDGES(s) pour récupérer le degré de ce sommet (disons $n$),
    3. pour tout $i, 0 \le i < n$ faire :
      1. utiliser l'opération EDGE(s, i) pour récupérer l'arête numéro $i$ (disons $e$) ayant une extrémité sur $s$,
      2. utiliser l'opération FOLLOW_EDGE(s, e) pour récupérer l'autre extrémité (disons $t$) de $e$,
      3. appeler récursivement la fonction mark_from avec le sommet $t$ comme argument,

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é $O(\vert V(G)\vert + \vert E(G)\vert)$, à 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 $10^5$ 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 $17$ minutes ($10^3$ secondes) environ, l'algorithme 9.8 est capable de faire la même chose en $10^{-2}$ secondes, soit en $10$ millisecondes. Par rapport à notre algorithme initial, dont le temps d'exécution était au moins $30$ 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.


next up previous contents index
suivant: Graphe Eulérien monter: Algorithmes sur les graphes précédent: Degré moyen   Table des matières   Index