ühenduvusest

Ühenduvus on mõiste, mis kirjeldab süsteemi võimet säilitada ühendus oma osade vahel. Erinevates kontekstides tähistab see võrgustike, teedevõrkude, sotsiaalsete suhete või informatsiooni sujuvat liikumist ja toimimist ka siis, kui osa elemente on puudulikult kättesaadav. Ühenduvus on kriitiline nii tehnilises kui ka sotsiaalses ja logistilises kontekstis, kus hooldatakse süsteemi vastupidavust häiredele või katkestustele.

Graafiteoorias on ühenduvus keskne mõiste. Kaudse definitsiooni järgi on grafi ühendatud, kui iga paar tipu vahel on tee; täpsemalt eristatakse kaks mõõdet: tipukinnituvus κ(G) ja joonkinnituvus λ(G). Tipukinnituvus on minimaalne arv tippe, mida eemaldades graaf ei ole enam ühendatud (või muudetakse eraldatuks). Joonkinnituvus on minimaalne arv servi, mille eemaldamine eraldab graafi. Mõlemad mõõdud on alati väiksema või võrdse graafi minimaalsete kraadidega δ(G), ning kehtib alati κ(G) ≤ λ(G) ≤ δ(G).

Näited: täielik graaf K_n omab κ(K_n) = λ(K_n) = n−1. Puud (tree) puhul on κ(G) = λ(G) = 1; igal hõlpsasti katkestataval lõimal on olemas üks katkestav tüüp serv või tipp. Sellised omadused peegeldavad graafi vastupidavust.

Rakendused ja hindamine: ühenduvust hinnatakse arvutites ja suutlikkuse analüüsis. Ühenduvuse kontrollimiseks kasutatakse DFS- või BFS-põhiseid meetodeid, ning min-katke probleeme lahendatakse näiteks Stoer-Wagneri algoritmiga. Kõrgem ühenduvus lisab süsteemi katkiskindlust ja näitab, kui palju ressursse on vaja suutmatuse tekkimiseks.

Ajaloo ja teooria taust: kontseptsioon sai varaseks Königsbergi sildade probleemi valguses ja on aluseks tänapäevasele grafoteooriale.