Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Cographe
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.