Force d'un graphe

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

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

Pour une partition ${\displaystyle P}$ des sommets, ${\displaystyle \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 ${\displaystyle |\delta (P)|}$ composantes, on doit choisir ${\displaystyle |\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 ${\displaystyle {\mathcal {T}}}$ l'ensemble des arbres couvrant de G. Alors

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

ou, par dualité en programmation linéaire :

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

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[1] en 1985. L'algorithme avec la meilleure complexité est dû à Trubin (1993) ; en utilisant la décomposition des flots de Goldberg et Rao (1998)[2], il est en complexité en temps ${\displaystyle O(\min(m^{1/2},n^{2/3})mn\log(n^{2}/m+2))}$ pour un graphe à n sommets et m arêtes.

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

${\displaystyle |\delta (P)|+k(|V|-|P|)}$

prise sur toutes les partitions ${\displaystyle P}$ de ${\displaystyle V}$[3].

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

${\displaystyle |\delta (P)|\geq k(|P|-1)}$

pour toute partition ${\displaystyle P}$ de ${\displaystyle V}$.[4]

• Le théorème de Tutte-Nash-Williams s'exprime avec la notion de force : ${\displaystyle \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).

• (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).

• 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)

• 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