Cycles dans les graphes et détection de cycles

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Marches, pistes, chemins et cycles

Un cycle est un trajet dans un graphe qui revient à son point de départ sans rien réutiliser en chemin. Cela semble simple, mais « trajet » peut désigner quatre choses différentes, et la plupart des confusions au sujet des cycles viennent de ce qu'on les mélange. Elles ne diffèrent que par ce qui peut se répéter.

• Une marche est une suite de sommets dans laquelle chaque paire consécutive est reliée par une arête. Sommets et arêtes peuvent tous deux se répéter. Sa longueur est le nombre d'arêtes qu'elle utilise, comptées avec répétition.
• Une piste est une marche qui n'utilise jamais deux fois la même arête. Les sommets peuvent encore se répéter.
• Un chemin est une marche qui ne visite jamais deux fois le même sommet, de sorte qu'il ne peut pas non plus répéter une arête.
• Une marche est fermée lorsqu'elle se termine là où elle a commencé. Une piste fermée s'appelle aussi un circuit, et un cycle est une piste fermée de longueur positive dont le seul sommet répété est celui où elle commence et se termine.

Les manuels n'emploient pas tous ces mots de la même façon. Certains disent « chemin » pour ce qui est appelé ici une marche, et certains disent « circuit » pour ce qui est appelé ici un cycle. Les idées sont stables même quand les noms ne le sont pas ; quand vous lisez un théorème, vérifiez donc lequel est visé. Dans un graphe simple un cycle a besoin d'au moins trois sommets. Dans un multigraphe, une boucle est un cycle de longueur 1 et deux arêtes parallèles forment un cycle de longueur 2.

Un seul graphe non orienté porte l'essentiel de l'article. Il a huit sommets et dix arêtes : un triangle A, B, C en haut, deux carrés B, C, E, D et D, E, G, F empilés en dessous, et un sommet H suspendu à G.

V = {A, B, C, D, E, F, G, H}                          8 sommets
E = {AB, BC, CA, BD, CE, DE, DF, EG, FG, GH}          10 arêtes

Deux faits sur les marches fermées servent sans cesse. Premièrement, une marche fermée ne contient pas forcément de cycle : A, B, A est fermée, mais elle ne fait qu'aller le long d'une arête et revenir par la même arête. Deuxièmement, une piste fermée de longueur positive contient toujours un cycle. Si elle répète un sommet en cours de route, coupez-la à cet endroit en deux pistes fermées plus courtes et reprenez l'argument sur l'une ou l'autre ; le processus s'arrête sur une piste fermée sans sommet répété, qui est un cycle. La section 8 a besoin d'une variante du même argument pour les marches de longueur impaire.

2. Maille, circonférence et graphes sans cycle

La maille d'un graphe est la longueur de son plus court cycle, et la circonférence est la longueur de son plus long cycle. L'exemple compte six cycles en tout, de longueurs 3, 4, 4, 5, 6 et 7 : sa maille vaut donc 3 et sa circonférence 7. Le plus long cycle, A, B, D, F, G, E, C, passe par tous les sommets sauf H, qui n'a qu'une seule arête et ne peut donc appartenir à aucun cycle.

Un graphe sans cycle est dit acyclique. Un graphe non orienté acyclique est une forêt, et une forêt connexe est un arbre. Une forêt à n sommets et k composantes a exactement n − k arêtes, si bien que compter les arêtes donne le test de cycle le plus rapide qui soit :

Un graphe à n sommets, m arêtes et k composantes contient un cycle si et seulement si m > n − k. En particulier, tout graphe ayant au moins autant d'arêtes que de sommets possède un cycle.

L'exemple vérifie 10 > 8 − 1, il doit donc contenir un cycle avant même qu'on en cherche un. Une condition sur les degrés fonctionne aussi : si chaque sommet est de degré au moins 2, le graphe possède un cycle, et même un cycle de longueur au moins δ + 1, où δ est le degré minimum. La preuve est un classique. Prenez un plus long chemin v0, v1, …, vℓ. Tout voisin de v0 se trouve sur le chemin, sinon le chemin pourrait être prolongé. v0 a au moins δ voisins sur ce chemin, donc le plus éloigné est au moins vδ, et l'arête qui y revient ferme un cycle de longueur au moins δ + 1, une observation qui figure dans l'article de Dirac de 1952. Cela a été vérifié par force brute sur tous les graphes ayant jusqu'à six sommets.

Dans un graphe orienté, un cycle doit suivre les flèches, et un graphe orienté acyclique s'appelle un DAG. Les DAG sont exactement les graphes orientés dont les sommets peuvent être placés sur une ligne avec chaque flèche pointant vers l'avant, et c'est ce qu'un tri topologique produit. Notez qu'un DAG peut avoir beaucoup d'arêtes : le test par comptage d'arêtes ci-dessus ne vaut que pour les graphes non orientés.

Trouver la maille est plus difficile que trouver un cycle quelconque. Lancer un parcours en largeur depuis chaque sommet et examiner chaque arête hors de l'arbre qu'il rencontre donne la maille avec une complexité O(nm) en temps. L'article d'Itai et Rodeh de 1978 sur les circuits minimaux donne cette borne, ainsi qu'une méthode plus rapide pour obtenir un cycle ayant au plus une arête de plus que le plus court.

3. Détecter un cycle dans un graphe non orienté

Si vous n'avez besoin que d'un oui ou d'un non, le comptage des arêtes tranche : calculez les composantes et comparez m avec n − k. En général, vous voulez davantage, à savoir un cycle concret que vous pouvez montrer à quelqu'un. Un cycle est un certificat : n'importe qui peut le vérifier arête par arête, et il prouve la réponse sans demander à personne de faire confiance à votre programme. Le parcours en profondeur en produit un presque gratuitement.

Le fait clé est qu'un parcours en profondeur d'un graphe non orienté range chaque arête dans l'une de deux catégories. Une arête d'arbre mène à un sommet vu pour la première fois. Une arête arrière mène à un sommet déjà sur le chemin de descente, un ancêtre du sommet courant. Il n'existe pas d'autres catégories : le graphe a donc un cycle exactement quand la recherche rencontre une arête arrière, et le cycle est cette arête arrière plus le chemin d'arbre qu'elle enjambe.

def find_cycle_undirected(vertices, edges):
    """Renvoie les sommets d'un cycle, dans l'ordre, ou None si le graphe est une forêt."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    parent = {}                                   # sommet -> (sommet parent, id de l'arête)
    for root in vertices:                         # une recherche par composante
        if root in parent:
            continue
        parent[root] = (None, None)
        stack = [(root, iter(adj[root]))]
        while stack:
            u, it = stack[-1]
            for v, i in it:
                if i == parent[u][1]:             # l'arête d'arrivée, pas un cycle
                    continue
                if v in parent:                   # arête arrière u-v : remonter de u à v
                    cycle = [u]
                    while cycle[-1] != v:
                        cycle.append(parent[cycle[-1]][0])
                    return cycle[::-1]
                parent[v] = (u, i)
                stack.append((v, iter(adj[v])))
                break
            else:
                stack.pop()
    return None

V = 'ABCDEFGH'
E = ['AB', 'BC', 'CA', 'BD', 'CE', 'DE', 'DF', 'EG', 'FG', 'GH']
print(find_cycle_undirected(V, E))
# ['A', 'B', 'C']
print(find_cycle_undirected(V, ['AB', 'BC', 'CE', 'DE', 'DF', 'FG', 'GH']))
# None
print(find_cycle_undirected('xy', ['xy', 'xy']))
# ['x', 'y']

Trois détails rendent ce code correct plutôt que presque correct. La recherche mémorise l'arête par laquelle elle est arrivée et n'ignore que cette arête-là ; sans cela, chaque arête ressemblerait à un cycle de longueur 2, un aller suivi d'un retour immédiat. Ignorer selon l'identité de l'arête plutôt que selon « le voisin qui est mon parent » garde le code correct pour les multigraphes, où une arête doublée est réellement un cycle de longueur 2, comme le montre le troisième appel. La boucle externe lance une recherche par composante, car un cycle peut se trouver dans n'importe laquelle d'entre elles. Et la pile est explicite, si bien qu'un long chemin ne peut pas dépasser la limite de récursion de Python.

Avec les voisins pris dans l'ordre alphabétique, la recherche depuis A descend A, B, C et en C trouve l'arête qui revient vers A. A est déjà visité et l'arête n'est pas celle par laquelle la recherche est arrivée, donc le code remonte les pointeurs parents de C jusqu'à A et renvoie le triangle. Si elle avait continué, la recherche aurait poursuivi par E, D, F, G, H, un unique chemin passant par les huit sommets, et aurait trouvé deux autres arêtes arrière, D–B et G–E. Sept arêtes d'arbre plus trois arêtes arrière font bien les dix.

Le temps d'exécution réserve un agréable bonus. Avant la première arête arrière, chaque entrée d'adjacence que lit la recherche est soit une arête d'arbre, au plus n − 1 en tout, soit l'arête qui revient vers un parent, au plus n − 1 là encore. La recherche elle-même lit donc au plus 2n − 1 entrées avant de trouver un cycle ou de se terminer, quel que soit le nombre d'arêtes du graphe. Cette borne a été vérifiée par comptage sur 4 000 graphes aléatoires. Lire l'entrée pour construire les listes d'adjacence coûte toujours O(V + E), mais pas la recherche.

4. Union-find : les cycles une arête à la fois

Il arrive que les arêtes arrivent une par une et que la question soit de savoir quelle arête crée le premier cycle. Une structure union-find y répond sans aucune recherche. Elle répartit les sommets en groupes, un groupe par composante construite jusque-là. Une arête entre deux groupes différents les fusionne. Une arête dont les deux extrémités sont déjà dans le même groupe relie deux sommets qui étaient déjà connectés ; avec le chemin qui existait déjà entre eux, elle ferme donc un cycle.

def first_cycle_edge(vertices, edges):
    """Ajoute les arêtes une à une ; renvoie la première arête qui ferme un cycle, ou None."""
    root = {v: v for v in vertices}
    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]               # compression par division du chemin (path halving)
            x = root[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:                              # u et v étaient déjà connectés
            return u + v
        root[ru] = rv
    return None

print(first_cycle_edge('ABCDEFGH', ['AB', 'BD', 'DF', 'FG', 'GH', 'BC', 'CE', 'EG', 'DE', 'CA']))
# EG

Dans cet ordre, les cinq premières arêtes forment le chemin A, B, D, F, G, H, puis B–C et C–E y accrochent deux sommets de plus. Quand E–G arrive, E et G ont déjà la même racine, et le cycle qu'elle ferme est B, C, E, G, F, D, long de six arêtes. C'est exactement le test que l'algorithme de Kruskal applique à chaque arête avant de l'ajouter à un arbre couvrant minimal.

L'union-find vous dit quelle arête ferme un cycle, pas par où passe ce cycle. Pour produire le cycle, il vous faut encore le chemin entre les deux extrémités dans la forêt construite jusque-là, qu'une courte recherche sur les arêtes acceptées permet de trouver. Et l'union-find ne fonctionne que pour les graphes non orientés. Dans le graphe orienté avec les flèches A→B, B→C et A→C, la troisième flèche relie deux sommets qui sont déjà dans un même groupe, et pourtant il n'y a pas de cycle orienté : suivre les flèches ne ramène jamais à A.

5. Graphes orientés : trois couleurs

Dans un graphe orienté le test non orienté donne de mauvaises réponses. Prenez six tâches avec ces dépendances :

A → B    A → C    B → D    C → D    C → E    E → F

Un parcours en profondeur depuis A atteint D en passant par B. Plus tard, en explorant C, il rencontre la flèche C→D et trouve D déjà visité. Un simple test « déjà visité » y voit un cycle, mais il n'y en a aucun : A→B→D et A→C→D sont deux trajets vers le même endroit, pas un trajet qui revient. Sur 6 000 graphes orientés aléatoires, le simple test a signalé un cycle dans 1 320 graphes qui n'en avaient aucun.

La solution consiste à retenir non seulement si un sommet a été visité, mais aussi si sa recherche est toujours en cours. Chaque sommet reçoit l'une de trois couleurs :

• BLANC : pas encore atteint.
• GRIS : atteint, et sa recherche n'est pas terminée. Les sommets gris forment exactement le chemin courant, de la racine jusqu'au sommet en cours d'exploration.
• NOIR : terminé. Tout ce qui est accessible depuis lui a été exploré, et aucun cycle n'y a été trouvé.

Un parcours en profondeur orienté range les arêtes en quatre catégories : les arêtes d'arbre vers les sommets blancs, les arêtes arrière vers les ancêtres gris, les arêtes avant vers les descendants noirs, et les arêtes transversales vers des sommets noirs d'une autre branche ou d'une recherche antérieure. Seule une arête arrière ferme un cycle, car seul un sommet gris est assuré d'atteindre le sommet courant. On obtient ainsi le théorème classique : un graphe orienté a un cycle si et seulement si un parcours en profondeur trouve une arête arrière, ce qui revient à trouver une flèche vers un sommet gris. Le chemin gris lui-même est le certificat.

WHITE, GRAY, BLACK = 0, 1, 2

def find_cycle_directed(graph):
    """Renvoie un cycle orienté sous forme de liste de sommets, ou None si le graphe est un DAG."""
    color = {v: WHITE for v in graph}
    for root in graph:
        if color[root] != WHITE:
            continue
        color[root] = GRAY
        path = [root]                             # les sommets GRAY (gris), dans l'ordre
        stack = [iter(graph[root])]
        while stack:
            for v in stack[-1]:
                if color[v] == GRAY:              # arête arrière : v est sur le chemin courant
                    return path[path.index(v):]
                if color[v] == WHITE:
                    color[v] = GRAY
                    path.append(v)
                    stack.append(iter(graph[v]))
                    break
            else:                                 # toutes les arêtes sortantes traitées : terminer le sommet
                color[path.pop()] = BLACK
                stack.pop()
    return None

dag = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': ['F'], 'F': []}
print(find_cycle_directed(dag))
# None
dag['F'].append('C')                              # une arête de plus : F -> C
print(find_cycle_directed(dag))
# ['C', 'E', 'F']

Sur les six tâches, D devient noir avant que C soit exploré, donc C→D est une arête transversale et se trouve correctement ignorée. Ajoutez une flèche, F→C, et tout change : la recherche parcourt C, E, F, tous gris, et la nouvelle flèche pointe de nouveau vers C, qui est toujours gris. Le chemin gris de C à F est renvoyé comme cycle. Une boucle v→v est traitée elle aussi : v est gris quand sa propre flèche est lue, et le cycle renvoyé est simplement [v].

6. L'algorithme de Kahn : les cycles comme un tri topologique bloqué

La seconde méthode standard ne demande ni récursion ni couleurs. Un sommet de degré entrant 0 ne dépend de rien et peut donc passer en premier sans risque. L'algorithme de Kahn, publié en 1962, retire de façon répétée un tel sommet et diminue les degrés entrants de ses successeurs. Si tous les sommets sont retirés, l'ordre de retrait est un ordre topologique et le graphe est un DAG. Si le processus s'arrête prématurément, le graphe a un cycle.

from collections import deque

def kahn(graph):
    """Ordre topologique si le graphe est un DAG, sinon (None, un cycle)."""
    indeg = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    ready = deque(v for v in graph if indeg[v] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)
    if len(order) == len(graph):
        return order, None
    left = {v for v in graph if indeg[v] > 0}     # chacun d'eux a un prédécesseur dans left
    pred = {v: u for u in left for v in graph[u] if v in left}
    v, seen = next(iter(sorted(left))), []
    while v not in seen:                          # reculer jusqu'à ce qu'un sommet se répète
        seen.append(v)
        v = pred[v]
    return None, seen[seen.index(v):][::-1]

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': ['F'], 'F': ['C']}
print(kahn(graph))
# (None, ['E', 'F', 'C'])
graph['F'] = []
print(kahn(graph))
# (['A', 'B', 'C', 'D', 'E', 'F'], None)

Pourquoi le blocage prouve-t-il un cycle ? Chaque sommet restant a encore au moins une flèche entrante, et cette flèche vient d'un sommet restant, car chaque sommet retiré a déjà soustrait ses flèches des compteurs. Depuis n'importe quel sommet restant, vous pouvez donc reculer le long d'une flèche vers un sommet restant, indéfiniment. Avec un nombre fini de sommets, cette marche à rebours doit répéter un sommet, et la portion comprise entre les deux visites est un cycle. Le code effectue exactement cette marche et renvoie E, F, C, le même cycle que précédemment, lu à partir d'un autre point de départ.

Un détail est facile à rater. Sur l'exemple, l'algorithme de Kahn retire A et B, puis se bloque avec C, D, E et F toujours en place. D n'est sur aucun cycle ; il n'est bloqué que parce qu'il attend C. Les sommets restants sont les cycles plus tout ce qui se trouve en aval, si bien que présenter l'ensemble restant comme « le cycle » est un bug. Sans la flèche F→C le même code renvoie l'ordre A, B, C, D, E, F, l'un des neuf ordres valides de ce DAG.

Les deux méthodes s'exécutent en temps O(V + E) et diffèrent par ce qu'elles fournissent : la version en profondeur vous donne directement un cycle, tandis que la version de Kahn vous donne un ordre topologique dès qu'il en existe un, ce qui est généralement ce que voulait d'emblée un ordonnanceur ou un outil de build.

7. Combien de cycles ? L'espace des cycles

Compter les cycles un par un devient vite ingérable. Le graphe complet K4 a 7 cycles, K5 en a 37, K6 en a 197, et K10 en a 556 014. Les énumérer tous est possible, et l'algorithme de Johnson de 1975 le fait pour les graphes orientés en temps O((n + e)(c + 1)) pour c cycles, mais la sortie à elle seule peut être exponentielle en la taille du graphe.

Il existe un bien meilleur décompte. Voyez un cycle comme un ensemble d'arêtes, et combinez deux ensembles d'arêtes par différence symétrique : ne garder que les arêtes qui sont dans exactement l'un des deux. Pour cette opération, les sous-graphes dans lesquels chaque sommet est de degré pair forment un espace vectoriel sur le corps à deux éléments, appelé espace des cycles. Tout cycle y appartient, et sa dimension est

le nombre cyclomatique, ou rang des cycles : m − n + k.

Une base est facile à construire. Prenez n'importe quelle forêt couvrante, qui a n − k arêtes. Chacune des m − n + k arêtes restantes ferme exactement un cycle avec la forêt, son cycle fondamental, et ces cycles sont indépendants car chacun contient une arête qu'aucun autre ne contient. L'idée remonte à Kirchhoff, qui l'utilisa en 1847 pour compter les équations de mailles indépendantes d'un réseau électrique ; le nom de nombre cyclomatique est venu plus tard. Un parcours en profondeur fournit directement la base : modifiez le détecteur de cycles pour qu'il enregistre chaque arête arrière au lieu de s'arrêter à la première.

def cycle_basis(vertices, edges):
    """Un cycle par arête hors arbre d'une forêt DFS : m - n + k cycles en tout."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    parent, used, basis = {}, set(), []
    for root in vertices:
        if root in parent:
            continue
        parent[root] = None
        stack = [(root, iter(adj[root]))]
        while stack:
            u, it = stack[-1]
            for v, i in it:
                if i in used:                     # arête d'arbre ou arête arrière déjà comptée
                    continue
                used.add(i)
                if v in parent:                   # arête arrière : enregistrer son cycle, continuer
                    cycle = [u]
                    while cycle[-1] != v:
                        cycle.append(parent[cycle[-1]])
                    basis.append(cycle[::-1])
                    continue
                parent[v] = u
                stack.append((v, iter(adj[v])))
                break
            else:
                stack.pop()
    return basis

V = 'ABCDEFGH'
E = ['AB', 'BC', 'CA', 'BD', 'CE', 'DE', 'DF', 'EG', 'FG', 'GH']
basis = cycle_basis(V, E)
print(len(basis), len(E) - len(V) + 1, basis)
# 3 3 [['A', 'B', 'C'], ['B', 'C', 'E', 'D'], ['E', 'D', 'F', 'G']]

def edges_of(cycle):
    return {''.join(sorted(p)) for p in zip(cycle, cycle[1:] + cycle[:1])}
total = edges_of(basis[0]) ^ edges_of(basis[1]) ^ edges_of(basis[2])
print(sorted(total))
# ['AB', 'AC', 'BD', 'CE', 'DF', 'EG', 'FG']

L'exemple a 10 − 8 + 1 = 3 cycles indépendants, et l'arbre de recherche de la section 3 produit les trois plus naturels : le triangle et les deux carrés. Leur différence symétrique annule les arêtes partagées B–C et D–E et laisse le cycle extérieur de longueur 7.

L'espace a 23 = 8 éléments, et les examiner tous est instructif. L'un est vide. Six sont les six cycles du graphe. Le dernier est le triangle accompagné du carré D, E, G, F : chaque sommet est de degré pair, mais les deux cycles n'ont aucun sommet commun, donc l'ensemble n'est pas un cycle unique. Les éléments de l'espace des cycles sont des unions de cycles disjoints en arêtes, pas toujours des cycles. Pour K10 l'écart entre les deux décomptes est spectaculaire : un rang de 45 − 10 + 1 = 36, contre 556 014 cycles réels.

Le même nombre apparaît en génie logiciel. La complexité cyclomatique de McCabe, introduite en 1976, mesure un programme par le rang des cycles de son graphe de flot de contrôle, soit E − N + 2P pour E arêtes, N nœuds et P morceaux connexes. Le P supplémentaire vient de ce qu'on imagine une arête de plus allant de chaque sortie vers son entrée, ce qui transforme tout chemin à travers le programme en cycle.

8. Cycles impairs et graphes bipartis

La longueur d'un cycle compte autant que son existence. Un graphe est biparti, c'est-à-dire que ses sommets se répartissent en deux côtés avec chaque arête allant de l'un à l'autre, si et seulement s'il n'a aucun cycle impair. Un sens est immédiat : un cycle alterne entre les côtés, il revient donc à son départ après un nombre pair de pas. L'autre sens, démontré par Kőnig en 1916, repose sur ce lemme :

Toute marche fermée de longueur impaire contient un cycle de longueur impaire.

Prenez une plus courte marche fermée impaire. Si elle répète un sommet en cours de route, coupez-la à cet endroit en deux marches fermées plus courtes. Leurs longueurs ont pour somme un nombre impair, donc l'une d'elles est impaire, ce qui contredit le choix de la plus courte. La plus courte marche fermée impaire ne répète donc rien, et c'est un cycle impair. (Sa longueur est au moins 3, car une marche fermée de longueur 1 nécessiterait une boucle.)

En pratique, le test est une 2-coloration par parcours en largeur : coloriez le sommet de départ, donnez à chaque voisin la couleur opposée, et cherchez une arête dont les deux extrémités reçoivent la même couleur. Quand vous en trouvez une, les deux chemins d'arbre allant de ses extrémités à leur plus proche ancêtre commun, plus l'arête elle-même, forment un cycle impair, qui est le certificat qu'aucune 2-coloration n'existe. L'exemple n'est pas biparti : trois de ses six cycles, de longueurs 3, 5 et 7, sont impairs, et le triangle suffit à lui seul à le constater.

9. Circuits eulériens et cycles hamiltoniens

Deux problèmes célèbres demandent des trajets fermés particuliers, et ils se situent de part et d'autre d'un profond clivage.

• Un circuit eulérien utilise chaque arête exactement une fois. C'est une piste fermée, généralement pas un cycle, puisqu'il peut passer de nombreuses fois par un même sommet. L'article d'Euler de 1736 sur les ponts de Königsberg a montré que chaque sommet doit alors être de degré pair, et l'article de Hierholzer de 1873 a prouvé la réciproque : un graphe connexe, sommets isolés mis à part, a un circuit eulérien exactement quand tous ses degrés sont pairs. L'histoire complète se trouve dans le guide consacré aux chemins et circuits eulériens.
• Un cycle hamiltonien visite chaque sommet exactement une fois. Aucun test comparable n'est connu. Décider s'il en existe un est NP-complet, l'un des 21 problèmes de la liste de Karp de 1972. Des conditions suffisantes existent, la plus connue étant le théorème de Dirac de 1952 : un graphe simple à n ≥ 3 sommets dans lequel chaque sommet est de degré au moins n/2 possède un cycle hamiltonien.

L'exemple échoue aux deux, pour des raisons simples. Six de ses sommets, B, C, D, E, G et H, sont de degré impair : il n'a donc pas de circuit eulérien, et comme plus de deux degrés sont impairs, pas même une piste eulérienne ouverte. Et H est de degré 1, donc aucun cycle ne peut passer par lui ; le mieux possible est le cycle de longueur 7 qui ne laisse de côté que H. Le problème hamiltonien assorti de distances est le problème du voyageur de commerce.

10. Cycles pondérés : les cycles négatifs

Dès que les arêtes portent des poids, un cycle a un poids total, et un cycle négatif, dont les poids ont une somme inférieure à zéro, casse les plus courts chemins. En faire le tour une fois de plus diminue toujours le coût, si bien que les marches vers tout sommet accessible depuis ce cycle n'ont aucune longueur minimale. L'algorithme de Bellman-Ford le détecte. Un plus court chemin sans cycle négatif a au plus n − 1 arêtes, donc après n − 1 passes de relâchement de toutes les arêtes, toutes les distances sont définitives. Si une n-ième passe améliore encore quelque chose, un cycle négatif existe, et remonter les pointeurs de prédécesseur depuis un sommet amélioré mène à ce cycle.

Une jolie application est l'arbitrage de devises. Donnez à l'arête allant de la devise a à la devise b le poids −log r, où r est le taux de change. Une série d'échanges multiplie l'argent par le produit des taux, et ce produit dépasse 1 exactement quand la somme des poids est négative. Une boucle rentable est un cycle négatif. Quand la question porte sur le cycle de plus petit poids moyen par arête, la caractérisation de la moyenne minimale des cycles donnée par Karp en 1978 la résout avec une complexité O(nm) en temps.

11. Cycles dans une suite : la tortue et le lièvre

Un autre type de détection de cycles s'applique aux graphes dans lesquels chaque sommet a exactement une arête sortante. Suivre les pointeurs next d'une liste chaînée, ou appliquer une fonction f à une valeur encore et encore, revient à parcourir un tel graphe. Sur un ensemble fini, la marche finit forcément par répéter une valeur, et à partir de là elle se répète indéfiniment. La suite ressemble à la lettre grecque rho, ρ : une queue de longueur μ menant à un cycle de longueur λ.

Stocker chaque valeur rencontrée permettrait de trouver la répétition, mais cela coûte une mémoire proportionnelle à μ + λ. La méthode de la tortue et du lièvre n'utilise que deux pointeurs. La tortue avance d'un pas à la fois, le lièvre de deux. Une fois que tous deux sont sur le cycle, le lièvre gagne un pas à chaque mouvement, il rattrape donc la tortue en au plus un tour. Knuth a attribué l'idée à Robert W. Floyd en 1969, bien qu'on ne connaisse aucun article de Floyd qui la décrive.

def floyd(f, x0):
    """Longueur de queue mu et longueur de cycle lam de x0, f(x0), f(f(x0)), ... en mémoire O(1)."""
    tortoise, hare = f(x0), f(f(x0))
    while tortoise != hare:                       # 1. se rencontrer quelque part sur le cycle
        tortoise, hare = f(tortoise), f(f(hare))
    mu, tortoise = 0, x0
    while tortoise != hare:                       # 2. avancer au même pas jusqu'à l'entrée du cycle
        tortoise, hare = f(tortoise), f(hare)
        mu += 1
    lam, hare = 1, f(tortoise)
    while tortoise != hare:                       # 3. faire une fois le tour du cycle
        hare = f(hare)
        lam += 1
    return mu, lam

f = lambda x: (x * x + 1) % 55
print(floyd(f, 0))
# (4, 6)
seq = [0]
for _ in range(11):
    seq.append(f(seq[-1]))
print(seq)
# [0, 1, 2, 5, 26, 17, 15, 6, 37, 50, 26, 17]

Pour f(x) = x2 + 1 mod 55 en partant de 0, les valeurs sont 0, 1, 2, 5 puis elles entrent dans la boucle 26, 17, 15, 6, 37, 50, donc μ = 4 et λ = 6. Les deux pointeurs se rencontrent pour la première fois après six déplacements de la tortue. La seconde phase fonctionne parce qu'au point de rencontre la tortue a fait un certain nombre t de pas et le lièvre 2t, donc t est un multiple de λ. Un pointeur relancé depuis x0 et un autre laissé au point de rencontre, avançant tous deux d'un pas à la fois, arrivent donc ensemble au début du cycle après exactement μ pas.

La méthode demande un temps O(μ + λ) et une mémoire constante. La variante de Brent de 1980, qui téléporte la tortue sur le lièvre aux puissances de deux, nécessite généralement moins d'évaluations de f. Les deux sont utilisées dans la méthode rho de Pollard pour factoriser des entiers, où f est une application polynomiale telle que x2 + c modulo le nombre à factoriser.

12. Là où la détection de cycles compte

Chaque fois que des flèches signifient « attend », « dépend de » ou « fait référence à », un cycle signifie que quelque chose ne peut pas se terminer, ne peut pas être construit ou ne peut pas être libéré.

L'interblocage est le cas d'école. Coffman, Elphick et Shoshani ont énoncé en 1971 quatre conditions qui doivent toutes être réunies pour qu'un interblocage se produise, et la dernière d'entre elles, l'attente circulaire, est en termes de graphes un cycle parmi les tâches en attente. Un système peut prévenir l'interblocage en excluant l'une des conditions, par exemple en acquérant toujours les verrous dans un ordre global fixe, ce qui fait du graphe d'attente un DAG. Il peut aussi laisser les interblocages se produire, chercher un cycle de temps en temps et le briser en interrompant l'un de ses membres.

La gestion de la mémoire est la même histoire sous une autre forme. Un compteur de références tombe à zéro quand le dernier pointeur vers un objet disparaît, mais deux objets qui pointent l'un vers l'autre maintiennent mutuellement leurs compteurs à 1 même quand plus rien d'autre ne peut les atteindre. C'est pourquoi CPython complète le comptage de références par un ramasse-miettes distinct, chargé de trouver ces cycles inaccessibles.

13. Erreurs courantes

14. Glossaire

16. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Euler, L. (1741). "Solutio problematis ad geometriam situs pertinentis." Commentarii academiae scientiarum Petropolitanae 8, 128 à 140. Volume daté de 1736. Les ponts de Königsberg et la condition de degré pour les circuits eulériens.
2. Kirchhoff, G. (1847). "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik und Chemie 72(12), 497 à 508. Les arbres couvrants et un cycle indépendant par arête restante.
3. Hierholzer, C. (1873). "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6(1), 30 à 32. Publié après la mort de l'auteur.
4. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77(4), 453 à 465. Un graphe est biparti exactement quand il n'a aucun cycle impair.
5. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2(1), 69 à 81.
6. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 à 90.
7. Kahn, A. B. (1962). "Topological Sorting of Large Networks." Communications of the ACM 5(11), 558 à 562.
8. Knuth, D. E. (1969). The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Reading, MA : Addison-Wesley. Section 3.1, exercice 6, avec la méthode de recherche de cycle attribuée à Floyd.
9. Coffman, E. G., Elphick, M. J. et Shoshani, A. (1971). "System Deadlocks." Computing Surveys 3(2), 67 à 78.
10. Tarjan, R. E. (1972). "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing 1(2), 146 à 160.
11. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." Dans Complexity of Computer Computations, 85 à 103. New York : Plenum. Le circuit hamiltonien orienté et non orienté figure parmi les 21 problèmes NP-complets.
12. Pollard, J. M. (1975). "A Monte Carlo Method for Factorization." BIT 15(3), 331 à 334.
13. Johnson, D. B. (1975). "Finding All the Elementary Circuits of a Directed Graph." SIAM Journal on Computing 4(1), 77 à 84.
14. McCabe, T. J. (1976). "A Complexity Measure." IEEE Transactions on Software Engineering SE-2(4), 308 à 320.
15. Itai, A. et Rodeh, M. (1978). "Finding a Minimum Circuit in a Graph." SIAM Journal on Computing 7(4), 413 à 423.
16. Karp, R. M. (1978). "A Characterization of the Minimum Cycle Mean in a Digraph." Discrete Mathematics 23(3), 309 à 311.
17. Brent, R. P. (1980). "An Improved Monte Carlo Factorization Algorithm." BIT 20(2), 176 à 184. Une méthode de recherche de cycle plus rapide.
18. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.