strongly connected component

Angol

Főnév

strongly connected component (tsz. strongly connected components)

1. (informatika) erősen összefüggő komponens

---

Egy strongly connected component (SCC) egy irányított gráf olyan maximális részhalmaza (komponense), amelyben minden csúcsból elérhető bármely másik csúcs az élek irányát követve.

---

🔁 Formális definíció

Egy irányított gráf ${\textstyle G=(V,E)}$ SCC-je olyan csúcshalmaz ${\textstyle C\subseteq V}$, amelyre:

• Minden ${\textstyle u,v\in C}$ esetén létezik út ${\textstyle u}$-ból ${\textstyle v}$-be és ${\textstyle v}$-ből ${\textstyle u}$-ba.
• ${\textstyle C}$ maximális ilyen halmaz, azaz nem bővíthető új csúcs hozzáadásával úgy, hogy a fenti tulajdonság megmaradjon.

---

🔧 Algoritmusok SCC meghatározására

1. Kosaraju algoritmus – két DFS futtatása, egyszer az eredeti gráfon, egyszer a transzponált gráfon.
2. Tarjan algoritmus – egy DFS-alapú algoritmus, amely hatékonyan találja meg az összes SCC-t egyetlen menetben.
3. Gabow algoritmus – alternatív, veremalapú SCC-meghatározás.

---

🧠 Példa

Ha egy gráfban:

• A → B → C → A → D
• És D → E (de E nem mutat vissza)

Akkor:

• {A, B, C} egy SCC
• {D} külön SCC
• {E} külön SCC

---

📌 Alkalmazások

• Programanalízis (pl. függőségi ciklusok detektálása)
• Webgraf elemzés (pl. összefüggő weboldalcsoportok)
• Adatfolyam- és vezérlési gráfok optimalizálása
• Moduláris komponenskeresés szoftverekben és hálózatokban

---

✅ Összefoglalás

A strongly connected component az irányított gráfok egyik alapvető strukturális eleme, amelyben minden csúcs elérhető bármely másikból. Az SCC-k meghatározása kulcsszerepet játszik a gráfok elemzésében, felbontásában és optimalizálásában.

További információk

• strongly connected component - Szótár.net (en-hu)
• strongly connected component - Sztaki (en-hu)
• strongly connected component - Merriam–Webster
• strongly connected component - Cambridge
• strongly connected component - WordNet
• strongly connected component - Яндекс (en-ru)
• strongly connected component - Google (en-hu)
• strongly connected component - Wikidata
• strongly connected component - Wikipédia (angol)