Sillat ja artikulaatiopisteet

Annettuna on suuntaamaton yhtenäinen verkko, jossa on n solmua ja m kaarta. Sanomme, että verkon kaari on silta, jos kaaren poistamisen jälkeen jonkin kahden solmun välillä ei ole polkua, ja verkon solmu on artikulaatiopiste, jos solmun (ja siihen liittyvien kaarten) poistamisen jälkeen jonkin kahden solmun välillä ei ole polkua. Jos verkossa ei ole yhtään artikulaatiopistettä, sanomme myös, että se on 2-yhtenäinen.

Tarkastellaan esimerkkinä seuraavaa verkkoa:

Tässä verkossa kaaret (4,5) ja (7,8) ovat siltoja ja solmut 4, 5 ja 7 ovat artikulaatiopisteitä.

Voimme löytää verkon sillat ja artikulaatiopisteet tehokkaasti syvyyshaun avulla. Aloitamme syvyyshaun jostakin solmusta, jolloin se muodostaa puun verkon solmuista. Puu sisältää kaaret, joita pitkin saavuimme uusiin solmuihin syvyyshaun aikana. Esimerkissämme muodostuu seuraava puu, kun aloitamme solmusta 5:

Syvyyshaku luokittelee kaaret kahteen ryhmään: puukaari on kaari, joka vie uuteen solmuun syvyyshaun aikana (merkitty yhtenäisesti kuvassa), ja takautuva kaari on kaari, joka osoittaa takaisin ylempänä puussa olevaan solmuun (merkitty katkoviivoin kuvassa).

Puukaari ab vastaa siltaa, jos solmun b alipuusta ei pääse takautuvaa kaarta pitkin solmuun a tai johonkin solmun a esivanhempaan. Esimerkissämme kaari 5 → 4 vastaa siltaa, koska solmun 4 alipuusta ei pääse takautuvaa kaarta pitkin solmuun 5 tai sen esivanhempaan.

Solmu x on artikulaatiopiste, jos (1) se on puun juuri ja sillä on kaksi tai enemmän lapsia tai (2) se ei ole puun juuri ja sillä on lapsi, jonka alipuusta ei pääse takautuvaa kaarta pitkin solmun x esivanhempaan. Esimerkissämme solmu 5 on artikulaatiopiste, koska se on puun juuri ja sillä on kaksi lasta, ja solmu 7 on artikulaatiopiste, koska sillä on lapsi 8, jonka alipuusta ei pääse takautuvaa kaarta pitkin solmun 7 esivanhempaan.

Pystymme siis selvittämään sekä sillat että artikulaatiopisteet syvyyshaulla ajassa O(n+m).