I grafteori sies en tilkoblet graf "å være k - toppunkt-koblet hvis den har minst k + 1 hjørner og hvis den fortsatt forblir tilkoblet etter å ha fjernet k - 1" .
En annen graf enn en fullstendig graf er av vertex- tilknyttet grad k hvis den er k -connected-vertex uten å være k + 1 -connected-vertex, så hvis k er størrelsen på den minste delmengden av hjørner hvis sletting frakobler grafen. Fullstendige grafer er ikke inkludert i denne versjonen av definisjonen fordi de ikke kan kobles fra ved å fjerne hjørner. Den komplette grafen med n hjørner er av graden av sammenheng n-1 .
En ekvivalent definisjon er at en graf med minst to hjørner er k -connected-vertex, for hvert par av sine hjørner er det k uavhengige kjeder som forbinder disse hjørnene; dette er Mengers teorem . Denne definisjonen gir det samme svaret n - 1, for tilkoblingen til den komplette grafen K n .
En 1-toppunkt-koblet graf kalles en koblet graf ; en to-toppunkt-koblet graf og kalt en to-koblet graf . En 3-koblet graf kalles også en trikoblet.
En vanlig graf av grad k er maksimalt k -connected-vertex og k - connected-edge . Hvis det virkelig er k -connected-top og k -connected-edge, sies det å være optimalt koblet .
Den Biggs-Smith graf er 3-regulær, 3-toppunkt-koblet og 3-kant-tilkoblet: den er optimalt koblet til.
Den mølle Grafen Wd (5,4) ikke lenger er tilkoblet hvis vi fjerner den sentrale topp-punkt: det er en verteks-koblet.
Den komplette grafen K 6 er 5-toppunkt-koblet.
Antall enkle toppunktforbundne grafer med hjørner fra 1 til 9, med referanse til OEIS :
\ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | OEIS |
---|---|---|---|---|---|---|---|---|---|---|
Total | 1 | 2 | 4 | 11 | 34 | 156 | 1044 | 12346 | 274668 | A000088 |
1 | 1 | 1 | 2 | 6 | 21 | 112 | 853 | 11117 | 261080 | A001349 |
2 | 0 | 1 | 1 | 3 | 10 | 56 | 468 | 7123 | 194066 | A002218 |
3 | 0 | 0 | 1 | 1 | 3 | 17 | 136 | 2388 | 80890 | A006290 |
4 | 0 | 0 | 0 | 1 | 1 | 4 | 25 | 384 | 14480 | A086216 |
5 | 0 | 0 | 0 | 0 | 1 | 1 | 4 | 39 | 1051 | A086217 |
6 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 5 | 59 | |
7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 5 |
Antall enkle, nøyaktig toppunktforbundne grafer med hjørner:
\ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | OEIS |
---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 5 | 1. 3 | 44 | 191 | 1229 | 13588 | |
1 | 1 | 0 | 1 | 3 | 11 | 56 | 385 | 3994 | 67014 | A052442 |
2 | 0 | 1 | 0 | 2 | 7 | 39 | 332 | 4735 | 113176 | A052443 |
3 | 0 | 0 | 1 | 0 | 2 | 1. 3 | 111 | 2004 | 66410 | A052444 |
4 | 0 | 0 | 0 | 1 | 0 | 3 | 21 | 345 | 13429 | A052445 |
5 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 34 | 992 | |
6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 4 | 54 |