k-szorosan élösszefüggő gráf

A matematika, azon belül a gráfelmélet területén G összefüggő gráfot akkor nevezünk k-szorosan élösszefüggő vagy k-élösszefüggő gráfnak, ha kevesebb mint k él eltávolítása után minden esetben összefüggő marad.

Egy gráf élösszefüggősége (jelölése: κ’(G) vagy Sablon:Math) az a legnagyobb k szám, amire igaz, hogy a gráf k-szorosan élösszefüggő.

Adott gráfban a csúcsösszefüggőség, az élösszefüggőség és a minimális fokszám között fennáll, hogy κ(G) ≤ κ’(G) ≤ δ(G).

Az élösszefüggőséget és a k-szorosan élösszefüggő gráfok leszámlálásának problémáját Camille Jordan már 1869-ben tanulmányozta.

Formális definíció

Egy 2-szeresen élösszefüggő gráf

Legyen $G=(V,E)$ tetszőleges gráf. Ha a $G^{\prime }=(V,E\setminus X)$ részgráf minden $X\subseteq E$-re összefüggő, ahol $|X|<k$, akkor G k-szorosan élösszefüggő. $G$ élösszefüggősége az a maximális k érték, amire a G k-szorosan élösszefüggő. A legkisebb X élhalmaz, aminek törlése után G szétesik, egy G-beli minimális vágás.

A Menger-tétel élösszefüggésre vonatkozó változata egy alternatív, az előzőkkel ekvivalens karakterizációra ad lehetőséget, a gráf éldiszjunkt útjait felhasználva. Ha a G gráf bármely csúcspárja k db olyan út végpontját alkotja, melyek közül semelyik kettőnek nincsen közös éle, akkor G k-szorosan élösszefüggő. Az egyik irányban ez könnyen belátható: ha létezik az utak említett rendszere, akkor minden, k-nál kevesebb élből álló X halmaz legalább egy úttal éldiszjunkt, ezért a csúcspár között X törlése után is vezetni fog út. A másik irányban, utak olyan rendszerének létezése minden csúcspárhoz, melyek néhány él törlésével nem szakíthatók szét, belátható a hálózati folyamok elméletének maximális folyam-minimális vágás tétele segítségével.

Kapcsolódó fogalmak

A minimális fokszám triviális felső korlátot ad az élösszefüggésre. Tehát, ha egy $G=(V,E)$ gráf k-élösszefüggő, akkor k ≤ δ(G), ahol δ(G) a v ∈ V csúcsok minimális fokszáma. Nyilvánvaló, hogy egy v csúcsból kiinduló összes él törlése után v kiszakadna a gráfból.

Az élösszefüggőség a girthparaméter (bőség, a gráf legrövidebb körének hossza) fogalmának duálisa, abban az értelemben, hogy egy síkgráf bősége megegyezik a duális gráfjának élösszefüggőségével és viszont. Ezeket a fogalmakat a matroidelmélet egyesíti a matroid girthparaméterében, ami a matroid legkisebb függő halmaz mérete. Grafikus matroid bősége megegyezik az eredeti gráf bőségével, míg kografikus matroidnál az élösszefüggőséggel egyezik meg.

A 2-élösszefüggő gráfok karakterizálhatók még az elválasztó élek hiányával, a fülfelbontás létezésével vagy a Robbins-tétel alapján, mely szerint ezek pontosan azok a gráfok, melyek rendelkeznek erős orientációval (olyan irányítással, melyek erősen összefüggő gráfot hoznak létre).

Számítási aspektusok

Létezik polinom idejű algoritmus annak meghatározására, hogy melyik az a legnagyobb k, amire a G k-élösszefüggő (κ’(G)). Egy naiv algoritmus minden (u,v) csúcspárra meghatározna az u és v közötti maximális folyamot, ha G éleinek kapacitása mindkét irányban 1. Egy gráf pontosan akkor k-élösszefüggő, ha az u és v közötti folyam bármely (u,v) csúcspárra legalább k, tehát k a minimális u-v-folyam az összes (u,v) között.

Ha a gráf csúcsainak száma n, ennek az egyszerű algoritmusnak $O(n^2)$-szer kellene megoldania a maximális folyam problémát, ami viszont $O(n^3)$ idejű. Tehát a fent leírt algoritmusnak a teljes bonyolultsága $O(n^5)$.

Egy továbbfejlesztési irány az lehet, hogy a maximális folyam problémát az olyan (u,v) párokra oldjuk csak meg, ahol u-t fixen választjuk, és csak v iterál végig a többi csúcson. Ez az algoritmikus bonyolultságot $O(n^4)$-re csökkenti, és jól működik, hiszen ha létezik egy k-nál kisebb kapacitású vágás, mindenképpen elválasztja az u-t valamely másik csúcstól. Gabow algoritmusa továbbfejleszti ezt az elgondolást, és legrosszabb esetben $O(n^3)$ idő alatt végez.

A Karger-algoritmus Karger–Stein-variánsa az élösszefüggés meghatározására gyorsabb véletlen algoritmus, várható futásideje $O(n^2{\log }^{3}n)$.

Kapcsolódó probléma: keressük meg G minimális, k-élösszefüggő feszítő részgráfját (azaz: válasszuk ki a lehető legkevesebb lehetséges élt G-ben úgy, hogy azok k-élösszefüggőek legyenek) NP-nehéz $k\ge 2$-re.

Kapcsolódó szócikkek

• k-szorosan összefüggő gráf
• Összefüggőség (gráfelmélet)

Fordítás

• Sablon:Fordítás