Gráf erőssége

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf erőssége (strength) a gráf (hálózat) támadásnak való ellenállásának W. H. Cunningham által bevezetett mértéke. A gráf erőssége megegyezik a gráf összes lehetséges felbontása közül a minimális „eltávolított élek/létrejött komponensek” aránynak.

Ennek a gráfnak az erőssége 2: az ábrán a gráf három komponensre van osztva, melyeket 4 él köt össze, ami a 4/(3-1)=2 arányt adja ki.

Felhasználható egy csúcshalmazban az élek magas koncentrációját tartalmazó zónák felderítésére. Analóg fogalom az élek helyett csúcsok eltávolításával definiált szívósság (graph toughness).

Definíciók

Egy irányítatlan, egyszerű G = (V, E) gráf erőssége, $\sigma (G)$ a következő három definícióval adható meg:

• Legyen $\Pi$ $V$ összes felbontásának a halmaza, $\partial \pi$ pedig a $\pi \in \Pi$ partíció halmazai között húzódó élek halmaza, ekkor $\displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1}}$.
• Illetve, ha ${\mathcal {T}}$ G összes feszítőfájának halmaza, akkor

$\sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T}}\ \lambda _{T}\geq 0{\mbox{ és }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.$

• És a lineáris programozási dualitás miatt:

$\sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geq 0{\mbox{ és }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.$

Számítási bonyolultság

Egy gráf erőssége polinom időben kiszámítható, az első ilyen algoritmust Cunningham (1985) írta le. Az eddigi legjobb, az erősség pontos értékét meghatározó algoritmus Trubin (1993) műve, ami Goldberg and Rao (1998) hálózati folyam-felbontásán alapul, futási ideje $O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))$.

Tulajdonságai

• Ha $\pi =\{V_{1},\dots ,V_{k}\}$ a gráf egy maximális tulajdonságú felbontása, és valamely $i\in \{1,\dots ,k\}$-re a $G_{i}=G/V_{i}$ a G korlátozása a $V_{i}$ csúcshalmazra, akkor $\sigma (G_{k})\geq \sigma (G)$.
• A Tutte–Nash-Williams-tétel: $\lfloor \sigma (G)\rfloor$ a G éldiszjunkt feszítőfáinak maximális száma.
• A gráffelbontási problémával ellentétben a gráf erősségének kiszámításakor kimenetként jelentkező felbontások nem feltétlenül kiegyensúlyozottak (tehát kb. azonos méretűek)

Fordítás

• Ez a szócikk részben vagy egészben a Strength of a graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• W. H. Cunningham. Optimal attack and reinforcement of a network, J of ACM, 32:549–561, 1985.
• A. Schrijver. Chapter 51. Combinatorial Optimization, Springer, 2003.
• V. A. Trubin. Strength of a graph and packing of trees and branchings,, Cybernetics and Systems Analysis, 29:379–384, 1993.
• Jérôme Galtier: New algorithms to compute the strength of a graph