Konektivní komponenta je maximálně spojitý podgraf neorientovaného grafu. Každý vrchol patří přesně do jedné spojité komponenty, stejně jako každá hrana. Graf je spojitý tehdy a jen tehdy, když má přesně jednu spojitou komponentu.
Silné komponenty jsou maximální silně propojené podgrafy směrovaného grafu.
Vrcholový řez neboli separační množina spojitého grafu G je množina vrcholů, jejichž odstraněním se G stane nespojitým. Vrcholová spojitost κ(G) (kde G není úplný graf) je velikost minimálního vrcholového řezu. Graf se nazývá k-vrcholově spojitý nebo k-spojitý, jestliže jeho vrcholová spojitost je k nebo větší.
Přesněji řečeno, o každém grafu G (úplném nebo neúplném) se říká, že je k-vrcholově spojitý, jestliže obsahuje alespoň k+1 vrcholů, ale neobsahuje množinu k – 1 vrcholů, jejichž odstranění graf rozpojí; a κ(G) je definováno jako největší k takové, že G je k-spojitý. Konkrétně úplný graf s n vrcholy, označený Kn, nemá vůbec žádné vrcholové řezy, ale κ(Kn) = n – 1.
Vrcholový řez pro dva vrcholy u a v je množina vrcholů, jejichž odstraněním z grafu dojde k rozpojení u a v. Lokální konektivita κ(u, v) je velikost nejmenšího vrcholového řezu oddělujícího u a v. Lokální konektivita je symetrická pro neorientované grafy, to znamená, že κ(u, v) = κ(v, u). Navíc s výjimkou úplných grafů se κ(G) rovná minimu κ(u, v) nad všemi nesousedními dvojicemi vrcholů u, v.
2-konektivita se také nazývá dvojkonektivita a 3-konektivita se také nazývá trojkonektivita. Graf G, který je spojitý, ale není 2-spojitý, se někdy nazývá oddělitelný.
Analogické pojmy lze definovat pro hrany. V jednoduchém případě, kdy by odříznutí jediné konkrétní hrany vedlo k rozpojení grafu, se tato hrana nazývá most. Obecněji je řez hran grafu G množina hran, jejichž odstraněním se graf stane nespojitým. Konektivita hran λ(G) je velikost nejmenšího řezu hran a lokální konektivita hran λ(u, v) dvou vrcholů u, v je velikost nejmenšího řezu hran odpojujícího u od v. Lokální konektivita hran je opět symetrická. Graf se nazývá k-hranově propojený, jestliže jeho hranová konektivita je k nebo větší.
O grafu se říká, že je maximálně propojený, jestliže se jeho konektivita rovná jeho minimálnímu stupni. O grafu se říká, že je maximálně hranově propojený, jestliže se jeho hranová propojenost rovná jeho minimálnímu stupni.
Super- a hyper-konektivitaEdit
O grafu se říká, že je super-konektivní nebo super-κ, jestliže každý minimální vrcholový řez izoluje vrchol. O grafu se říká, že je hyper-konektivní nebo hyper-κ, jestliže odstranění každého minimálního vrcholového řezu vytvoří přesně dvě komponenty, z nichž jedna je izolovaný vrchol. Graf je polohyperspojený nebo polohyper-κ, jestliže každý minimální vrcholový řez rozdělí graf na přesně dvě složky.
Přesněji: o spojitém grafu G se říká, že je superspojený nebo super-κ, jestliže všechny minimální vrcholové řezy sestávají z vrcholů sousedících s jedním vrcholem (minimálního stupně).O spojitém grafu G se říká, že je super-hranově spojitý nebo super-λ, jestliže všechny minimální hranové řezy sestávají z hran sousedících s nějakým vrcholem (minimálního stupně).
Výřez X grafu G se nazývá netriviální výřez, jestliže X neobsahuje okolí N(u) žádného vrcholu u ∉ X. Pak superkonektivita κ1 grafu G je:
κ1(G) = min{|X| : X je netriviální výřez}.
Netriviální hranový řez a hranová superspojitost λ1(G) jsou definovány analogicky.
.
