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

olyan gráf, mely bármely k‒1 él elhagyásával is összefüggő marad

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 λ(G)) 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.[1]

Formális definícióSzerkesztés

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

Legyen   tetszőleges gráf. Ha a   részgráf minden  -re összefüggő, ahol  , akkor G k-szorosan élösszefüggő.   é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ó fogalmakSzerkesztés

A minimális fokszám triviális felső korlátot ad az élösszefüggésre. Tehát, ha egy   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.[2]

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).[3]

Számítási aspektusokSzerkesztés

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  -szer kellene megoldania a maximális folyam problémát, ami viszont   idejű. Tehát a fent leírt algoritmusnak a teljes bonyolultsága  .

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  -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   idő alatt végez.[4]

A Karger-algoritmus Karger–Stein-variánsa az élösszefüggés meghatározására gyorsabb véletlen algoritmus, várható futásideje  .[5]

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  -re.[6]

Kapcsolódó szócikkekSzerkesztés

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a K-edge-connected 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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Jordan, Camille (1869). „Sur les assemblages de lignes” (French nyelven). Journal für die reine und angewandte Mathematik 70 (2), 185–190. o.  
  2. Cho, Jung Jin; Chen, Yong & Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics 155 (18): 2456–2470, DOI 10.1016/j.dam.2007.06.015.
  3. Robbins, H. E. (1939). „A theorem on graphs, with an application to a problem on traffic control”. American Mathematical Monthly 46, 281–283. o. DOI:10.2307/2303897.  
  4. Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259–273, 1995.
  5. (1996) „A new approach to the minimum cut problem”. Journal of the ACM 43 (4), 601. o. DOI:10.1145/234533.234534.  
  6. M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.