Loading AI tools
En théorie des graphes, l'arboricité (arboricity en anglais) d'un graphe non orienté est le nombre minimum de forêts nécessaires pour couvrir toutes les arêtes. Il en existe plusieurs variantes avec des couvertures par des arbres particuliers, comme les étoiles.
C'est une mesure de la densité d'un graphe : une grande arboricité correspond à un graphe dense alors qu'une faible arboricité correspond à un graphe assez proche d'un arbre donc de faible densité.
On peut toujours décomposer un graphe en une union de forêts dont les arêtes sont disjointes (par exemple chaque arête est une des forêts). L'arboricité d'un graphe G[1] est le nombre minimum de forêts nécessaire pour couvrir les arêtes de G.
L'arboricité d'un arbre est un, puisqu'il suffit d'un arbre pour le couvrir : lui-même.
La biclique à quatre sommets est d'arboricité 3. Le dessin ci-contre montre une décomposition en trois forêts, et on peut montrer que c'est le minimum.
Crispin Nash-Williams a prouvé la propriété suivante[2] : en notant l'arboricité d'un graphe , et les nombres de nœuds et d'arêtes d'un sous-graphe , on a : .
Ainsi un graphe ayant, même localement, un grand nombre d'arêtes par rapport à son nombre de nœuds, aura une grande arboricité, en ce sens l'arboricité est une mesure de la densité du graphe[3].
Cette expression permet de borner l'arboricité des graphes planaires, en effet ceux-ci ont au plus arêtes, donc une arboricité bornée par 3.
L'arboricité est liée à d'autres paramètres de graphes, comme la dégénérescence.
L'anarboricité d'un graphe est le nombre maximum de sous-graphes non acycliques à arêtes disjointes dans lesquels les arêtes du graphe peuvent être partitionnées.
L'arboricité en étoile d'un graphe est la taille minimale d'une forêt dont chaque arbre est une étoile (un arbre avec au plus un nœud qui n'est pas une feuille), dans laquelle les arêtes du graphe peuvent être partitionnées. Si un arbre n'est pas lui-même une étoile, son arboricité est de deux, comme on peut le voir en partitionnant les arêtes en deux sous-ensembles à des distances impaires et paires de la racine de l'arbre, respectivement. Par conséquent, l'arboricité en étoile de tout graphe est au moins égale à son arboricité, et au plus égale à deux fois son arboricité.
L'arboricité linéaire d'un graphe est le nombre minimum de forêts linéaires (une collection de chemins) dans lesquelles les arêtes du graphe peuvent être partitionnées. L'arboricité linéaire d'un graphe est étroitement liée à son degré maximum.
La pseudo-arboricité (en) d'un graphe le nombre minimum de pseudo-forêts dans lesquelles ses arêtes peuvent être partitionnées. De manière équivalente, il s'agit du rapport maximal entre les arêtes et les sommets dans tout sous-graphe du graphe, arrondi à un nombre entier. Comme pour l'arboricité, la pseudo-arboricité a une structure matroïde qui permet de la calculer efficacement[4].
L'épaisseur (en) d'un graphe est le nombre minimum de sous-graphes planaires dans lesquels ses arêtes peuvent être partitionnées. Comme tout graphe planaire a une arboricité au plus trois, l'épaisseur de tout graphe est au moins égale à un tiers de l'arboricité, et au plus égale à l'arboricité.
La dégénérescence d'un graphe est le maximum, sur tous les sous-graphes induits du graphe, du degré minimum d'un sommet dans le sous-graphe. La dégénérescence d'un graphe d'arboricité est au moins égale à , et au plus égale à . Le nombre de coloration d'un graphe, aussi appelé son nombre de Szekeres-Wilf[5] est toujours égal à sa dégénérescence plus 1 [6].
La force d'un graphe est une valeur fractionnaire dont la partie entière donne le nombre maximum d'arbres couvrants disjoints que l'on peut obtenir dans un graphe. C'est le problème d'empaquetage (packing problem) qui est dual au problème de recouvrement soulevé par l'arboricité. Les deux paramètres ont été étudiés ensemble par Tutte et Nash-Williams.
L'arboricité fractionnaire est un raffinement de l'arboricité ; elle est définie pour un graphe comme En d'autres termes, l'arboricité d'un graphe est la partie entière supérieure de l'arboricité fractionnaire.
Parmi les variantes de cette notion, on peut citer l'arboricité en étoile dirigée, introduite par Algor et Alon 1989[7].
Pour certains problèmes algorithmiques, faire l'hypothèse d'une arboricité bornée permet d'avoir de meilleurs résultats, c'est le cas par exemple en coloration de graphe distribuée[8].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
