Ensemble stable de poids maximal
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Définition du problème

Dans un graphe non orienté sans boucle ni arête multiple (cf. définitions dans théorie des graphes), noté G = (X, V), on recherche un ensemble stable de poids maximal (noté ESPM).

Un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être...) S inclus dans X est dit stable si et seulement si deux sommets distincts de S ne sont pas adjacents, c’est-à-dire, Γ(G) étant l'ensemble des sommets adjacents aux éléments de S, si et seulement si Γ(G) ∩ S = ∅.

  • Un ensemble stable de G est maximal si et seulement s'il n'est contenu dans aucun autre ensemble stable de G.
  • On associe à chaque sommet x de X un poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la Terre sur un corps massique en raison uniquement du...) positif ou nul noté p(x) et on définit alors le poids P(S) d'un ensemble stable S par : P(S) = \sum_{x \in S} p(x).

Le problème de l'ESPM consiste à déterminer dans G un ensemble stable S0 tel que P(S_0) = \max_{S \in S_G} P(S).

On notera qu'il existe un problème voisin qui est celui de l'ensemble stable de cardinal maximal (ESCM), qui se définit par :

  • Soit SG la famille des ensembles stables de G, le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de stabilité est : \alpha (G)\, = \max_{S \in S_G} |S|.
  • Le problème de l'ESCM consiste à déterminer dans G un ensemble stable de cardinal α(G). Il s'agit d'un cas particulier d'ESPM où les poids sont égaux à 1.
  • Le problème de l'ESPM, tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) comme celui de l'ESCM, est NP-complet au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution...) de la théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un problème peut...).

Problèmes directement équivalents

  • Une clique ( En théorie des graphes, dans les ouvrages de référence, une clique est un ensemble de sommets deux-à-deux adjacents. Dans les armées, une clique désigne également une fanfare ou une musique militaire. Dans un régiment,...) de G est un ensemble de sommets C \subset X, deux à deux adjacents, le graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) complémentaire de G est le graphe G' = (X,V') dont l'ensemble V' vérifie: (x,y) \in V' \equiv (x,y) \notin V.
  • Un support de G est un ensemble de sommets T \subset X contenant au moins une extrémité de chaque arête de G.
  • Un ESPM de G est une clique de poids maximal de G', T est un support de poids minimal si et seulement si XT est un ESPM.

Autres problèmes équivalents

La recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également le cadre...) d'un ESPM dans un graphe permet la résolution des problèmes de maximisation de fonction pseudo-booléennes et de partitionnement.

  • Étant donné une fonction pseudo booléenne f, on va construire un graphe en associant à chaque monôme (À la fin XIXe siècle, le monôme était une manifestation étudiante sous la forme d'un cortège ou d'une procession en file indienne. Il est généralement effectué la main sur l'épaule et rythmé par des chants. Il est toujours en...) un sommet du graphe en construction, de poids valant le coefficient (En mathématiques un coefficient est un facteur multiplicatif qui dépend d'un certain objet, comme une variable (par exemple, les coefficients d'un polynôme), un espace vectoriel,...) dudit monôme. Une arête est générée entre deux sommets lorsque le produit booléen (Un booléen en logique et en programmation informatique est un type de variable à deux états. Les variables de ce type sont ainsi soit à l'état vrai soit à l'état faux (en anglais true et...) des monômes est nul. Ainsi le maximum de la fonction est égal au poids de l'ESPM du graphe.
Exemple :
Soit f(x_1,x_2,x_3) =  3 x_1\overline{x_2} + 4 x_1\overline{x_2}x_3 + 6 x_1\overline{x_3}+ 7 x_2\overline{x_3}
Le graphe généré est le suivant :

ESPM equiv bool.png

L'ESPM (3,4) a pour poids 13, le maximum de la fonction vaut 13.
  • Problème de partitionnement.
Exemple :
Chercher le minimum de 2x1 + 3x2 + 7x3 + 4x4 + 8x5 avec les contraintes :
  • x4 + x5 = 1
  • x2 + x3 + x4 = 1
  • x3 + x4 = 1
  • x1 + x2 + x4 = 1
Le graphe généré est le suivant :

ESPM equiv parti.png

L'ESPM trouvé est (1, 3, 5).
La solution est
  • x1 = 1
  • x2 = 0
  • x3 = 1
  • x4 = 0
  • x5 = 0
Page générée en 0.076 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique