Force d'un graphe

Modèle:Infobox Graphe 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 $𝒫$ l'ensemble des partitions de $V$, et, pour toute partition $P\in 𝒫$, soit $\delta (P)$ l'ensemble des arêtes qui relient des parties de la partition $P$. La force $\sigma (G)$ est :

$\sigma (G)=\underset{P\in 𝒫}{\min }\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 $𝒯$ l'ensemble des arbres couvrant de G. Alors

$\sigma (G)=\max \sum _{T\in 𝒯}{\lambda }_T$ avec les contraintes : ${\lambda }_T\ge 0$ et $\sum _{T\ni e}{\lambda }_T\le 1$.

ou, par dualité en programmation linéaire :

$\sigma (G)=\min \sum _{e\in E}{y}_e$ avec les contraintes : $y_e\ge 0$ et $\sum _{e\in E}{y}_e\ge 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)Modèle:Sfn, 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$Modèle:Sfn.

• 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)\ge \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)|\ge k(|P|-1)$

pour toute partition $P$ de $V$.Modèle:Sfn

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

Bibliographie

• Modèle:Ouvrage.
• Modèle:Article
• Modèle:Article
• Modèle:Article

Articles connexes

• Dureté d'un graphe, un concept analogue pour les suppressions de sommets
• Modèle:Lien
• Lexique de la théorie des graphes