# Fichier: python_cheats/cheatsheets/théorie_des_graphes.txt
# Cheatsheet Théorie des Graphes - Guide Ultra-Détaillé pour Grands Débutants


[OK] CONCEPTS FONDAMENTAUX (EXPLICATIONS TRÈS DÉTAILLÉES)

# === QU'EST-CE QU'UN GRAPHE ? ===

# Imagine que tu es sur Facebook
# Tu as des amis, et tes amis ont leurs propres amis
# Comment représenter toutes ces relations?

# Solution: UN GRAPHE!

# Un graphe = Une structure mathématique pour représenter des RELATIONS
# Il est composé de:
#   - SOMMETS (ou NŒUDS): Les éléments individuels
#   - ARÊTES (ou ARCS): Les connexions entre les éléments

# Exemple concret Facebook:
#   - Chaque PERSONNE = un sommet
#   - Chaque AMITIÉ = une arête entre deux sommets

# Représentation visuelle simple:

#     Alice ———— Bob
#       |          |
#       |          |
#     Carol ——— David

# Ici:
# - 4 sommets: Alice, Bob, Carol, David
# - 4 arêtes: Alice-Bob, Alice-Carol, Bob-David, Carol-David

# POURQUOI utiliser des graphes?
# - Modéliser des réseaux sociaux (Facebook, Twitter)
# - GPS et navigation (routes, villes)
# - Réseaux informatiques (routeurs, ordinateurs)
# - Molécules chimiques (atomes, liaisons)
# - Planification de projets (tâches, dépendances)
# - Intelligence artificielle (états, transitions)

# NOTATION MATHÉMATIQUE:
# Un graphe G est défini par: G = (V, E)
# V = Ensemble des sommets (Vertices)
# E = Ensemble des arêtes (Edges)

# Exemple:
# V = {Alice, Bob, Carol, David}
# E = {(Alice,Bob), (Alice,Carol), (Bob,David), (Carol,David)}


# === VOCABULAIRE ESSENTIEL (À CONNAÎTRE ABSOLUMENT!) ===

# SOMMET (Vertex/Node)
# = Un point dans le graphe
# = Représente un élément individuel
# Analogie: Une personne dans un réseau social
# Synonymes: Nœud, Point

# ARÊTE (Edge)
# = Une ligne qui connecte deux sommets
# = Représente une relation entre deux éléments
# Analogie: Une amitié entre deux personnes
# Synonymes: Arc, Lien, Connexion

# DEGRÉ d'un sommet
# = Nombre d'arêtes connectées à ce sommet
# Formule: deg(v) = nombre d'arêtes incidentes à v
# Exemple:
#     A ———— B
#     |
#     C
# deg(A) = 2 (connecté à B et C)
# deg(B) = 1 (connecté à A seulement)
# deg(C) = 1 (connecté à A seulement)

# CHEMIN (Path)
# = Séquence de sommets connectés par des arêtes
# = Tu peux "voyager" d'un sommet à un autre
# Exemple: A -> B -> D -> E est un chemin

# LONGUEUR d'un chemin
# = Nombre d'arêtes dans le chemin
# Exemple: A -> B -> C a une longueur de 2

# CYCLE (Circuit)
# = Chemin qui commence et finit au même sommet
# = Tu reviens à ton point de départ
# Exemple: A -> B -> C -> A est un cycle

# CONNEXITÉ
# = Un graphe est CONNEXE si tu peux aller de n'importe quel sommet
#   vers n'importe quel autre sommet en suivant des arêtes
# Exemple connexe:
#     A ———— B
#     |      |
#     C ———— D
# Tu peux aller de A vers D (A->B->D)

# GRAPHE DÉCONNECTÉ
# = Il existe au moins deux sommets entre lesquels il n'y a AUCUN chemin
# Exemple déconnecté:
#     A ———— B        E ———— F
# Impossible d'aller de A vers E!

# POIDS (Weight)
# = Valeur numérique associée à une arête
# = Représente un coût, une distance, un temps, etc.
# Exemple: Routes avec distances
#     Paris ——100km—— Lyon ——200km—— Marseille


# === TYPES DE GRAPHES (TRÈS IMPORTANT!) ===

# === 1. GRAPHE NON ORIENTÉ (Undirected Graph) ===

# QUOI?
# = Les arêtes n'ont PAS de direction
# = Si A est connecté à B, alors B est connecté à A
# = Les relations sont SYMÉTRIQUES

# POURQUOI?
# - Modéliser des relations réciproques
# - Exemple: Amitié sur Facebook (si tu es ami avec X, X est ami avec toi)

# NOTATION:
# Arête entre A et B: {A, B} ou (A, B)
# Pas de flèche!

# REPRÉSENTATION VISUELLE:
#     A ———— B
#     |      |
#     C ———— D

# Caractéristiques:
# - La relation est bidirectionnelle
# - deg(v) = nombre total d'arêtes connectées
# - Matrice d'adjacence symétrique

# EXEMPLES RÉELS:
# - Réseau routier (route A->B = route B->A)
# - Molécules chimiques (liaison A-B = liaison B-A)
# - Collaboration (si A collabore avec B, B collabore avec A)


# === 2. GRAPHE ORIENTÉ (Directed Graph / Digraph) ===

# QUOI?
# = Les arêtes ONT une direction (flèche)
# = Si A est connecté à B, ça ne veut PAS dire que B est connecté à A
# = Les relations sont ASYMÉTRIQUES

# POURQUOI?
# - Modéliser des relations à sens unique
# - Exemple: Twitter (tu peux suivre quelqu'un qui ne te suit pas)

# NOTATION:
# Arête de A vers B: (A, B) ou A -> B
# Avec une flèche!

# REPRÉSENTATION VISUELLE:
#     A ——-> B
#     ^     v
#     C <-—— D

# Vocabulaire spécifique:
# - DEGRÉ ENTRANT (in-degree): Nombre d'arêtes qui ARRIVENT au sommet
# - DEGRÉ SORTANT (out-degree): Nombre d'arêtes qui PARTENT du sommet
# Exemple:
#     A ——-> B ——-> C
#     ^           v
#     D <-———————— E
# deg_in(B) = 1 (une flèche arrive: A->B)
# deg_out(B) = 1 (une flèche part: B->C)

# EXEMPLES RÉELS:
# - Twitter (follow/following)
# - Pages web (liens hypertextes A->B)
# - Processus (étape A -> étape B)
# - Hiérarchies (manager -> employé)


# === 3. GRAPHE PONDÉRÉ (Weighted Graph) ===

# QUOI?
# = Chaque arête a un POIDS (valeur numérique)
# = Le poids représente un coût, distance, temps, capacité, etc.

# POURQUOI?
# - Modéliser des coûts ou distances variables
# - Exemple: GPS (distance entre villes)

# NOTATION:
# Arête entre A et B avec poids w: (A, B, w)

# REPRÉSENTATION VISUELLE:
#     A ——5—— B
#     |       |
#     3       7
#     |       |
#     C ——2—— D

# Les nombres sur les arêtes = poids

# Utilité:
# - Trouver le chemin le PLUS COURT (algorithme de Dijkstra)
# - Trouver le chemin le MOINS CHER
# - Optimiser des ressources

# EXEMPLES RÉELS:
# - GPS (distance en km)
# - Réseaux de transport (coût du billet)
# - Réseaux électriques (capacité en ampères)
# - Flux logistique (temps de livraison)


# === 4. GRAPHE COMPLET (Complete Graph) ===

# QUOI?
# = TOUS les sommets sont connectés entre eux
# = Chaque paire de sommets a une arête

# POURQUOI?
# - Cas théorique important
# - Problème du voyageur de commerce (TSP)

# NOTATION:
# Graphe complet à n sommets: Kn

# FORMULE:
# Nombre d'arêtes dans Kn = n(n-1)/2
# Exemple: K4 (4 sommets) = 4×3/2 = 6 arêtes

# REPRÉSENTATION VISUELLE K4:
#       A ———— B
#       |\    /|
#       | \  / |
#       |  \/  |
#       |  /\  |
#       | /  \ |
#       |/    \|
#       C ———— D

# Tous les sommets sont connectés!

# EXEMPLES RÉELS:
# - Tournoi où tout le monde joue contre tout le monde
# - Réseau où tous les ordinateurs communiquent entre eux
# - Groupe où tout le monde se connaît


# === 5. GRAPHE BIPARTI (Bipartite Graph) ===

# QUOI?
# = Les sommets peuvent être divisés en DEUX ensembles disjoints U et V
# = Toutes les arêtes connectent un sommet de U à un sommet de V
# = AUCUNE arête ne connecte deux sommets du MÊME ensemble

# POURQUOI?
# - Modéliser des relations entre deux types d'entités différentes
# - Exemple: Étudiants et cours (étudiant <-> cours, mais pas étudiant <-> étudiant)

# REPRÉSENTATION VISUELLE:
#     Ensemble U          Ensemble V
#     
#        A ————————————— 1
#        |  \            
#        |    \          
#        B      ————————— 2
#         \      /
#          \    /
#        C ————————————— 3

# U = {A, B, C} (étudiants)
# V = {1, 2, 3} (cours)
# Arêtes: A<->1, A<->2, B<->2, C<->2, C<->3

# Propriété importante:
# Un graphe est biparti SI ET SEULEMENT SI il ne contient AUCUN cycle de longueur impaire

# EXEMPLES RÉELS:
# - Étudiants <-> Cours inscrits
# - Acteurs <-> Films joués
# - Clients <-> Produits achetés
# - Utilisateurs <-> Recommandations


# === 6. GRAPHE ACYCLIQUE (Acyclic Graph) ===

# QUOI?
# = Graphe qui ne contient AUCUN cycle
# = Impossible de revenir à un sommet en suivant les arêtes

# POURQUOI?
# - Représenter des hiérarchies
# - Modéliser des dépendances sans circularité

# TYPES SPÉCIAUX:

# DAG (Directed Acyclic Graph)
# = Graphe orienté sans cycle
# = Très utilisé en informatique!

# REPRÉSENTATION VISUELLE DAG:
#       A
#      / \
#     B   C
#     |   |
#     D   E
#      \ /
#       F

# Pas de cycle possible!
# Tu ne peux jamais revenir à A en suivant les flèches

# EXEMPLES RÉELS:
# - Dépendances de packages (package A nécessite B, B nécessite C)
# - Arbre généalogique (ancêtres -> descendants)
# - Blockchain (blocs précédents -> blocs suivants)
# - Ordonnancement de tâches (tâche A avant tâche B)


# === 7. ARBRE (Tree) ===

# QUOI?
# = Graphe connexe SANS cycle
# = Il existe UN ET UN SEUL chemin entre deux sommets
# = Cas particulier de graphe acyclique

# DÉFINITIONS IMPORTANTES:

# RACINE (Root)
# = Sommet spécial en haut de l'arbre (dans les arbres enracinés)

# FEUILLE (Leaf)
# = Sommet sans enfants (au bout des branches)

# PARENT / ENFANT
# = Relation entre sommets connectés (parent au-dessus, enfant en-dessous)

# HAUTEUR (Height)
# = Longueur du plus long chemin de la racine à une feuille

# REPRÉSENTATION VISUELLE:
#           A (racine)
#          / \
#         B   C
#        / \   \
#       D   E   F (feuilles)

# PROPRIÉTÉS:
# - n sommets -> n-1 arêtes (toujours!)
# - Connexe et acyclique
# - Ajouter une arête crée un cycle
# - Retirer une arête déconnecte le graphe

# EXEMPLES RÉELS:
# - Système de fichiers (dossiers/fichiers)
# - Organigramme d'entreprise (hiérarchie)
# - Arbre de décision (choix successifs)
# - Structure HTML/XML (balises imbriquées)


# === 8. GRAPHE PLANAIRE (Planar Graph) ===

# QUOI?
# = Graphe qu'on peut dessiner sur un plan SANS que les arêtes se croisent

# POURQUOI?
# - Circuits imprimés (pas de croisement de fils)
# - Cartes géographiques

# THÉORÈME D'EULER (pour graphes planaires connexes):
# V - E + F = 2
# V = nombre de sommets
# E = nombre d'arêtes
# F = nombre de faces (régions délimitées)

# EXEMPLE:
#     A ———— B
#     |      |
#     C ———— D

# V = 4 (A, B, C, D)
# E = 4 (AB, BC, CD, DA)
# F = 2 (intérieur du carré + extérieur)
# Vérification: 4 - 4 + 2 = 2 [OK]

# NON PLANAIRE:
# K5 (graphe complet à 5 sommets) ne peut PAS être dessiné sans croisement!

# EXEMPLES RÉELS:
# - Plans d'architecture (pas de murs qui se croisent)
# - Circuits électroniques sur une seule couche


# === 9. GRAPHE EULÉRIEN (Eulerian Graph) ===

# QUOI?
# = Graphe où il existe un CHEMIN EULÉRIEN ou un CYCLE EULÉRIEN

# CHEMIN EULÉRIEN:
# = Chemin qui passe par TOUTES les arêtes EXACTEMENT une fois
# (les sommets peuvent être visités plusieurs fois)

# CYCLE EULÉRIEN:
# = Cycle qui passe par toutes les arêtes exactement une fois
# ET revient au point de départ

# THÉORÈME D'EULER:
# Un graphe connexe possède un CYCLE EULÉRIEN
# SI ET SEULEMENT SI tous les sommets ont un degré PAIR

# Un graphe connexe possède un CHEMIN EULÉRIEN
# SI ET SEULEMENT SI il a exactement 0 ou 2 sommets de degré impair

# EXEMPLE CLASSIQUE: Les 7 ponts de Königsberg
# Problème historique résolu par Euler en 1736
# Question: Peut-on traverser tous les ponts exactement une fois?
# Réponse: Non, car il y a 4 sommets de degré impair!

# EXEMPLES RÉELS:
# - Planification de tournées (facteur, éboueur)
# - Traçage de figures sans lever le crayon


# === 10. GRAPHE HAMILTONIEN (Hamiltonian Graph) ===

# QUOI?
# = Graphe où il existe un CHEMIN HAMILTONIEN ou un CYCLE HAMILTONIEN

# CHEMIN HAMILTONIEN:
# = Chemin qui passe par TOUS les sommets EXACTEMENT une fois
# (contrairement à Eulérien, ici ce sont les SOMMETS, pas les arêtes!)

# CYCLE HAMILTONIEN:
# = Cycle qui visite tous les sommets exactement une fois
# ET revient au point de départ

# DIFFÉRENCE IMPORTANTE:
# EULÉRIEN -> toutes les ARÊTES une fois
# HAMILTONIEN -> tous les SOMMETS une fois

# PROBLÈME:
# Il n'existe PAS de condition simple pour savoir si un graphe est hamiltonien!
# C'est un problème NP-complet (très difficile!)

# EXEMPLE:
#     A ———— B
#     |      |
#     C ———— D

# Cycle hamiltonien: A -> B -> D -> C -> A
# (visite tous les sommets une fois)

# EXEMPLES RÉELS:
# - Problème du voyageur de commerce (TSP): visiter toutes les villes une fois
# - Tournées de livraison optimales
# - Planification de visites


# === RÉSUMÉ COMPARATIF DES TYPES ===

# Type              | Arêtes orientées? | Poids? | Cycles? | Exemple réel
# ------------------|-------------------|--------|---------|------------------------
# Non orienté       | Non               | Non    | Oui     | Amitié Facebook
# Orienté           | Oui               | Non    | Oui     | Following Twitter
# Pondéré           | Dépend            | Oui    | Oui     | GPS, routes
# Complet           | Non               | Non    | Oui     | Tournoi complet
# Biparti           | Non               | Non    | Non*    | Étudiants-Cours
# Acyclique (DAG)   | Oui               | Non    | Non     | Dépendances
# Arbre             | Non               | Non    | Non     | Système fichiers
# Planaire          | Non               | Non    | Oui     | Circuits imprimés
# Eulérien          | Dépend            | Non    | Oui     | Tournée facteur
# Hamiltonien       | Dépend            | Non    | Oui     | Voyageur commerce

# *Biparti: pas de cycle de longueur impaire


[OK] REPRÉSENTATIONS DE GRAPHES (COMMENT STOCKER UN GRAPHE?)

# Un graphe existe conceptuellement, mais comment le STOCKER en mémoire?
# Il existe plusieurs méthodes, chacune avec ses avantages et inconvénients

# === 1. LISTE D'ADJACENCE (Adjacency List) ===

# QUOI?
# = Pour chaque sommet, on stocke la LISTE de ses voisins

# STRUCTURE:
# Dictionnaire où:
# - Clé = sommet
# - Valeur = liste des sommets adjacents

# EXEMPLE:
#     A ———— B
#     |      |
#     C ———— D

# Liste d'adjacence:
# A -> [B, C]
# B -> [A, D]
# C -> [A, D]
# D -> [B, C]

# POUR GRAPHE ORIENTÉ:
#     A ——-> B
#     ^     v
#     C <-—— D

# A -> [B]
# B -> [D]
# C -> [A]
# D -> [C]

# POUR GRAPHE PONDÉRÉ:
# On stocke des paires (voisin, poids)
# A -> [(B, 5), (C, 3)]
# B -> [(A, 5), (D, 7)]

# AVANTAGES:
# + Économe en mémoire si le graphe est SPARSE (peu d'arêtes)
# + Parcourir les voisins d'un sommet: rapide O(deg(v))
# + Idéal pour DFS/BFS (parcours en profondeur/largeur)

# INCONVÉNIENTS:
# - Vérifier si deux sommets sont adjacents: lent O(deg(v))
# - Nécessite de parcourir la liste

# COMPLEXITÉ SPATIALE:
# O(V + E)
# V = nombre de sommets
# E = nombre d'arêtes

# QUAND UTILISER?
# - Graphes sparse (peu d'arêtes par rapport aux sommets)
# - Algorithmes de parcours (DFS, BFS)
# - Graphes de grande taille


# === 2. MATRICE D'ADJACENCE (Adjacency Matrix) ===

# QUOI?
# = Tableau 2D de taille V×V
# = mat[i][j] = 1 si arête entre sommet i et sommet j
# = mat[i][j] = 0 sinon

# EXEMPLE:
#     A ———— B
#     |      |
#     C ———— D

# Numérotons: A=0, B=1, C=2, D=3

# Matrice:
#     A  B  C  D
# A   0  1  1  0
# B   1  0  0  1
# C   1  0  0  1
# D   0  1  1  0

# Lecture:
# mat[0][1] = 1 -> arête entre A et B
# mat[0][3] = 0 -> pas d'arête entre A et D

# POUR GRAPHE ORIENTÉ:
#     A ——-> B
#     ^     v
#     C <-—— D

#     A  B  C  D
# A   0  1  0  0  (A->B)
# B   0  0  0  1  (B->D)
# C   1  0  0  0  (C->A)
# D   0  0  1  0  (D->C)

# La matrice n'est PAS symétrique!

# POUR GRAPHE PONDÉRÉ:
# mat[i][j] = poids de l'arête
# mat[i][j] = ∞ (ou 0) si pas d'arête

# EXEMPLE:
#     A ——5—— B
#     |       |
#     3       7
#     |       |
#     C ——2—— D

#     A  B  C  D
# A   0  5  3  ∞
# B   5  0  ∞  7
# C   3  ∞  0  2
# D   ∞  7  2  0

# AVANTAGES:
# + Vérifier adjacence: très rapide O(1)
# + Simple à implémenter
# + Idéal pour graphes DENSES (beaucoup d'arêtes)
# + Facile pour certains algorithmes matriciels

# INCONVÉNIENTS:
# - Consomme beaucoup de mémoire O(V²) même si peu d'arêtes!
# - Parcourir les voisins: lent O(V)
# - Inefficace pour graphes sparse

# COMPLEXITÉ SPATIALE:
# O(V²)

# QUAND UTILISER?
# - Graphes denses (beaucoup d'arêtes)
# - Beaucoup de vérifications d'adjacence
# - Opérations matricielles (puissance de matrice)
# - Petits graphes


# === 3. LISTE D'ARÊTES (Edge List) ===

# QUOI?
# = Simple liste de toutes les arêtes du graphe
# = Chaque arête = paire (u, v) ou triplet (u, v, poids)

# EXEMPLE:
#     A ———— B
#     |      |
#     C ———— D

# Liste d'arêtes:
# [(A, B), (A, C), (B, D), (C, D)]

# POUR GRAPHE ORIENTÉ:
# [(A, B), (B, D), (C, A), (D, C)]

# POUR GRAPHE PONDÉRÉ:
# [(A, B, 5), (A, C, 3), (B, D, 7), (C, D, 2)]

# AVANTAGES:
# + Très simple
# + Économe en mémoire O(E)
# + Idéal pour algorithmes travaillant sur les arêtes (Kruskal)

# INCONVÉNIENTS:
# - Trouver les voisins d'un sommet: très lent O(E)
# - Vérifier adjacence: lent O(E)

# COMPLEXITÉ SPATIALE:
# O(E)

# QUAND UTILISER?
# - Algorithmes de graphes basés sur les arêtes
# - Algorithme de Kruskal (arbre couvrant minimal)
# - Stockage de données brutes


# === COMPARAISON DES REPRÉSENTATIONS ===

# Opération                  | Liste d'adj | Matrice d'adj | Liste d'arêtes
# ---------------------------|-------------|---------------|----------------
# Espace mémoire             | O(V + E)    | O(V²)         | O(E)
# Vérifier si (u,v) existe   | O(deg(u))   | O(1)          | O(E)
# Trouver voisins de u       | O(deg(u))   | O(V)          | O(E)
# Ajouter un sommet          | O(1)        | O(V²)         | O(1)
# Ajouter une arête          | O(1)        | O(1)          | O(1)
# Supprimer une arête        | O(deg(u))   | O(1)          | O(E)

# RÈGLE GÉNÉRALE:
# - Graphe SPARSE (peu d'arêtes): Liste d'adjacence
# - Graphe DENSE (beaucoup d'arêtes): Matrice d'adjacence
# - Algorithmes sur arêtes: Liste d'arêtes


[OK] PROPRIÉTÉS IMPORTANTES DES GRAPHES

# === 1. CONNEXITÉ (Connectivity) ===

# GRAPHE CONNEXE:
# = Il existe un chemin entre TOUTE paire de sommets
# = Le graphe est en "un seul morceau"

# EXEMPLE CONNEXE:
#     A ———— B
#     |      |
#     C ———— D
# Tu peux aller de n'importe où vers n'importe où

# GRAPHE NON CONNEXE (DÉCONNECTÉ):
# = Il existe au moins deux sommets sans chemin entre eux
# = Le graphe est en "plusieurs morceaux"

# EXEMPLE DÉCONNECTÉ:
#     A ———— B        E ———— F
#     |              |
#     C              G
# Impossible d'aller de A vers E!

# COMPOSANTE CONNEXE:
# = Sous-graphe connexe maximal
# = "Morceau" du graphe

# Dans l'exemple ci-dessus:
# Composante 1: {A, B, C}
# Composante 2: {E, F, G}

# COMMENT TROUVER LES COMPOSANTES?
# Utilise DFS ou BFS depuis chaque sommet non visité

# CONNEXITÉ FORTE (pour graphes orientés):
# = Il existe un chemin de u vers v ET de v vers u pour TOUTE paire (u, v)

# EXEMPLE FORTEMENT CONNEXE:
#     A ——-> B
#     ^     v
#     C <-—— D
# Tu peux aller de n'importe où vers n'importe où en suivant les flèches

# COMPOSANTE FORTEMENT CONNEXE (SCC):
# = Sous-graphe orienté où chaque sommet peut atteindre tous les autres


# === 2. DEGRÉ (Degree) ===

# DEGRÉ d'un sommet:
# = Nombre d'arêtes incidentes (connectées) à ce sommet

# NOTATION: deg(v) ou d(v)

# EXEMPLE:
#     A ———— B ———— C
#     |             |
#     D ———————————— E

# deg(A) = 2 (connecté à B et D)
# deg(B) = 2 (connecté à A et C)
# deg(C) = 2 (connecté à B et E)
# deg(D) = 2 (connecté à A et E)
# deg(E) = 2 (connecté à C et D)

# THÉORÈME DE LA SOMME DES DEGRÉS:
# La somme des degrés de tous les sommets = 2 × nombre d'arêtes
# Formule: Σ deg(v) = 2|E|

# POURQUOI?
# Chaque arête contribue au degré de DEUX sommets

# Vérification de l'exemple:
# Σ deg(v) = 2+2+2+2+2 = 10
# |E| = 5 arêtes
# 2|E| = 10 [OK]

# COROLLAIRE:
# Le nombre de sommets de degré impair est TOUJOURS pair!

# POUR GRAPHES ORIENTÉS:

# DEGRÉ ENTRANT (in-degree):
# = Nombre d'arêtes qui ARRIVENT au sommet
# Notation: deg⁻(v)

# DEGRÉ SORTANT (out-degree):
# = Nombre d'arêtes qui PARTENT du sommet
# Notation: deg⁺(v)

# EXEMPLE:
#     A ——-> B ——-> C
#     ^           v
#     D <-———————— E

# deg⁻(B) = 1 (A->B)
# deg⁺(B) = 1 (B->C)
# deg⁻(E) = 1 (C->E)
# deg⁺(E) = 1 (E->D)

# THÉORÈME:
# Σ deg⁺(v) = Σ deg⁻(v) = |E|


# === 3. DISTANCE ET DIAMÈTRE ===

# DISTANCE entre deux sommets:
# = Longueur du PLUS COURT chemin entre ces sommets
# Notation: d(u, v)

# Si aucun chemin n'existe: d(u, v) = ∞

# EXEMPLE:
#     A ———— B ———— C
#     |             |
#     D ———————————— E

# d(A, C) = 2 (chemin: A->B->C)
# d(A, E) = 2 (chemin: A->D->E)
# d(B, E) = 2 (chemin: B->C->E)

# EXCENTRICITÉ d'un sommet v:
# = Distance maximale de v vers n'importe quel autre sommet
# Notation:
ecc(v) = max{d(v, u) pour tout u}

# RAYON du graphe:
# = Excentricité minimale
# Notation: rad(G) = min{ecc(v) pour tout v}

# DIAMÈTRE du graphe:
# = Excentricité maximale
# = Distance maximale entre deux sommets quelconques
# Notation: diam(G) = max{ecc(v) pour tout v}

# EXEMPLE:
#     A ———— B ———— C

# ecc(A) = 2 (plus loin = C)
# ecc(B) = 1 (plus loin = A ou C)
# ecc(C) = 2 (plus loin = A)

# rad(G) = 1 (minimum des excentricités)
# diam(G) = 2 (maximum des excentricités)

# CENTRE du graphe:
# = Ensemble des sommets ayant l'excentricité minimale
# Dans l'exemple: centre = {B}


# === 4. DENSITÉ (Density) ===

# DENSITÉ d'un graphe:
# = Mesure de la proportion d'arêtes présentes par rapport au maximum possible

# POUR GRAPHE NON ORIENTÉ:
# Formule: densité = 2|E| / (|V| × (|V| - 1))

# Maximum possible d'arêtes: |V| × (|V| - 1) / 2

# POUR GRAPHE ORIENTÉ:
# Formule: densité = |E| / (|V| × (|V| - 1))

# Maximum possible d'arêtes: |V| × (|V| - 1)

# INTERPRÉTATION:
# densité = 0 -> graphe vide (aucune arête)
# densité = 1 -> graphe complet (toutes les arêtes possibles)

# EXEMPLE:
#     A ———— B
#     |      |
#     C ———— D

# |V| = 4, |E| = 4
# Max arêtes = 4×3/2 = 6
# densité = 2×4 / (4×3) = 8/12 = 0.67

# GRAPHE SPARSE:
# = Peu d'arêtes par rapport aux sommets
# = densité proche de 0
# = Nombre d'arêtes: O(V)

# GRAPHE DENSE:
# = Beaucoup d'arêtes
# = densité proche de 1
# = Nombre d'arêtes: O(V²)


# === 5. ISOMORPHISME (Isomorphism) ===

# QUOI?
# = Deux graphes sont ISOMORPHES s'ils ont la même structure
# = On peut transformer l'un en l'autre en renommant les sommets

# FORMELLEMENT:
# Deux graphes G₁ = (V₁, E₁) et G₂ = (V₂, E₂) sont isomorphes
# s'il existe une bijection f: V₁ -> V₂ telle que:
# (u, v) ∈ E₁ ⟺ (f(u), f(v)) ∈ E₂

# EN GROS:
# Même nombre de sommets, même nombre d'arêtes, même structure de connexions

# EXEMPLE:
# Graphe G₁:          Graphe G₂:
#     A ———— B            1 ———— 2
#     |      |            |      |
#     C ———— D            4 ———— 3

# G₁ et G₂ sont isomorphes!
# Correspondance: A<->1, B<->2, C<->4, D<->3

# CONDITIONS NÉCESSAIRES (mais pas suffisantes!):
# - Même nombre de sommets
# - Même nombre d'arêtes
# - Même séquence de degrés
# - Même nombre de cycles

# VÉRIFIER L'ISOMORPHISME:
# Problème difficile! Pas d'algorithme polynomial connu
# En pratique:
# 1. Vérifier les conditions nécessaires
# 2. Essayer de trouver une correspondance
# 3. Utiliser des invariants (propriétés conservées)


# === 6. COLORABILITÉ (Colorability) ===

# COLORATION D'UN GRAPHE:
# = Assigner une couleur à chaque sommet
# = CONTRAINTE: Deux sommets adjacents ne peuvent pas avoir la même couleur

# NOMBRE CHROMATIQUE χ(G):
# = Nombre MINIMUM de couleurs nécessaires pour colorer le graphe

# EXEMPLE:
#     A ———— B
#     |      |
#     C ———— D

# Coloration possible:
# A = rouge, B = bleu, C = bleu, D = rouge
# χ(G) = 2 (2 couleurs suffisent)

# THÉORÈME DES 4 COULEURS:
# Toute carte planaire peut être coloriée avec au plus 4 couleurs
# (prouvé en 1976 avec aide informatique)

# GRAPHE BIPARTI:
# χ(G) = 2 (exactement 2 couleurs)

# GRAPHE COMPLET Kn:
# χ(Kn) = n (chaque sommet nécessite une couleur différente)

# APPLICATIONS:
# - Planification d'horaires (cours sans conflit)
# - Attribution de fréquences radio (éviter interférences)
# - Coloration de cartes géographiques
# - Allocation de registres (compilation)


[OK] ALGORITHMES DE PARCOURS (EXPLORATION DE GRAPHES)

# Les algorithmes de parcours permettent de VISITER tous les sommets
# Il existe deux approches fondamentales:
# - Parcours en PROFONDEUR (Depth-First Search - DFS)
# - Parcours en LARGEUR (Breadth-First Search - BFS)

# === 1. PARCOURS EN PROFONDEUR (DFS - Depth-First Search) ===

# PRINCIPE:
# = Aller le PLUS LOIN possible avant de revenir en arrière
# = Explorer une branche complètement avant d'explorer les autres

# ANALOGIE:
# Comme explorer un labyrinthe:
# - Tu vas tout droit jusqu'au bout
# - Quand tu atteins une impasse, tu reviens en arrière
# - Tu explores une autre direction

# ALGORITHME:
# 1. Marquer le sommet de départ comme visité
# 2. Pour chaque voisin non visité:
#    - Visiter récursivement ce voisin (DFS récursif)
# 3. Quand tous les voisins sont visités, revenir en arrière

# STRUCTURE DE DONNÉES:
# Utilise une PILE (Stack) ou la RÉCURSION

# PSEUDO-CODE:
# DFS(graphe, sommet_départ):
#     marquer sommet_départ comme visité
#     afficher sommet_départ
#     
#     pour chaque voisin de sommet_départ:
#         si voisin non visité:
#             DFS(graphe, voisin)

# EXEMPLE D'EXÉCUTION:
#     A ———— B
#     |      |
#     C ———— D ———— E

# DFS depuis A:
# Ordre de visite: A -> C -> D -> B -> E
# ou: A -> B -> D -> C -> E
# (dépend de l'ordre des voisins)

# Explication étape par étape:
# 1. Visiter A, marquer comme visité
# 2. Aller vers C (premier voisin de A)
# 3. Visiter C, marquer comme visité
# 4. Aller vers D (voisin de C)
# 5. Visiter D, marquer comme visité
# 6. Aller vers B (voisin de D non encore visité)
# 7. Visiter B, marquer comme visité
# 8. Aller vers E (voisin de D)
# 9. Visiter E, marquer comme visité
# 10. Aucun voisin non visité -> terminé!

# COMPLEXITÉ:
# Temps: O(V + E)
# - V = parcourir tous les sommets
# - E = examiner toutes les arêtes
# Espace: O(V) (pour la pile de récursion)

# AVANTAGES:
# + Utilise moins de mémoire que BFS
# + Facile à implémenter avec récursion
# + Détecte les cycles
# + Trouve les composantes connexes

# INCONVÉNIENTS:
# - Ne trouve PAS le plus court chemin
# - Peut s'enfoncer très profondément (risque de stack overflow)

# APPLICATIONS:
# - Détection de cycles
# - Tri topologique
# - Trouver les composantes fortement connexes
# - Résoudre des labyrinthes
# - Problème des 8 reines (backtracking)


# === 2. PARCOURS EN LARGEUR (BFS - Breadth-First Search) ===

# PRINCIPE:
# = Explorer tous les voisins IMMÉDIATS d'abord
# = Avancer niveau par niveau (couche par couche)

# ANALOGIE:
# Comme une vague qui s'étend:
# - D'abord les sommets à distance 1
# - Puis les sommets à distance 2
# - Puis distance 3, etc.

# ALGORITHME:
# 1. Marquer le sommet de départ comme visité
# 2. Ajouter le sommet de départ à une file
# 3. Tant que la file n'est pas vide:
#    - Retirer le sommet en tête de file
#    - Pour chaque voisin non visité:
#      * Marquer comme visité
#      * Ajouter à la file

# STRUCTURE DE DONNÉES:
# Utilise une FILE (Queue) - FIFO (First In First Out)

# PSEUDO-CODE:
# BFS(graphe, sommet_départ):
#     créer une file vide
#     marquer sommet_départ comme visité
#     ajouter sommet_départ à la file
#     
#     tant que file non vide:
#         sommet = retirer de la file
#         afficher sommet
#         
#         pour chaque voisin de sommet:
#             si voisin non visité:
#                 marquer voisin comme visité
#                 ajouter voisin à la file

# EXEMPLE D'EXÉCUTION:
#     A ———— B
#     |      |
#     C ———— D ———— E

# BFS depuis A:
# Ordre de visite: A -> B -> C -> D -> E

# Explication étape par étape:
# État de la file à chaque étape:

# Étape 1: [A]
# - Retirer A
# - Voisins de A: B, C
# - Marquer B et C comme visités
# File: [B, C]

# Étape 2: [B, C]
# - Retirer B
# - Voisins de B: A (déjà visité), D (nouveau)
# - Marquer D comme visité
# File: [C, D]

# Étape 3: [C, D]
# - Retirer C
# - Voisins de C: A (déjà visité), D (déjà visité)
# File: [D]

# Étape 4: [D]
# - Retirer D
# - Voisins de D: B (déjà visité), C (déjà visité), E (nouveau)
# - Marquer E comme visité
# File: [E]

# Étape 5: [E]
# - Retirer E
# - Voisins de E: D (déjà visité)
# File: []

# Terminé!
# Ordre: A -> B -> C -> D -> E

# NIVEAUX DE DISTANCE:
# Niveau 0: {A} (départ)
# Niveau 1: {B, C} (distance 1 de A)
# Niveau 2: {D} (distance 2 de A)
# Niveau 3: {E} (distance 3 de A)

# COMPLEXITÉ:
# Temps: O(V + E)
# Espace: O(V) (pour la file)

# AVANTAGES:
# + Trouve le PLUS COURT CHEMIN (en nombre d'arêtes)
# + Explore niveau par niveau (distances croissantes)
# + Idéal pour graphes non pondérés

# INCONVÉNIENTS:
# - Utilise plus de mémoire que DFS
# - Pas idéal pour graphes très larges

# APPLICATIONS:
# - Plus court chemin dans graphe non pondéré
# - Réseau social (amis à distance n)
# - Crawler web (explorer pages niveau par niveau)
# - Problème du cavalier sur échiquier
# - Propagation de messages dans un réseau


# === COMPARAISON DFS vs BFS ===

# Critère              | DFS                    | BFS
# ---------------------|------------------------|------------------------
# Structure            | Pile (récursion)       | File (queue)
# Ordre exploration    | Profondeur d'abord     | Largeur d'abord
# Plus court chemin    | Non                    | Oui
# Mémoire              | O(hauteur)             | O(largeur)
# Complexité temps     | O(V + E)               | O(V + E)
# Détection cycle      | Oui                    | Oui
# Tri topologique      | Oui                    | Non
# Distances            | Non                    | Oui

# QUAND UTILISER DFS?
# - Détecter des cycles
# - Tri topologique
# - Trouver composantes connexes
# - Backtracking (résoudre puzzles)
# - Graphes profonds et étroits

# QUAND UTILISER BFS?
# - Plus court chemin (non pondéré)
# - Trouver les sommets à distance k
# - Niveau par niveau
# - Graphes larges et peu profonds


[OK] PLUS COURTS CHEMINS (SHORTEST PATH ALGORITHMS)

# Problème fondamental: Trouver le chemin le plus court entre deux sommets
# "Plus court" peut signifier:
# - Minimum d'arêtes (graphe non pondéré) -> BFS
# - Somme minimale des poids (graphe pondéré) -> Dijkstra, Bellman-Ford

# === 1. ALGORITHME DE DIJKSTRA ===

# QUI?
# Edsger W. Dijkstra (1956)

# QUOI?
# = Trouve le plus court chemin d'un sommet SOURCE vers TOUS les autres sommets
# = Fonctionne avec des poids POSITIFS seulement!

# POURQUOI?
# - GPS: trouver le chemin le plus rapide
# - Réseau informatique: routage optimal
# - Logistique: livraison optimale

# PRINCIPE:
# 1. Maintenir une distance provisoire pour chaque sommet
# 2. Commencer avec distance 0 pour la source, ∞ pour les autres
# 3. Répéter:
#    - Choisir le sommet non visité avec la plus petite distance
#    - Pour chaque voisin, mettre à jour sa distance si on trouve un meilleur chemin
#    - Marquer le sommet comme visité
# 4. Continuer jusqu'à avoir visité tous les sommets

# ALGORITHME DÉTAILLÉ:

# Dijkstra(graphe, source):
#     # Initialisation
#     pour chaque sommet v:
#         distance[v] = ∞
#         prédécesseur[v] = null
#         visité[v] = false
#     
#     distance[source] = 0
#     
#     tant qu'il existe des sommets non visités:
#         # Choisir le sommet non visité avec la plus petite distance
#         u = sommet non visité avec min(distance[u])
#         marquer u comme visité
#         
#         # Relaxation des arêtes
#         pour chaque voisin v de u:
#             si non visité[v]:
#                 nouvelle_distance = distance[u] + poids(u, v)
#                 si nouvelle_distance < distance[v]:
#                     distance[v] = nouvelle_distance
#                     prédécesseur[v] = u
#     
#     retourner distance, prédécesseur

# EXEMPLE COMPLET:

# Graphe:
#       5
#   A ——— B
#   |  2  |\
# 3 |     | \ 1
#   |     |  \
#   C ——— D   E
#      4     /
#           / 6
#          F

# Trouver le plus court chemin de A vers tous les autres sommets

# INITIALISATION:
# Sommet | Distance | Prédécesseur | Visité
# -------|----------|--------------|--------
#   A    |    0     |     null     | false
#   B    |    ∞     |     null     | false
#   C    |    ∞     |     null     | false
#   D    |    ∞     |     null     | false
#   E    |    ∞     |     null     | false
#   F    |    ∞     |     null     | false


# ITÉRATION 1: Choisir A (distance = 0)
# Examiner les voisins de A: B (poids 5), C (poids 3)
# - distance[B] = min(∞, 0+5) = 5, prédécesseur[B] = A
# - distance[C] = min(∞, 0+3) = 3, prédécesseur[C] = A
# Marquer A comme visité

# État:
# Sommet | Distance | Prédécesseur | Visité
# -------|----------|--------------|--------
#   A    |    0     |     null     | true
#   B    |    5     |      A       | false
#   C    |    3     |      A       | false
#   D    |    ∞     |     null     | false
#   E    |    ∞     |     null     | false
#   F    |    ∞     |     null     | false


# ITÉRATION 2: Choisir C (distance = 3, la plus petite parmi non visités)
# Examiner les voisins de C: A (déjà visité), D (poids 4)
# - distance[D] = min(∞, 3+4) = 7, prédécesseur[D] = C
# Marquer C comme visité

# État:
# Sommet | Distance | Prédécesseur | Visité
# -------|----------|--------------|--------
#   A    |    0     |     null     | true
#   B    |    5     |      A       | false
#   C    |    3     |      A       | true
#   D    |    7     |      C       | false
#   E    |    ∞     |     null     | false
#   F    |    ∞     |     null     | false


# ITÉRATION 3: Choisir B (distance = 5)
# Examiner les voisins de B: A (visité), D (poids 2), E (poids 1)
# - distance[D] = min(7, 5+2) = 7 (pas de changement)
# - distance[E] = min(∞, 5+1) = 6, prédécesseur[E] = B
# Marquer B comme visité

# État:
# Sommet | Distance | Prédécesseur | Visité
# -------|----------|--------------|--------
#   A    |    0     |     null     | true
#   B    |    5     |      A       | true
#   C    |    3     |      A       | true
#   D    |    7     |      C       | false
#   E    |    6     |      B       | false
#   F    |    ∞     |     null     | false


# ITÉRATION 4: Choisir E (distance = 6)
# Examiner les voisins de E: B (visité), F (poids 6)
# - distance[F] = min(∞, 6+6) = 12, prédécesseur[F] = E
# Marquer E comme visité

# État:
# Sommet | Distance | Prédécesseur | Visité
# -------|----------|--------------|--------
#   A    |    0     |     null     | true
#   B    |    5     |      A       | true
#   C    |    3     |      A       | true
#   D    |    7     |      C       | false
#   E    |    6     |      B       | true
#   F    |   12     |      E       | false


# ITÉRATION 5: Choisir D (distance = 7)
# Examiner les voisins de D: C (visité), B (visité)
# Aucune mise à jour
# Marquer D comme visité


# ITÉRATION 6: Choisir F (distance = 12)
# Examiner les voisins de F: E (visité)
# Aucune mise à jour
# Marquer F comme visité


# RÉSULTAT FINAL:
# Sommet | Distance | Chemin depuis A
# -------|----------|------------------
#   A    |    0     | A
#   B    |    5     | A -> B
#   C    |    3     | A -> C
#   D    |    7     | A -> C -> D
#   E    |    6     | A -> B -> E
#   F    |   12     | A -> B -> E -> F


# RECONSTRUCTION DU CHEMIN:
# Pour reconstruire le chemin de A vers F:
# 1. Commencer par F
# 2. prédécesseur[F] = E
# 3. prédécesseur[E] = B
# 4. prédécesseur[B] = A
# 5. prédécesseur[A] = null (terminé)
# Chemin: A -> B -> E -> F


# COMPLEXITÉ:
# Avec file de priorité (tas binaire): O((V + E) log V)
# Avec tableau simple: O(V²)

# AVANTAGES:
# + Efficace pour graphes avec poids positifs
# + Trouve le plus court chemin vers TOUS les sommets
# + Largement utilisé en pratique (GPS, routage)

# INCONVÉNIENTS:
# - Ne fonctionne PAS avec des poids négatifs!
# - Nécessite de visiter tous les sommets (même si on cherche juste un chemin)

# QUAND UTILISER?
# - Graphes avec poids positifs
# - Trouver le plus court chemin depuis une source
# - GPS, routage réseau, logistique


# === 2. ALGORITHME DE BELLMAN-FORD ===

# QUI?
# Richard Bellman (1958), Lester Ford Jr. (1956)

# QUOI?
# = Trouve le plus court chemin d'un sommet SOURCE vers TOUS les autres
# = Fonctionne même avec des poids NÉGATIFS!
# = Détecte les cycles de poids négatif

# POURQUOI?
# - Dijkstra ne marche pas avec poids négatifs
# - Certains problèmes ont naturellement des poids négatifs
#   (ex: gagner de l'argent = poids négatif)

# PRINCIPE:
# 1. Initialiser les distances (0 pour source, ∞ pour les autres)
# 2. Répéter V-1 fois (V = nombre de sommets):
#    - Pour CHAQUE arête (u, v, poids):
#      * Relaxer l'arête: si distance[u] + poids < distance[v],
#        alors distance[v] = distance[u] + poids
# 3. Vérifier s'il existe un cycle de poids négatif:
#    - Si on peut encore relaxer une arête, il y a un cycle négatif

# ALGORITHME DÉTAILLÉ:

# BellmanFord(graphe, source):
#     # Initialisation
#     pour chaque sommet v:
#         distance[v] = ∞
#         prédécesseur[v] = null
#     
#     distance[source] = 0
#     
#     # Relaxation V-1 fois
#     répéter V-1 fois:
#         pour chaque arête (u, v, poids):
#             si distance[u] + poids < distance[v]:
#                 distance[v] = distance[u] + poids
#                 prédécesseur[v] = u
#     
#     # Détection de cycle négatif
#     pour chaque arête (u, v, poids):
#         si distance[u] + poids < distance[v]:
#             retourner "Cycle de poids négatif détecté!"
#     
#     retourner distance, prédécesseur

# EXEMPLE AVEC POIDS NÉGATIFS:

# Graphe:
#       5
#   A ——— B
#   |     |\
# 3 |     | \ -2
#   |     |  \
#   C ——— D   E
#     -1

# Trouver le plus court chemin de A vers tous les sommets

# INITIALISATION:
# distance[A] = 0
# distance[B] = distance[C] = distance[D] = distance[E] = ∞

# ITÉRATION 1 (relaxation de toutes les arêtes):
# Arête A-B (poids 5): distance[B] = min(∞, 0+5) = 5
# Arête A-C (poids 3): distance[C] = min(∞, 0+3) = 3
# Arête B-D (poids 1): distance[D] = min(∞, 5+1) = 6
# Arête B-E (poids -2): distance[E] = min(∞, 5-2) = 3
# Arête C-D (poids -1): distance[D] = min(6, 3-1) = 2

# Après itération 1:
# A:0, B:5, C:3, D:2, E:3

# ITÉRATION 2:
# Arête A-B: distance[B] = min(5, 0+5) = 5 (pas de changement)
# Arête A-C: distance[C] = min(3, 0+3) = 3 (pas de changement)
# Arête B-D: distance[D] = min(2, 5+1) = 2 (pas de changement)
# Arête B-E: distance[E] = min(3, 5-2) = 3 (pas de changement)
# Arête C-D: distance[D] = min(2, 3-1) = 2 (pas de changement)

# Aucun changement -> convergence!

# RÉSULTAT:
# A:0, B:5, C:3, D:2, E:3

# DÉTECTION DE CYCLE NÉGATIF:
# Si après V-1 itérations, on peut encore relaxer une arête,
# alors il existe un cycle de poids négatif!

# Exemple de cycle négatif:
#   A ——1—-> B
#   ^       |
#   |       | -3
#   |       v
#   C <-——1—— D

# Total du cycle: 1 + (-3) + 1 = -1 (négatif!)
# On peut boucler indéfiniment et réduire la distance!

# COMPLEXITÉ:
# Temps: O(V × E)
# Espace: O(V)

# AVANTAGES:
# + Fonctionne avec poids négatifs
# + Détecte les cycles de poids négatif
# + Simple à implémenter

# INCONVÉNIENTS:
# - Plus lent que Dijkstra
# - O(V × E) peut être très lent pour grands graphes

# QUAND UTILISER?
# - Graphes avec poids négatifs
# - Détection de cycles négatifs
# - Problèmes d'arbitrage (finance)


# === 3. ALGORITHME DE FLOYD-WARSHALL ===

# QUI?
# Robert Floyd (1962), Stephen Warshall (1962)

# QUOI?
# = Trouve le plus court chemin entre TOUTES les paires de sommets
# = Utilise la programmation dynamique

# POURQUOI?
# - Dijkstra trouve les chemins depuis UNE source
# - Floyd-Warshall trouve les chemins entre TOUTES les paires en une seule exécution

# PRINCIPE:
# 1. Créer une matrice de distances
# 2. Initialiser avec les poids des arêtes directes
# 3. Pour chaque sommet intermédiaire k:
#    - Pour chaque paire (i, j):
#      * Vérifier si passer par k améliore la distance i -> j
#      * distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

# ALGORITHME DÉTAILLÉ:

# FloydWarshall(graphe):
#     # Initialisation
#     créer une matrice distance de taille V×V
#     
#     pour chaque sommet i:
#         pour chaque sommet j:
#             si i == j:
#                 distance[i][j] = 0
#             sinon si il existe une arête (i, j):
#                 distance[i][j] = poids(i, j)
#             sinon:
#                 distance[i][j] = ∞
#     
#     # Programmation dynamique
#     pour k de 0 à V-1:
#         pour i de 0 à V-1:
#             pour j de 0 à V-1:
#                 si distance[i][k] + distance[k][j] < distance[i][j]:
#                     distance[i][j] = distance[i][k] + distance[k][j]
#     
#     retourner distance

# EXEMPLE:

# Graphe:
#   A ——3—-> B
#   v       v
#   2       1
#   v       v
#   C ——4—-> D

# INITIALISATION:
# Matrice de distances:
#     A  B  C  D
# A   0  3  2  ∞
# B   ∞  0  ∞  1
# C   ∞  ∞  0  4
# D   ∞  ∞  ∞  0

# ITÉRATION k=0 (passer par A):
# Pour chaque paire (i,j), vérifier si passer par A améliore:
# B->C: min(∞, B->A + A->C) = min(∞, ∞) = ∞
# B->D: min(1, B->A + A->D) = min(1, ∞) = 1
# ...
# Aucune amélioration (A n'est pas intermédiaire utile)

# ITÉRATION k=1 (passer par B):
# A->D: min(∞, A->B + B->D) = min(∞, 3+1) = 4 [OK]
# C->D: reste 4 (C ne peut pas atteindre B)

# Matrice après k=1:
#     A  B  C  D
# A   0  3  2  4
# B   ∞  0  ∞  1
# C   ∞  ∞  0  4
# D   ∞  ∞  ∞  0

# ITÉRATION k=2 (passer par C):
# A->D: min(4, A->C + C->D) = min(4, 2+4) = 4
# Aucune amélioration

# ITÉRATION k=3 (passer par D):
# Aucune amélioration (D n'a pas de sortie)

# RÉSULTAT FINAL:
#     A  B  C  D
# A   0  3  2  4
# B   ∞  0  ∞  1
# C   ∞  ∞  0  4
# D   ∞  ∞  ∞  0

# Plus court chemin de A vers D: 4 (A->B->D)

# COMPLEXITÉ:
# Temps: O(V³)
# Espace: O(V²)

# AVANTAGES:
# + Trouve toutes les paires de plus courts chemins
# + Simple à implémenter
# + Fonctionne avec poids négatifs (mais pas cycles négatifs)

# INCONVÉNIENTS:
# - O(V³) très lent pour grands graphes
# - Consomme beaucoup de mémoire O(V²)

# QUAND UTILISER?
# - Petits graphes (V < 500)
# - Besoin de TOUS les plus courts chemins
# - Matrice de distances complète nécessaire


# === COMPARAISON DES ALGORITHMES ===

# Algorithme     | Source      | Poids négatifs | Complexité | Usage
# ---------------|-------------|----------------|------------|------------------
# BFS            | Une seule   | Non applicable | O(V+E)     | Non pondéré
# Dijkstra       | Une seule   | Non            | O(E log V) | Poids positifs
# Bellman-Ford   | Une seule   | Oui            | O(V×E)     | Poids négatifs
# Floyd-Warshall | Toutes      | Oui            | O(V³)      | Toutes les paires


[OK] ARBRES COUVRANTS (SPANNING TREES)

# === QU'EST-CE QU'UN ARBRE COUVRANT? ===

# ARBRE COUVRANT (Spanning Tree):
# = Sous-graphe qui:
#   1. Est un ARBRE (connexe, sans cycle)
#   2. Contient TOUS les sommets du graphe original
#   3. Utilise un sous-ensemble des arêtes

# POURQUOI?
# - Minimiser le coût de connexion de tous les sommets
# - Réseau de télécommunication (câbles)
# - Réseau électrique (lignes)
# - Routes (connections minimales)

# EXEMPLE:
# Graphe original:
#     A ———— B
#     |  \   |
#     |   \  |
#     C ———— D

# Arbre couvrant possible:
#     A ———— B
#     |      
#     |      
#     C ———— D

# On a enlevé l'arête A-D et B-D
# Reste un arbre qui couvre tous les sommets!

# PROPRIÉTÉS:
# - Si le graphe a V sommets, l'arbre couvrant a V-1 arêtes
# - Un graphe connexe a au moins un arbre couvrant
# - Un graphe peut avoir plusieurs arbres couvrants différents


# === ARBRE COUVRANT MINIMAL (MST - Minimum Spanning Tree) ===

# QUOI?
# = Arbre couvrant avec la SOMME MINIMALE des poids des arêtes

# POURQUOI?
# - Minimiser le coût total de connexion
# - Exemple: Connecter toutes les villes avec le minimum de câbles/routes

# EXEMPLE:
# Graphe pondéré:
#       5        3
#   A ———— B ———— C
#   |      |      |
# 2 |    1 |    4 |
#   |      |      |
#   D ———— E ———— F
#       6        2

# Arbre couvrant minimal:
#   A ———— B ———— C
#   |      |      |
# 2 |    1 |    2 |
#   |      |      |
#   D      E      F

# Arêtes choisies: A-D (2), B-E (1), B-C (3), C-F (2), A-B (5)
# Coût total: 2+1+3+2+5 = 13

# DEUX ALGORITHMES CLASSIQUES:
# 1. Algorithme de Kruskal
# 2. Algorithme de Prim


# === 1. ALGORITHME DE KRUSKAL ===

# QUI?
# Joseph Kruskal (1956)

# PRINCIPE:
# = Approche GLOUTON (greedy)
# = Choisir les arêtes par ordre croissant de poids
# = Éviter les cycles

# ALGORITHME:
# 1. Trier toutes les arêtes par poids croissant
# 2. Initialiser une forêt (ensemble d'arbres) avec chaque sommet seul
# 3. Pour chaque arête (u, v, poids) dans l'ordre:
#    - Si u et v sont dans des arbres différents:
#      * Ajouter l'arête au MST
#      * Fusionner les deux arbres (Union-Find)
#    - Sinon (ils sont dans le même arbre):
#      * Ignorer l'arête (créerait un cycle)
# 4. Continuer jusqu'à avoir V-1 arêtes

# STRUCTURE DE DONNÉES:
# Union-Find (Disjoint Set Union - DSU)
# Permet de:
# - Savoir si deux sommets sont dans le même arbre: Find(u) == Find(v)
# - Fusionner deux arbres: Union(u, v)

# EXEMPLE DÉTAILLÉ:

# Graphe:
#       5        3
#   A ———— B ———— C
#   |      |      |
# 2 |    1 |    4 |
#   |      |      |
#   D ———— E ———— F
#       6        2

# ÉTAPE 1: Trier les arêtes par poids croissant
# Arêtes triées:
# (B, E, 1)
# (A, D, 2)
# (C, F, 2)
# (B, C, 3)
# (C, E, 4)
# (A, B, 5)
# (D, E, 6)

# ÉTAPE 2: Initialisation Union-Find
# Chaque sommet est dans son propre arbre:
# {A}, {B}, {C}, {D}, {E}, {F}

# ÉTAPE 3: Traiter les arêtes

# Arête (B, E, 1):
# B et E dans des arbres différents? Oui ({B} et {E})
# -> Ajouter au MST
# -> Fusionner: {B, E}
# MST: [(B, E, 1)]
# Ensembles: {A}, {B, E}, {C}, {D}, {F}

# Arête (A, D, 2):
# A et D dans des arbres différents? Oui ({A} et {D})
# -> Ajouter au MST
# -> Fusionner: {A, D}
# MST: [(B, E, 1), (A, D, 2)]
# Ensembles: {A, D}, {B, E}, {C}, {F}

# Arête (C, F, 2):
# C et F dans des arbres différents? Oui ({C} et {F})
# -> Ajouter au MST
# -> Fusionner: {C, F}
# MST: [(B, E, 1), (A, D, 2), (C, F, 2)]
# Ensembles: {A, D}, {B, E}, {C, F}

# Arête (B, C, 3):
# B et C dans des arbres différents? Oui ({B, E} et {C, F})
# -> Ajouter au MST
# -> Fusionner: {B, E, C, F}
# MST: [(B, E, 1), (A, D, 2), (C, F, 2), (B, C, 3)]
# Ensembles: {A, D}, {B, E, C, F}

# Arête (C, E, 4):
# C et E dans des arbres différents? Non (tous deux dans {B, E, C, F})
# -> IGNORER (créerait un cycle)
# MST inchangé
# Ensembles inchangés

# Arête (A, B, 5):
# A et B dans des arbres différents? Oui ({A, D} et {B, E, C, F})
# -> Ajouter au MST
# -> Fusionner: {A, D, B, E, C, F}
# MST: [(B, E, 1), (A, D, 2), (C, F, 2), (B, C, 3), (A, B, 5)]
# Ensembles: {A, D, B, E, C, F}

# TERMINÉ! On a V-1 = 5 arêtes

# MST FINAL:
#       5        3
#   A ———— B ———— C
#   |      |      |
# 2 |    1 |    2 |
#   |      |      |
#   D      E      F

# Coût total: 1+2+2+3+5 = 13

# COMPLEXITÉ:
# Temps: O(E log E) (tri des arêtes)
# Espace: O(V) (pour Union-Find)

# AVANTAGES:
# + Facile à comprendre et implémenter
# + Efficace pour graphes sparse
# + Utilise Union-Find (structure élégante)

# INCONVÉNIENTS:
# - Nécessite de trier toutes les arêtes
# - Pas optimal pour graphes denses

# QUAND UTILISER?
# - Graphes sparse (peu d'arêtes)
# - Quand toutes les arêtes sont disponibles dès le début


# === 2. ALGORITHME DE PRIM ===

# QUI?
# Robert Prim (1957), Vojtěch Jarník (1930), Edsger Dijkstra (1959)

# PRINCIPE:
# = Approche GLOUTON (greedy)
# = Construire l'arbre en ajoutant des sommets un par un
# = Toujours choisir l'arête de poids minimal qui connecte un nouveau sommet

# ALGORITHME:
# 1. Choisir un sommet de départ arbitraire
# 2. Ajouter ce sommet à l'arbre
# 3. Répéter jusqu'à avoir tous les sommets:
#    - Choisir l'arête de poids minimal qui connecte un sommet dans l'arbre
#      à un sommet HORS de l'arbre
#    - Ajouter cette arête et le nouveau sommet à l'arbre

# EXEMPLE DÉTAILLÉ:

# Même graphe:
#       5        3
#   A ———— B ———— C
#   |      |      |
# 2 |    1 |    4 |
#   |      |      |
#   D ———— E ———— F
#       6        2

# DÉPART: Choisir A comme sommet de départ

# ÉTAPE 1:
# Sommets dans l'arbre: {A}
# Sommets hors de l'arbre: {B, C, D, E, F}
# Arêtes candidates (connectent dedans/dehors):
#   - A-B (5)
#   - A-D (2) <- minimum!
# Choisir A-D
# Ajouter D à l'arbre
# MST: [(A, D, 2)]

# ÉTAPE 2:
# Sommets dans l'arbre: {A, D}
# Sommets hors: {B, C, E, F}
# Arêtes candidates:
#   - A-B (5)
#   - D-E (6)
# Choisir A-B
# MST: [(A, D, 2), (A, B, 5)]

# ÉTAPE 3:
# Sommets dans l'arbre: {A, D, B}
# Sommets hors: {C, E, F}
# Arêtes candidates:
#   - B-C (3)
#   - B-E (1) <- minimum!
#   - D-E (6)
# Choisir B-E
# MST: [(A, D, 2), (A, B, 5), (B, E, 1)]

# ÉTAPE 4:
# Sommets dans l'arbre: {A, D, B, E}
# Sommets hors: {C, F}
# Arêtes candidates:
#   - B-C (3) <- minimum!
#   - E-C (4)
#   - D-E (6) (mais E déjà dans l'arbre, ignorer)
# Choisir B-C
# MST: [(A, D, 2), (A, B, 5), (B, E, 1), (B, C, 3)]

# ÉTAPE 5:
# Sommets dans l'arbre: {A, D, B, E, C}
# Sommets hors: {F}
# Arêtes candidates:
#   - C-F (2) <- minimum!
#   - E-F (ignoré si pas d'arête)
# Choisir C-F
# MST: [(A, D, 2), (A, B, 5), (B, E, 1), (B, C, 3), (C, F, 2)]

# TERMINÉ!

# MST FINAL: identique à Kruskal
# Coût: 13

# COMPLEXITÉ:
# Avec file de priorité (tas binaire): O(E log V)
# Avec tableau simple: O(V²)

# AVANTAGES:
# + Efficace pour graphes denses
# + Peut commencer depuis n'importe quel sommet
# + Similaire à Dijkstra (facile si on connaît Dijkstra)

# INCONVÉNIENTS:
# - Nécessite de maintenir une file de priorité

# QUAND UTILISER?
# - Graphes denses (beaucoup d'arêtes)
# - Quand on construit l'arbre progressivement


# === COMPARAISON KRUSKAL vs PRIM ===

# Critère          | Kruskal              | Prim
# -----------------|----------------------|---------------------
# Approche         | Arêtes               | Sommets
# Structure        | Union-Find           | File de priorité
# Complexité       | O(E log E)           | O(E log V)
# Graphe sparse    | Meilleur             | Bon
# Graphe dense     | Bon                  | Meilleur
# Implémentation   | Plus simple          | Plus complexe


[OK] TRI TOPOLOGIQUE (TOPOLOGICAL SORTING)

# === QU'EST-CE QUE LE TRI TOPOLOGIQUE? ===

# TRI TOPOLOGIQUE:
# = Ordonnancement linéaire des sommets d'un DAG (graphe orienté acyclique)
# = Si une arête (u, v) existe, alors u apparaît AVANT v dans l'ordre

# POURQUOI?
# - Ordonnancer des tâches avec dépendances
# - Planification de projets
# - Compilation (dépendances de modules)
# - Curriculum scolaire (cours prérequis)

# EXEMPLE:
# Graphe (dépendances de cours):

#   Math1 ——-> Math2 ——-> Math3
#     |                   ^
#     |                   |
#     v                   |
#   Physique ————————————

# Dépendances:
# - Math2 nécessite Math1
# - Math3 nécessite Math2
# - Math3 nécessite Physique
# - Physique nécessite Math1

# UN tri topologique possible:
# Math1 -> Physique -> Math2 -> Math3

# AUTRE tri topologique possible:
# Math1 -> Math2 -> Physique -> Math3

# Les deux sont valides!

# CONDITION IMPORTANTE:
# Le tri topologique existe SI ET SEULEMENT SI le graphe est un DAG
# (pas de cycle!)

# Si cycle existe:
#   A ——-> B
#   ^     v
#   C <-——— D
# Impossible de trier! (A avant B, B avant D, D avant C, C avant A -> contradiction!)


# === ALGORITHME 1: DFS (Depth-First Search) ===

# PRINCIPE:
# 1. Faire un DFS sur le graphe
# 2. Quand un sommet est complètement exploré (tous ses successeurs visités),
#    l'ajouter à une pile
# 3. À la fin, la pile contient le tri topologique (ordre inverse)

# ALGORITHME DÉTAILLÉ:

# TriTopoDFS(graphe):
#     pile = pile vide
#     visité = ensemble vide
#     
#     fonction DFS(sommet):
#         marquer sommet comme visité
#         pour chaque voisin de sommet:
#             si voisin non visité:
#                 DFS(voisin)
#         empiler sommet sur la pile  # Après avoir exploré tous les successeurs!
#     
#     pour chaque sommet v du graphe:
#         si v non visité:
#             DFS(v)
#     
#     retourner pile (dans l'ordre inverse)

# EXEMPLE DÉTAILLÉ:

# Graphe:
#   A ——-> B ——-> D
#   |           ^
#   v           |
#   C ——————————

# EXÉCUTION:

# Commencer DFS depuis A:
# 1. Visiter A, marquer comme visité
# 2. Explorer B (voisin de A)
#    - Visiter B, marquer comme visité
#    - Explorer D (voisin de B)
#      * Visiter D, marquer comme visité
#      * Aucun voisin non visité
#      * Empiler D -> pile: [D]
#    - Retour à B, tous les voisins visités
#    - Empiler B -> pile: [D, B]
# 3. Retour à A, explorer C (autre voisin de A)
#    - Visiter C, marquer comme visité
#    - Explorer D (voisin de C) -> déjà visité, skip
#    - Empiler C -> pile: [D, B, C]
# 4. Retour à A, tous les voisins visités
#    - Empiler A -> pile: [D, B, C, A]

# TRI TOPOLOGIQUE (ordre inverse de la pile):
# A -> C -> B -> D

# Vérification:
# - A avant C [OK] (A->C existe)
# - C avant D [OK] (C->D existe)
# - B avant D [OK] (B->D existe)
# - A avant B [OK] (A->B existe)

# COMPLEXITÉ:
# Temps: O(V + E)
# Espace: O(V)

# AVANTAGES:
# + Simple à implémenter
# + Utilise DFS (déjà connu)
# + Efficace

# INCONVÉNIENTS:
# - Ne détecte pas les cycles explicitement (besoin d'une variante)


# === ALGORITHME 2: KAHN (BFS) ===

# PRINCIPE:
# 1. Calculer le degré entrant de chaque sommet
# 2. Ajouter à une file tous les sommets de degré entrant 0 (pas de prérequis)
# 3. Répéter:
#    - Retirer un sommet de la file
#    - L'ajouter au résultat
#    - Pour chaque voisin, décrémenter son degré entrant
#    - Si degré entrant devient 0, ajouter à la file
# 4. Si tous les sommets sont traités: tri topologique trouvé
#    Sinon: cycle détecté!

# ALGORITHME DÉTAILLÉ:

# TriTopoKahn(graphe):
#     # Calculer les degrés entrants
#     degré_entrant = tableau initialisé à 0
#     pour chaque arête (u, v):
#         degré_entrant[v] += 1
#     
#     # File des sommets sans prérequis
#     file = file vide
#     pour chaque sommet v:
#         si degré_entrant[v] == 0:
#             ajouter v à la file
#     
#     résultat = liste vide
#     
#     tant que file non vide:
#         u = retirer de la file
#         ajouter u au résultat
#         
#         pour chaque voisin v de u:
#             degré_entrant[v] -= 1
#             si degré_entrant[v] == 0:
#                 ajouter v à la file
#     
#     si longueur(résultat) == nombre de sommets:
#         retourner résultat
#     sinon:
#         retourner "Cycle détecté!"

# EXEMPLE DÉTAILLÉ:

# Même graphe:
#   A ——-> B ——-> D
#   |           ^
#   v           |
#   C ——————————

# ÉTAPE 1: Calculer les degrés entrants
# degré_entrant[A] = 0 (aucune arête arrive)
# degré_entrant[B] = 1 (A->B)
# degré_entrant[C] = 1 (A->C)
# degré_entrant[D] = 2 (B->D, C->D)

# ÉTAPE 2: Initialiser la file avec sommets de degré 0
# file = [A]
# résultat = []

# ÉTAPE 3: Boucle principale

# Itération 1:
# Retirer A de la file
# résultat = [A]
# Voisins de A: B, C
#   - degré_entrant[B] = 1-1 = 0 -> ajouter B à la file
#   - degré_entrant[C] = 1-1 = 0 -> ajouter C à la file
# file = [B, C]

# Itération 2:
# Retirer B de la file
# résultat = [A, B]
# Voisins de B: D
#   - degré_entrant[D] = 2-1 = 1 (pas encore 0)
# file = [C]

# Itération 3:
# Retirer C de la file
# résultat = [A, B, C]
# Voisins de C: D
#   - degré_entrant[D] = 1-1 = 0 -> ajouter D à la file
# file = [D]

# Itération 4:
# Retirer D de la file
# résultat = [A, B, C, D]
# Voisins de D: aucun
# file = []

# TERMINÉ!
# TRI TOPOLOGIQUE: A -> B -> C -> D

# Vérification:
# longueur(résultat) = 4 = nombre de sommets [OK]
# Pas de cycle!

# COMPLEXITÉ:
# Temps: O(V + E)
# Espace: O(V)

# AVANTAGES:
# + Détecte les cycles facilement
# + Intuitif (traiter ce qui est "prêt")
# + Peut traiter plusieurs ordres simultanément

# INCONVÉNIENTS:
# - Nécessite le calcul des degrés entrants

# QUAND UTILISER?
# - Ordonnancement de tâches
# - Détection de cycles dans DAG
# - Planification avec dépendances


# === APPLICATIONS RÉELLES ===

# 1. COMPILATION:
# - Modules A dépend de B, B dépend de C
# - Ordre de compilation: C -> B -> A

# 2. GESTION DE PACKAGES:
# - Package X nécessite Y et Z
# - Ordre d'installation: Y, Z -> X

# 3. CURRICULUM SCOLAIRE:
# - Cours avancés nécessitent cours de base
# - Planifier l'ordre des cours

# 4. BUILD SYSTEMS (Make, Maven, Gradle):
# - Fichiers sources avec dépendances
# - Ordre de build

# 5. ORDONNANCEMENT DE TÂCHES:
# - Projet avec tâches interdépendantes
# - Déterminer l'ordre d'exécution


[OK] DÉTECTION DE CYCLES (CYCLE DETECTION)

# Détecter si un graphe contient un cycle est un problème fondamental

# === GRAPHE NON ORIENTÉ ===

# MÉTHODE 1: DFS

# PRINCIPE:
# Pendant le DFS, si on rencontre un sommet déjà visité
# (qui n'est PAS le parent direct), alors il y a un cycle

# ALGORITHME:

# DétecterCycleDFS(graphe):
#     visité = ensemble vide
#     
#     fonction DFS(sommet, parent):
#         marquer sommet comme visité
#         pour chaque voisin de sommet:
#             si voisin non visité:
#                 si DFS(voisin, sommet) == True:
#                     retourner True  # Cycle détecté
#             sinon si voisin != parent:
#                 retourner True  # Cycle détecté!
#         retourner False
#     
#     pour chaque sommet v:
#         si v non visité:
#             si DFS(v, null) == True:
#                 retourner "Cycle détecté"
#     
#     retourner "Pas de cycle"

# EXEMPLE:

# Graphe AVEC cycle:
#     A ———— B
#     |      |
#     C ———— D

# DFS depuis A:
# 1. Visiter A (parent=null)
# 2. Explorer B (parent=A)
#    - Visiter B
#    - Explorer D (parent=B)
#      * Visiter D
#      * Explorer C (parent=D)
#        - Visiter C
#        - Explorer A (parent=C)
#          A est visité ET A ≠ C -> CYCLE DÉTECTÉ!

# MÉTHODE 2: Union-Find

# PRINCIPE:
# Pour chaque arête (u, v):
# - Si u et v sont déjà dans le même ensemble: cycle!
# - Sinon: fusionner les ensembles

# EXEMPLE:

# Graphe:
#     A ———— B
#     |      |
#     C ———— D

# Traiter arêtes:
# 1. A-B: Union({A}, {B}) -> {A, B}
# 2. A-C: Union({A, B}, {C}) -> {A, B, C}
# 3. B-D: Union({A, B, C}, {D}) -> {A, B, C, D}
# 4. C-D: C et D déjà dans le même ensemble -> CYCLE!


# === GRAPHE ORIENTÉ ===

# MÉTHODE: DFS avec états

# PRINCIPE:
# Trois états pour chaque sommet:
# - BLANC (non visité)
# - GRIS (en cours de traitement)
# - NOIR (complètement traité)
#
# Si pendant le DFS on rencontre un sommet GRIS, il y a un cycle!

# ALGORITHME:

# DétecterCycleOrienté(graphe):
#     état = dictionnaire (tous = BLANC)
#     
#     fonction DFS(sommet):
#         état[sommet] = GRIS  # En cours
#         
#         pour chaque voisin de sommet:
#             si état[voisin] == GRIS:
#                 retourner True  # Cycle détecté!
#             si état[voisin] == BLANC:
#                 si DFS(voisin) == True:
#                     retourner True
#         
#         état[sommet] = NOIR  # Terminé
#         retourner False
#     
#     pour chaque sommet v:
#         si état[v] == BLANC:
#             si DFS(v) == True:
#                 retourner "Cycle détecté"
#     
#     retourner "Pas de cycle"

# EXEMPLE:

# Graphe AVEC cycle:
#   A ——-> B
#   ^     v
#   C <-—— D

# DFS depuis A:
# 1. A = GRIS
# 2. Explorer B
#    - B = GRIS
#    - Explorer D
#      * D = GRIS
#      * Explorer C
#        - C = GRIS
#        - Explorer A
#          A = GRIS déjà -> CYCLE DÉTECTÉ!


[OK] COMPOSANTES CONNEXES ET FORTEMENT CONNEXES

# === COMPOSANTES CONNEXES (pour graphes non orientés) ===

# COMPOSANTE CONNEXE:
# = Sous-graphe maximal où tous les sommets sont connectés entre eux

# TROUVER LES COMPOSANTES:
# Utiliser DFS ou BFS depuis chaque sommet non visité

# ALGORITHME:

# TrouverComposantes(graphe):
#     visité = ensemble vide
#     composantes = []
#     
#     pour chaque sommet v:
#         si v non visité:
#             composante = []
#             DFS(v, composante)  # Ou BFS
#             composantes.ajouter(composante)
#     
#     retourner composantes

# EXEMPLE:

# Graphe:
#     A ———— B        E ———— F
#     |              |
#     C              G

# Composantes:
# Composante 1: {A, B, C}
# Composante 2: {E, F, G}


# === COMPOSANTES FORTEMENT CONNEXES (SCC - Strongly Connected Components) ===

# Pour graphes ORIENTÉS

# COMPOSANTE FORTEMENT CONNEXE:
# = Sous-graphe maximal où il existe un chemin de tout sommet vers tout autre# ALGORITHME DE KOSARAJU:

# 1. Faire un DFS sur le graphe original, noter l'ordre de fin
# 2. Construire le graphe transposé (inverser toutes les arêtes)
# 3. Faire un DFS sur le graphe transposé dans l'ordre inverse de fin
# 4. Chaque arbre DFS = une SCC

# EXEMPLE:

# Graphe:
#   A ——-> B ——-> C
#   ^           v
#   E <-———— D <-—

# SCCs:
# SCC 1: {A, B, C, D, E} (tous peuvent atteindre tous)

# Graphe déconnecté:
#   A ——-> B        D ——-> E
#   ^     v        ^     v
#   C <-———        F <-———

# SCCs:
# SCC 1: {A, B, C}
# SCC 2: {D, E, F}


[OK] PROBLÈMES CLASSIQUES ET APPLICATIONS

# === 1. PROBLÈME DU VOYAGEUR DE COMMERCE (TSP) ===

# DESCRIPTION:
# Étant donné n villes et les distances entre elles,
# trouver le plus court circuit qui visite chaque ville exactement une fois
# et revient à la ville de départ

# TYPE: Problème NP-complet (très difficile!)

# GRAPHE: Graphe complet pondéré

# APPROCHES:
# - Force brute: O(n!) (impossible pour n > 15)
# - Programmation dynamique: O(n² × 2^n)
# - Heuristiques (approximations)

# APPLICATION:
# - Livraison de colis
# - Tournées de techniciens
# - Routage de drones


# === 2. PROBLÈME DU CHEMIN HAMILTONIEN ===

# DESCRIPTION:
# Trouver un chemin qui visite chaque sommet exactement une fois

# TYPE: NP-complet

# DIFFÉRENCE avec TSP:
# - Hamiltonien: chemin (pas de retour)
# - TSP: cycle (retour au départ)

# APPLICATION:
# - Planification de visites
# - Puzzles (Knight's Tour sur échiquier)


# === 3. FLOT MAXIMUM (Maximum Flow) ===

# DESCRIPTION:
# Étant donné un graphe avec capacités sur les arêtes,
# trouver le flot maximum de la source vers le puits

# ALGORITHMES:
# - Ford-Fulkerson
# - Edmonds-Karp
# - Dinic

# APPLICATION:
# - Réseaux de transport (eau, électricité)
# - Réseaux informatiques (bande passante)
# - Assignation de ressources


# === 4. COUPLAGE MAXIMUM (Maximum Matching) ===

# DESCRIPTION:
# Dans un graphe biparti, trouver le maximum de paires de sommets connectés
# telles qu'aucun sommet n'apparaît deux fois

# ALGORITHMES:
# - Algorithme hongrois
# - Hopcroft-Karp

# APPLICATION:
# - Assignation emploi-candidat
# - Mariage stable
# - Allocation de ressources


# === 5. COLORATION DE GRAPHES (Graph Coloring) ===

# DESCRIPTION:
# Assigner des couleurs aux sommets tels que deux sommets adjacents
# n'aient pas la même couleur, avec le minimum de couleurs

# TYPE: NP-complet pour trouver le minimum

# HEURISTIQUES:
# - Algorithme glouton
# - Welsh-Powell

# APPLICATION:
# - Planification d'horaires (exams, cours)
# - Attribution de fréquences radio
# - Allocation de registres (compilation)


# === 6. PROBLÈME DES PONTS DE KÖNIGSBERG ===

# DESCRIPTION HISTORIQUE:
# La ville de Königsberg avait 7 ponts
# Question: Peut-on traverser tous les ponts exactement une fois?

# SOLUTION (Euler, 1736):
# Un graphe a un chemin eulérien SI ET SEULEMENT SI
# il a exactement 0 ou 2 sommets de degré impair

# Königsberg: 4 sommets de degré impair -> IMPOSSIBLE!

# C'est le PREMIER théorème de la théorie des graphes!


# === 7. PROBLÈME DU SAC À DOS (Knapsack) ===

# Peut être modélisé comme un graphe!

# APPLICATION:
# - Optimisation de ressources
# - Planification budgétaire


[OK] PROPRIÉTÉS AVANCÉES

# === PLANARITÉ ===

# THÉORÈME DE KURATOWSKI:
# Un graphe est planaire SI ET SEULEMENT SI
# il ne contient ni K5 ni K3,3 comme sous-graphe

# K5 = graphe complet à 5 sommets
# K3,3 = graphe biparti complet 3×3

# APPLICATION:
# - Circuits imprimés
# - Cartes géographiques


# === THÉORÈME D'EULER (graphes planaires) ===

# Pour un graphe planaire connexe:
# V - E + F = 2

# V = nombre de sommets
# E = nombre d'arêtes
# F = nombre de faces

# EXEMPLE:
# Carré: V=4, E=4, F=2 (intérieur + extérieur)
# 4 - 4 + 2 = 2 [OK]


# === GRAPHES RÉGULIERS ===

# GRAPHE k-RÉGULIER:
# = Tous les sommets ont le même degré k

# EXEMPLES:
# - Graphe complet Kn: (n-1)-régulier
# - Cycle Cn: 2-régulier
# - Cube: 3-régulier


# === GRAPHES DE CAYLEY ===

# Utilisés en théorie des groupes et cryptographie

# APPLICATION:
# - Réseaux d'interconnexion
# - Cryptographie


# === PETIT MONDE (Small World) ===

# PROPRIÉTÉ:
# Dans de nombreux graphes réels, la distance moyenne entre deux sommets
# est petite (logarithmique)

# EXEMPLE:
# Réseaux sociaux: "6 degrés de séparation"
# En moyenne, toute personne est à 6 connexions d'une autre


# === GRAPHES SANS ÉCHELLE (Scale-Free) ===

# PROPRIÉTÉ:
# Distribution des degrés suit une loi de puissance
# Quelques sommets (hubs) ont beaucoup de connexions

# EXEMPLE:
# - Internet (quelques serveurs très connectés)
# - Réseaux sociaux (influenceurs)


[OK] RÉSUMÉ ET AIDE-MÉMOIRE

# === TYPES DE GRAPHES ===

# Type               | Orienté | Pondéré | Cycles | Exemple
# -------------------|---------|---------|--------|------------------
# Simple             | Non     | Non     | Oui    | Amitié
# Orienté            | Oui     | Non     | Oui    | Twitter
# Pondéré            | Dépend  | Oui     | Oui    | GPS
# Complet            | Non     | Non     | Oui    | Tournoi complet
# Biparti            | Non     | Non     | Non*   | Étudiants-Cours
# DAG                | Oui     | Non     | Non    | Dépendances
# Arbre              | Non     | Non     | Non    | Fichiers
# Eulérien           | Dépend  | Non     | Oui    | Facteur
# Hamiltonien        | Dépend  | Non     | Oui    | TSP


# === ALGORITHMES ESSENTIELS ===

# Problème                    | Algorithme      | Complexité
# ----------------------------|-----------------|------------
# Parcours                    | DFS             | O(V+E)
# Parcours                    | BFS             | O(V+E)
# Plus court chemin (1 source)| Dijkstra        | O(E log V)
# Plus court chemin (négatif) | Bellman-Ford    | O(V×E)
# Plus courts chemins (tous)  | Floyd-Warshall  | O(V³)
# Arbre couvrant minimal      | Kruskal         | O(E log E)
# Arbre couvrant minimal      | Prim            | O(E log V)
# Tri topologique             | DFS / Kahn      | O(V+E)
# Détection de cycle          | DFS / Union-Find| O(V+E)
# Composantes connexes        | DFS / BFS       | O(V+E)


# === QUAND UTILISER QUEL ALGORITHME? ===

# PARCOURS:
# - Plus court chemin (non pondéré): BFS
# - Détection de cycles: DFS
# - Tri topologique: DFS ou Kahn

# PLUS COURT CHEMIN:
# - Poids positifs: Dijkstra
# - Poids négatifs: Bellman-Ford
# - Toutes les paires: Floyd-Warshall

# ARBRE COUVRANT MINIMAL:
# - Graphe sparse: Kruskal
# - Graphe dense: Prim

# REPRÉSENTATION:
# - Sparse: Liste d'adjacence
# - Dense: Matrice d'adjacence
# - Algorithmes sur arêtes: Liste d'arêtes


# === PROPRIÉTÉS IMPORTANTES ===

# - Σ deg(v) = 2|E| (théorème de la somme des degrés)
# - Arbre: |E| = |V| - 1
# - Graphe complet: |E| = V(V-1)/2
# - V - E + F = 2 (graphes planaires, Euler)


# === APPLICATIONS PAR DOMAINE ===

# RÉSEAUX SOCIAUX:
# - Composantes connexes (communautés)
# - Plus court chemin (degrés de séparation)
# - Centralité (influenceurs)

# TRANSPORT / GPS:
# - Dijkstra (plus court chemin)
# - Arbre couvrant minimal (réseau routier)

# ORDONNANCEMENT:
# - Tri topologique (dépendances)
# - Chemin critique (gestion de projet)

# BIOLOGIE:
# - Réseaux métaboliques
# - Arbre phylogénétique

# INTERNET:
# - Routage (plus court chemin)
# - PageRank (importance des pages)


[OK] CONCEPTS AVANCÉS POUR ALLER PLUS LOIN

# === CENTRALITÉ (Centrality) ===

# Mesure l'importance d'un sommet dans le graphe

# TYPES:
# 1. Centralité de degré: deg(v)
# 2. Centralité de proximité: inverse de la somme des distances
# 3. Centralité d'intermédiarité: nombre de plus courts chemins passant par v
# 4. PageRank (Google): importance basée sur les liens entrants


# === GRAPHES DYNAMIQUES ===

# Graphes qui changent dans le temps
# - Ajout/suppression de sommets/arêtes
# - Réseaux sociaux évolutifs


# === GRAPHES PROBABILISTES ===

# Arêtes existent avec une certaine probabilité
# - Modèles de réseaux sociaux
# - Propagation d'épidémies


# === GRAPHES ÉTIQUETÉS ===

# Sommets et/ou arêtes ont des étiquettes/attributs
# - Réseaux sociaux (attributs utilisateurs)
# - Graphes de connaissances (Knowledge Graphs)


# === THÉORIE SPECTRALE DES GRAPHES ===

# Étude des propriétés via les valeurs propres de matrices associées
# - Clustering spectral
# - Détection de communautés


# === GRAPHES HYPERBOLIQUES ===

# Graphes dans l'espace hyperbolique
# - Modélisation d'Internet
# - Réseaux complexes


# FIN DU CHEATSHEET - Tu as maintenant une compréhension complète de la théorie des graphes!
```