Elválasztó é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.

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

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. .
2. .
3. .
4. .
5. .
6. .