Kétszeresen összefüggő gráf
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ó
szerkesztésEgy 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
szerkesztés| 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
szerkesztés-
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
szerkesztésFordítás
szerkeszté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
szerkesztés- 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
szerkesztés- The tree of the biconnected components Java implementation in the jBPT library (see BCTree class).
