next up previous
suivant: Connexité, forte connexité monter: Sous graphes, graphes partiels précédent: Définitions générales

Cliques, Stables, Coloration

Deux sous graphes particuliers ont une importance toute particulière dans le monde de la théorie des graphes : les cliques et les stables. Comme nous allons le voir immédiatement, ces deux notions sont totalement opposées.
\begin{defi}[Clique]
On appelle \emph{clique} sur un graphe $G$\ tout sous graphe complet.
\end{defi}

\begin{defi}[Stable]
Un \emph{stable} sur un graphe $G$\ est un sous graphe sans arc.
\end{defi}
Remarque : Un sommet isolé est à la fois une clique et un stable. Par extension, l'ensemble des sommets d'un stable (respectivement une clique) de $ G$ sera nommé un stable (respectivement, une clique).
\begin{defi}[Coloration]
On appelle \emph{Coloration} une partition en stables d'un graphe.
\end{defi}
Cette dernière notation est lié au problème classique de coloration d'une carte. Soit une carte géographique représentant plusieurs pays. On souhaite colorier chaque pays de manière à ce qu'il n'ait pas la même couleur que chacun de ses voisins. Ce problème peut être résolu en cherchant une partition en stables du graphe obtenu en associant chaque pays à un sommet et chaque arc à une frontière commune entre 2 pays. Il suffit alors d'associer une couleur à chaque stable obtenu. Remarque : on essaye le plus souvent de déterminer le nombre minimal de couleurs nécessaires. Il a été démontré que l'on peut toujours colorier un graphe planaire avec, au plus, 3 couleurs.
next up previous
suivant: Connexité, forte connexité monter: Sous graphes, graphes partiels précédent: Définitions générales
Bruno Garcia 2000-12-17