Kytkeytynyt komponentti on suuntaamattoman graafin maksimaalinen kytkeytynyt aligrafi. Jokainen huippu kuuluu täsmälleen yhteen kytkettyyn komponenttiin, samoin jokainen reuna. Graafi on kytketty, jos ja vain jos sillä on täsmälleen yksi kytketty komponentti.
Vahvat komponentit ovat suunnatun graafin maksimaalisesti vahvasti kytkeytyneitä osagraafeja.
Yhteen kytketyn graafin G pisteiden leikkaus tai erottelujoukko on joukko kärkipisteitä, joiden poistaminen tekee G:stä kytkemättömän. Vertex connectivity κ(G) (jos G ei ole täydellinen graafi) on minimaalisen vertex cutin koko. Graafia kutsutaan k-vertex-connected tai k-connected, jos sen vertex-connectivity on k tai suurempi.
Tarkemmin sanottuna, minkä tahansa graafin G (täydellinen tai ei täydellinen) sanotaan olevan k-vertex-connected, jos se sisältää vähintään k + 1 kärkeä, mutta ei sisällä joukkoa k – 1 kärkeä, joiden poistaminen irrottaa graafin; ja κ(G) määritellään suurimmaksi k:ksi siten, että G on k-connected. Erityisesti täydellisellä graafilla, jossa on n kärkeä ja jota kutsutaan Kn:ksi, ei ole lainkaan kärkileikkauksia, mutta κ(Kn) = n – 1.
Kahden kärjen leikkaus kahdelle kärjelle u ja v on joukko kärkiä, joiden poistaminen graafista katkaisee yhteydet u:n ja v:n. Paikallinen kytkeytyvyys κ(u, v) on pienimmän u:n ja v:n erottavan kärjen leikkauksen koko. Paikallinen kytkeytyvyys on symmetrinen suuntaamattomille graafeille, eli κ(u, v) = κ(v, u). Lisäksi täydellisiä graafeja lukuun ottamatta κ(G) on yhtä kuin κ(u, v):n minimi kaikkien ei-viereisten kärkiparien u, v yli.
2-kytkeytyneisyyttä kutsutaan myös bikytkeytyneisyydeksi ja 3-kytkeytyneisyyttä kutsutaan myös trikytkeytyneisyydeksi. Graafia G, joka on kytkeytynyt mutta ei 2-kytkeytynyt, kutsutaan joskus separoituvaksi.
Analogiset käsitteet voidaan määritellä reunoille. Yksinkertaisessa tapauksessa, jossa yksittäisen, tietyn reunan katkaiseminen katkaisisi graafin, kyseistä reunaa kutsutaan sillaksi. Yleisemmin G:n reunaleikkaus on joukko reunoja, joiden poistaminen tekee graafista irrallisen. Reunan liitettävyys λ(G) on pienimmän reunaleikkauksen koko, ja kahden kärkipisteen u, v paikallinen reunan liitettävyys λ(u, v) on pienimmän reunaleikkauksen koko, joka katkaisee u:n ja v:n välisen yhteyden. Graafia sanotaan k-särmäliitännäiseksi, jos sen särmäliitännäisyys on k tai suurempi.
Graafin sanotaan olevan maksimaalisesti liitetty, jos sen liitännäisyys on yhtä suuri kuin sen pienin aste. Graafin sanotaan olevan maksimaalisesti reunakytkeytynyt, jos sen reunakytkeytyneisyys on yhtä suuri kuin sen minimiaste.
Super- ja hyperkytkeytyneisyysMuutos
Graafia sanotaan superkytkeytyneeksi tai super-κ:ksi, jos jokainen minimaalinen verteksin leikkaus eristää verteksin. Graafin sanotaan olevan hyperyhteydellinen tai hyper-κ, jos jokaisen minimipisteen leikkauksen poistaminen luo täsmälleen kaksi komponenttia, joista toinen on eristetty piste. Graafi on puolihyper-yhtenäinen tai puolihyper-κ, jos mikä tahansa minimipisteen leikkaus jakaa graafin täsmälleen kahteen komponenttiin.
Tarkemmin sanottuna: G-yhtenäisen graafin sanotaan olevan super-yhtenäinen tai super-κ, jos kaikki minimipisteen leikkaukset koostuvat niistä pisteistä, jotka ovat vierekkäin yhden (minimiasteisen) pisteen kanssa.G:n yhdistetyn graafin sanotaan olevan super-edge-connected tai super-λ, jos kaikki minimaaliset edge-cuts koostuvat jonkun (minimiasteisen) verteksin vierekkäisistä reunoista.
G:n leikkausjoukkoa X sanotaan ei-triviaaliksi leikkausjoukoksi, jos X ei sisällä minkään verteksin u ∉ X naapurustoa N(u). Tällöin G:n superconnectivity κ1 on:
κ1(G) = min{|X| : X on ei-triviaali leikkausjoukko}.
Ei-triviaali reunaleikkaus ja reunojen superkonnektiivisuus λ1(G) määritellään analogisesti.
