Arboricité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, l'arboricité (arboricity en anglais) d'un graphe non orienté est le nombre minimum de forêt 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é.

Définition[modifier | modifier le code]

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.

Exemple[modifier | modifier le code]

Une partition de K4,4 en trois forêts

L'arboricité d'un arbre est un, puisque il suffit d'un arbre pour le couvrir : lui-même.

La biclique à quatre sommets K_{4,4} 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.

Propriétés[modifier | modifier le code]

Crispin Nash-Williams a prouvé la propriété suivante[2] : en notant a(G) l'arboricité d'un graphe G, V(H) et E(H) les nombres de nœuds et d'arêtes d'un sous-graphe H, on a : a(G)=\max_{H \subseteq G} \frac{E(H)}{V(H)-1}.

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.

Cette expression permet de borner l'arboricité des graphes planaires, en effet ceux-ci ont au plus 3V(G)-6 arêtes, donc une arboricité bornée par 3.

Variantes[modifier | modifier le code]

Parmi les variantes de cette notion, on peut citer l'étoile arboricité dirigée, introduite par (Algor et Alon 1989)[3].

Utilisations[modifier | modifier le code]

Pour certains problèmes algorithmique, faire l'hypothèse d'une arboricité bornée permet d'avoir de meilleurs résultats, c'est la cas par exemple en coloration de graphe distribuée[4].

Notes et références[modifier | modifier le code]

  1. La traduction d'arboricity par arboricité peut par exemple être trouvée dans la thèse de doctorat Pinlou 2006.
  2. Nash-Williams 1964
  3. Cette version a elle-même des variantes comme la version acircuitique décrite dans Pinlou 2006.
  4. Voir par exemple l'article : Leonid Barenboim et Michael Elkin, « Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition », Distributed Computing, vol. 22, no 5-6,‎ 2010, p. 363-379

Bibliographie[modifier | modifier le code]

  • Alexandre Pinlou, Arc-coloration et sommet-coloration orientées, Université Bordeaux 1 (Thèse de doctorat),‎ 2006 (lire en ligne)
  • Ilan Algor et Noga Alon, « The star arboricity of graphs », Annals of Discrete Mathematics, Elsevier, vol. 43,‎ 1989

Liens externes[modifier | modifier le code]