Marches, pistes, chemins, circuits et cycles

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Six mots pour se déplacer dans un graphe

La théorie des graphes dispose d'une petite famille de mots pour désigner les déplacements le long des arêtes d'un graphe : marche, piste et chemin pour les parcours qui peuvent se terminer n'importe où, et marche fermée, circuit et cycle pour les parcours qui reviennent à leur point de départ. Ils ne diffèrent que sur trois points : un sommet peut-il être visité deux fois, une arête peut-elle être empruntée deux fois, et le parcours se termine-t-il à son sommet de départ.

• Une marche est une suite de sommets v0, v1, ..., vk dans laquelle deux sommets consécutifs sont toujours reliés par une arête. Les sommets et les arêtes peuvent se répéter. La longueur de la marche est k, le nombre de pas effectués, les arêtes répétées étant comptées à chaque passage.
• Une piste est une marche qui n'emprunte jamais deux fois la même arête. Elle peut passer plus d'une fois par un même sommet.
• Un chemin est une marche qui ne visite jamais deux fois le même sommet. Une arête empruntée deux fois ramènerait à ses deux extrémités, donc un chemin ne répète jamais non plus une arête.
• Une marche fermée est une marche dont le dernier sommet est le premier.
• Un circuit est une piste fermée : il se termine là où il a commencé et n'emprunte aucune arête deux fois.
• Un cycle est une marche fermée de longueur au moins 3 dans laquelle aucun sommet ne se répète, si ce n'est que le dernier sommet est le premier.

Ce sont les définitions employées par la plupart des manuels modernes de théorie des graphes, mais pas par tous, et la section 4 montre où les principales conventions divergent. L'exemple suivi est une bande de quatre triangles, avec 6 sommets et 9 arêtes :

edges = {AB, AC, BC, BD, CD, CE, DE, DF, EF}      6 sommets, 9 arêtes

rangée du haut :   B     D     F
rangée du bas :  A     C     E

deg:   A 2   B 3   C 4   D 4   E 3   F 2

Chaque parcours de la figure reçoit le nom le plus précis des six qui lui convienne :

• A, B, C, A, B, D est une marche de longueur 5. Elle emprunte l'arête A-B deux fois, donc ce n'est pas une piste.
• A, C, B, D, C, E est une piste de longueur 5. Elle visite C deux fois, donc ce n'est pas un chemin, mais ses cinq arêtes sont toutes différentes.
• A, C, D, F est un chemin de longueur 3. Ses quatre sommets sont tous différents.
• A, B, C, D, B, A est une marche fermée de longueur 5. Elle revient en A, mais emprunte A-B deux fois.
• A, B, C, D, E, C, A est un circuit de longueur 6. Il revient en A avec six arêtes différentes, mais passe par C deux fois.
• A, B, D, F, E, C, A est un cycle de longueur 6. Il fait le tour extérieur de la bande et ne répète rien.

Un sommet seul, comme A, compte aussi : c'est une marche de longueur 0 et un chemin de longueur 0, que l'on appelle marche triviale ou chemin trivial. Cela compte surtout pour les cas limites des preuves et du code, où « le chemin d'un sommet à lui-même » doit exister et avoir la longueur 0.

2. Comment les six s'emboîtent

Les définitions s'emboîtent. Tout chemin est une piste, car un parcours qui ne revisite jamais un sommet ne peut pas réemprunter une arête, et toute piste est une marche. Du côté fermé, tout cycle est un circuit et tout circuit est une marche fermée. Aucune de ces inclusions ne s'inverse, comme le montrent les exemples de la section 1. Trois questions suffisent toujours à trouver le bon nom, et l'ordre dans lequel on les pose n'a pas d'importance.

Les décomptes de l'exemple montrent à quelle vitesse les familles s'écartent. De A à F il y a exactement 13 chemins : 3 de longueur 3, 6 de longueur 4 et 4 de longueur 5. Il y a 23 pistes : les 13 chemins plus 10 pistes qui passent deux fois par un même sommet, comme A, C, B, D, C, E, F. Il y a une infinité de marches, car une marche peut faire des allers-retours sur n'importe quelle arête aussi souvent qu'elle le veut. Le nombre de marches ne devient fini que lorsque la longueur est fixée, et la section 6 les compte exactement.

Deux détails piègent les débutants :

• La longueur compte les arêtes, pas les sommets. Le chemin A, C, D, F a quatre sommets et une longueur de 3. Un cycle passant par k sommets a une longueur de k, car son dernier pas revient au départ.
• Un cycle s'écrit de plusieurs façons. Le cycle A, B, D, F, E, C, A peut être écrit à partir de n'importe lequel de ses 6 sommets et dans les deux sens, ce qui donne 12 suites pour un seul cycle. Un chemin peut de même être lu depuis l'une ou l'autre de ses extrémités. Un code qui compte les cycles en énumérant des suites doit diviser par 2k, sinon il comptera chaque cycle de longueur k autant de fois.

Pourquoi un cycle doit-il avoir une longueur d'au moins 3 ? Dans un graphe simple, les marches fermées les plus courtes, comme A, B, A, partent le long d'une arête et reviennent aussitôt par la même. Elles répètent une arête, donc ce ne sont ni des circuits ni des cycles. Dans un multigraphe la situation change : deux arêtes parallèles entre les deux mêmes sommets forment un cycle de longueur 2, et une boucle forme un cycle de longueur 1. C'est aussi pourquoi la définition formelle d'une marche énumère les arêtes en plus des sommets, v0, e1, v1, e2, ..., vk : lorsque deux arêtes parallèles relient les mêmes sommets, la liste des sommets seule ne dit pas quelle arête a été empruntée. Dans un graphe simple, les sommets déterminent les arêtes, et il suffit d'énumérer les sommets.

3. Vérifier un parcours avec du code

Les définitions se traduisent directement en une courte fonction. Elle prend un graphe simple et une suite de sommets, vérifie que chaque pas suit une arête, puis pose les trois questions de la section 2.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def classify(adj, seq):
    """Nomme le type de marche le plus précis auquel correspond la suite de sommets seq."""
    steps = list(zip(seq, seq[1:]))
    if any(v not in adj[u] for u, v in steps):
        return 'not a walk'
    closed = len(seq) > 1 and seq[0] == seq[-1]
    edges = [frozenset(step) for step in steps]
    no_repeated_edge = len(set(edges)) == len(edges)
    inner = seq[:-1] if closed else seq          # une marche fermée finit là où elle a commencé
    no_repeated_vertex = len(set(inner)) == len(inner)
    if not closed:
        return 'path' if no_repeated_vertex else 'trail' if no_repeated_edge else 'walk'
    if no_repeated_vertex and len(edges) >= 3:
        return 'cycle'
    return 'circuit' if no_repeated_edge else 'closed walk'

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
for seq in ['ABCABD', 'ACBDCE', 'ACDF', 'ABCDBA', 'ABCDECA', 'ABDFECA', 'ABA', 'ABE']:
    print(seq, classify(strip, seq))
# ABCABD walk
# ACBDCE trail
# ACDF path
# ABCDBA closed walk
# ABCDECA circuit
# ABDFECA cycle
# ABA closed walk
# ABE not a walk

La fonction rejette d'abord A, B, E, car il n'y a pas d'arête entre B et E. Pour un parcours fermé, elle compare les sommets sans le dernier, puisqu'une marche fermée répète toujours son premier sommet à la fin. Le test len(edges) >= 3 est ce qui empêche A, B, A d'être signalé comme un cycle : ses deux sommets sont différents, mais ses deux pas empruntent la même arête. La vérification complète prend un temps proportionnel à la longueur du parcours.

4. Pourquoi les manuels divergent

Si vous avez déjà rencontré ces mots, vous les avez peut-être rencontrés avec d'autres sens. La théorie des graphes s'est développée dans plusieurs pays et plusieurs domaines à la fois, et son vocabulaire n'a jamais été entièrement normalisé. Le tableau compare les mots anglais que quelques manuels très utilisés donnent aux mêmes quatre idées.

Depuis le livre de Harary de 1969, la plupart des ouvrages de théorie des graphes s'accordent sur l'essentiel : le mot walk (marche) désigne un parcours qui peut tout répéter, et le mot path (chemin) un parcours qui ne répète rien. En 1962, l'ouvrage d'Ore Theory of Graphs montrait l'usage plus ancien, dans lequel path désignait un parcours sans arête répétée, ce que l'on appelle aujourd'hui trail (piste). Le manuel de Rosen intitulé Discrete Mathematics and Its Applications, ouvrage de référence pour les premiers cours de mathématiques discrètes, en conserve une version : path y désigne n'importe quelle marche (walk), et le terme simple path un parcours qui ne répète pas d'arête. Rosen signale lui-même le conflit et cite walk, closed walk et trail comme les mots des autres ouvrages, mais un étudiant qui apprend « path » chez Rosen puis ouvre un livre de théorie des graphes y trouvera le même mot avec un sens plus strict.

Les mots circuit et cycle sont les moins stables. West, ainsi que Chartrand et Zhang, emploient circuit pour une piste fermée (closed trail), comme le fait cet article. Ore employait circuit pour ce que l'on appelle aujourd'hui un cycle, et les ingénieurs disent souvent « circuit » pour n'importe quelle boucle fermée. Les graphes orientés ajoutent une couche de plus : dans les ouvrages classiques de Berge, écrits d'abord en français, un parcours dans un graphe non orienté est une chaîne (chain en anglais) et un parcours fermé un cycle, tandis qu'un parcours qui suit les flèches est un chemin (path en anglais) et un parcours fermé un circuit.

L'habitude la plus sûre consiste à énoncer la définition que vous utilisez la première fois qu'un mot apparaît, ou à remplacer le mot ambigu par la propriété : « un parcours qui ne répète aucun sommet » ne peut pas être mal compris. En lisant, cherchez la définition dans le premier chapitre et attendez-vous à ce qu'elle diffère de celle du dernier livre que vous avez lu.

La victime la plus connue de ces noms est le chemin eulérien. Il emprunte chaque arête d'un graphe exactement une fois et passe généralement plusieurs fois par certains sommets ; dans le vocabulaire de cet article, c'est donc une piste, pas un chemin. Le nom survit parce que le problème est plus ancien que le vocabulaire, et « piste eulérienne » est aujourd'hui le nom le plus rigoureux pour la même chose. Le chemin hamiltonien, qui visite chaque sommet exactement une fois, est vraiment un chemin. La section 8 revient sur les deux.

5. Toute marche contient un chemin

Le fait le plus utile sur les marches est que la répétition n'est jamais nécessaire pour aller quelque part. S'il existe une marche de u à v, il existe un chemin de u à v, et ce chemin n'est pas plus long que la marche. La preuve est un raccourci. Si la marche visite un sommet x deux fois, supprimez tout ce qui se trouve entre les deux visites : la marche va toujours de u à v, et elle est plus courte. Recommencez jusqu'à ce qu'aucun sommet ne se répète. Ce qui reste est un chemin.

Ce petit lemme a de grandes conséquences :

• Connexité. « Il existe une marche entre deux sommets quelconques » et « il existe un chemin entre deux sommets quelconques » veulent dire la même chose, donc un graphe peut être dit connexe avec l'un ou l'autre mot. Le guide des composantes connexes s'appuie sur ce fait.
• Les plus courts parcours sont des chemins. Une plus courte marche entre deux sommets ne répète jamais un sommet, puisque supprimer la répétition la raccourcirait. C'est pourquoi le parcours en largeur et l'algorithme de Dijkstra peuvent explorer des marches sans jamais vérifier les sommets répétés, tout en renvoyant des chemins. Le guide des algorithmes de plus court chemin couvre les deux.
• Les poids négatifs le mettent en défaut. Avec des poids d'arêtes négatifs, couper une boucle peut allonger un parcours, car la boucle pouvait avoir un poids total négatif. Si un cycle négatif est accessible, les marches peuvent devenir aussi bon marché que l'on veut en refaisant le tour, et les plus courtes marches cessent d'exister. Les plus courts chemins existent toujours, mais en trouver un devient NP-difficile en général, puisque cela permettrait aussi de trouver les plus longs chemins de la section 7. Le guide de l'algorithme de Bellman-Ford montre comment détecter de tels cycles.

Les marches fermées demandent plus de soin. Une marche fermée ne contient pas toujours un cycle : A, B, A est fermée mais n'en contient aucun. Une marche fermée de longueur impaire en contient toujours un, et le cycle qu'elle contient est lui aussi impair. Coupez la marche fermée en un sommet répété pour obtenir deux marches fermées plus courtes. Leurs longueurs ont pour somme la longueur impaire d'origine, donc l'une d'elles est impaire. Gardez la marche impaire et recommencez. Le processus s'arrête sur une marche fermée impaire sans sommet répété, et comme un graphe simple n'a aucune marche fermée de longueur 1, cette marche est un cycle de longueur au moins 3.

Cet argument est l'étape clé du théorème de Kőnig : un graphe est biparti exactement lorsqu'il n'a aucun cycle de longueur impaire. Un circuit se découpe de la même façon, en cycles qui ne partagent aucune arête. Le programme ci-dessous réalise les trois opérations : il coupe les boucles d'une marche, trouve un cycle impair dans une marche fermée impaire et découpe un circuit en cycles.

def walk_to_path(walk):
    """Coupe chaque boucle. Le résultat est un chemin ayant les deux mêmes extrémités."""
    path, where = [], {}
    for v in walk:
        if v in where:                       # retour en v : on supprime tout depuis la dernière visite
            for u in path[where[v] + 1:]:
                del where[u]
            del path[where[v] + 1:]
        else:
            where[v] = len(path)
            path.append(v)
    return ''.join(path)

def split_closed_walk(walk):
    """Coupe une marche fermée en son premier sommet répété, en deux marches fermées plus courtes."""
    seen = {}
    for i, v in enumerate(walk[:-1]):
        if v in seen:
            j = seen[v]
            return walk[j:i + 1], walk[:j] + walk[i:]
        seen[v] = i
    return None                              # rien ne se répète : un cycle, ou un aller-retour

def odd_cycle(walk):
    """Une marche fermée de longueur impaire contient toujours un cycle de longueur impaire."""
    while True:
        parts = split_closed_walk(walk)
        if parts is None:
            return walk
        walk = next(p for p in parts if (len(p) - 1) % 2 == 1)

def circuit_to_cycles(walk):
    """Découpe un circuit en cycles qui ne partagent aucune arête."""
    parts = split_closed_walk(walk)
    if parts is None:
        return [walk]
    return circuit_to_cycles(parts[0]) + circuit_to_cycles(parts[1])

print(walk_to_path('ACBDCEF'))               # marche de longueur 6
# ACEF
print(odd_cycle('ABCDCA'))                   # marche fermée de longueur 5, arête C-D empruntée deux fois
# ABCA
print(circuit_to_cycles('ABCDECA'))          # circuit de longueur 6 passant deux fois par C
# ['CDEC', 'ABCA']

La piste A, C, B, D, C, E, F visite C deux fois, donc la boucle C, B, D, C disparaît, ce qui laisse A, C, E, F. La marche fermée A, B, C, D, C, A se coupe au sommet C en C, D, C, de longueur 2, et A, B, C, A, de longueur 3, qui est le cycle impair. Le circuit A, B, C, D, E, C, A se coupe au sommet C en deux triangles, C, D, E, C et A, B, C, A.

Le découpage du circuit est un cas particulier d'un théorème publié par Oswald Veblen en 1912 : les arêtes d'un graphe peuvent être réparties en cycles qui ne partagent aucune arête si et seulement si chaque sommet est de degré pair. Un cycle utilise deux arêtes en chaque sommet par lequel il passe, donc les degrés doivent être pairs ; la réciproque s'obtient en retirant un cycle de façon répétée, ce qui garde tous les degrés pairs.

6. Compter les marches avec les puissances de matrices

Les marches sont difficiles à énumérer mais faciles à compter. Écrivez le graphe sous la forme de sa matrice d'adjacence A, avec un 1 à la ligne u, colonne v lorsque u et v sont adjacents et un 0 sinon. Le guide de la représentation des graphes explique la matrice elle-même. Un fait classique est alors vrai : le coefficient à la ligne u, colonne v de la puissance Ak est le nombre de marches de longueur k de u à v.

La raison tient à la règle de multiplication des matrices. Une marche de longueur k de u à v est une marche de longueur k - 1 de u jusqu'à un certain sommet w, suivie d'un pas de w à v. Le nombre de ces marches est donc la somme sur tous les w de (marches de longueur k - 1 de u à w) fois A[w][v], ce qui est exactement le coefficient de Ak-1 fois A. Une récurrence sur k fait le reste.

La bande illustre plusieurs conséquences à la fois :

• La diagonale de A2 est la liste des degrés. Une marche fermée de longueur 2 part le long d'une arête et revient, et il y en a une pour chaque arête du sommet : 2, 3, 4, 4, 3, 2 pour les sommets de A à F.
• A2[A][D] = 2, pour les marches A, B, D et A, C, D.
• La première puissance ayant un coefficient non nul donne la distance. A1 et A2 valent 0 à la ligne A, colonne F, et A3 vaut 3. La distance de A à F est donc 3, et les trois marches de cette longueur sont les trois plus courts chemins A, B, D, F, A, C, D, F et A, C, E, F. D'après la section 5, les plus courtes marches sont toujours des chemins.
• Les triangles viennent de la diagonale de A3. Une marche fermée de longueur 3 dans un graphe simple fait le tour d'un triangle. Chaque triangle est compté une fois depuis chacun de ses 3 sommets dans chacun des 2 sens, donc le nombre de triangles est la somme de la diagonale divisée par 6 : ici 24 / 6 = 4, les triangles ABC, BCD, CDE et DEF.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def matmul(X, Y):
    return [[sum(x * y for x, y in zip(row, col)) for col in zip(*Y)] for row in X]

def walk_counts(adj, order, k):
    """Le coefficient [i][j] de la puissance k-ième de la matrice d'adjacence compte les marches de longueur k."""
    A = [[int(v in adj[u]) for v in order] for u in order]
    M = A
    for _ in range(k - 1):
        M = matmul(M, A)
    return M

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
order = 'ABCDEF'
for k in range(1, 7):
    M = walk_counts(strip, order, k)
    print(f'length {k}:  A to F {M[0][5]:3}   A back to A {M[0][0]:3}')
# length 1:  A to F   0   A back to A   0
# length 2:  A to F   0   A back to A   2
# length 3:  A to F   3   A back to A   2
# length 4:  A to F   6   A back to A  11
# length 5:  A to F  29   A back to A  24
# length 6:  A to F  78   A back to A  92
A3 = walk_counts(strip, order, 3)
print('triangles:', sum(A3[i][i] for i in range(len(order))) // 6)
# triangles: 4

Le nombre de marches de A à F croît rapidement avec la longueur, de 3 à 78 en trois pas, et pourtant le calcul reste peu coûteux. Chaque multiplication de deux matrices n sur n demande environ n3 opérations, et l'élévation au carré répétée atteint Ak en environ log2 k multiplications, si bien que même les marches de longueur un million peuvent être comptées exactement en quelques dizaines de produits de matrices. La somme de la diagonale de Ak est aussi la somme des valeurs propres de la matrice élevées à la puissance k, et c'est là que les marches rejoignent la théorie spectrale des graphes : la plus grande valeur propre fixe le taux de croissance du nombre de longues marches.

7. Les marches sont faciles, les chemins sont difficiles

L'astuce matricielle n'a pas d'équivalent pour les chemins. Le nombre de chemins entre deux sommets est, en général, difficile à calculer : Leslie Valiant a prouvé en 1979 que compter les chemins entre deux sommets donnés est #P-complet, l'analogue de NP-complet pour les problèmes de comptage. On ne connaît aucune méthode nettement meilleure que l'essai des parcours un par un, et l'on ne s'attend pas à en trouver une. Le programme ci-dessous compte les chemins exactement par ce genre de recherche, et compte les pistes de la même façon, avec les arêtes à la place des sommets.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def count_paths(adj, s, t, seen=None):
    """Nombre de chemins de s à t : essayer chaque voisin non visité, puis annuler."""
    if s == t:
        return 1
    seen = seen or {s}
    total = 0
    for w in adj[s] - seen:
        seen.add(w)
        total += count_paths(adj, w, t, seen)
        seen.remove(w)
    return total

def count_trails(adj, s, t, used=None):
    """Nombre de pistes de s à t. Une piste peut passer par t et y revenir plus tard."""
    used = used or set()
    total = 1 if s == t else 0
    for w in adj[s]:
        e = frozenset((s, w))
        if e not in used:
            used.add(e)
            total += count_trails(adj, w, t, used)
            used.remove(e)
    return total

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
print(count_paths(strip, 'A', 'F'), count_trails(strip, 'A', 'F'))
# 13 23

def grid(n):
    """La grille de rues n sur n : sommets (ligne, colonne), arêtes vers la droite et vers le bas."""
    return graph([((r, c), (r, c + 1)) for r in range(n) for c in range(n - 1)] +
                 [((r, c), (r + 1, c)) for r in range(n - 1) for c in range(n)])

for n in range(2, 6):
    print(n, count_paths(grid(n), (0, 0), (n - 1, n - 1)))
# 2 2
# 3 12
# 4 184
# 5 8512

Sur la bande, la recherche confirme les décomptes de la section 2 : 13 chemins et 23 pistes de A à F. La grille montre à quelle vitesse les nombres explosent. Entre les coins opposés d'une grille de rues ayant 2, 3, 4 et 5 sommets de côté, il y a 2, 12, 184 et 8 512 chemins, et une ligne et une colonne de plus donnent 1 262 816. Les physiciens et les chimistes appellent les chemins dans un réseau régulier des marches auto-évitantes et s'en servent comme modèles de chaînes de polymères, une molécule qui ne peut pas se traverser elle-même.

Le même écart sépare les questions faciles et difficiles sur un parcours unique :

• Plus court chemin : facile. Le parcours en largeur en trouve un en temps linéaire quand les arêtes n'ont pas de poids, et l'algorithme de Dijkstra quand les poids sont positifs ou nuls, grâce au lemme du raccourci de la section 5.
• Plus long chemin : difficile. Décider si un graphe possède un chemin d'au moins une longueur donnée est NP-complet. Un chemin passant par les n sommets a pour longueur n - 1, donc la question contient le problème du chemin hamiltonien comme cas particulier. Dans la bande, le plus long chemin de A à F a pour longueur 5 et passe par les six sommets ; le zigzag A, B, C, D, E, F en est un.
• Plus longue marche : sans objet. Les marches peuvent répéter des arêtes, donc tout graphe ayant une arête possède des marches de toutes les longueurs.

8. Pistes, circuits et Euler

Les pistes appartiennent à Euler. Sa solution de 1736 au problème des ponts de Königsberg cherchait une marche traversant chaque pont exactement une fois : une piste passant par chaque arête d'un multigraphe. Une telle piste est une piste eulérienne, et une piste eulérienne fermée est un circuit eulérien. La condition d'Euler, démontrée complètement par Carl Hierholzer dans un article publié en 1873, porte sur les degrés. Un graphe connexe possède un circuit eulérien exactement lorsque chaque sommet est de degré pair, et une piste eulérienne non fermée exactement lorsque deux sommets, et deux seulement, sont de degré impair ; la piste doit alors commencer en l'un d'eux et se terminer en l'autre.

Dans la bande, B et E sont de degré 3 et tous les autres sommets sont de degré pair, donc une piste eulérienne va de B à E :

B, A, C, B, D, C, E, D, F, E        9 arêtes, chacune empruntée une fois

Elle passe par B, C, D et E deux fois chacun, ce qui explique pourquoi « chemin eulérien » est, à strictement parler, un nom impropre. Le guide des chemins et circuits eulériens présente l'algorithme de Hierholzer en détail. Quand un graphe a plus de deux sommets impairs, certaines arêtes doivent être parcourues deux fois, et trouver la marche fermée la moins coûteuse passant par chaque arête est le problème du postier chinois.

Le théorème de Veblen, vu à la section 5, est l'autre face de la même médaille. Un circuit eulérien est un circuit passant par chaque arête, et le couper en ses sommets répétés répartit les arêtes en cycles qui ne partagent aucune arête. Réciproquement, un graphe connexe dont les arêtes se répartissent en de tels cycles a tous ses degrés pairs, et les cycles peuvent être raccordés en leurs sommets communs pour former un seul circuit eulérien.

9. Cycles, maille et circonférence

La bande a exactement 10 cycles : les quatre triangles, trois cycles de longueur 4, deux de longueur 5 et un de longueur 6.

longueur 3 :  ABC, BCD, CDE, DEF
longueur 4 :  ABDC, BDEC, CDFE
longueur 5 :  ABDEC, BDFEC
longueur 6 :  ABDFEC

Deux nombres résument les cycles d'un graphe. La maille est la longueur d'un plus court cycle, ici 3, et la circonférence est la longueur d'un plus long cycle, ici 6. Un cycle passant par chaque sommet, comme A, B, D, F, E, C, A, est un cycle hamiltonien, donc la bande est hamiltonienne. Un graphe sans aucun cycle est une forêt, et une forêt connexe est un arbre, dans lequel il existe exactement un chemin entre deux sommets quelconques ; le guide des arbres développe cette idée. Le guide des cycles dans les graphes explique comment détecter un cycle par parcours en profondeur et combien de cycles indépendants possède un graphe.

10. Marches et chemins orientés

Dans un graphe orienté chaque pas doit suivre une flèche, de son origine vers son extrémité. Avec ce seul changement, les six définitions se transposent toutes : marche orientée, piste orientée, chemin orienté, marche fermée orientée, circuit orienté et cycle orienté. Quelques points se comportent différemment :

• Des cycles de longueur 2 existent. Deux flèches u → v et v → u sont des arêtes différentes, donc u, v, u est un cycle orienté même dans un graphe sans arêtes parallèles.
• L'accessibilité est à sens unique. Un chemin orienté de u à v ne dit rien d'un chemin retour. Les sommets qui peuvent s'atteindre mutuellement dans les deux sens forment une composante fortement connexe, et le guide des composantes fortement connexes montre comment les trouver.
• Sans cycle orienté, un ordre existe. Un graphe orienté sans cycle orienté, un DAG, peut toujours être énuméré de sorte que chaque flèche pointe vers l'avant. Cette énumération est un tri topologique, et dans un DAG, même le plus long chemin peut être trouvé en temps linéaire.
• Ignorer les flèches donne une semi-marche ou un semi-chemin, qui peut avancer à contresens d'une flèche. Un graphe orienté est faiblement connexe lorsque ses sommets sont reliés par des semi-chemins.

L'astuce matricielle de la section 6 fonctionne telle quelle pour les graphes orientés : le coefficient à la ligne u, colonne v de Ak compte les marches orientées de longueur k de u à v.

11. Où sert chaque type de parcours

Chacun des six mots désigne le bon modèle pour un type différent de problème réel :

• Les chemins sont les parcours de tout ce qui ne doit pas boucler : itinéraires routiers, paquets qui traversent un réseau, chaîne de présentations entre deux personnes. Tout problème de plus court parcours est un problème de chemin, d'après le lemme du raccourci.
• Les pistes et les circuits décrivent le fait de couvrir une fois chaque rue, chaque canalisation ou chaque câble : chasse-neige, balayeuses et tournées postales. Lorsque certaines arêtes doivent être répétées, cela devient le problème du postier chinois de la section 8.
• Les marches apparaissent partout où le mouvement est aléatoire. Une marche aléatoire se déplace vers un voisin aléatoire à chaque pas. George Pólya a prouvé en 1921 qu'une marche aléatoire sur la grille des points à coordonnées entières revient à son point de départ avec certitude en dimension un ou deux, mais pas en dimension trois. Le PageRank original de Google, décrit par Sergey Brin et Lawrence Page en 1998, classe les pages web selon la fréquence à laquelle un internaute aléatoire qui suit les liens les visite, et les méthodes de plongement de graphes comme DeepWalk apprennent à partir de nombreuses courtes marches aléatoires.
• Les cycles sont généralement ce qu'il faut trouver ou interdire : un interblocage est un cycle de processus dont chacun attend le suivant, une importation circulaire ou une formule de tableur qui fait référence à elle-même est un cycle de dépendances, et la loi des mailles de Kirchhoff dit que les tensions le long de chaque cycle d'un réseau électrique ont une somme nulle.
• Les marches fermées comptent des structures : la diagonale de A3 compte les triangles, ce que l'analyse des réseaux sociaux utilise pour mesurer à quel point les amis d'une personne se connaissent entre eux.

12. Erreurs fréquentes

13. Glossaire

15. 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. Présenté en 1736.
2. Hierholzer, C. (1873). "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6, 30 à 32.
3. Veblen, O. (1912). "An Application of Modular Equations in Analysis Situs." Annals of Mathematics, 2e série, 14, 86 à 94.
4. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77, 453 à 465.
5. Pólya, G. (1921). "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz." Mathematische Annalen 84, 149 à 160.
6. Berge, C. (1958). Théorie des graphes et ses applications. Paris : Dunod.
7. Ore, O. (1962). Theory of Graphs. American Mathematical Society Colloquium Publications 38. Providence, RI : American Mathematical Society.
8. Harary, F. (1969). Graph Theory. Reading, MA : Addison-Wesley.
9. Garey, M. R. et Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco : W. H. Freeman.
10. Valiant, L. G. (1979). "The Complexity of Enumeration and Reliability Problems." SIAM Journal on Computing 8(3), 410 à 421.
11. Biggs, N. (1993). Algebraic Graph Theory, 2e édition. Cambridge : Cambridge University Press.
12. Brin, S. et Page, L. (1998). "The Anatomy of a Large-Scale Hypertextual Web Search Engine." Computer Networks and ISDN Systems 30(1 à 7), 107 à 117.
13. West, D. B. (2001). Introduction to Graph Theory, 2e édition. Upper Saddle River, NJ : Prentice Hall.
14. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres : Springer.
15. Chartrand, G. et Zhang, P. (2012). A First Course in Graph Theory. Mineola, NY : Dover.
16. Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 7e édition. New York : McGraw-Hill.
17. Perozzi, B., Al-Rfou, R. et Skiena, S. (2014). "DeepWalk: Online Learning of Social Representations." Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 701 à 710.
18. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.