Ê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
Largeur de clique
Résumé
vignette|upright=1.6|Construction d'un graphe (ici un graphe à distance héréditaire) de largeur de clique 3 par une succession d'unions disjointes, de renommages et de fusions d'étiquettes. Les étiquettes des sommets sont affichées sous forme de couleurs.
En théorie des graphes, la largeur de clique d'un graphe est l'un des paramètres qui décrit la complexité structurelle du graphe ; il est étroitement lié à largeur arborescente, mais contrairement à celle-ci, elle peut être bornée même pour des graphes denses .
La largeur de clique d'un graphe est le nombre minimum d'étiquettes nécessaires pour construire au moyen des 4 opérations suivantes :
Création d'un nouveau sommet v d'étiquette i (noté i(v) ou )
Union disjointe de deux graphes étiquetés G et H (notée )
Jonction par une arête de chaque sommet étiqueté i à chaque sommet étiqueté j (noté η(i,j)), où
Renommage de l'étiquette i en étiquette j (notée ρ (i, j) ou ).
Dans l’exemple, le graphe final est obtenu par la jonction des trois sommets rouges et des deux sommets verts ; le graphe précédent est l’union disjointe des eux graphes bleu-rouge et vert-bleu, etc. La suite des graphes construits par les opérations est figurée dans l'arbre des opérations.
Les graphes de largeur de clique bornée comprennent les cographes et les graphes à distance héréditaire. Il est NP-difficile de calculer la largeur de clique lorsqu'elle n'est pas bornée, et il est inconnu si elle peut être calculée en temps polynomial lorsqu'elle est bornée ; des algorithmes d'approximation efficaces pour la largeur de clique existent. Sur la base de ces algorithmes et du théorème de Courcelle, de nombreux problèmes d'optimisation de graphes qui sont NP-difficiles pour des graphes arbitraires peuvent être résolus ou approximés rapidement sur les graphes de largeur de clique bornée.
Les séquences de construction sous-jacentes au concept de largeur de clique ont été formulées par Courcelle, Engelfriet et Rozenberg en 1990 et par Wanke en 1994. Le nom de largeur de clique ("clique-width") a été utilisé pour un concept différent par Chlebíková en 1992 .
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.