A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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
- ↑ 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>.
- ↑ Westbrook, Jeffery & Tarjan, Robert E. (1992), "Maintaining bridge-connected and biconnected components on-line", Algorithmica 7 (5-6): 433–464, DOI 10.1007/BF01758773.
- ↑ a b 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.
Analóg multiméterek túlterhelés elleni védelme
Egyenáram
Egyenáram mérése
Egyenirányítós lengőtekercses műszer
Elektromágnes (fizika)
Elektromos feszültség
Elektromos térerősség
Fáziseltolódás
Fázismutató
Fajlagos ellenállás
Feszültséggenerátor
Feszültségváltó
Forgó mágneses tér
Háromfázisú hálózat
Hőelektromosság
Hatásos ellenállás
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.