Egy gráf összekapcsolhatósági összetevője
Egy összefüggő gráfkomponens (vagy egyszerűen egy gráfkomponens ) egy gráf maximális (befoglalással) összefüggő részgráfja .
Más szóval, ez egy olyan részgráf , amelyet csúcsok halmaza generál, amelyben a gráf bármely csúcspárjához van -lánc , és bármely csúcspárhoz nincs -lánc .
Az irányított gráfok esetében az erősen összefüggő komponens fogalmát definiáljuk .
Algoritmus
A Breadth-First Search vagy a Depth -First Search használható a csatlakozási összetevők kinyerésére . Ebben az esetben az eltöltött idő lineáris lesz a gráf csúcsainak és éleinek számának összegében.
Lásd még
- Összekapcsolt grafikon
- Teljesen leválasztott grafikon
- A gráfelméleti kifejezések szószedete
- Erősen összefüggő komponens egy digráfban
- Perkolációs elmélet