Cographe

Un cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud. La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles. Cette famille de graphe a été introduite par plusieurs auteurs indépendamment dans les années 1970 sous divers noms, notamment D*-graphes, hereditary Dacey graphs et 2-parity graphs. Un cographe est un graphe simple qui peut-être construit de manière récursive selon les règles suivantes : le graphe à un sommet est un cographe, le complémentaire d'un cographe est un cographe, l'union de deux cographes est un cographe. Le "join" de deux graphes disjoints et , est l'opération qui consiste à créer un nouveau graphe , où et . Cette opération est en fait le complémentaire de l'union des complémentaires. Un cographe est alors un graphe qui peut être formé à partir des graphes à un sommet, par "join" et par union. Il existe de nombreuses caractérisations des cographes, notamment : les cographes sont les graphes -free, c'est-à-dire ceux qui n'ont pas le chemin sur quatre sommets comme sous-graphe induit; les cographes sont graphes pour lesquels tous les sous-graphes induits non triviaux possèdent deux sommets ayant le même voisinage. les cographes sont les graphes d'inversions des permutations séparables. Un coarbre décrit un cographe, grâce aux opérations qui sont nécessaires pour les construire. Les feuilles représentent les nœuds du cographe, et les nœuds internes représentent des opérations. Les nœuds étiquetés par un 0 représentent l'union des cographes représentés par les sous-arbres et ceux étiquetés par un 1 représentent le "join" de ces cographes. Il existe une arête entre deux nœuds de l'arbre si et seulement si le plus petit ancêtre commun à ces nœuds est étiqueté par 1. Cette représentation est unique. C'est une manière compacte de représenter les cographes. De plus en échangeant les 1 et les 0, on obtient le coarbre du graphe complémentaire.