Elválasztó él

16 csúccsal és 6 pirossal jelölt híddal rendelkező gráf

Irányítatlan összefüggő gráf, szeparáló élek nélkül

A matematika, azon belül a gráfelmélet területén egy elválasztó él, szeparáló él, hídél vagy egyszerűen híd (az angol szakirodalomban: bridge, isthmus, cut-edge, cut arc) egy gráf olyan éle, melynek törlése megnövelné az adott gráf komponenseinek számát.^[1] Ezzel ekvivalens megfogalmazásban, egy él akkor és csak akkor híd, ha nem része egyetlen körnek sem. A gráfot hídmentesnek (bridgeless, isthmus-free) neveznek, ha nem tartalmaz egyetlen hidat sem.

Fák és erdők

Egy n csúcsú gráf legfeljebb n − 1 hídélt tartalmazhat, hiszen onnantól tetszőleges él hozzáadása kört hozna létre. A pontosan n − 1 hidat tartalmazó gráfok megegyeznek a fákkal, az olyan gráfok pedig, melyeknek minden éle elválasztó él, az erdőkkel.

Minden irányítatlan gráfban létezik a csúcsokon értelmezett ekvivalenciareláció, mely szerint két csúcs relációban van egymással, ha létezik közöttük egyetlen élükben sem megegyező két út (minden csúcs relációban van saját magával, amennyiben létezik a saját magával összekötő két nulla hosszúságú út, melyek ugyan megegyeznek, de egyetlen közös élük sincs). A reláció ekvivalenciaosztályai a kétszeresen élösszefüggő komponensek, és a gráf hídjai pontosan azok az élek, melyek végpontjai különböző komponensekhez tartoznak. Egy gráf híd–blokk fája (bridge-block tree) egy-egy csúcsot tartalmaznak az eredeti gráf minden nem triviális komponense után, és minden hídhoz egy élet.^[2]

Kapcsolat az összefüggőséggel

A hidak szorosan kapcsolódnak az artikulációs pontokhoz (elvágó pont), melyek egyes csúcspárok közötti minden útnak részét képezik. A hidak két végpontja artikulációs pont, hacsak nem egy fokszámúak; létezhet viszont olyan, két artikulációs pont között húzódó él, amely nem híd. Ahogy a hídmentes gráfok kétszeresen élösszefüggőek, úgy az artikulációs pontok nélküli gráfok kétszeresen összefüggőek.

A 3-reguláris gráfokban minden elvágó pont legalább egy híd végpontja.

Hídmentes gráfok

A hídmentes gráf (bridgeless graph) olyan gráf, ami nem tartalmaz elvágó élet. Ezzel ekvivalens feltétel, hogy a gráf minden összefüggő komponensének létezzen olyan nyílt fülfelbontása,^[3] hogy vagy minden összekötött komponens kétszeresen élösszefüggő, vagy (a Robbins-tétel alapján) minden összefüggő komponens rendelkezzen erős irányultsággal.^[3]

A hídélekkel összefüggő fontos megoldatlan probléma a kétszeres körfedés (cycle double cover conjecture), amit Seymour és Szekeres egymástól függetlenül 1978-ban, illetve 1979-ben vetettek fel. Ez kimondja, hogy minden hídélmentes gráfban létezik egyszerű körök olyan halmaza, melyek minden élet pontosan kétszer tartalmaznak.^[4]

Hídkereső algoritmusok

A gráfokban való hídkeresésre az első lineáris idejű algoritmust Robert Tarjan írta le 1974-ben.^[5]

Egy másik, igen egyszerű hídkereső algoritmus ^[6] láncfelbontásokat használ. A láncfelbontások nem csak a hídélek megkeresését teszik lehetővé, hanem eközben lehetővé teszik a gráf összes artikulációs pontjának (és a gráf blokk-vágás-fájának) „leolvasását”, így általános keretet adva a gráf 2-élösszefüggőségének és 2-összefüggőségének teszteléséhez (ami kiterjeszthető lineáris idejű 3-élösszefüggés- és 3-összefüggés-tesztelésre is).

Jegyzetek

1. Bollobás, Béla (1998), Modern Graph Theory, vol. 184, Graduate Texts in Mathematics, New York: Springer-Verlag, p. 6, ISBN 0-387-98488-7, doi:10.1007/978-1-4612-0619-4, <http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA6>.
2. Westbrook, Jeffery & Tarjan, Robert E. (1992), "Maintaining bridge-connected and biconnected components on-line", Algorithmica 7 (5-6): 433–464, DOI 10.1007/BF01758773.
3. Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly 46: 281–283, DOI 10.2307/2303897.
4. Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, vol. 27, North-Holland Mathematics Studies, pp. 1–12, DOI 10.1016/S0304-0208(08)72993-1.
5. Tarjan, R. Endre, "A note on finding the bridges of a graph", Information Processing Letters 2 (6): 160–161, DOI 10.1016/0020-0190(74)90003-9.
6. Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters 113 (7): 241–244, DOI 10.1016/j.ipl.2013.01.016.