Stable maximum

Stable maximum

Le lecteur est renvoyé à l'article théorie des graphes pour une introduction aux graphes et au lexique de la théorie des graphes pour les définitions élémentaires.

Le problème du stable maximum est parfaitement équivalent à celui de la clique maximum et très proche du transversal minimum.

Définition du problème

Le problème du stable maximum se pose dans un graphe que l'on peut considérer simple puisque son éventuelle orientation ou la présence d'arêtes multiples ne jouent aucun rôle ici (on peut se débarrasser des sommets incidents aux boucles car ils n'appartiennent à aucun stable du graphe).

Soit G un graphe simple, et soit S un sous-ensemble stable de l'ensemble X des sommets de G.

  • S est maximal (par rapport à l'inclusion) s'il n'est contenu dans aucun autre ensemble stable de G. Tout stable maximal est un ensemble dominant.
  • S est de cardinalité maximum si sa cardinalité est supérieure ou égale à la cardinalité de tout autre stable de G.

Une cardinalité maximum implique maximal, mais non l'inverse. Le nombre de stabilité de G, noté α(G), est la cardinalité d'un stable maximum. Le problème du stable maximum consiste à déterminer α(G) étant donné un graphe G. Ce problème est NP-complet au sens de la théorie de la complexité.

Munissons maintenant G d'une pondération en associant à chaque sommet x de X un réel p(x) appelé le poids de x. Le poids P(Y) d'un sous-ensemble Y de X est alors égal à la somme des poids des sommets de Y.

  • S est de poids maximum si le poids de S est supérieur ou égal au poids de tout autre stable de G.

Le problème du stable maximum dans un graphe pondéré consiste à déterminer le poids maximum d'un stable de G. À moins que la fonction p ne soit positive, un stable maximum n'est pas nécessairement maximal dans les graphes pondérés.

Problèmes proches

Puisque le problème du stable maximum est NP-dur, tous les problèmes de cette classe peuvent s'exprimer comme un problème de stable maximum (et vice versa). Toutefois, certains problèmes, comme ceux que nous présentons ci-dessous, lui sont plus directement relié.

  • Problème de la clique maximum : Il s'agit de déterminer le poids maximum d'une clique de G. L'équivalence est totale, même au niveau des algorithmes d'approximation, il suffit de reformuler le problème dans le graphe complémentaire de G.
  • Problème du transerval minimum (ou encore de la couverture minimum par des sommets): Il s'agit de déterminer un transversal minimum. L'équivalence vient du fait que le complémentaire d'un transversal de G (par rapport à l'ensemble X) est un stable de G. Attention ce problème n'est pas équivalent au sens de l'approximation.

Les problèmes suivants ne nécessitent qu'une simple transformation pour être reformulés comme un problème de stable maximum:

  • Problème de la maximisation d'une fonction pseudo booléenne (par exemple la fonction  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}). L'équivalence passe par la construction d'un graphe auxiliaire. Associons à chaque monôme de la fonction un sommet du graphe, auquel on donne un poids égal au coefficient du monôme. Relions deux sommets par une arête lorsque le produit booléen des deux monômes correspondants est nul. Ainsi le maximum de la fonction est égal au poids maximum d'un stable du graphe. Avec la fonction f donnée en exemple, on obtient le graphe suivant :
ESPM equiv bool.png
Ici le stable maximum est composé des sommets 3 et 4 et a pour poids 13, le maximum de f vaut 13 (il est atteint par x1 = 0,x2 = 0,x3 = 1,x4 = 1, c'est-à-dire lorsque seul les troisième et quatrième monômes valent 1.

Référence

B Ambert et P Castéra, Réalisation d'un algorithme efficace pour la détermination en ensemble stable de poids maximal d'un graphe, Mémoire d'ingénieur de l'Institut d'Informatique d'Entreprise (IIE-CNAM), Paris 1981


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Stable maximum de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Maximum throughput scheduling — is a procedure for scheduling data packets in a packet switched best effort communications network, typically a wireless network, in view to maximize the total throughput of the network, or the system spectral efficiency in a wireless network.… …   Wikipedia

  • Stable (theorie des graphes) — Stable (théorie des graphes) Pour les articles homonymes, voir stable. L ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe. Dans la théorie des graphes, un stable – appelé aussi ensem …   Wikipédia en Français

  • Maximum time aloft — (MTA) is a type of boomerang competition involving specially engineered boomerangs. They are launched high, and enter a stable hover. In the official USBA (United States Boomerang Association) competition throwers get five throws, and the times… …   Wikipedia

  • Ensemble stable de poids maximal — Stable maximum Le lecteur est renvoyé à l article théorie des graphes pour une introduction aux graphes et à l article Lexique de la théorie des graphes pour les définitions élémentaires. Le problème du stable maximum est parfaitement équivalent… …   Wikipédia en Français

  • Maximum sustainable yield — In population ecology and economics, maximum sustainable yield or MSY is, theoretically, the largest yield (or catch) that can be taken from a species stock over an indefinite period. Fundamental to the notion of sustainable harvest, the concept… …   Wikipedia

  • Stable marriage problem — In mathematics, the stable marriage problem (SMP) is the problem of finding a stable matching mdash; a matching in which no element of the first matched set prefers an element of the second matched set that also prefers the first element.It is… …   Wikipedia

  • Maximum entropy probability distribution — In statistics and information theory, a maximum entropy probability distribution is a probability distribution whose entropy is at least as great as that of all other members of a specified class of distributions. According to the principle of… …   Wikipedia

  • Stable theory — For differential equations see Stability theory. In model theory, a complete theory is called stable if it does not have too many types. One goal of classification theory is to divide all complete theories into those whose models can be… …   Wikipedia

  • Stable (théorie des graphes) — Pour les articles homonymes, voir stable. L ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe. En théorie des graphes, un stable – appelé aussi …   Wikipédia en Français

  • Maximum magnitude — An important parameter in the calculation of seismic hazard, maximum magnitude (expressed as Moment magnitude scale) is also one of the more contentious. The choice of the value can greatly influence the final outcome of the results, yet this is… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”