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.

modifier

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 ${\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}$.

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

Propriétés

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

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

1. (en) William H. Cunningham, « Optimal attack and reinforcement of a network », Journal of the ACM, vol. 32, n^o 3,‎ juillet 1985, p. 549–561 (ISSN 0004-5411 et 1557-735X, DOI 10.1145/3828.3829, lire en ligne, consulté le 10 mars 2021)
2. Goldberg et Rao 1998.
3. Shrijver 2003, (Theorem 51.1).
4. Shrijver 2003, (Corollary 51.1a).

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