Tämän viikon tehtävien aiheena on etsiä syvyyshaun avulla verkosta kaaria ja solmuja, joiden poistaminen jakaa verkon osiin.

Käsitteitä

Verkko on 2-yhtenäinen, jos se säilyy yhtenäisenä, vaikka siitä poistetaan mikä tahansa yksittäinen solmu ja siihen liittyvät kaaret.

Esimerkiksi seuraavassa kuvassa vasen verkko on 2-yhtenäinen, mutta oikea verkko ei ole, koska solmun $3$ poistaminen jakaa sen kahteen osaan.

Verkossa oleva kaari on silta, jos sen poistaminen jakaa verkon osiin, ja verkossa oleva solmu on artikulaatiopiste, jos sen poistaminen jakaa verkon osiin.

Esimerkiksi seuraavassa verkossa kaaret $4$–$5$ ja $7$–$8$ ovat siltoja ja solmut $4$, $5$ ja $7$ ovat artikulaatiopisteitä.

Kaarten luokittelu

Kun syvyyshaku käy läpi verkon solmut tietystä solmusta alkaen, syntyy puu, jonka avulla verkon kaaria voidaan luokitella. Jokainen kaari on joko puukaari, joka kulkee uuteen solmuun, tai takautuva kaari, joka palaa takaisin aiempaan solmuun.

Seuraavassa kuvassa on verkko ja sitä vastaava puu solmusta $1$ alkaen. Yhtenäiset viivat kuvaavat puukaaret ja katkoviivat kuvaavat takautuvat kaaret.

Algoritmit

Voimme tunnistaa syvyyshaun tuottamasta puusta verkon sillat ja artikulaatiopisteet. Tarkastellaan seuraavaa puuta, joka vastaa ylempänä esiintynyttä verkkoa:

Puussa oleva kaari $a \rightarrow b$ vastaa siltaa, jos se on puukaari eikä solmun $b$ alipuusta ole takautuvaa kaarta solmuun $a$ eikä mihinkään solmun $a$ esivanhempaan. Yllä olevassa verkossa esimerkiksi kaari $5 \rightarrow 4$ vastaa siltaa, koska solmun $4$ alipuusta ei ole takautuvaa kaarta solmuun $5$ eikä sen esivanhempaan.

Puussa oleva solmu $x$ on artikulaatiopiste kahdessa tapauksessa. Ensinnäkin jos solmu $x$ on juuri, se on artikulaatiopiste tarkalleen silloin, kun sillä on kaksi tai useampia lapsia. Jos taas solmu $x$ ei ole juuri, se on artikulaatiopiste, jos sillä on lapsi, jonka alipuussa ei ole takautuvaa kaarta solmun $x$ esivanhempaan. Yllä olevassa verkossa solmu $5$ on artikulaatiopiste, koska se on juuri ja sillä on kaksi lasta. Solmu $4$ on puolestaan artikulaatiopiste sen vuoksi, että sen lapsen $2$ alipuussa ei ole takautuvaa solmua solmun $4$ esivanhempaan.

Tällä tavalla voimme etsiä sekä verkon sillat että artikulaatiopisteet tehokkaasti lineaarisessa ajassa suorittamalla syvyyshaun jostakin solmusta.