Összefüggő komponens

Összefüggő komponensek, II/16
Erdő: körmentes gráf, körmentes gráf minden komponense fa
Körmentes gráf élszáma = pontok száma - komponensek száma ...

Egy összefüggő komponens (vagy komponens) egy maximális összefüggő részgráf. Az összefüggő gráfok egyetlen komponensből állnak, míg a nem összefüggők legalább kettőből. A G gráf komponenseinek számát C(G)-vel jelöljük.
Csúcsok ...

Egy G gráf komponense (vagy összefüggő komponense) minden maximális (nem bővíthető) összefüggő részgráfja. G bármely két összefüggő komponense pont-diszjunkt, és minden pont (és él) pontosan egy komponensbe tartozik.

Definíció: Egy irányított gráfra az osztályai által feszített részgráfokat az irányított gráf erősen összefüggő komponenseinek nevezzük. A továbbiakban feltesszük, hogy gráfunk egyszerű.

Lásd még: Összefüggő, Él, Komponens, Gráf, Részgráf