Arboricité

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 GLa traduction darboricity par arboricité peut par exemple être trouvée dans la thèse de doctorat . 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 : 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. 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. Lanarboricité 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. Larboricité 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.