Katkaisupisteet

Katkaisupisteet grafiikassa ovat solmuja, joiden poistaminen kasvattaa erillisten komponenttien määrää. Niitä kutsutaan myös artikulointipisteiksi. Ne ovat kriittisiä piirteitä verkoissa ja verkostovalvonnassa, koska niiden olemassaolo voi kertoa, mitkä solmupisteet ovat välttämättömiä koko verkon yhteydelle.

Määritelmä: Olkoot G = (V,E) grafiikki. Solmu v on katkaisupiste, jos G−v koostuu useammasta kuin yhdestä yhteydestään. Jos G on alussa yhteenliitetty, katkaisupisteen poistaminen tekee verkosta useita komponentteja. Algoritmisesti katkaisupisteitä voidaan löytää syvyyssuuntaisella haulla (DFS) käyttämällä disc- sekä low-arvoja. Juurisolmu on katkaisupiste, jos sillä on vähintään kaksi DFS-lapsikaarta. Ei-juurilla solmu v on katkaisupiste, jos löytyy lapsi u, jolla low[u] ≥ disc[v]. Tutkimukset voivat hyödyntää myös Tarjanin algoritmia, joka ratkaisee tämän O(V+E)-aikavaatimuksella.

Esimerkki: viiva- tai polkuverkon tapauksessa solmut 2 ja 3 ovat katkaisupisteita, jolloin niiden poisto erottelee verkon useammaksi osaksi. Ympyröity keskeltä poistaa yhteyden loogisesti.

Sovellukset ja liittyvät käsitteet: Katkaisupisteet auttavat arvioimaan verkon luotettavuutta ja suunnittelemaan kriittisiä pistorasioita, kuten infrastruktuurin, tietoverkkojen ja sosiaalisten verkkojen analysoinnissa. Niiden lähellä esiintyy myös ajatuksia siltoista (kappaleen poistaminen voi estää yhteydet) sekä verkkojen osien erottamista bikonnektoituneisiin rakenneosiin.