ühenduvusklassid

Ühenduvusklassid on jaotused, mis tekivad ühenduvuse alusel. Graafiteoorias ja topoloogias moodustavad need klassid maksimaalseid ühendatud alamhulki; iga element kuulub täpselt ühte klassi ja erinevad klassid on omavahel disjunktid. Ühenduvusklassid aitavad kirjeldada, kuidas komponendid graafis või ruumis on omavahel ühendatud.

Graafide kontekstis: G = (V,E). Kahe tipu u,v vahel defineeritakse seos u ~ v, kui nende vahel leidub tee graafis. See on ekvivalentsusrelatsioon ja selle ekvivalentsusklassid on ühenduvusklassid, ehk ühendatud komponendid. Iga klass on maksimaalne ühendatud alamhulk; kogu V jaguneb klassideks. Lõpptulemuseks on graafi ühenduvuse arv ehk ühenduvusklasside arv.

Topoloogias: ruumi X ühenduvusklassid on maksimaalsed ühendatud alamhulgad; iga punkt kuulub täpselt ühte klassi; klassid on omavahel disjunktid ja nende ühisus on kogu ruum. Kui X koosneb mitmest komponendist, siis on nende arv sama palju ühenduvusklasse.

Arvutamine: ühenduvusklasside leidmiseks kasutatakse tavaliselt BFS- või DFS-otsingut: vali algtipp ja märgi kõik selle klassi punktid, seejärel jätka järgmise märkimata tipuga. Korda, kuni kõik tipud on klassidega märgitud. Suuremate võrkude puhul kasutatakse ka sobivaid dünaamilisi andmestruktuure ühenduvuste jälgimiseks.

Rakendused: võrgustruktuuride analüüs, sotsiaalvõrgud, logistika ja arvutivõrgud. Ühenduvusklassid annavad ülevaate struktuurilisest eraldatusest ning aitavad mõista kommunikatsiooni vooge või katkestusi.