Stable d'un graphe
Un stable, ou ensemble indépendant, d'un graphe $G$ (orienté ou non) est un ensemble de sommets $S$ de $G$ tel que pour tout couple de sommets distincts $(u,v)$ de $S$, il n'existe pas d'arête reliant $u$ et $v$. Autrement dit, un ensemble indépendant de $G$ est un ensemble de sommets de $G$ deux à deux non-adjacents.
Les trois propriétés suivantes sont caractéristiques d'un ensemble indépendant :
- Le sous-graphe de $G$ induit par $S$ est un graphe nul ;
- Chaque arête de $G$ a au plus une extrémité dans $S$ ;
- $S$ est une clique dans le graphe complémentaire de $G$.
La taille d'un ensemble indépendant est le nombre de sommets qu'il contient.
Un ensemble indépendant est dit maximal s'il n'est pas inclus dans un ensemble indépendant strictement plus grand, et il est dit maximum s'il n'existe pas d'ensemble indépendant strictement plus grand dans le graphe. En particulier, un ensemble indépendant maximum est toujours maximal.