Concept

Dégénérescence (théorie des graphes)

En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d'un graphe est le plus petit k tel qu'il est k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets (appelé ordre de dégénérescence) tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. On parle alors parfois de nombre de marquage. Il est possible de calculer l'ordre de dégénérescence en temps linéaire. L'algorithme consiste à retirer itérativement les nœuds de plus faible degré, en maintenant à jour une file de paquets indexés par leur degré courant. Les composantes connexes obtenues lorsque tous les sommets de degré inférieur à k ont été retirés sont appelés k-cœur du graphe, et la dégénérescence k est alors donnée par la plus grande valeur k associée à un k-cœur non-vide. La dégénérescence est une mesure de la non-densité du graphe (c'est-à-dire d'à quel point le graphe est creux). On l'utilise notamment dans les problèmes de coloration de graphes. vignette|400px|Un graphe 2-dégénéré. Historiquement, la première définition proposée (sous le nom de coloring number) est due à Paul Erdős et András Hajnal en 1966. Elle dit qu'un graphe a un coloring number de k s'il existe un ordre sur les sommets tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. Don Lick et Arthur White proposent une définition équivalente (en employant le terme de k-degenerate graph) en 1970: un graphe est dit k-dégénéré si tout sous-graphe induit contient un nœud de degré inférieur ou égal à k. On appelle dégénérescence d'un graphe le plus petit entier k tel que le graphe est k-dégénéré. En français, on emploie également les terme nombre de marquage. En anglais, les termes degeneracy et coloring number sont tous deux employés. Il ne faut pas confondre le coloring number avec le chromatic number (ou nombre chromatique).

À 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.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.