# Connectiviteit (grafentheorie)

In verschillende takken van wetenschap en technologie slaat de term connectiviteit op de mate waarin een structuur onderlinge samenhang vertoont. Wiskundige modellen van connectiviteit worden meestal ontleend aan de grafentheorie of soms aan de topologie.

## Wiskundige definitie
### Graaf

Een (ongerichte) graaf bestaat uit een koppel $(V,E)$ van twee verzamelingen waarvan de elementen respectievelijk knopen en zijden heten, en een afbeelding die met elke zijde één of twee knopen associeert die men de eindpunten van de zijde noemt. Het onderliggende model is een tekening van punten in het vlak die met al dan niet kruisende (soms kromme) lijnen verbonden worden. Een zijde met slechts één eindpunt is een lus die dat eindpunt met zichzelf verbindt. Verschillende zijden mogen dezelfde verzameling eindpunten hebben. Een graaf zonder lussen en waarbij verschillende zijden nooit dezelfde twee eindpunten hebben, heet enkelvoudig of simpel.
Een deelgraaf van een graaf wordt gevormd door deelverzamelingen van de knopen en zijden, waarbij de eindpunten van de zijden nog steeds tot de knopenverzameling moeten behoren.
De graad van een knoop is het aantal keer dat die knoop als eindpunt van een zijde optreedt, waarbij een lus tweemaal geteld wordt.

### Connectiviteit

Een pad tussen twee knopen $v_{1}$ en $v_{2}$ is een eindige rij zijden $e_{1},e_{2},\ldots ,e_{n}$ waarbij twee opeenvolgende zijden $e_{i}$ en $e_{i+1}$ telkens één gemeenschappelijk eindpunt hebben, waarbij geen enkele knoop als eindpunt van 3 of meer zijden fungeert, en waarbij $v_{1}$ een eindpunt is van $e_{1}$ en $v_{2}$ een eindpunt van $e_{n}.$
Een graaf is samenhangend als tussen elk paar knopen een pad bestaat. De lege graaf en een graaf met één zijde worden als samenhangend beschouwd. Een graaf met minstens twee knopen en zonder zijden is onsamenhangend. Een component is een maximale samenhangende deelgraaf.
De knopenconnectiviteit van een samenhangende graaf is het kleinste aantal knopen dat moet verwijderd worden om een onsamenhangende graaf te bekomen. De definitie van een graaf vereist dat bij die operatie ook de zijden verwijderd worden waarvan een of beide eindpunten verwijderd zijn.
Een knopensnede is een deelverzameling van $V$ die, als ze uit de graaf verwijderd wordt, resulteert in een onsamenhangende graaf. De knopenconnectiviteit is het aantal elementen van de kleinste knopensnede.
De zijdenconnectiviteit van een samenhangende graaf is het kleinste aantal zijden dat moet verwijderd worden om een onsamenhangende graaf te bekomen. De zijdenconnectiviteit van een graaf met minstens twee knopen kan niet groter zijn dan het minimum van de graden van alle knopen: als alle zijden met als eindpunt één knoop met minimale graad worden weggelaten, blijft die knoop namelijk geïsoleerd over.
Een zijdensnede is een deelverzameling van $E$ die, als ze uit de graaf verwijderd wordt, resulteert in een onsamenhangende graaf. De zijdenconnectiviteit is het aantal elementen van de kleinste zijdensnede.

### Eigenschappen

Als in een enkelvoudige graaf elke knoop graad 3 heeft (een zgn. kubische graaf), dan zijn de zijdenconnectiviteit en de knopenconnectiviteit gelijk.
(Whitney) Bij een graaf met minstens 3 knopen is de knopenconnectiviteit minstens 2 als en slechts als elk paar knopen verbonden kan worden door minstens 2 paden die geen knopen (buiten de eindpunten) gemeenschappelijk hebben.
(Menger) Gegeven twee knopen die niet rechtstreeks met een zijde verbonden zijn, dan is het minimaal aantal knopen dat uit de graaf moet verwijderd worden om de twee knopen te scheiden gelijk aan het maximaal aantal paden tussen de twee knopen die onderling geen knopen (buiten de eindpunten) gemeenschappelijk hebben.
Van de stellingen van Whitney en Menger bestaan ook varianten over zijdenconnectiviteit en zijdensnedes.

## Communicatienetwerken

Bij het ontwerp van een communicatienetwerk is de topologie een compromis tussen robuustheid en kost: meer onderlinge verbindingen verhogen de installatie- en onderhoudskost van het netwerk, maar verminderen de kwetsbaarheid voor plaatselijke onderbrekingen. Veel communicatieprotocollen, zoals IP bij computernetwerken, voorzien in alternative routeringen van de berichten naargelang van de wisselende beschikbaarheid van tussenstations.
De verbindingen tussen de diverse communicatiepartners kunnen worden voorgesteld door een graaf, waarbij de zijden van de graaf rechtstreekse communicatielijnen voorstellen. In dat geval geven de knopenconnectiviteit en de zijdenconnectiviteit twee verschillende numerieke evaluaties van de robuustheid van het netwerk; als de zijdenconnectiviteit 1 is, dan volstaat een breuk in één communicatielijn om twee delen van het netwerk van elkaar te isoleren. Als de knopenconnectiviteit 1 is, dan kan een overbelasting van één server het netwerk effectief stilleggen.
De twee extreme gevallen zijn de volledige graaf en een boom. Bij een volledige graaf is elke knoop rechtstreeks verbonden met elke andere knoop. Voor een enkelvoudige graaf is dit het hoogst mogelijke aantal zijden. Als er $n$ knopen zijn, dan vertrekken uit elke knoop $n-1$ zijden en het totale aantal zijden is $n(n-1)/2.$ De knopenconnectiviteit is dan gelijk aan $n:$ hoeveel knopen je ook verwijdert, de resulterende graaf is nog steeds volledig (op een kleiner aantal knopen) en dus samenhangend. De zijdenconnectiviteit is $n-1.$ Dit is het duurste en ook het meest robuuste netwerk.
Een (ongerichte) boom is een samenhangende graaf met een minimaal aantal zijden ($n-1$ als het aantal knopen $n$ is). Een boom met minstens 2 knopen, en dus minstens 1 zijde, heeft zijdenconnectiviteit 1: het verwijderen van eender welke zijde maakt de resulterende graaf onsamenhangend. De knopenconnectiviteit is 1 als het aantal knopen $n$ minstens 3 bedraagt. Dit is de goedkoopste, maar ook de kwetsbaarste manier om $n$ communicatiepartners met elkaar te verbinden.