Grafikon teljesítménye

Az irányítatlan gráf kardinalitása egy gráfkarakterisztika , amely megegyezik a gráfból eltávolított élek számának és az ilyen eltávolítás eredményeként kapott komponensek számának minimális arányával (1-gyel csökkentve). Ez a módszer lehetővé teszi a nagy élkoncentrációjú területek azonosítását. A gráf számossága hasonló a gráf merevség fogalmához , amelyet azonban a csúcsok, nem pedig az élek eltávolításának eljárása határoz meg.

Definíciók

Egy irányítatlan egyszerű gráf kardinalitása három egyenértékű módon határozható meg: $\sigma (G)$ $G=(V,E)$

Legyen a halmaz összes partíciójának halmaza . Felosztásnál jelölje a különböző komponensekből származó csúcsokat összekötő élek halmazát . Akkor . $\Pi$ $V$ $\pi \in \Pi$ $\partial \pi$ $\pi$ $\displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1))$
Legyen a gráf összes feszítőfájának halmaza . Akkor ${\mathcal {T}}$ $G$

\sigma (G)=\max \left\{\sum _{T\in {\mathcal {T))}\lambda _{T}\ :\ \forall T\in {\mathcal {T} }\ \lambda _{T}\geqslant 0;\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leqslant 1\right\}.

A lineáris programozás kettőssége szerint

\sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geqslant 0;\forall T\ in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geqslant 1\right\}.

Nehézség

A gráf számosságának kiszámítása polinomiális időben is elvégezhető. Az első polinomiális algoritmust Cunningham (1985) fedezte fel. A teljesítmény legjobb bonyolultságú kiszámítására szolgáló algoritmus Trubin (1993) alapján Goldberg és Rao (1998) áramlási dekompozícióját használja, és időben fut . $O(\min({\sqrt {m)),n^{2/3})mn\log(n^{2}/m+2))$

Tulajdonságok

Ha egy aránymaximalizáló partíció és for a G gráf korlátozása a halmazra , akkor . $\pi =\{V_{1},\dots ,V_{k}\}$ $i\in \{1,\dots ,k\}$ $G_{i}=G/V_{i}$ $V_i$ $\sigma (G_{k})\geqslant \sigma (G)$
A Tutt-Nash-Williams tétel: a G -ben tartalmazható él-diszjunkt átívelő fák maximális száma . $\lfloor \sigma (G)\rfloor$
A gráf particionálási problémával ellentétben az eredményül kapott particionálási számosságszámítások nem feltétlenül kiegyensúlyozottak (azaz közel azonos méretűek).

Irodalom

Cunningham WH Optimális támadás és hálózat megerősítése // J of ACM. - 1985. - Kiadás. 32 . - S. 549-561 .
Alexander Schrijver. 51. fejezet // Kombinatorikus optimalizálás. Poliéder és hatékonyság . - Springer, 2003. - ISBN 978-3-540-44389-6 .
Trubin VA Grafikon erőssége és fák és elágazások tömörítése // Kibernetika és rendszerelemzés. - 1993. - Kiadás. 29 . - S. 379-384 .