matematikai fogalom a gráfelméletben From Wikipedia, the free encyclopedia
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.
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.
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 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.