Un ensemble stable est un ensemble de sommets non reliés 2 à 2.

 

Le nombre de stabilité d'un graphe, noté α, sera le cardinal (nombre d'éléments) maximum d'un ensemble stable.

 

Combien peut-on choisir de sommets, au maximum, qui ne soient pas adjacents ?

 

 

On ne peut pas trouver 5 sommets qui ne soient pas reliés par des arcs.

 

On peut en trouver 4 (ceux en bleu).

 

Le nombre de stabilité de ce graphe est donc égal à 4.

 

 

Un ensemble absorbant est un ensemble de sommets du graphe tel que tous les autres sommets du graphe soient adjacents à au moins l'un d'entre eux.

 

Le nombre d'absorption, noté β, sera le cardinal minimal d'un ensemble absorbant.

 

Combien de sommets, au minimum pour contrôler tous les sommets ?

 

On ne peut pas "controler" tous les sommets du graphe à partir de l'un d'entre eux.

 

Avec les 2 sommets en bleu, on peut le faire.

 

Tout sommet du graphe est adjacent de l'un des deux bleus.

 

Le nombre d'absorption de ce graphe est donc égal à deux.

 

Stabilité et absorption sont des notions duales

 

Un ensemble, à la fois stable et absorbant est appelé un noyau.

 

La notion de noyau joue un rôle important dans la définition de stratégies gagnantes dans des jeux comme, par exemple, celui dit de Marienbad, de Nim ou Fan-Tan.

 

Une stratégie gagnante consite à toujours laisser l'adversaire dans une position appartenant au noyau : il devra forcément en sortir et vous pourrez toujours y revenir.