A kapcsolt komponens egy irányítatlan gráf maximálisan összefüggő részgráfja. Minden csúcs pontosan egy összefüggő komponenshez tartozik, akárcsak minden él. Egy gráf akkor és csak akkor összefüggő, ha pontosan egy összefüggő komponenssel rendelkezik.
Az erős komponensek egy irányított gráf maximálisan erősen összefüggő részgráfjai.
A G összefüggő gráf csúcskivágása vagy elválasztó halmaza olyan csúcsok halmaza, amelyek eltávolítása G-t összefüggéstelenné teszi. A κ(G) csúcsösszekötő képesség (ahol G nem teljes gráf) a minimális csúcskivágás mérete. Egy gráfot k-csúcsösszekötöttnek vagy k-összekötöttnek nevezünk, ha a csúcsösszekötöttsége k vagy nagyobb.
Pontosabban, bármely (teljes vagy nem teljes) G gráfot k-csúcsösszekötöttnek nevezünk, ha legalább k+1 csúcsot tartalmaz, de nem tartalmaz olyan k – 1 csúcsból álló halmazt, amelynek eltávolítása a gráfot szétkapcsolja; és κ(G) a legnagyobb k, amely szerint G k-összekötött. Különösen egy n csúcsú teljes gráf, amelyet Kn-nek jelölünk, egyáltalán nem rendelkezik csúcskivágásokkal, de κ(Kn) = n – 1.
A csúcsvágás két u és v csúcs esetében olyan csúcsok halmaza, amelyeknek a gráfból való eltávolítása szétválasztja u-t és v-t. A κ(u, v) helyi összekapcsolhatóság az u-t és v-t elválasztó legkisebb csúcsvágás mérete. A helyi összekapcsolhatóság irányítatlan gráfok esetén szimmetrikus, azaz κ(u, v) = κ(v, u). Továbbá, teljes gráfok kivételével, κ(G) egyenlő a κ(u, v) minimumával az u, v csúcsok összes nem szomszédos párja felett.
A 2-kapcsolhatóságot bikapcsolhatóságnak, a 3-kapcsolhatóságot pedig trikapcsolhatóságnak is nevezik. Egy olyan G gráfot, amely összefüggő, de nem 2-összekötött, néha szeparálhatónak nevezünk.
Az élekre is definiálhatók hasonló fogalmak. Abban az egyszerű esetben, amikor egyetlen, meghatározott él elvágása szétkapcsolná a gráfot, ezt az élt hídnak nevezzük. Általánosabban, G élek vágott éle olyan élek halmaza, amelyek eltávolítása a gráfot szétkapcsolttá teszi. A λ(G) élkapcsolhatóság a legkisebb élkivágás mérete, két u, v csúcs λ(u, v) lokális élkapcsolhatósága pedig az u-t v-től elválasztó legkisebb élkivágás mérete. A lokális élkapcsolhatóság ismét szimmetrikus. Egy gráfot k-élekkel összekapcsoltnak nevezünk, ha az élkapcsolhatósága k vagy nagyobb.
Egy gráfot maximálisan összekapcsoltnak nevezünk, ha a kapcsolhatósága megegyezik a minimális fokszámával. Egy gráfot maximálisan élösszekötöttnek mondunk, ha élösszekötöttsége egyenlő a minimális fokszámával.
Szuper- és hiperösszekötöttségSzerkesztés
Egy gráfot szuperösszekötöttnek vagy szuper-κ-nek mondunk, ha minden minimális csúcsmetszés elszigetel egy csúcsot. Egy gráfot akkor mondjuk hiper-összekötöttnek vagy hiper-κ-nek, ha minden egyes minimális csúcsmetszés törlése pontosan két komponenst hoz létre, amelyek közül az egyik egy izolált csúcs. Egy gráf fél-hiper-összekötött vagy fél-hiper-κ, ha bármelyik minimális csúcskivágás pontosan két komponensre osztja a gráfot.
Pontosabban: egy G összefüggő gráfot szuper-összekötöttnek vagy szuper-κ-nek mondjuk, ha minden minimális csúcskivágás az egy (minimális fokú) csúccsal szomszédos csúcsokból áll.Egy G összefüggő gráfot szuper-élekkel összefüggőnek vagy szuper-λ-nek mondjuk, ha az összes minimális élkivágás valamely (minimális fokú) csúcsra eső élekből áll.
G egy X vágáshalmazát nem triviális vágáshalmaznak nevezzük, ha X nem tartalmazza egyetlen u ∉ X csúcs N(u) szomszédságát sem. Ekkor G κ1 szuperkapcsolhatósága:
κ1(G) = min{|X| : X egy nem triviális vágáshalmaz}.
A nem-triviális élmetszetet és az él-szuperkonnektivitást λ1(G) analóg módon definiáljuk.
