Sous-graphe

Dénombrements et probabilités -- Théorie des graphes

  Si G est un graphe dont les sommets sont l'ensemble S et les arêtes sont l'ensemble A, et si S' est une partie de S, on appelle sous-graphe de S formé à partir de S' le graphe dont les sommets sont les éléments de S' et les arêtes sont les éléments de A reliant deux sommets de S'. Par exemple, dans l'exemple suivant, on a tracé un graphe et sous-graphe formé à partir des sommets A,B,C,D :
  Un sous-graphe est dit stable s'il ne comporte aucune arête. Colorier un graphe revient à chercher des sous-graphes stables dans un graphe.

Version imprimable


Pour signaler une erreur, proposer une amélioration, contacter les auteurs, écrivez à
La BibM@th 2000-2013 - V&F Bayart