2connectiviteit

2connectiviteit, in het Nederlands vaak biconnectiviteit genoemd, is een eigenschap van een verbonden grafiek die de robuustheid tegen wegvallen van knopen beschrijft. Een graf is 2connectief als het verbonden blijft na verwijdering van elke afzonderlijke knoop.

Een equivalente definitie zegt dat de graf geen knoop heeft die bij verwijdering de graf in twee of meer componenten splitst; zo'n knoop heet een articulation point. Een 2-verbonden graf bevat daarom geen articulation point. Een 2-verbonden graf vereist minimaal drie knopen.

Daarnaast geldt dat voor elk paar knopen er twee vertex-disjoint paden tussen hen bestaan (volgens Menger's theorem). Dit geeft aan dat er sprake is van redundante, onafhankelijke paden tussen elk paar knopen.

Voorbeelden: circulaire grafen Cn met n ≥ 3 en volledige grafen Kn met n ≥ 3 zijn 2-connected; K2 is dat niet. Een 2-connected component is een maximale subgraf die zelf 2-connected is. Een verbonden graf kan worden opgesplitst in deze componenten, die onderling verbonden zijn via articulation points. De verzameling van componenten vormt samen een blok-structuur van de graf.

Detectie en algoritmen: met een diepte-eerstzoektocht (DFS) kun je articulation points opsporen. Als de graf verbonden is en geen articulation point bevat, is deze 2-connected. Tarjan-achtige algoritmen worden gebruikt om in lineaire tijd alle articulation points en de 2-connected componenten te vinden.

Relaties: 2-connectiviteit impliceert 2-edge-connectiviteit (verwijdering van één rand laat de graf verbonden), maar omgekeerd geldt dit niet altijd. Toepassingen bevinden zich in netwerkontwerp en betrouwbaarheidstoepassingen, waar redundantie van paden en veerkracht tegen knooppuntuitval centraal staan.