Gebruiker:Lieven Smits/Kladblok

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 graaf met vijf knopen en zes randen. De knoop $x_{4}$ heeft graad 4 omdat de lus dubbel telt.

Een (ongerichte) graaf bestaat uit een koppel $(V,E)$ van twee verzamelingen waarvan de elementen respectievelijk knopen en randen heten, en een afbeelding die met elke rand één of twee knopen associeert die men de eindpunten van de rand noemt. Het onderliggende model is een tekening van punten in het vlak die met al dan niet kruisende (soms kromme) lijnen verbonden worden. Een rand met slechts één eindpunt is een lus die dat eindpunt met zichzelf verbindt. Verschillende randen mogen dezelfde verzameling eindpunten hebben. Een graaf zonder lussen en waarbij verschillende randen nooit dezelfde twee eindpunten hebben, heet enkelvoudig of simpel.

Een deelgraaf van een graaf wordt gevormd door deelverzamelingen van de knopen en randen, waarbij de eindpunten van de randen nog steeds tot de knopenverzameling moeten behoren.

De graad van een knoop is het aantal keer dat die knoop als eindpunt van een rand optreedt, waarbij een lus tweemaal geteld wordt.

Connectiviteit

Een samenhangende graaf met knopenconnectiviteit 2. Als eender welke afzonderlijke knoop met bijhorende randen wordt weggelaten, blijft het resultaat samenhangend; maar als zowel de uiterst linkse als de uiterst rechtse knoop worden weggelaten, blijft een onsamenhangende graaf met 3 componenten over. De randenconnectiviteit van deze graaf is eveneens 2.

Een pad tussen twee knopen $v_{1}$ en $v_{2}$ is een eindige rij randen $e_{1},e_{2},\ldots ,e_{n}$ waarbij twee opeenvolgende randen $e_{i}$ en $e_{i+1}$ telkens een gemeenschappelijk eindpunt hebben 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 rand worden als samenhangend beschouwd. Een graaf met minstens twee knopen en zonder randen 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 randen 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 randenconnectiviteit van een samenhangende graaf is het kleinste aantal randen dat moet verwijderd worden om een onsamenhangende graaf te bekomen. De randenconnectiviteit van een graaf met minstens twee knopen kan niet groter zijn dan het minimum van de graden van alle knopen: als alle randen met als eindpunt één knoop met minimale graad worden weggelaten, blijft die knoop namelijk geïsoleerd over.

Een randensnede is een deelverzameling van $E$ die, als ze uit de graaf verwijderd wordt, resulteert in een onsamenhangende graaf. De randenconnectiviteit is het aantal elementen van de kleinste randensnede.

Eigenschappen

Als in een enkelvoudige graaf elke knoop graad 3 heeft (een zgn. kubische graaf), dan zijn de randenconnectiviteit 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 1927) Gegeven twee knopen die niet rechtstreeks met een rand 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 randenconnectiviteit en randensnedes.

Communicatienetwerken

Een volledige graaf op 4 knopen heeft 6 randen. Elke knoop heeft graad 3.

Een boom met 8 knopen en 7 randen. Er zijn eindknopen met graad 1 en tussenliggende knopen met graad 2 of meer. De samenhang gaat verloren bij het verwijderen van een rand of een tussenknoop, maar niet bij het verwijderen van een eindknoop.

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 randen van de graaf rechtstreekse communicatielijnen voorstellen. In dat geval geven de knopenconnectiviteit en de randenconnectiviteit twee verschillende numerieke evaluaties van de robuustheid van het netwerk; als de randenconnectiviteit 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 randen. Als er $n$ knopen zijn, dan vertrekken uit elke knoop $n-1$ randen en het totale aantal randen 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 randenconnectiviteit is $n-1.$ Dit is het duurste en ook het meest robuuste netwerk.

Een (ongerichte) boom is een samenhangende graaf met een minimaal aantal randen ($n-1$ als het aantal knopen $n$ is). Een boom met minstens 2 knopen, en dus minstens 1 rand, heeft randenconnectiviteit 1: het verwijderen van eender welke rand 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.

Bronnen

• (en) Balakrishnan, R., Ranganathan, K. (2012). A Textbook of Graph Theory, 2de uitgave. Springer Universitext, New York. ISBN 978-1-4614-4528-9.
• (en) Bollobás, Béla (1998). Modern Graph Theory. Springer Graduate Texts in Mathematics 184. ISBN 978-0-387-98488-9.
• (en) Diestel, Reinhard (2017). Graph Theory, 5de uitgave. Springer Graduate Texts in Mathematics 173. ISBN 978-3-662-53621-6.