Théorie des graphes¶

Les graphes sont partout — réseaux, dépendances, workflows, routage — et les algorithmes qui les traversent sont le socle invisible de l'infrastructure moderne.

La structure universelle¶

Un réseau de microservices est un graphe. Un arbre de dépendances npm est un graphe. Le routage BGP entre AS est un graphe. Les états d'une machine a états sont un graphe. Un schéma de base de données avec des clés etrangeres est un graphe.

La théorie des graphes fournit un vocabulaire commun et des algorithmes prouvablement corrects pour analyser toutes ces structures. Savoir qu'OSPF utilisé Dijkstra ou que le tri topologique détecté les cycles n'est pas de la culture générale — c'est savoir pourquoi ces outils ont les propriétés qu'ils ont et ou ils échouent.

Définitions fondamentales¶

Graphe non orienté¶

Un graphe G = (V, E) est compose de :

• V (vertices / sommets) : ensemble des nœuds
• E (edges / aretes) : ensemble de paires {u, v} de sommets

Le degré d'un sommet est le nombre d'aretes qui lui sont incidentes.

Graphe orienté (digraphe)¶

Les aretes sont des paires ordonnées (u, v) — on distingue l'origine et la destination. Le degré entrant (in-degree) est le nombre d'aretes pointant vers un sommet. Le degré sortant (out-degree) est le nombre d'aretes partant d'un sommet.

Graphe pondere¶

Chaque arete porte un poids w(u, v) ∈ ℝ — une distance, une latence, un coût, une capacité.

Connexite¶

Un graphe non orienté est connexe si tout sommet est accessible depuis tout autre sommet. Une composante connexe est un sous-graphe connexe maximal.

Un graphe orienté est fortement connexe si tout sommet est accessible depuis tout autre via un chemin orienté. Un graphe est faiblement connexe si le graphe non orienté sous-jacent est connexe.

Représentations en mémoire¶

from collections import defaultdict

# Liste d'adjacence : la representation standard
class Graphe:
    def __init__(self, oriente=False):
        self.adj = defaultdict(list)
        self.oriente = oriente

    def ajouter_arete(self, u, v, poids=1):
        self.adj[u].append((v, poids))
        if not self.oriente:
            self.adj[v].append((u, poids))

    def voisins(self, u):
        return self.adj[u]

    def sommets(self):
        return set(self.adj.keys())

Parcours : BFS et DFS¶

BFS — Breadth-First Search (parcours en largeur)¶

Le BFS explore le graphe niveau par niveau, en utilisant une file (FIFO). Il trouve le plus court chemin en nombre d'aretes dans un graphe non pondere.

from collections import deque

def bfs(graphe, source):
    """Retourne les distances depuis source (en nombre d'aretes)."""
    distances = {source: 0}
    file = deque([source])

    while file:
        u = file.popleft()
        for v, _ in graphe.voisins(u):
            if v not in distances:
                distances[v] = distances[u] + 1
                file.append(v)

    return distances

# Complexite : O(V + E)

Propriétés du BFS :

• Garantit le chemin le plus court (en aretes non ponderees) vers chaque sommet
• Peut tester la connexite : si len(distances) < |V|, le graphe n'est pas connexe
• Base de l'algorithme de bipartition (un graphe est biparti si et seulement si il n'a pas de cycle impair — détecté par BFS)

DFS — Depth-First Search (parcours en profondeur)¶

Le DFS explore aussi loin que possible avant de revenir en arriere, en utilisant une pile (explicite ou la pile d'appels recursifs).

def dfs(graphe, source, visite=None):
    """DFS recursif — retourne l'ensemble des sommets visites."""
    if visite is None:
        visite = set()
    visite.add(source)
    for voisin, _ in graphe.voisins(source):
        if voisin not in visite:
            dfs(graphe, voisin, visite)
    return visite

# Complexite : O(V + E)

Détection de cycles avec DFS¶

Le DFS colorie les sommets en trois états pour détecter les cycles dans un graphe orienté :

• Blanc : non visite
• Gris : en cours de visite (dans la pile d'appels)
• Noir : traitement termine

Un cycle existe si et seulement si on rencontre un sommet gris pendant le DFS.

def contient_cycle(graphe):
    """Detecte un cycle dans un graphe oriente via DFS."""
    BLANC, GRIS, NOIR = 0, 1, 2
    couleur = {s: BLANC for s in graphe.sommets()}

    def dfs_cycle(u):
        couleur[u] = GRIS
        for v, _ in graphe.voisins(u):
            if couleur[v] == GRIS:
                return True  # Arc arriere -> cycle
            if couleur[v] == BLANC and dfs_cycle(v):
                return True
        couleur[u] = NOIR
        return False

    return any(
        dfs_cycle(u)
        for u in graphe.sommets()
        if couleur[u] == BLANC
    )

Tri topologique¶

Le tri topologique ordonné les sommets d'un DAG (Directed Acyclic Graph) de sorte que pour chaque arete (u, v), u apparaisse avant v. Il n'existe que si le graphe n'a pas de cycle.

Algorithme de Kahn (base sur les degrés entrants) :

from collections import deque

def tri_topologique(graphe):
    """Algorithme de Kahn. Retourne None si un cycle est detecte."""
    # Calculer les degres entrants
    degre_entrant = defaultdict(int)
    for u in graphe.sommets():
        for v, _ in graphe.voisins(u):
            degre_entrant[v] += 1

    # File des sommets sans predecesseur
    file = deque(
        s for s in graphe.sommets()
        if degre_entrant[s] == 0
    )
    ordre = []

    while file:
        u = file.popleft()
        ordre.append(u)
        for v, _ in graphe.voisins(u):
            degre_entrant[v] -= 1
            if degre_entrant[v] == 0:
                file.append(v)

    if len(ordre) != len(list(graphe.sommets())):
        return None  # Cycle detecte
    return ordre

Applications directes du tri topologique :

• Résolution de dépendances (npm install, pip, Maven)
• Ordonnancement de tâches (Makefile, DAGs Airflow)
• Compilation (ordre de compilation des modules)
• Migrations de base de données

Plus courts chemins¶

Dijkstra¶

L'algorithme de Dijkstra trouve le plus court chemin depuis un sommet source vers tous les autres sommets dans un graphe a poids positifs.

Principe : à chaque étape, extraire le sommet non encore traite avec la distance minimale connue, puis "relaxer" ses voisins — mettre à jour leur distance si le passage par ce sommet est plus court.

Table de progression (exemple sur un graphe de 5 nœuds) :

import heapq

def dijkstra(graphe, source):
    """Retourne les distances et predecesseurs depuis source."""
    distances = {source: 0}
    predecesseur = {}
    # Tas min : (distance, sommet)
    tas = [(0, source)]

    while tas:
        dist_u, u = heapq.heappop(tas)

        # Si on a deja traite ce sommet avec une meilleure distance
        if dist_u > distances.get(u, float('inf')):
            continue

        for v, poids in graphe.voisins(u):
            nouvelle_dist = distances[u] + poids
            if nouvelle_dist < distances.get(v, float('inf')):
                distances[v] = nouvelle_dist
                predecesseur[v] = u
                heapq.heappush(tas, (nouvelle_dist, v))

    return distances, predecesseur

def reconstituer_chemin(predecesseur, source, cible):
    chemin = []
    noeud = cible
    while noeud != source:
        chemin.append(noeud)
        noeud = predecesseur[noeud]
    chemin.append(source)
    return list(reversed(chemin))

# Complexite : O((V + E) log V) avec un tas binaire

Bellman-Ford¶

Bellman-Ford géré les poids negatifs et détecté les cycles de poids negatif (qui rendent le problème du plus court chemin sans solution).

Principe : relacher toutes les aretes V-1 fois (un chemin sans cycle a au plus V-1 aretes). Après V-1 iterations, toute distance qui peut encore être améliorée appartient a un cycle negatif.

def bellman_ford(graphe, source):
    """Retourne None si un cycle de poids negatif est detecte."""
    sommets = list(graphe.sommets())
    aretes = [
        (u, v, poids)
        for u in sommets
        for v, poids in graphe.voisins(u)
    ]

    distances = {s: float('inf') for s in sommets}
    distances[source] = 0

    # V - 1 relaxations
    for _ in range(len(sommets) - 1):
        for u, v, poids in aretes:
            if distances[u] + poids < distances[v]:
                distances[v] = distances[u] + poids

    # Detection de cycle negatif
    for u, v, poids in aretes:
        if distances[u] + poids < distances[v]:
            return None  # Cycle negatif detecte

    return distances

# Complexite : O(V × E) — plus lent que Dijkstra

Flot maximal¶

Formulation du problème¶

Dans un graphe orienté pondere, chaque arete a une capacité — le flux maximal qu'elle peut transporter. On cherche le flux maximal de la source s vers le puits t.

Applications : débit maximal d'un réseau, affectation de ressources, correspondance bipartie (matching), découpé d'images en vision par ordinateur.

Ford-Fulkerson et le théorème min-cut/max-flow¶

Algorithme de Ford-Fulkerson : trouver un chemin augmentant (source vers puits avec capacité residuelle positive), augmenter le flux sur ce chemin, répéter jusqu'à ce qu'il n'existe plus de chemin augmentant.

Théorème min-cut/max-flow (Ford-Fulkerson, 1956) : la valeur du flot maximal est egale à la capacité du coupe minimal (l'ensemble d'aretes dont la suppression déconnecté source et puits et dont la somme des capacités est minimale).

Ce théorème a des implications profondes : il etablit une dualite entre un problème de maximisation (flot) et un problème de minimisation (coupe). Il est utilisé dans la théorie des réseaux, la planification de capacité, et la conception de CDN.

Diagramme : graphe de dépendances et chemin critique¶

graph LR
    A([Debut]) --> B[Infra: 2j]
    A --> C[Schema DB: 1j]
    B --> D[Backend API: 3j]
    C --> D
    C --> E[Migration: 2j]
    D --> F[Tests integration: 2j]
    E --> F
    D --> G[Frontend: 4j]
    F --> H[Staging: 1j]
    G --> H
    H --> I([Fin])

    style A fill:#2d6a4f,color:#fff
    style I fill:#2d6a4f,color:#fff
    style B fill:#e76f51,color:#fff
    style D fill:#e76f51,color:#fff
    style G fill:#e76f51,color:#fff
    style H fill:#e76f51,color:#fff

Chemin critique (en rouge) : Infra (2j) → Backend API (3j) → Frontend (4j) → Staging (1j) = 10 jours. Tout retard sur ce chemin retarde la livraison.

Le chemin critique est le plus long chemin du début à la fin dans le graphe de dépendances de tâches — il détermine la durée minimale du projet. L'algorithme de calcul est un tri topologique suivi d'une relaxation des distances (Dijkstra adapté pour la maximisation).

Applications systèmes¶

Graphes de dépendances : npm, Maven, pip¶

Un package manager maintient un DAG de dépendances. L'installation suit un tri topologique. La détection de conflits de version est un problème de satisfiabilite sur un graphe contraint (SAT, dans les cas complexes).

probleme npm : trouver un sous-ensemble de versions
tel que toutes les contraintes (A@>=1.0 ∧ B@<2.0 ∧ ...) soient satisfaites
et que le graphe de dependances resultant soit sans cycle

Les "dependency hell" surgissent quand le système de contraintes est insatisfaisable — deux packages exigent des versions incompatibles d'un même tiers.

Routage réseau : OSPF et Dijkstra¶

OSPF (Open Shortest Path First) est un protocole de routage interne qui utilise exactement l'algorithme de Dijkstra. Chaque routeur :

1. Construit une représentation complète de la topologie du réseau (Link State Database)
2. Exécuté Dijkstra depuis lui-même comme source
3. Installe les prochains sauts dans sa table de routage

Le "poids" d'une arete OSPF est configurable — il peut représenter la bande passante inverse, la latence, ou un coût administratif. Un opérateur peut forcer le trafic vers un lien en abaissant son poids OSPF.

BGP (inter-AS) n'utilise pas Dijkstra mais un algorithme de vecteur de distance (inspiré de Bellman-Ford) avec des attributs de politique — car les AS ont des politiques de routage différentes, pas seulement des coûts.

Ordonnancement de tâches et méthode du chemin critique¶

La méthode PERT/CPM (Critical Path Method) est un tri topologique suivi d'un calcul de chemin critique. En DevOps :

• Les pipelines CI/CD sont des DAGs — Jenkins, GitLab CI, GitHub Actions les représentent explicitement
• Airflow, Prefect, et Dagster modelisent les workflows de données comme des DAGs
• Les Makefiles sont des DAGs de dépendances de fichiers

Composantes fortement connexes¶

Les composantes fortement connexes (SCC) d'un graphe orienté sont les groupes maximaux de sommets mutuellement accessibles. L'algorithme de Kosaraju ou de Tarjan les calcule en O(V+E).

Application : dans un graphe de microservices, une SCC de plus d'un nœud indique un couplage circulaire — le service A dépend de B qui dépend de A. C'est presque toujours une erreur d'architecture. Un outil comme dependency-cruiser détecté ces cycles en construisant le graphe de dépendances et en calculant les SCC.

Formulaire de référence¶