A matematika, azon belül a gráfelmélet területén egy kétszeresen összefüggő gráf (biconnected graph) összefüggő és „nem szétválasztható”, ami azt jelenti, hogy bármely csúcsot eltávolítva a gráf összefüggő marad. Tehát egy kétszeresen összefüggő gráfnak nincsenek elvágó (artikulációs) csúcsai.

A 2-összefüggő gráf fogalma a kétszeresen összefüggő gráféval csaknem ekvivalens, azzal az eltéréssel, hogy a két csúcsból és egy élből álló teljes gráfot néha úgy tekintik, mint ami kétszeresen összefüggő, de nem 2-összefüggő.

Ez a tulajdonság különösen hasznos redundanciával rendelkező hálózati folyamok fenntartásához, melyek nem szakadnak meg egyetlen él (kapcsolat) megszűntével.

Definíció

Egy kétszeresen összefüggő irányítatlan gráf olyan összefüggő gráf, melyet egyetlen csúcs (és a hozzákapcsolódó élek) eltávolításával nem lehet több darabra szétszedni.

Egy kétszeresen összefüggő irányított gráfban bármely két v és w csúcshoz tartozik két irányított út v-ből w-be, melyek nem tartalmaznak a 'v-n és w-n kívül más közös csúcsot.

Leszámlálás

Példák

• 
  Kétszeresen összefüggő gráf négy csúccsal és négy éllel
• 
  Nem kétszeresen összefüggő gráf. Az x csúcs eltávolítása után a gráf szétesne.
• 
  Kétszeresen összefüggő gráf öt csúccsal és hat éllel
• 
  Nem kétszeresen összefüggő gráf. Az x csúcs eltávolítása után a gráf szétesne.

Kapcsolódó szócikkek

• Kétszeresen összefüggő komponens

Fordítás

• Ez a szócikk részben vagy egészben a Biconnected graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Eric W. Weisstein. "Biconnected Graph." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/BiconnectedGraph.html
• Paul E. Black, "biconnected graph", in Dictionary of Algorithms and Data Structures , Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html

További információk

• The tree of the biconnected components Java implementation in the jBPT library (see BCTree class).