Force d'un graphe

Force d'un graphe (exemple)

Un graphe de force 2 : le graphe est décomposé en trois parties avec un total de 4 arêtes entre les composantes, ce qui donne le rapport 4/(3-1)=2.

En théorie des graphes, la force d'un graphe (strength en anglais) non orienté est le plus petit rapport entre le nombre d'arêtes supprimées et le nombre de composantes créées dans une décomposition du graphe.

Définition

Soit $G=(V,E)$ un graphe non orienté. Soit ${\cal {P}}$ l'ensemble des partitions de $V$, et, pour toute partition $P\in {\cal {P}}$, soit $\delta (P)$ l'ensemble des arêtes qui relient des parties de la partition $P$. La force $\sigma (G)$ est :

$\sigma (G)=\min _{P\in {\cal {P}}}{\frac {|\delta (P)|}{|P|-1}}$ .

Pour une partition $P$ des sommets, $\delta (P)$ est l'ensemble de toutes les arêtes reliant des parties de la partition. Pour qu'il y ait une arête au moins entre deux des $|\delta (P)|$ composantes, on doit choisir $|\delta (P)|-1$ arêtes de façon appropriée ; la force est le plus petit rapport des deux entiers.

Par formulation en programmation linéaire, on a des définitions équivalentes : Soit ${\mathcal {T}}$ l'ensemble des arbres couvrant de G. Alors

$\sigma (G)=\max \sum _{T\in {\mathcal {T}}}\lambda _{T}\quad$ avec les contraintes : $\ \lambda _{T}\geq 0\$ et $\ \sum _{T\ni e}\lambda _{T}\leq 1$.

ou, par dualité en programmation linéaire :

$\sigma (G)=\min \sum _{e\in E}y_{e}\quad$ avec les contraintes : $\ y_{e}\geq 0\$ et $\ \sum _{e\in E}y_{e}\geq 1$.

Complexité du calcul

Le calcul de la force d'un graphe peut être fait en temps polynomial ; le premier algorithme de ce type a été décrit par Cunningham en 1985. L'algorithme avec la meilleure complexité est dû à Trubin (1993) ; en utilisant la décomposition des flots de Goldberg et Rao (1998), il est en complexité en temps $O(\min(m^{1/2},n^{2/3})mn\log(n^{2}/m+2))$ pour un graphe à n sommets et m arêtes.

Propriétés

• Soit $G=(V,E)$ un graphe non orienté et soit $k$ un entier positif. La taille maximale d'une union de $k$ forêts est égale à la plus petite valeur de

$|\delta (P)|+k(|V|-|P|)$

prise sur toutes les partitions $P$ de $V$.

• Si $P=\{V_{1},\dots ,V_{k}\}$ est une partition qui maximise $\sigma (G)$, et si $G_{i}=G|V_{i}$ est la restriction de G à l'ensemble $V_{i}$, alors $\sigma (G_{k})\geq \sigma (G)$ .
• Théorème de Tutte-Nash-Williams. — Un graphe $G=(V,E)$ contient k arbres couvrants à arêtes disjointes si et seulement si

$|\delta (P)|\geq k(|P|-1)$

pour toute partition $P$ de $V$.

• Le théorème de Tutte-Nash-Williams s'exprime avec la notion de force : $\lfloor \sigma (G)\rfloor$ est le nombre maximum d'arbres couvrant à arêtes disjointes qui peuvent être contenus dans G.
• Contrairement au problème de partitionnement d'un graphe, les partitions produites par le calcul de la force ne sont pas nécessairement équilibrées (c'est-à-dire ne sont pas de taille presque égale).

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Strength of a graph » (voir la liste des auteurs).

Bibliographie

• Alexander Schrijver, Combinatorial Optimization, Springer, 2003 (ISBN 978-3-540-44389-6),   Chapitre 51.
• William H. Cunningham, « Optimal attack and reinforcement of a network », Journal of the ACM, vol. 32, n^o 3,‎ 1985, p. 549–561 (DOI 10.1145/3828.3829)
• V. A. Trubin, « Strength of a graph and packing of trees and branchings », Cybernetics and Systems Analysis, vol. 29, n^o 3,‎ 1993, p. 379–384 (DOI 10.1007/BF01125543)
• Andrew V. Goldberg et Satish Rao, « Beyond the flow decomposition barrier », Journal of the ACM, vol. 45, n^o 5,‎ 1998, p. 783-797 (DOI 10.1145/290179.290181)

Articles connexes

• Dureté d'un graphe, un concept analogue pour les suppressions de sommets
• Théorème de Nash-Williams (en)
• Lexique de la théorie des graphes