Conexitate

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În matematică, conexitatea este proprietatea unui obiect matematic de a consta, într-un anume sens, „dintr-o singură bucată” (este integru). Când un obiect matematic are această proprietate spunem ca el este „conex”. Când un obiect neconex poate fi împărțit în mod natural în părți conexe, fiecare astfel de bucată este numită „componentă” (sau „componentă conexă”).

Conexitatea în topologie[modificare | modificare sursă]

Un spațiu topologic se numește „spațiu conex” dacă el nu poate fi conținut în două mulțimi deschise nevide și disjuncte. O mulțime este deschisă dacă nu conține niciun punct de pe marginea sa; astfel, într-un sens intuitiv, neformal, faptul că un spațiu poate fi împărțit în două mulțimi deschise disjuncte sugerează că limita dintre cele două mulțimi nu este parte a spațiului, și deci îl împarte în două bucăți separate.

Conexitatea în teoria grafurilor[modificare | modificare sursă]

Grafuri neorientate[modificare | modificare sursă]

În teoria grafurilor, un graf conex este un graf neorientat în care există un drum între oricare două noduri distincte. Un graf neorientat conex care are un nod cu proprietatea că dacă acel nod este eliminat (împreună cu muchiile adiacente), graful își pierde proprietatea de conectivitate, se numește „1-conex”. Similar, un graf este „2-conex” dacă pentru a-i elimina proprietatea de conexitate este nevoie de eliminarea a două noduri. În general, dacă pentru a obține un graf neconex dintr-un graf conex este nevoie să se elimine cel puțin n noduri (cu muchiile adiacente lor), atunci graful conex inițial este „n-conex”.

Grafuri orientate[modificare | modificare sursă]

În cazul grafurilor orientate există două noțiuni asociate cu noțiunea generală de conexitate. Un graf orientat este „slab conex” dacă, înlocuindu-i toate arcele cu muchii, transformându-l astfel într-un graf neorientat, graful neorientat astfel obținut este conex. Un graf orientat este „tare conex” dacă, oricare ar fi două noduri ale acestuia u și v, există drum și de la u la v, și de la v la u.