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

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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ó fogalmak[szerkeszté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 aspektusok[szerkeszté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ócikkek[szerkesztés]

Fordítás[szerkesztés]

Jegyzetek[szerkeszté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.