Gráf erőssége

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.

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.

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 $\mathrm{\Pi }$ $V$ összes felbontásának a halmaza, $\partial \pi$ pedig a $\pi \in \mathrm{\Pi }$ partíció halmazai között húzódó élek halmaza, ekkor $\sigma (G)=\underset{\pi \in \mathrm{\Pi }}{\min }\frac{|\partial \pi |}{|\pi |-1}$.
• Illetve, ha $𝒯$ G összes feszítőfájának halmaza, akkor

$\sigma (G)=\max \{\sum _{T\in 𝒯}{\lambda }_T:\mathrm{\forall }T\in 𝒯{\lambda }_T\ge 0\text{ és }\mathrm{\forall }e\in E\sum _{T\ni e}{\lambda }_T\le 1\}.$

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

$\sigma (G)=\min \{\sum _{e\in E}{y}_e:\mathrm{\forall }e\in E{y}_e\ge 0\text{ és }\mathrm{\forall }T\in 𝒯\sum _{e\in E}{y}_e\ge 1\}.$

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)\ge \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

• Sablon:Fordítás

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,Sablon:Halott link, Cybernetics and Systems Analysis, 29:379–384, 1993.
• Jérôme Galtier: New algorithms to compute the strength of a graph