Elválasztó él
olyan él egy nem feltétlenül összefüggő gráfban, melynek elhagyásával a gráf komponenseinek száma növekszik From Wikipedia, the free encyclopedia
olyan él egy nem feltétlenül összefüggő gráfban, melynek elhagyásával a gráf komponenseinek száma növekszik From Wikipedia, the free encyclopedia
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.
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]
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.
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]
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).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
