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. 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.

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, 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.

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.

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

Egy másik, igen egyszerű hídkereső algoritmus  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

Gráfok összefüggősége
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 . 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 −hídélt tartalmazhat , hiszen onnantól tetszőleges él hozzáadása kört hozna létre . A pontosan n −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 . 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 . Aregulá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 , 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 . 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ülban , illetveben 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 . Hídkereső algoritmusok A gráfokban való hídkeresésre az első lineáris idejű algoritmust Robert Tarjan írta leben . Egy másik , igen egyszerű hídkereső algoritmus 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élösszefüggőségének ésösszefüggőségének teszteléséhez ( ami kiterjeszthető lineáris idejűélösszefüggés- ésösszefüggés-tesztelésre is ) . Jegyzetek Gráfok összefüggősége