Erősen kapcsolódó komponens

Egy irányított gráfot (digráfot) erősen összefüggőnek nevezünk , ha bármely két s és t csúcsa erősen össze van kötve, vagyis ha van egy irányított út odáig ,  és egyidejűleg van irányított út odáig .

A digráf erősen összefüggő összetevői a zárványmaximális erősen összefüggő részgráfjai. Az erősen kapcsolódó régió erősen összefüggő komponensek csúcsainak halmaza.

Definíciók

Egy olyan digráf, amely nem tartozik az erősen összefüggő gráfok osztályába, tartalmaz erősen összefüggő komponensek halmazát, és néhány irányított élhalmazt, amelyek egyik komponensről a másikra haladnak.

A digráf bármely csúcsa erősen kapcsolódik önmagához.

Algoritmusok

A legegyszerűbb algoritmus a digráfban erősen összefüggő komponensek megtalálásának problémájának megoldására a következőképpen működik:

  1. A tranzitív lezárás segítségével ellenőrizzük, hogy az összes párnál elérhető - e és onnan
  2. Ezután definiálunk egy olyan irányítatlan gráfot , amely minden ilyen párhoz tartalmaz egy élt.
  3. Egy ilyen irányítatlan gráf összefüggő komponenseinek keresése a digráf erősen összefüggő összetevőit eredményezi.

Nyilvánvaló, hogy ennek az algoritmusnak a fő futási idejét egy tranzitív lezárás foglalja el.

Három olyan algoritmus is létezik, amely ezt a problémát lineáris időben oldja meg, azaz V-szer gyorsabban, mint a fenti algoritmus. Ezek a Kosaraju algoritmusai , az erősen összefüggő komponensek keresése két veremben , és a Tarjan .

Példa

Az ábrán egy digráf látható, amelyen mindhárom erősen összefüggő komponens látható (szaggatott vonallal körvonalazott, árnyékolt területek).

Lásd még

Irodalom