Híd (gráfelmélet)

A híd a gráfelméletben  egy él , amelynek eltávolítása megnöveli a kapcsolódó komponensek számát [1] . Az ilyen bordákat vágóbordáknak , vágóíveknek vagy földszorosoknak is nevezik . Egy ekvivalens definíció szerint egy él akkor és csak akkor híd, ha egyetlen ciklusban sem szerepel .

Fák és erdők

Egy csúcsokkal rendelkező gráf legfeljebb hidat tartalmazhat, mivel egy további él hozzáadása elkerülhetetlenül ciklus megjelenéséhez vezet. Azokat a grafikonokat, amelyeknek pontosan hidaik vannak, fáknak nevezzük, azokat a gráfokat pedig, ahol bármely él híd, erdők .

Minden irányítatlan gráfban létezik egy csúcsekvivalencia reláció , amely szerint két csúcs ekvivalens, ha két olyan út köti össze őket, amelyek nem metszik egymást az élek mentén (bármely csúcs önmagával ekvivalensnek tekinthető). Ennek a relációnak az ekvivalencia osztályait 2-él-összekapcsolt komponenseknek nevezzük , és a gráf hídjai pontosan azok az élek, amelyek végei különböző komponensekhez tartoznak. A gráf áthidaló blokkdiagramja minden nem triviális komponenshez rendelkezik csúcsponttal és minden hídnak egy élével [2] .

Kapcsolat csúcskapcsolattal

A hidak szorosan kapcsolódnak a csuklópántok fogalmához , olyan csúcsokhoz, amelyek bármely olyan útvonalba belépnek, amely két csúcsot összeköt. A híd két végpontja csuklós, hacsak nem 1-es fokú, bár a nem hídélek is mindkét végén csuklósan csuklósak. Akárcsak a hidak nélküli gráfok, amelyek 2 éllel vannak összekötve, a csuklópánt nélküli gráfok 2-es csúcsokkal vannak összekötve .

A köbös gráfokban bármely csukló legalább egy híd terminális csúcsa.

Grafikonok hidak nélkül

Ahogy a neve is sugallja, a híd nélküli gráf  olyan gráf, amelynek nincsenek hidak. Ekvivalens feltétel, hogy a gráf minden összekapcsolt komponense nyitott fülű dekompozícióval rendelkezzen [3] , hogy minden összekapcsolt komponens kétélű legyen , vagy ( Robbins tétele szerint ), hogy minden összekapcsolt komponens erős orientációjú [3 ] .

A hidakkal kapcsolatos fontos nyitott probléma a Seymour és Székeres által (1978-ban és 1979-ben, egymástól függetlenül) javasolt kettős ciklusú lefedettség sejtés , amely szerint bármely híd nélküli gráf lefedhető egyszerű ciklusokkal, amelyek minden élt kétszer tartalmaznak [4] .

Tarján hídkereső algoritmusa

Az első algoritmust, amellyel lineáris futásidejű gráfban hidak kereshetők, Robert Tarjan írta le 1974- ben [5] . Az algoritmus így működik:

• Keresse meg a gráf átfogó erdejét .
• Hozzon létre egy erdőt, amelynek gyökerei egy átívelő fából vannak.
• Közvetlen sorrendben körbejárjuk az erdőt , és megszámozzuk a csúcsokat. A szülőcsúcsok most alacsonyabban vannak számozva, mint a gyermekeik.

A fában lévő élt (v,w) -ként fogjuk jelölni , és nem -ként .

• A közvetlen bejárás során minden csúcsra a következőket hajtjuk végre:
  • Kiszámoljuk a csúcs gyermekeinek számát, és hozzáadunk egyet, amikor a következő csúcsra lépünk (beleértve a csúcsot is ).

.

• • Számítsa ki azt a minimális számot, amely elérhetõ a csúcsból , követve a részfa -tól kezdõdõ éleit (kivéve az utolsó élt). Ez a minimális szám abban a halmazban, amely a csúcs leszármazottainak értékeiből és a nem -hez tartozó élekről elérhető csúcsok számából áll .

• • Hasonlóképpen számítsa ki azt a legnagyobb számot, amelyet a részfa -val kezdődő éleinek követésével lehet elérni . Ez a maximális szám az értékkészletben, amely a csúcs leszármazottainak értékéből és azon csúcsok számából áll , amelyek nem tartoznak a -hoz tartozó élek mentén elérhetők .

• • Minden olyan csúcsnál , amelynek szülője van, ellenőrizzük, hogy és , akkor a -tól -ig lévő él egy híd.

Ha egy híd, akkor egyértelmű, hogy a benne gyökerező részfából nem lehet olyan csúcsra menni, amely nem ehhez a részfához tartozik. Ennek ellenőrzéséhez elegendő az L(w), H(w) ellenőrzése - a feltétel azt jelenti, hogy nem megyünk a gyökérhez közelebb eső csúcsba, a feltétel pedig azt, hogy nem megyünk másik részfára.

Hidak keresése láncbontással

Egy nagyon egyszerű hídkereső algoritmus [6] a láncbontáson alapul. A láncbontás nemcsak az összes hidat eredményezi, hanem a G gráf összes csuklóját (és duplán összefüggő komponenseit is) , így alapot biztosít az él és a 2-es csúcs összekapcsolhatóságának teszteléséhez (és ez a módszer kiterjeszthető a lineáris időben történő verifikációra is) él- és csúcs 3-kapcsolat).

A láncbontás a fülbontás speciális esete, amely a G gráf T fáján végzett mélységi keresésen alapul, és nagyon egyszerűen elvégezhető:

legyen minden csúcs meg nem látogatottként jelölve. Minden v csúcsnál az 1... n bejárási számok növekvő sorrendjében bejárjuk a v -be beeső minden hátrafelé eső élt (azaz egy olyan élt, amely nem tartozik a bejárási fához) , és követjük a fa éleit a gyökérig, amíg meg nem találkozik a meglátogatott csúcsponttal. Az áthaladás során minden átadott csúcsot meglátogatottnak jelölünk. Ez a lépés egy elérési úttal vagy egy v -vel kezdődő ciklussal végződik , ezt nevezzük útvonalnak vagy láncnak . Az ilyen eljárással kapott i-edik karakterláncot C i - ként fogjuk jelölni . C=C 1 ,C 2 ,... ekkor a G gráf láncokra való felosztása .

A következő tulajdonságok lehetővé teszik, hogy C - ből hatékonyan nyerjünk információt a G gráfról, beleértve az összes hidat [6] :

Legyen C egy egyszerű összefüggő gráf láncfelbontása G=(V,E) .

1. G akkor és csak akkor 2-él-összefüggő, ha C láncai tartalmazzák az összes élt E -ből .
2. Egy G -beli e él akkor és csak akkor híd, ha e nem szerepel C -ből származó láncban .
3. Ha G 2-élen kapcsolódik, akkor C füldekompozíció .
4. G akkor és csak akkor kapcsolódik két csúcshoz, ha G minimum foka 2, és C 1 az egyetlen ciklus C -ben .
5. Egy 2 éllel összefüggő G gráf v csúcsa akkor és csak akkor csukló, ha v a C-C 1 ciklus első csúcsa .
6. Ha G 2-es csúcshoz kapcsolódik, akkor C egy nyitott fülekre való szétbontás .

Jegyzetek

1. ↑ Bollobas Béla. Modern gráfelmélet. - New York: Springer-Verlag, 1998. - T. 184. - P. 6. - (Graduate Texts in Mathematics). — ISBN 0-387-98488-7 . - doi : 10.1007/978-1-4612-0619-4 .
2. ↑ Jeffery Westbrook, Robert E. Tarjan. Hídkapcsolt és bikapcsolt összetevők online karbantartása // Algorithmica. - 1992. - T. 7 , szám. 5-6 . - S. 433-464 . - doi : 10.1007/BF01758773 .
3. ↑ 1 2 H. E. Robbins. Tétel a grafikonokról, alkalmazással egy forgalomirányítási problémára  // The American Mathematical Monthly . - 1939. - T. 46 . - S. 281-283 .
4. ↑ F. Jaeger. Annals of Discrete Mathematics 27 - Ciklusok a grafikonokban. - 1985. - T. 27. - S. 1-12. — (North-Holland Mathematics Studies). - doi : 10.1016/S0304-0208(08)72993-1 .
5. ↑ R. Endre Tarjan. Megjegyzés a gráf hídjainak megtalálásához // Information Processing Letters. - T. 2 , sz. 6 . - S. 160-161 . - doi : 10.1016/0020-0190(74)90003-9 .
6. ↑ 1 2 Jens M. Schmidt. Egy egyszerű teszt a 2-csúcs- és 2-él-kapcsolaton // Információfeldolgozási levelek. - 2013. - T. 113 , sz. 7 . - S. 241-244 . - doi : 10.1016/j.ipl.2013.01.016 .