Kuvaajan teho

Suuntaamattoman graafin kardinaalisuus on graafin ominaisuus, joka on yhtä suuri kuin graafista poistettujen reunojen lukumäärän vähimmäissuhde tällaisen poistamisen tuloksena saatuun komponenttien määrään (vähennettynä 1:llä). Tämän menetelmän avulla voit tunnistaa alueet, joissa on paljon reunoja. Graafin kardinaalisuus on samanlainen kuin graafin jäykkyyden käsite , joka kuitenkin määräytyy kärkien, ei reunojen, poistamisen avulla.

Määritelmät

Suuntaamattoman yksinkertaisen graafin kardinaalisuus voidaan määritellä kolmella vastaavalla tavalla: $\sigma (G)$ $G=(V,E)$

Antaa olla joukko joukon kaikki osiot . Halkaisua varten merkitään joukkona reunoja, jotka yhdistävät pisteitä eri komponenteista . Sitten . $\Pi$ $V$ $\pi \in \Pi$ $\partial \pi$ $\pi$ $\displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1))$
Antaa olla kaavion kaikkien virittävien puiden joukko . Sitten ${\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\}.

Lineaarisen ohjelmoinnin kaksinaisuuden mukaan

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

Vaikeus

Graafin kardinaalisuuden laskeminen voidaan tehdä polynomiajassa. Ensimmäisen polynomialgoritmin keksi Cunningham (1985). Trubinin (1993) johdosta parhaalla monimutkaisuudella toimivan tehon laskemisalgoritmi käyttää Goldbergin ja Raon (1998) virtauksen hajottamista ja ajaa ajassa . $O(\min({\sqrt {m)),n^{2/3})mn\log(n^{2}/m+2))$

Ominaisuudet

Jos on suhteen maksimoiva osio ja for on graafin G rajoitus joukkoon , niin . $\pi =\{V_{1},\dots ,V_{k}\}$ ${\displaystyle i\in \{1,\dots ,k\))$ $G_{i}=G/V_{i}$ $V_i$ $\sigma (G_{k})\geqslant \sigma (G)$
Tutt-Nash-Williams-lause: on G :n sisältämien reunahajottujen virittävien puiden enimmäismäärä . $\lfloor \sigma (G)\rfloor$
Toisin kuin graafin osiointiongelmassa , tuloksena olevat osituksen kardinaliteettilaskelmat eivät välttämättä ole tasapainoisia (eli lähes samankokoisia).

Kirjallisuus

Cunningham WH Optimaalinen hyökkäys ja verkon vahvistaminen // J of ACM. - 1985. - Numero. 32 . - S. 549-561 .
Alexander Schrijver. Luku 51 // Kombinatorinen optimointi. Polyhedra ja tehokkuus . - Springer, 2003. - ISBN 978-3-540-44389-6 .
Trubin VA Graafin ja puiden ja oksien pakkauksen vahvuus // Cybernetics and Systems Analysis. - 1993. - Numero. 29 . - S. 379-384 .