La théorie des graphes est un outil fondamental pour modéliser et résoudre des problèmes d'optimisation dans des systèmes complexes. Cette compétence couvre les concepts clés — partitionnement, flots, couplages, marches aléatoires — et leurs applications en systèmes multi-agents, réseaux distribués, transport, et apprentissage automatique.
Les problèmes d'optimisation sur graphes apparaissent dans de nombreux contextes :
Partitionnement de graphes : diviser un réseau en communautés ou clusters équilibrés.
Flot maximal / coupe minimale : optimiser le routage dans un réseau de transport.
Couplage optimal : assigner des tâches à des agents de manière optimale.
Marches aléatoires et PageRank : classer l'importance des nœuds dans un graphe.
Graphes de connaissances : raisonner sur des entités et leurs relations.
Quand l'utiliser
Situation
Modélisation
Algorithme clé
Partitionner un réseau en communautés
Graphe de similarité
Louvain, Spectral Clustering
Optimiser le routage dans un réseau
Graphe orienté pondéré
Dijkstra, A*, Flot max
Assigner des tâches à des agents
Graphe biparti
Hungarian algorithm
Détecter des communautés dans un réseau social
Graphe non orienté
Girvan-Newman, Label Propagation
Compresser un graphe tout en préservant sa structure
Graphe avec degrés
Graphitour, fusion de nœuds
Planifier des chemins pour une flotte de véhicules
Graphe temporel
VRP, Christofides
1. Partitionnement de Graphes
1.1 Partitionnement en Étoiles
Le partitionnement en étoiles consiste à diviser un graphe en sous-ensembles centrés autour d'un nœud pivot. Chaque étoile est définie par un sommet central connecté à ses voisins directs.
import networkx as nx
defpartition_en_etoiles():
G = G.copy()
etoiles = []
nœuds_triés = (G.nodes(), key= n: G.degree(n), reverse=)
centre nœuds_triés:
centre G:
voisins = (G.neighbors(centre))[:max_voisins]
etoile = [centre] + voisins
etoiles.append(etoile)
G.remove_node(centre)
v voisins:
v G:
G.remove_node(v)
etoiles
G = nx.complete_bipartite_graph(, )
etoiles = partition_en_etoiles(G)
()
i, etoile (etoiles):
()
G: nx.Graph, max_voisins: int = 3
"""Partitionne un graphe en sous-graphes en forme d'étoile.
Args:
G: Graphe NetworkX à partitionner.
max_voisins: Nombre maximum de voisins par étoile.
Returns:
list: Liste des étoiles (chaque étoile est une liste de nœuds).
"""
# Trier les nœuds par degré décroissant (centres prioritaires)
sorted
lambda
True
for
in
if
not
in
continue
list
# Retirer les nœuds de l'étoile du graphe restant
for
in
if
in
return
# Exemple : partition d'un graphe biparti complet
4
5
print
f"Nombre d'étoiles : {len(etoiles)}"
for
in
enumerate
print
f" Étoile {i+1} : {etoile}"
1.2 Détection de Communautés (Louvain)
L'algorithme de Louvain optimise la modularité pour trouver des communautés dans un grand graphe :
import networkx as nx
import community as community_louvain # python-louvainimport matplotlib.pyplot as plt
defdetecter_communautes(G: nx.Graph):
"""Détecte les communautés via l'algorithme de Louvain.
Args:
G: Graphe non orienté.
Returns:
dict: Mapping {nœud: id_communauté}
"""
partition = community_louvain.best_partition(G)
# Statistiques
n_communautes = len(set(partition.values()))
modularité = community_louvain.modularity(partition, G)
print(f"Nombre de communautés détectées : {n_communautes}")
print(f"Modularité : {modularité:.4f}")
for com_id inset(partition.values()):
membres = [n for n, c in partition.items() if c == com_id]
print(f" Communauté {com_id} : {len(membres)} membres")
return partition
1.3 Compression de Graphes (Perte Nulle)
L'idée du Graphitour et des méthodes de compression sans perte : réduire la taille d'un graphe tout en conservant ses propriétés structurelles (connectivité, diamètre, centralité).
defcompresser_graphe(G: nx.Graph, seuil_degre: int = 2):
"""Compresse un graphe en fusionnant les nœuds de faible degré.
Args:
G: Graphe à compresser.
seuil_degre: Degré maximum pour qu'un nœud soit fusionné.
Returns:
nx.Graph: Graphe compressé.
"""
G_comp = G.copy()
fusionne = Truewhile fusionne:
fusionne = Falsefor nœud inlist(G_comp.nodes()):
if G_comp.degree(nœud) <= seuil_degre and G_comp.degree(nœud) > 0:
voisins = list(G_comp.neighbors(nœud))
iflen(voisins) == 1:
# Fusionner avec l'unique voisin
G_comp = nx.contracted_nodes(G_comp, voisins[0], nœud,
self_loops=False)
fusionne = Truebreak# Recommencer depuis le débutreturn G_comp
# Démonstration
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 1), (3, 4), (4, 5), (5, 6), (6, 3)])
print(f"Taille originale : {G.number_of_nodes()} nœuds")
G_comp = compresser_graphe(G)
print(f"Taille compressée : {G_comp.number_of_nodes()} nœuds")
2. Flots et Couplages
2.1 Flot Maximum et Coupe Minimale
Le problème du flot maximum consiste à trouver le débit maximal pouvant circuler d'une source $s$ vers un puits $t$ dans un graphe orienté avec capacités.
import networkx as nx
defflot_maximum(G: nx.DiGraph, source: str, puits: str):
"""Calcule le flot maximum entre source et puits.
Args:
G: Graphe orienté avec attribut 'capacity' sur les arêtes.
source: Nœud source.
puits: Nœud puits.
Returns:
tuple: (valeur_du_flot, dictionnaire_de_flot)
"""
valeur_flot, dict_flot = nx.maximum_flow(G, source, puits)
print(f"Flot maximum de '{source}' à '{puits}' : {valeur_flot}")
for (u, v), flot in dict_flot.items():
if flot > 0:
capacité = G[u][v]['capacity']
print(f" {u} → {v} : {flot}/{capacité}")
return valeur_flot, dict_flot
# Exemple : réseau de distribution
G = nx.DiGraph()
G.add_edge('usine', 'entrepôt_A', capacity=20)
G.add_edge('usine', 'entrepôt_B', capacity=30)
G.add_edge('entrepôt_A', 'client_1', capacity=15)
G.add_edge('entrepôt_A', 'client_2', capacity=10)
G.add_edge('entrepôt_B', 'client_2', capacity=25)
G.add_edge('entrepôt_B', 'client_3', capacity=20)
G.add_edge('client_1', 'marché', capacity=15)
G.add_edge('client_2', 'marché', capacity=30)
G.add_edge('client_3', 'marché', capacity=20)
flot_maximum(G, 'usine', 'marché')
2.2 Couplage Maximum dans un Graphe Biparti
Le couplage (matching) trouve l'ensemble d'arêtes sans sommets communs de cardinalité maximale.
Le PageRank mesure l'importance des nœuds dans un graphe dirigé. La version personnalisée permet de biaser l'importance vers certains nœuds.
defpagerank_personnalise(G: nx.DiGraph, graines: list[str],
alpha: float = 0.85):
"""Calcule le PageRank personnalisé à partir de nœuds sources.
Args:
G: Graphe orienté.
graines: Nœuds sources (seed nodes).
alpha: Facteur d'amortissement.
Returns:
dict: Mapping {nœud: score}
"""
perso = {n: 1.0 / len(graines) if n in graines else0.0for n in G.nodes()}
pr = nx.pagerank(G, alpha=alpha, personalization=perso)
# Trier par score décroissant
classement = sorted(pr.items(), key=lambda x: -x[1])
print("Classement PageRank personnalisé :")
for nœud, score in classement[:10]:
print(f" {nœud} : {score:.4f}")
return pr
3.2 Centralité et Marches Aléatoires
defanalyser_centralites(G: nx.Graph):
"""Calcule et compare différentes mesures de centralité.
Args:
G: Graphe non orienté.
"""
centralites = {
'Degré': nx.degree_centrality(G),
'Proximité': nx.closeness_centrality(G),
'Intermédiarité': nx.betweenness_centrality(G),
'Eigenvector': nx.eigenvector_centrality(G, max_iter=1000),
}
for nom, cent in centralites.items():
top = sorted(cent.items(), key=lambda x: -x[1])[:3]
print(f"Centralité de {nom} (top 3) :")
for nœud, score in top:
print(f" {nœud} : {score:.4f}")
print()
4. Applications Multi-Agents
4.1 Planification de Chemins pour une Flotte
defplanifier_tournees(points: list[tuple[float, float]],
n_vehicules: int = 1):
"""Planification naive de tournées (Clarke-Wright simplifié).
Args:
points: Liste des points (x, y) à visiter.
n_vehicules: Nombre de véhicules disponibles.
Returns:
list: Tournées pour chaque véhicule.
"""import numpy as np
defdistance(p1, p2):
return np.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
n = len(points)
depôt = points[0]
non_visites = list(range(1, n))
tournees = [[0] for _ inrange(n_vehicules)]
while non_visites:
meilleur_gain = -float('inf')
meilleur_vehicule = 0
meilleur_point = Nonefor v inrange(n_vehicules):
dernier = points[tournees[v][-1]]
for p in non_visites:
gain = distance(dernier, depôt) - distance(dernier, points[p])
if gain > meilleur_gain:
meilleur_gain = gain
meilleur_vehicule = v
meilleur_point = p
if meilleur_point isnotNone:
tournees[meilleur_vehicule].append(meilleur_point)
non_visites.remove(meilleur_point)
else:
breakreturn tournees
# Exemple
points = [(0, 0), (1, 2), (3, 1), (4, 3), (2, 4), (5, 2)]
tournees = planifier_tournees(points, n_vehicules=2)
for i, tour inenumerate(tournees):
print(f"Véhicule {i+1} : {tour}")
4.2 Consensus Distribué sur Graphe
import numpy as np
defconsensus_distribue(adjacence: np.ndarray, valeurs_init: np.ndarray,
iterations: int = 100):
"""Algorithme de consensus distribué sur un graphe.
Chaque nœud met à jour sa valeur comme moyenne pondérée de ses voisins.
Args:
adjacence: Matrice d'adjacence (n×n).
valeurs_init: Valeurs initiales des nœuds.
iterations: Nombre d'itérations.
Returns:
np.ndarray: Évolution des valeurs (iterations × n).
"""
n = len(valeurs_init)
# Normaliser la matrice (matrice laplacienne normalisée)
degres = np.sum(adjacence, axis=1)
P = adjacence / degres[:, np.newaxis]
np.fill_diagonal(P, 1 - np.sum(P, axis=1))
valeurs = np.zeros((iterations, n))
valeurs[0] = valeurs_init
for t inrange(1, iterations):
valeurs[t] = P.T @ valeurs[t-1]
print(f"Valeurs initiales : {valeurs_init}")
print(f"Consensus atteint : {valeurs[-1, 0]:.4f} " +
f"(moyenne : {np.mean(valeurs_init):.4f})")
return valeurs
5. Pièges Courants
Piège
Symptôme
Solution
Graphe non connexe
Partitionnement impossible ou absurde
Vérifier la connexité avec nx.is_connected() ; traiter chaque composante séparément
Mauvaise modélisation des capacités
Flot maximum irréaliste
Vérifier que les capacités sont cohérentes avec la physique du problème
Oubli de l'orientation des arêtes
Dijkstra échoue sur graphe non orienté
Utiliser nx.DiGraph() pour les flux dirigés, nx.Graph() pour les réseaux sociaux
Complexité exponentielle
Algorithme ne termine pas pour n>20
Utiliser des heuristiques (recuit simulé, glouton) au lieu de l'exact
Surapprentissage du partitionnement
Communautés non pertinentes
Ajuster la résolution de Louvain ; valider avec des métriques de qualité (silhouette)
PageRank non convergent
Erreur de convergence
Vérifier que le graphe n'a pas de nœuds sans arêtes sortantes ; ajouter des téléports
Métriques de centralité abusives
Interprétation erronée des scores
Toujours comparer plusieurs mesures ; la centralité de degré n'est pas l'importance
Matrice d'adjacence non symétrique
Erreurs pour les graphes non orientés
Vérifier que adj[i][j] == adj[j][i] pour les graphes non orientés
6. Checklist d'Implémentation
Le problème est modélisé comme un graphe (nœuds, arêtes, poids).
Le type de graphe est choisi (orienté / non orienté, pondéré / non pondéré).
La bibliothèque NetworkX est installée (pip install networkx).
Les algorithmes de base sont validés sur des graphes de test simples.
Le partitionnement est évalué avec une métrique objective (modularité, silhouette).
Les flots sont vérifiés avec la conservation du débit.
Les couplages sont optimaux (vérification par enumeration pour petits cas).
La complexité algorithmique est adaptée à la taille du graphe.
Le code gère les graphes non connexes.
Les visualisations sont produites (nx.draw(), plt.savefig()).
Les résultats sont reproductibles (fixer random.seed() et np.random.seed()).
La documentation précise la signification de chaque métrique.
Références
Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
Barabási, A.-L. (2016). Network Science. Cambridge University Press.
