Partitionnement de graphe
En théorie des graphes et en algorithmique, le partitionnement de graphe est la tâche qui consiste à diviser un graphe orienté ou non orienté en plusieurs parties. Plusieurs propriétés peuvent être recherchées pour ce découpage, par exemple on peut minimiser le nombre d'arêtes liant deux parties différentes. Coupe maximum et Coupe minimum sont deux exemples communs de partitionnement de graphe.
Cet article a besoin d’être illustré ().
Pour améliorer cet article, des médias (images, animations, vidéos, sons) sous licence libre ou du domaine public sont les bienvenus.
Si vous êtes l’auteur d’un média que vous souhaitez partager, importez-le. Si vous n’êtes pas l’auteur, vous pouvez néanmoins faire une demande de libération d’image à son auteur.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Définitions modifier
Une partition d'un graphe est une partition de ses nœuds, ou plus rarement de ses arêtes[réf. nécessaire]. Si le nombre de groupes dans la partition est fixé à un entier k, on parle de k-partition. Pour k=2, on parle parfois de bisection[1].
Le partitionnement est le fait de calculer une partition. Le plus souvent le partitionnement de graphe consiste à créer une subdivision de l'ensemble des sommets de S en k sous ensembles de tailles réduites de façon à minimiser un ou plusieurs critères.
Problèmes modifier
On peut considérer plusieurs objectifs pour les partitionnements.
On cherche le plus souvent à minimiser une quantité liée à la coupe, c'est-à-dire le nombre d'arêtes dont les extrémités ne sont pas dans le même groupe, avec certaines contraintes sur les propriétés des groupes eux-mêmes. Par exemple, on peut minimiser la taille de la coupe avec la contrainte que les groupes doivent être de même taille (plus ou moins un)[1].
D'autres fonctions objectifs sont le ratio de coupe et la coupe normalisée[1].
Complexité des problèmes modifier
La plupart des problèmes de partitionnement de graphe sont NP-difficile[1], c'est pourquoi des algorithmes utilisant une heuristique ou des algorithmes d'approximations sont souvent utilisés pour résoudre des problèmes de partitionnement de graphe.
Méthodes modifier
Parmi les méthodes classiques de partitionnement, on compte les méthodes inertielles (comme k-moyennes), le partitionnement spectral et des méthodes locales d'échange de points entre clusters (dans le même esprit que heuristique de Lin-Kernighan pour le problème du voyageur de commerce)[1].
Méthodes multi-niveau modifier
Un algorithme de partitionnement multiniveau de graphe fonctionne en appliquant une ou plusieurs étapes. Chaque étape consiste à réduire la taille du graphe en détruisant des nœuds et arêtes, partitionner le graphe ainsi réduit, et en déduire une partition du graphe originel. Il existe une grande variété de méthode pour partitionner le graphe réduit et pour déduire une partition du graphe originel à partir d'une partition du graphe réduit. Le plus souvent cette technique donne des algorithmes plus rapides et plus précis (dans le cas d'algorithmes d'approximations). METIS est un logiciel commun utilisant des méthodes de partitionnement multiniveau de graphes.
Applications modifier
Les applications du partitionnement de graphe sont multiples, elles comprennent le calcul scientifique, le partitionnement de différentes étapes d'un circuit de type VLSI et la planification des tâches dans les systèmes multi-processeurs[1]. Récemment, le problème de partitionnement de graphe a gagné en importance en raison de son application pour le clustering et la détection des cliques dans les réseaux sociaux, pathologiques et biologiques.
Article lié modifier
Notes et références modifier
- Charles-Edmond Bichot, « Introduction au partitionnement de graphe », sur ENS Lyon, .
