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 +Nem szétválasztható (kétszeresen összefüggő) gráfok n csúccsal Csúcsok Lehetőségek száma 1 0 2 1 3 1 4 3 5 10 6 56 7 468 8 7123 9 194066 10 9743542 11 900969091 12 153620333545 13 48432939150704 14 28361824488394169 15 30995890806033380784 16 63501635429109597504951 17 244852079292073376010411280 18 1783160594069429925952824734641 19 24603887051350945867492816663958981

Példák

Kapcsolódó szócikkek Kétszeresen összefüggő komponens

Fordítás

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 [online], 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).

Kategória:Gráfcsaládok Kategória:Gráfok összefüggősége