Összefüggő komponens (gráfelmélet)
A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf összefüggő komponense (vagy csak komponense) (connected component) olyan részgráf, mely összefüggő, azaz bármely két csúcsát út köti össze, de az eredeti gráf többi csúcsához nem csatlakozik. Például a jobb oldali ábrán látható gráf három összefüggő komponensből áll. Egy izolált csúcs, melyből nem indulnak élek önmagában egy összefüggő komponenst alkot. Egy összefüggő gráf pontosan egy darab összefüggő komponenssel rendelkezik, ami az egész gráfot magában foglalja.
Ekvivalenciareláció szerkesztés
Az összefüggő komponensek definiálása elvégezhető a gráf csúcsain értelmezett ekvivalenciareláció ekvivalenciaosztályain keresztül is. Egy irányítatlan gráf v csúcsa elérhető az u csúcsból, ha létezik út u és v között. Ebben a definícióban egyetlen csúcsra nulla hosszúságú útként tekintünk, és ugyanaz a csúcs egynél többször is előfordulhat ugyanazon út részeként. Az elérhetőség ekvivalenciareláció, mivel:
- reflexív: bármely csúcsot saját magával triviálisan nulla hosszúságú út köt össze.
- szimmetrikus: ha létezik út u és v között, ugyanazok az élek utat alkotnak v és u között is.
- tranzitív: ha létezik út u és v között, valamint létezik út v és w között, akkor a két út összefűzhető egy u és w közötti útba.
Az összefüggő komponensek az így definiált ekvivalenciareláció ekvivalenciaosztályai által meghatározott feszített részgráfok.
Az összefüggő komponensek száma szerkesztés
Az összefüggő komponensek száma a gráf fontos topologikus invariánsa. A topologikus gráfelméletben úgy értelmezhető, mint a gráf nulladik Betti-száma. Az algebrai gráfelmélet területén megegyezik a gráf Laplace-mátrixa 0 sajátértékeinek multiplicitásával. Megegyezik továbbá a gráf kromatikus polinomjának első nem nulla együtthatójával. Az összefüggő komponensek száma fontos szerepet kap a teljes párosítással rendelkező gráfok Tutte-féle leírásával, és a gráf szívósságának definíciójában.
Algoritmusok szerkesztés
Egy gráf összefüggő komponensei viszonylag egyszerűen megkereshetők lineáris idejű (a gráf csúcsai és élei szerint) algoritmussal, akár mélységi, akár szélességi kereséssel. Bármely esetben, a valamely v csúcsból elinduló keresés a v-t tartalmazó teljes összefüggő komponenst (és nem többet) fogja megtalálni visszatérése előtt. A gráf összes összefüggő komponensének megtalálásához végig kell lépkedni az összes csúcson, és minden, a korábbi lépésben meg nem talált csúcsból el kell indítani a következő mélységi vagy szélességi keresést. Hopcroft és Tarjan (1973)[1] lényegében ezt az algoritmust írják le, amit 1973-ban már jól ismertnek tekintettek.
Léteznek hatékony, diszjunkt halmaz-adatszerkezetet használó algoritmusok a gráf összefüggő komponenseinek dinamikus számon tartására akkor is, ha csúcsok és élek kerülnek hozzáadása az eredeti gráfhoz. Ezeknek az algoritmusoknak O(α(n)) amortizált időre van szükségük műveletenként, ahol a műveletek közé tartozik a csúcsok és élek hozzáadása, valamint annak meghatározása, hogy egy csúcsú melyik összefüggő komponensbe tartozik, α(n) pedig egy igen gyorsan növekvő Ackermann-függvény nagyon lassan növekvő inverze. Kapcsolódó probléma az összefüggő komponensek követése, miközben a gráf élei egyenként törlésre kerülnek; létezik algoritmus, ami ezt lekérdezésenként konstans időben megoldja, míg az adatstruktúra karbantartására O(|V||E|) időre van szükség; ennek az amortizált ideje O(|V|) éltörlésenként. Erdők esetében a költség csökkenthető O(q + |V| log |V|)-re, avagy O(log |V|)-re éltörlésenként.[2]
A kutatók vizsgáltak olyan algoritmusokat is, ahol a számításnak bizonyos korlátok határt szabnak, például a program munkamemóriája logaritmikus számú bitre korlátozódik (ami az L bonyolultsági osztálynak felel meg). (Lewis & Papadimitriou 1982) tette fel a kérdést, hogy vajon lehetséges-e logspace-ben megállapítani, hogy egy irányítatlan gráf két csúcsa ugyanabba az összefüggő komponensbe esik-e, és meghatározta az SL bonyolultsági osztály az összefüggőség logspace-ekvivalens problémáira. Végül (Reingold 2008) sikeresen meghatározott egy algoritmust, ami logaritmikus tárterületen megoldotta ezt a problémát, igazolva ezzel, hogy L = SL.
Kapcsolódó szócikkek szerkesztés
- Óriás komponens
- Erősen összefüggő komponens, az irányított gráfoknál fellépő hasonló fogalom
- 2-összefüggő komponens
- Modulfelbontás, az összefüggő komponensek általánosítása (irányítatlan gráfoknál)
- Perkolációelmélet, a rácsgráfok véletlen részgráfjai összefüggő komponenseinek viselkedését leíró elmélet
- Centralitás
- Elválasztó él
Jegyzetek szerkesztés
- ↑ (1973) „Algorithm 447: efficient algorithms for graph manipulation”. Communications of the ACM 16 (6), 372–378. o. DOI:10.1145/362248.362272.
- ↑ Shiloach, Y. and Even, S. 1981. An On-Line Edge-Deletion Problem. Journal of the ACM: 28, 1 (Jan. 1981), pp.1-4.
- Lewis, Harry R. & Papadimitriou, Christos H. (1982), "Symmetric space-bounded computation", Theoretical Computer Science 19 (2): 161–187, DOI 10.1016/0304-3975(82)90058-5.
- Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM 55 (4): Article 17, 24 pages, DOI 10.1145/1391289.1391291.
Fordítás szerkesztés
- Ez a szócikk részben vagy egészben a Connected component (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
További információk szerkesztés
- MATLAB code to find connected components in undirected graphs, MATLAB File Exchange.
- Connected components, Steven Skiena, The Stony Brook Algorithm Repository