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

Définition modifier

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

Une partition de K_4,4 en trois forêts

L'arboricité d'un arbre est un, puisqu'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

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^[3].

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.

L'arboricité est liée à d'autres paramètres de graphes, comme la dégénérescence.

Paramètres liés modifier

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é $a$ est au moins égale à $a$ , et au plus égale à $2a-1$ . 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 $G$ comme $\max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.$ En d'autres termes, l'arboricité d'un graphe est la partie entière supérieure de l'arboricité fractionnaire.

Variantes modifier

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

Utilisations modifier

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

Notes et références modifier

↑ La traduction d'arboricity par arboricité peut par exemple être trouvée dans la thèse de doctorat Pinlou 2006.
↑ Nash-Williams 1964
↑ (en) Reinhard Diestel, Graph Theory [détail des éditions], « Tree-packing and arboricity », p. 48-52.
↑ Gabow et Westermann 1992.
↑ Szekeres et Wilf 1968.
↑ Jensen et Toft 1995, p. 77f.
↑ Cette version a elle-même des variantes comme la version sans circuit décrite dans Pinlou 2006.
↑ 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, n^os 5-6,‎ 2010, p. 363-379

Bibliographie modifier

Alexandre Pinlou, Arc-coloration et sommet-coloration orientées (Thèse de doctorat), Université Bordeaux 1, 2006 (lire en ligne)
Ilan Algor et Noga Alon, « The star arboricity of graphs », Annals of Discrete Mathematics, Elsevier, vol. 43,‎ 1989, p. 11-22
C. St. J. A. Nash-Williams, « Decomposition of finite graphs into forests », Journal of the London Mathematical Society, vol. 39, n^o 1,‎ 1964 (DOI 10.1112/jlms/s1-39.1.12, MR 0161333)
H. N. Gabow et H. H. Westermann, « Forests, frames, and games: Algorithms for matroid sums and applications », Algorithmica, vol. 7, n^o 1,‎ 1992, p. 465–497 (DOI 10.1007/BF01758774, MR 1154585)
S. L. Hakimi, J. Mitchem et E. E. Schmeichel, « Star arboricity of graphs », Discrete Mathematics, vol. 149,‎ 1996, p. 93–98 (DOI 10.1016/0012-365X(94)00313-8, MR 1375101)
(en) T. R. Jensen et B. Toft, Graph Coloring Problems, New York, Wiley-Interscience, 1995, 295 p. (ISBN 0-471-02865-7, MR 1304254)
G. Szekeres et H. S. Wilf, « An inequality for the chromatic number of a graph », Journal of Combinatorial Theory,‎ 1968 (DOI 10.1016/s0021-9800(68)80081-x , MR 0218269)

Liens externes modifier

(en) Eric W. Weisstein, « Arboricity », sur MathWorld

[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] (en) Reinhard Diestel, Graph Theory [détail des éditions], « Tree-packing and arboricity », p. 48-52.

[4] Gabow et Westermann 1992.

[5] Szekeres et Wilf 1968.

[6] Jensen et Toft 1995, p. 77f.

[7] Cette version a elle-même des variantes comme la version sans circuit décrite dans Pinlou 2006.

[8] 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, n^os 5-6,‎ 2010, p. 363-379

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]