skærepunkter

Skærepunkter, eller cut points, er et begreb inden for topologi og grafteori. I topologi defineres et punkt x i et sammenhængende rum X som et skærepunkt hvis X uden {x} ikke længere er sammenhængende. Med andre ord, fjernelsen af x opdeler rummet i mindst to separate sammenhængende dele.

Inden for grafteori omtales et skærepunkt også som en articulation point. G er en sammenhængende graf; et vertex v er et skærepunkt hvis fjernelsen af v øger antallet af sammenhængende komponenter i grafen.

Et klassisk eksempel i topologi er intervallet [0,1]. Enhver indre punkt virker som skærepunkt, fordi fjernelse af et sådant punkt splitter intervallet i to adskilte dele; endepunkterne 0 og 1 er ikke skærepunkter i denne forstand. Cirkelens topologi S^1 derimod har ingen skærepunkter; fjernelse af et punkt efterlader en sammenhængende kurve (en åben bue).

Væsentligt er, at ikke alle sammenhængende rum har skærepunkter. Rum kan have få eller mange skærepunkter afhængig af deres struktur. I grafiske netværk kan skærepunkter bruges til at vurdere netværkets robusthed: et netværk er mest kritisk hvis det indeholder få eller centrale skærepunkter; identifikation sker ofte ved dybde-første gennemgang og algoritmer til at finde articulation points.

Anvendelser af begrebet findes i netværksdesign og analyse, i studier af kontinua og i teorier om opdeling af rum.