Problème du sandwich de graphes
From Wikipedia, the free encyclopedia
En théorie des graphes et en informatique, le problème du sandwich de graphes est le problème consistant à trouver un graphe qui appartient à une famille particulière de graphes et qui est "pris en sandwich" entre deux autres graphes, dont l'un doit être un sous-graphe et l'autre doit être un « supergraphe »[1] du graphe considéré[2].
Les problèmes de sandwich de graphes généralisent le problème de tester si un graphe donné appartient à une famille de graphes ; ils ont attiré l'attention en raison de leurs applications et en tant que généralisation naturelle des problèmes de reconnaissance[2].
Étant donné un ensemble de sommets , un ensemble d'arêtes et un autre ensemble d'arêtes plus grand , un graphe est appelé un graphe sandwich pour la paire et si .
Formellement, le problème du sandwich de graphe pour la propriété Π est défini comme suit :
- instance : un ensemble de sommets et deux ensembles d'arêtes ;
- question : existe-t-il un graphe tel que et qui vérifie la propriété Π ?
Le problème de reconnaissance pour une classe de graphes qui satisfont à une propriété Π est équivalent au problème particulier du sandwich de graphes où , c'est-à-dire qu'il n'y a pas d'arêtes facultatives.
