Définitions et problèmes sur les stables
Définition : Points adjacents
Dans un graphe G=(X,E), deux points sont adjacents, s'il existe une arête dont les points sont les deux extrémités.
Définition : Stable
Dans un graphe G=(X,E), un sous-ensemble S de points de X est un stable si ses points ne sont pas adjacents entre eux.
On s'intéresse aux stables lorsque l'on cherche des sous-ensembles d'objets deux à deux compatibles, sachant que le graphe G représente alors l'incompatibilité entre les objets.
Définition : Stable maximum
Dans un graphe G=(X,E), un sous-ensemble stable S est maximum si sa cardinalité est maximale.
Définition : Stable maximal
Dans un graphe G=(X,E), un sous-ensemble stable S n'est pas maximal s'il est inclus strictement dans un autre stable.
Un stable est donc maximal au sens de l'inclusion des ensembles.
Un stable maximum est obligatoirement maximal.
Un stable maximal n'est pas forcément maximum.
Cliquer pour choisir entre les petits et les grands graphes et cliquer sur Précédent ou Suivant pour faire tourner les exemples.
Le stable de gauche qui contient le point 1 est toujours maximal. Les autres ne sont pas forcément maximaux puisque l'on interdit des points.
Cliquez sur Anim pour démarrer l'animation. Choisissez un graphe à l'aide des touches Précédent, Suivant ou Aléatoire. Cliquez sur les points du graphe pour les faire passer de la couleur noir à la couleur rouge. Cliquez sur OK pour vérifier si les points rouges sélectionnés forment bien un stable et si ce stable est ou non maximal. Toute erreur vous est en outre signalée.
