Sillad, artikulatsioonipunktid ja DFS-puu

Vaata ka 2020. aasta materjali ja originaalset blogi.

1. Sillad ja artikulatsioonipunktid

1.1. Mõisted

Vaatleme suunamata sidusat graafi \(G\), millel on \(n\) tippu ja \(m\) serva.

• Sillaks (ingl. bridge) nimetatakse serva, mille eemaldamisel graaf enam sidus ei ole.
• Artikulatsioonipunktiks (ingl. articulation point või cut vertex) nimetatakse tippu, mille eemaldamisel graaf enam sidus ei ole.

Meie esimene eesmärk on töötada välja algoritm, mis leiab graafi kõik sillad ja artikulatsioonipunktid \(O(n + m)\) ajas.

1.2. DFS-puu

Selleks on parem alustada pisut kaugemalt. Võtame selle graafi ja jooksutame selle peal tavalist sügavuti läbimist.

function dfs (u):
    visited[u] = 1
    for (all neighbors v of u):
        if not visited[u]:
        mark the edge uv
        call dfs(v)

Näiteks dfs(1) välja kutsumine näeb välja nii:

1 / 23

❮

❯

Vaatleme real 5 märgistatud servi. Nad moodustavad graafi \(G\) toespuu, juurega 1. Kutsume märgistatud servi toeservadeks (ingl. span-edge) ja ülejäänud servi naasvateks servadeks (ingl. back-edge). Kui graafi pisut ümber tõsta, näeb see välja nii:

Näiteks ülevalolevas graafis ei saaks kuidagi tippude 4 ja 8 vahel olla naasvat serva, sest kumbki ei ole teise eellane. Kui tippude 4 ja 8 vahel oleks olnud serv, siis oleks sügavuti läbimise käigus tipust 4 tippu 2 naasmise asemel liigutud tippu 8.

1.3. Sillaks ja artikulatsioonipunktiks olemise tingimused DFS-puu terminites

Vaatleme esiteks sildu. Esiteks võime tähele panna, et ükski naasev serv ei ole kunagi sild. Tõepoolest: isegi kui me eemaldaksime kõik naasvad servad, oleks graaf siiski sidus, kuna tema toeservad moodustavad ju toesepuu. Niisiis peame sildade jaoks kandidaate otsima ainult toeservade seast.

Tõestus. Serva \(uv\) eemaldamine lõhub toespuu kaheks sidususkomponendiks: \(uv\) alampuu ja ülejäänud toespuu. Kui nende komponentide vahel on serv, siis on graaf sidus, vastasel juhul on \(uv\) sild. Ainus viis, kuidas naasev serv need kaks sidususkomponenti ühendada saab on \(uv\) eellase ühendamine \(uv\) järglasega.

Artikulatsioonipunktidega on pisut keerulisem. Esiteks peame eraldi vaatlema puu juurt ja ülejäänud tippe.

Vaatleme mõnd tippu \(u\), mis ei ole puu juur. Tal on DFS-puus vanem \(p\) ning mõned lapsed \(v_1, v_2, \ldots, v_k\). Teame DFS-puu omaduste tõttu, et graafis ei ole mingeid teekondi \(v_i \leadsto v_j\), mis ei läbi tippu \(u\). Seega, kui eemaldame \(u\) ja graaf jääb sidusaks, peab iga last \(v_i\) graafi küljes hoidma mõni naasev serv, mis ühendab \(v_i\) või mõnd tema järglast tipu \(p\) või mõne tema eellasega. Niisiis on selline tipp artikulatsioonipunkt parajasti siis, kui tal on vähemalt üks laps \(v\), mille alampuust ei ole ühtki naasvat serva tippu \(p\) või mõnda selle eellasesse.

Juurega on asi lihtsam. Tegu on artikulatsioonipunktiga parajasti siis, kui tal on vähemalt kaks last.

1.4. Tuvastamine ("lowlink meetod") ja implementatsioon

Nüüd vaatame, kuidas neid asju implementeerida ja kuidas kõige lihtsamini koodis neid tingimusi kontrollida. On oluline mainida, et kõik siit edasi toodu on implementatsioonidetail, sealhulgas massiivid \(\mathrm{low}\) ja \(\mathrm{ord}\). Mõned arvavad, et klassikalise sildade ja artikulatsioonipunktide leidmise algoritmi kõige tähtsam osa ongi need \(\mathrm{low}\) ja \(\mathrm{ord}\) (mis me varsti sisse toome). See ei ole nii. \(\mathrm{ord}\) asemel võib kasutada mis iganes massiivi, kus iga tipu indeks on oma vanema omast suurem ja ka \(\mathrm{low}\) kasutamisest saab ümber. Ainus põhjus, miks ma üldse \(\mathrm{ord}\) kasutan on teiste õpetustega "ühilduvuse jaoks", sest kõik teised kasutavad seda. Algoritmi iva on DFS-puus ja ülal toodud tingimustes.

vector<int> adj [MAX_N];
int ord [MAX_N];

void dfs (int u, int &cur) {
    cur++;
    ord[u] = cur;

    for (int nxt : adj[u]) {
        if (ord[nxt] == 0) {
            // külastamata tipp
            dfs(nxt, cur);
        }
    }
}

Eeltoodud DFS korral näevad need \(\mathrm{ord}\) väärtused välja nii:

Ülaltoodud tingimuste kontrollimiseks on meil vaja mingit meetodit selle kontrollimiseks, kas mingi tipu alampuust läheb naasev serv mingi tipu eellasesse. Selleks toome sisse veel teise massiivi \(\mathrm{low}\). Me defineerime \(\mathrm{low}[u]\) kui kõige kõrgema tipu \(\mathrm{ord}[\cdot]\), millesse on tipu \(u\) alampuust naasev serv, või \(\mathrm{ord}[u]\), kui \(u\) alampuust ei lähe ühtki naasvat serva ühtegi \(u\) eellasesse.

\(\mathrm{low}[u]\) on järgnevate arvude miinimum:

• \(\mathrm{ord}[u]\)
• \(\mathrm{low}[v]\) üle \(u\) kõikide laste \(v\)
• \(\mathrm{ord}[w]\) (ja mitte \(\mathrm{low}\)!) üle tipust \(u\) üles minevate naasvate servade \(uw\)

Need väärtused tuleks arvutada "alt üles"; seda võib teha DFS käigus, näiteks nii:

vector<int> adj [MAX_N];
int ord [MAX_N];
int low [MAX_N];

void dfs (int u, int p, int &cur) {
    cur++;
    ord[u] = cur;
    low[u] = ord[u];

    for (int nxt : adj[u]) {
        if (ord[nxt] == 0) {
            // külastamata tipp - laps toesepuus
            dfs(nxt, u, cur);
            low[u] = min(low[u], low[nxt]);
        } else if (ord[nxt] < ord[u] && nxt != p) {
            // üles minev naasev serv
            // serv vanemasse ei loe!
            // (NB: kui graafis on lubatud "mitmekordsed servad" siis see ei toimi)!
            low[u] = min(low[u], ord[nxt]); // ja mitte low[nxt]!
        }
    }
}

Meie puus näevad \(\mathrm{low}\) väärtused välja nii:

Nüüd, kus need väärtused välja on arvutatud vaatame, kuidas neid kasutada. Meenutame, et \(up\) on sild siis ja ainult siis, kui ei leidu naasvat serva, mis ühendab \(up\) mingit järglast \(up\) mingi eellasega. Seega, kui eeldame, et \(p\) on \(u\) vanem, siis tähendab see, et:

Samuti, juurest erinev tipp \(u\) on artikulatsioonipunkt parajasti siis, kui tal on vähemalt üks laps, mille alampuust ei lähe ühtki naasvat serva tipu \(u\) mõnda päriseellasesse (mitte tippu \(u\) endasse!), ehk:

Lõplik kood on siis:

vector<int> adj [MAX_N];
int ord [MAX_N];
int low [MAX_N];

void dfs (int u, int p, int &cur) {
    cur++;
    ord[u] = cur;
    low[u] = ord[u];

    int child_count = 0;
    bool cut_reported = false;
    for (int nxt : adj[u]) {
        if (ord[nxt] == 0) {
            // külastamata tipp - laps toesepuus
            child_count++;
            dfs(nxt, u, cur);
            low[u] = min(low[u], low[nxt]);
            if (low[nxt] >= ord[u] && ord[u] != 1 &&amp !cut_reported) {
                cut_reported = true;
                cout << "ART. PUNKT" << u <&lt endl;
            }
        } else if (ord[nxt] < ord[u] &&amp nxt != p) {
            // üles minev naasev serv
            // serv vanemasse ei loe!
            // (NB: kui graafis on lubatud "mitmekordsed servad" siis see ei toimi)!
            low[u] = min(low[u], ord[nxt]); // ja mitte low[nxt]!
        }
    }

    if (ord[u] != 1 && low[u] == ord[u]) {
        cout << "SILD " << u << " " << p &lt&lt endl;
    }

    if (ord[u] == 1 && child_count > 1) {
        cout << "ART. PUNKT" << u <&lt endl;
    }
}

2. Teisi DFS-puu ülesandeid

DFS-puu ei ole kasulik ainult sildade ja artikulatsioonipunktide leidmiseks. See on väga suur lihtsustus graafi struktuurile: suvaliste servade asemel on meil lihtsalt puu pluss mõned täiendavad servad ülevalt alla. Teatud "struktuursete" probleemide jaoks on see väga kasulik.

2.1. Tugevalt suunamine

Suunatud graafi nimetatakse tugevalt sidusaks, kui igast tipust on võimalik igasse tippu mööda suunatud servi liikuda.

Tõestus. Oletame, et \(uv\) on sild. Üldisust kitsendamata suuname selle \(u \to v\). Siis aga ei saa kuidagi mööda suunatud servi liikuda tipust \(v\) tippu \(u\).

Edasises eeldame niisiis, et graafis ei ole sildu. Vaatleme tema DFS-puud. Suuname kõik toeservad "alla" ja kõik naasvad servad "üles".

Tõestus. Võime lihtsalt mööda toeservi alla liikuda.

Nendest tähelepanekutest järeldub, et graaf on nüüd tugevalt sidus. Põhimõtteliselt on seda lahendust võimalik implementeerida ka ilma otseselt DFS-puud kasutamata. Samas oleks korrektsuse tõestamine (ja ehk ka lahenduse peale tulemine) äärmiselt tülikas.

2.2. Kolm sõltumatut teekonda

Ülejäänud juhtudel on see võimalik. Eeldame, et puu ei ole kaktus. Kasutame DFS-puud, et sellised kolm teekonda leida. Loendame iga toeserva jaoks, mitu naasvat serva temast "üle läheb". Seda saab arvutada "alt üles": iga tipu juures liidame sealt üles minevate naasvate servade arvu ning lahutame sealt alla minevate naasvate servade arvu.

Leidub vähemalt üks toeserv \(st\), millest "läheb üle" kaks erinevat naasvat serva \(ab\) ja \(cd\) (vastasel juhul on tegu kaktusega). Üldisust kitsendamata eeldame, et \(a\) on \(b\) eellane, \(c\) on \(d\) eellane ning \(a\) on \(c\) eellane. Olgu \(l = \mathrm{lca}(b, d)\).

Võtame \(u = c\) ja \(v = l\). Kolm sõltumatut teekonda on:

• \(u = c d \leadsto l = v\) (\(d \leadsto l\) on üles mööda toeservi);
• \(u = c \leadsto a b \leadsto l = v\) (\(c \leadsto a\) ja \(b \leadsto l\) on mõlemad üles mööda toeservi);
• \(u = c \leadsto l = v\) (alla mööda toeservi);

Alljärgneval joonisel on need kolm teekonda märgitud kolme eri värviga.

3. Tsüklite vektorruum*

Seda siin on tõenäoliselt harva päris ülesannetes vaja, aga lisalugemiseks sobib. Sellegipoolest on sarnaseid ideid vahel ülesannetes leidunud.

Olgu \(G = (V, E)\) sidus graaf. Defineerime

See \(\mathcal{C}\) koosneb niisiis \(G\) kõikidest sellistest alamgraafidest \(H\), milles on kõik graafi \(G\) tipud ja osad \(G\) servad, aga nii, et \(H\) iga tipu aste on paaris. Niisiis koosneb \(\mathcal{C}\) kõikidest \(G\) alamgraafidest, millel on Euleri ahel. Mingis mõttes koosneb see kõikidest \(G\) tsüklitest. Tuleb aga arvestada, et seal võib olla ka selliseid alamgraafe, mis koosnevad mitmest lõikumatust tsüklist. Sellegipoolest kutsume hulka \(\mathcal{C}\) graafi \(G\) tsüklite ruumiks (ingl. cycle space).

Kahe \(\mathcal{C}\) elemendi \(H_1\) ja \(H_2\) "summa" \(H_1 \oplus H_2\) koosneb nendest servadest, mis esinevad täpselt ühes neist.

Võtame \(G\) mõne toesepuu \(T\). See võib olla ükskõik milline, aga implementeerimise mugavuse jaoks on hea võtta DFS-puu. Iga \(G\) serv, mis puusse \(T\) ei kuulu, moodustab koos \(T\) servadega tsükli. Neid tsükleid nimetame graafi \(G\) fundamentaalseteks tsükliteks.

Tuleb välja, et suvalist \(\mathcal{C}\) elementi (ja seega suvalist tsüklit) saab esitada fundamentaalsete tsüklite summana, seejuures täpselt ühel viisil. Algebralistes terminites tähendab see, et \((\mathcal{C}, \oplus)\) on vektorruum üle \(\mathbb{F}_2\) ja fundamentaalsed tsüklid on selle vektorruumi baas.

4. Ploki-lõike puu*

Olgu \(G\) sidus suunamata graaf. Plokiks (ingl. block) nimetatakse graafi maksimaalset sellist alamgraafi, milles ei ole (eraldi graafina vaadatuna) ühtki artikulatsioonipunkti. "Maksimaalne" tähendab siin "selline, millesse ei ole võimalik rohkem ühtegi tippu lisada", mitte "suurim võimalik". Alloleval joonisel on toodud üks graaf ja tema plokid.

Tasub tähele panna, et tipp \(a\) on artikulatsioonipunkt, kui vaadelda tervet graafi, aga mitte, kui vaadata ainult joonisel rohelist plokki.

Paneme tähele, et kahe ploki ühisosas on ainult artikulatsioonipunktid. Lisaks paistab, et plokid moodustavad justkui puustruktuuri. Ehitame graafi, mille tippudeks on graafi artikulatsioonipunktid ja plokid. Ploki \(B\) ja artikulatsioonipunkti \(v\) vahel on serv, kui artikulatsioonipunkt \(v\) kuulub plokki \(B\). Nii moodustatud graafi nimetatatakse ploki-lõike puuks (ingl. block-cut tree).

Kuidas aga ploki-lõike puud arvutada? Meenutame, et juurest erinev tipp \(u\) (tähistagu \(p\) tema vanemat) on artikulatsioonipunkt parajasti siis, kui tal leidub vähemalt üks laps \(v_i\) nii, et tipu \(v_i\) alampuust ei lähe ühtki naasvat serva mõnda \(p\) eellasesse. Siis peavad servad \(pu\) ja \(p v_i\) kuuluma ka eri plokkidesse. Seevastu kui \(v_i\) alampuust läheb mõni naasev serv mõnda \(p\) eellasesse, siis on servad \(pu\) ja \(p v_i\) kindlasti samas plokis: too naasev serv moodustab koos toesepuuga tsükli, kuhu kuuluvad ka need servad, ja kuna tsüklis pole artikulatsioonipunkte, sisaldub see mingis plokis. Seega saame puud ehitades mõelda sellele, mis servad on samas plokis ja mis erinevas. Siit saaks mingi konstruktsiooni juba kätte (DSU servadel vmt), aga saab ka elegantsemalt.

Teeme DFS nagu artikulatsioonipunkte leides. Hoiame lisaks meeles aga ka üht pinu stk. Hoiame invarianti, et pärast funktsioonist dfs(u, ...) lahkumist koosneb pinu stk täpselt nendest tippudest, mis on juba läbi käidud ja mis on samas plokis mõne servaga, mis on teekonnal juurest tippu \(u\), läbi käimise järjestuses.

vector<int> adj [MAX_N];
int ord [MAX_N];
int low [MAX_N];

void dfs (int u, int p, int &cur, vector<int> &stk) {
    cur++;
    ord[u] = cur;
    low[u] = ord[u];

    stk.push_back(u);

    int child_count = 0;
    bool cut_reported = false;
    for (int nxt : adj[u]) {
        if (ord[nxt] == 0) {
            // külastamata tipp - laps toesepuus
            child_count++;
            dfs(nxt, u, cur, stk);
            low[u] = min(low[u], low[nxt]);
            if (low[nxt] >= ord[u] && ord[u] != 1 || ord[u] == 1) {
                if (ord[u] != 1 && !cut_reported) {
                    cut_reported = true;
                    cout << "ART. PUNKT" << u <&lt endl;
                }

                // nüüd on teada, et (u nxt) ja (p u) ei ole samas plokis.
                // stk koosneb hetkel kõikidest tippudest, mis kuuluvad
                // samasse plokki ühega servadest (u nxt), (p u), (parent(p) p) jne.
                // välja visata tuleb need, mis on samas plokis servaga (u nxt), v.a. u
                // need on täpselt need, mis on nxt alampuus.
                // kuna pinus on tipud läbi käimise järjestuses, siis nxt on viimane,
                // mis välja visata tuleb.
                // välja visatud tipud pluss u ongi see uus plokk
                vector<int> block;
                while (stk.back() != nxt) {
                    block.push_back(stk.back());
                    stk.pop_back();
                }

                // ...ja nxt ise
                block.push_back(stk.back());
                stk.pop_back();

                // lisaks läheb plokki u
                block.push_back(u);

                // need tuleb ise teha (mis iganes meetodil on hea p-l puud esitada):
                // lisa ploki-lõike puusse uus tipp x mis tähistab plokki block
                // lisa ploki-lõike puus serv x ja kõikide art. punktide vahele, mis
                // plokki kuuluvad (selleks tuleb meelde jätta, mis olid art. punktid)
                // pane tähele, et juurtipp ei ole selleks hetkeks veel
                // artikulatsioonipunktiks märgitud!
             }
        } else if (ord[nxt] < ord[u] &&amp nxt != p) {
            // üles minev naasev serv
            // serv vanemasse ei loe!
            // (NB: kui graafis on lubatud "mitmekordsed servad" siis see ei toimi!)
            low[u] = min(low[u], ord[nxt]); // ja mitte low[nxt]!
        }
    }

    if (ord[u] == 1 && child_count > 1) {
        cout << "ART. PUNKT" << u <&lt endl;
    }
}

Olen tähele pannud, et mõnes (aga mitte igas!) ülesandes on parem kasutada järgmist kergelt modifitseeritud varianti: ploki-lõike puus on tipp mitte ainult iga graafi artikulatsioonipunkti, vaid iga tipu kohta. Serv on ploki iga tipu ja ploki vahel, muus osas on struktuur sama. Mitte-artikulatsioonipunktid on siis lehed.