Cours Graphes et algorithmique des graphes en PDF (Avancé)

Graphes et algorithmique des graphes : Ce qu'il faut savoir. Un graphe est une structure combinatoire composée d'un ensemble de sommets et d'arêtes (ou d'arcs pour les graphes orientés) permettant de modéliser relations et connexions entre objets. Ce document définit formellement un graphe G = (V,E) comme un couple d'ensembles finis de sommets et d'arêtes. Le domaine couvre à la fois des définitions formelles (degrés, voisinages, chaînes, cycles) et une large palette d'algorithmes pour le parcours, l'optimisation (arbres couvrants, plus courts chemins), le flot et la coloration.

Ce que vous allez apprendre

• Représentations et parcours (BFS/DFS) — maîtrise des représentations usuelles (listes d'adjacence, matrices d'adjacence), implémentation et analyse en complexité des parcours en largeur et profondeur, et utilisation de la classification des arcs issue du DFS pour détecter cycles et extraire arbres couvrants de parcours.
• Arbres couvrants de poids minimum — propriétés des arbres couvrants minimaux et application des algorithmes de Kruskal et Prim; preuves de correction et analyses en complexité pour contextes pondérés.
• Plus courts chemins — techniques pour chemins de coût minimum, notamment Dijkstra et Bellman‑Ford (garanties et limitations); choix d'algorithme selon la présence de poids négatifs et structures de données pour l'efficacité.
• Flot maximum et coupes — concepts de réseaux, graphe des écarts et chemins améliorants (Ford–Fulkerson), variantes Edmonds–Karp et méthodes par préflots; relations flots/coupes et analyses de validité et complexité.
• Couplage et coloration — étude du couplage maximum (notamment pour graphes bipartis), nombre chromatique et heuristiques de coloration utiles en pratique.
• Rigueur algorithmique et exercices — pseudo‑code commenté, preuves de correction et analyses asymptotiques; exemples et exercices pour consolider l'intuition et la capacité à raisonner formellement.

Définitions et notations fondamentales

Les notations employées sont précisées afin d'éviter les ambiguïtés en démonstration et en implémentation. On note généralement G = (V,E) un graphe, avec V l'ensemble des sommets et E l'ensemble des arêtes. Pour les graphes orientés, une arête est un couple ordonné (u,v) ∈ V×V, tandis que pour les graphes non orientés on considère des paires non ordonnées. Les notions de degré, de voisin, de chemin, de cycle et de composantes connexes sont définies formellement et illustrées par des exemples et notations standard permettant d'analyser la complexité algorithmique des méthodes présentées.

Sommaire du document

• Cours Graphes et algorithmique des graphes en PDF (Avancé)

Pourquoi choisir ce cours ?

Support issu d'un enseignement à l'École normale supérieure de Lyon, rédigé par Brice Goglin. L'approche combine définitions formelles, démonstrations mathématiques et présentations algorithmiques avec pseudo‑code et analyses de complexité, ce qui rend le document adapté aux travaux pratiques et à la préparation aux examens pour étudiants et ingénieurs.

À qui s'adresse ce cours ?

• Public cible : étudiants en informatique (niveau licence 3 / L3), masters débutants et ingénieurs en algorithmique impliqués dans réseaux, optimisation ou combinatoire.
• Prérequis : mathématiques discrètes (ensembles, preuves), complexité algorithmique et notations asymptotiques, structures de données de base (listes, piles, files, tableaux) et capacité à lire du pseudo‑code.

FAQ

Comment la classification des arcs issue d'un DFS permet‑elle de détecter les cycles et d'assister un tri topologique ?

En DFS on distingue arcs d'arbre, arcs avant, arcs arrière et arcs transverses; la présence d'un arc arrière signale un cycle dirigé. Si aucun arc arrière n'est trouvé, les temps de sortie du DFS fournissent un ordre des sommets utilisable pour produire un tri topologique valide.

Dans quel cas Dijkstra est‑il inadapté et que propose Bellman‑Ford à la place ?

Dijkstra exige des poids d'arêtes non négatifs pour garantir l'optimalité des distances extraites d'une file de priorité; en présence d'arêtes à poids négatif, Bellman‑Ford reste correct et détecte les cycles de poids négatif. Bellman‑Ford a toutefois une complexité temporelle plus élevée, généralement en O(n·m) selon l'implémentation.

Plus courts chemins

La section traite des algorithmes classiques pour les distances minimales et compare leurs garanties, complexités et structures de données associées. Dijkstra, avec une file de priorité, atteint O((n+m) log n) ou O(m + n log n) selon la mise en œuvre et la file utilisée; Bellman‑Ford couvre les poids négatifs en O(n·m). Le choix entre algorithmes dépend de la densité du graphe, de la présence de poids négatifs et des contraintes mémoire. Des cas d'application concrets et des variantes optimisées sont fournis pour des contextes orientés performance.

Exemple d'implémentation

# structure minimale d'une file de priorité en Python (heapq)
import heapq

def dijkstra(adj, source):
    n = len(adj)
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]  # (distance, sommet)
    while heap:
        d, u = heapq.heappop(heap)
        if d != dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Cas d'usage concrets

Les concepts et méthodes présentés se transposent à des problèmes industriels et de recherche. Pour chaque cas, la complexité typique est indiquée afin de guider le choix d'algorithmes et de structures de données.

• Optimisation de réseaux de transport (Dijkstra) — calcul de plus courts chemins pour routage et navigation; complexité typique O(m + n log n) avec heap binaire ou O(m log n) selon structure utilisée.
• Planification de tâches (Tri topologique) — ordonnancement de tâches acycliques et détection d'ordre partiel; algorithme de tri topologique linéaire en O(n + m) sur les graphes acycliques dirigés.
• Analyse de réseaux sociaux (Connexité) — découverte de composantes connexes et distances moyennes; parcours BFS/DFS en O(n + m) permettent d'extraire composantes et mesures de centralité.

Exercices et Travaux Dirigés

Le PDF inclut une collection d'exercices et de travaux dirigés avec corrigés couvrant graphes orientés, couplage, flots, arbres couvrants et complexité algorithmique. Les corrigés commentés facilitent l'apprentissage autonome et la préparation aux TD, en mettant l'accent sur la rigueur des preuves et l'analyse asymptotique.

Index des notations et symboles

Ce index récapitule les symboles et notations fréquemment utilisés dans le document afin d'assurer une lecture cohérente et sans ambiguïté. Les définitions ci‑dessous servent de référence rapide lors de la lecture des démonstrations et des pseudo‑codes.

Bibliographie et ressources complémentaires

Pour approfondir la théorie et les algorithmes présentés, les références ci‑dessous offrent des développements détaillés, exercices corrigés et perspectives avancées en théorie des graphes, graphes orientés et complexité algorithmique.

Références bibliographiques

• Minoux, M. — Graphes et algorithmes (ouvrage technique de référence en algorithmique des graphes).
• Diestel, R. — Graph Theory (exposition rigoureuse de la théorie des graphes).
• Kleinberg, J. & Tardos, É. — Algorithm Design (méthodes d'analyse et conception d'algorithmes).
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. — Introduction to Algorithms (chapitres pertinents sur graphes et complexité).