Lõikepunktid

Lõikepunktid on mõiste, mida kasutatakse nii graafiteoorias kui ka üldises topoloogilises ruumis. Graafis on lõikepunkt tipp, mille eemaldamine koos selle külge kuuluvate servadega eraldab graafi vähemalt kaheks sõltumatuks osaks. Topoloogilises mõttes on lõikepunkt punkt, mille eemaldamine eraldab ruumi kaheks või enamaks ühenduvuse komponendiks.

Graafis on lõikepunkt tipp v, kui graaf G − v ei ole ühendatud. See tähendab, et eksisteerib vähemalt kaks ühenduvust nõrka alamhulka, mille vahel ei ole teed, mis ei läiks läbi v. Juur (DFS-i alguspunkt) on lõikepunkt, kui tal on rohkem kui üks laps DFS-puu tremis, või kui mõnel alampuuu korral ei pääse ükski tee juurde vanemast esivanemani.

Lõikepunktid on tihedalt seotud blokide mõistega. Blokkideks nimetatakse maksimaalseid alamsubu, mis on 2-ühenduvad (ei sisalda lõikepunkte). Lõikepunktid ühendavad need blokid ning graafi struktuuri kirjeldab blokide–lõikepunktide puu (block-cut tree). Selline jaotus aitab mõista graafi ühenduvust ja selle kriitilisi punkte.

Arvutuslikult leitakse lõikepunktid sageli sügavusef, DFS-analüüsi abil. Tarjani algoritm kasutab kahte väärtust: tin (avastamise aeg) ja low (minimaalne tin-aeg, mida alamhau sildist saab jõuda kasutades ainult nende sõlmede servu). Tipp on lõikepunkt, kui mõnel lapsel on low[laps] >= tin[v], ja juur on lõikepunkt, kui tal on vähemalt kaks DFS-lasti. Tehnika töötab O(n + m) ajal graafi puhul.

Näited: P4-joonis sisaldab sisemisi tippe kui lõikepunkte; otsad ei ole. Tsükliline graaf Cn ei sisalda lõikepunkte. Lõikepunktide mõiste on oluline võrkude usaldusväärsuse hindamisel ja graafi struktuuri analüüsil.