DFS-puu

See tekst (v.a. osade seletatavate ülesannete valik) põhineb suuresti järgmisel blogil.

1. DFS-puu mõiste

Vaatleme suunamata sidusat graafi \(G\). Jooksutame tema peal järgmist koodi:

function visit(u):
	visited[u] = 1
	for (üle kõigi u naabrite v):
		if (visited[v] == 0):
			märgistame serva uv
			kutsume visit(v)

Tegu on graafi \(G\) sügavuti läbi käimisega. Animeeritult näeb visit(1) kutsumine välja järgmine:

Vaatleme real 5 märgstaitud servi. Nad moodustavad graafi \(G\) toespuu, juurtipuga 1. Kutsume märgistatud servi toeservadeks (span-edge), ülejäänud servi naasvateks servadeks (back-edge, varasemalt olen kasutanud lisaserv).

Meie graafi DFS-puu näeb välja järgmine:

Tähelepanek. Iga DFS-puu naasev serv ühendab mingi tipu oma eellasega. See omadus on see, mis teeb DFS-puu kasulikuks.

Tõestus

Olgu antud serv \(uv\); üldisust kitsendamata eeldame, et kui DFS läbib tippu \(u\), on tipp \(v\) veel läbimata. Vaatleme kaht juhtu.

DFS liigub tipust \(u\) tippu \(v\) mööda serva \(uv\). Siis \(uv\) on toeserv.
DFS ei liigu tipust \(u\) tippu \(v\) mööda serva \(uv\). See tähendab, et kui real 4 seda kontrolliti, siis oli tipp \(v\) juba külastatud. Järelikult külastati seda tipu \(u\) mõne teise naabri külastamise käigus. Seega \(u\) on \(v\) eellane DFS-puus.

Seega ei saa \(uv\) olla midagi muud peale toeserva ja serva, mis tippu eellasega ühendab.

Näiteks ülalolevas 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.

2. Praktilised ülesanded

2.1. Ülesanne: sildade leidmine

Sillaks nimetatakse graafi serva, mille eemaldamisel graaf enam sidus ei ole.

Ülesanne. Olgu antud \(n\) tipu ja \(m\) servaga sidus suunamata graaf \(G\). Leia graafi \(G\) kõik sillad.

\(1 \le n, m \le 10^5\).

Tähelepanek. Toeserv \(uv\) on sild siis ja ainult siis, kui ei leidu naasvat serva, mis ühendab \(uv\) mingit järglast \(uv\) mingi eellasega. Teisisõnu, \(uv\) on sild siis ja ainult siis, kui ei leidu naasvat serva, mis servast \(uv\) "üle läheb".

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.

Näiteks ülaloleval graafil \(6-2\) ei ole sild, kuna tema eemaldamisel naasev serv \(3-8\) hoiab graafi koos. Seevastu \(2-4\) on sild, kuna ükski naasev serv tema eemaldamisel graafi koos ei hoia.

Tähelepanek. Naasev serv ei ole kunagi sild.

Need kaks tähelepanekut on klassikalise servade leidmise meetodi aluseks. Sisendgraafi \(G\) korral leiame sillad üles nii:

leiame graafi \(G\) DFS-puu;
iga toeserva \(uv\) korral kontrollime, kas leidub naasev serv, mis servast \(uv\) "üle läheb"; kui ei ole, siis oleme leidnud silla.

DFS-puu lihtsa struktuuri tõttu ei ole sammu 2 keeruline teha. Üks klassikaline meetod on pidada meeles teatud massiivi \(\mathrm{low}[u]\). Uute ideede tutvustamise eesmärgil teeme seekord teistmoodi. Olgu \(\mathrm{dp}[u]\) naasvate servade arv, mis tipu \(u\) ja tema vanema vahelisest servast "üle lähevad". Seda saab arvutada välja valemiga

\[ \mathrm{dp}[u] = (\text{tipust } u \text{ üles minev. naasv. servade \#}) - (\text{tipust } u \text{ alla minev. naasv. servade \#}) + \sum_{v \text{ on } u \text{ laps}} \mathrm{dp}[v]. \]

Kui \(p\) on tipu \(u\) vanem, siis \(pu\) on sild parajasti siis, kui \(\mathrm{dp}[u] = 0\).

2.2. Ülesanne: servade orienteerimine

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

Ülesanne. Olgu antud \(n\) tipu ja \(m\) servaga sidus suunamata graaf \(G\). Määra kõikidele servadele suunad nii, et graaf muutuks tugevalt sidusaks (või teata, et see ei ole võimalik).

\(1 \le n, m \le 10^5\).

Tähelepanek. Kui \(G\) sisaldab sildu, siis see ei ole võimalik.

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ähelepanek. Juurtipust leidub igasse tippu suunatud teekond.

Tõestus

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

Tähelepanek. Igast tipust leidub juurtippu suunatud teekond.

Tõestus

Olgu \(v\) mingi tipp, mis ei ole juurtipp; olgu \(u\) tema vanem DFS-puus. Et graafis ei ole sildu, siis peab leiduma mingi naasev serv, mis "läheb üle" toeservast \(uv\). See naasev serv ühendab mingi \(u\) eellase mingi \(v\) järglasega. Võime liikuda mööda toeservi alla, kuni jõuame selle naasva serva alumise otspunktini. Seejärel liigume mööda toda naasvat serva üles. Nii oleme vähemalt ühe sammu juure suunas liikunud. Seda protsessi saab korrata, kuni jõuame juurtippu.

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.3. Ülesanne: kolm sõltumatut teekonda

Ülesanne. Olgu antud \(n\) tipu ja \(m\) servaga sidus suunamata graaf \(G\). Vali tipud \(u\) ja \(v\) ning leia kolm teekonda \(u \leadsto v\) nii, et nendel teekondadel ei ole (paarikaupa) ühiseid tippe peale \(u\) ja \(v\) (või teata, et see ei ole võimalik).

\(1 \le n, m \le 10^5\). [Allikas: CF 521 E]

Kui puu on kaktus (iga serv sisaldub ülimalt ühes lihttsüklis), siis see ei ole võimalik.

Tõestus

Oletame, et sellised kolm teekonda leiduvad ja tähistame nad \(u a_1 a_2 \ldots a_{k_a} v\), \(u b_1 b_2 \ldots b_{k_b} v\) ja \(u c_1 c_2 \ldots c_{k_c} v\). Võime eeldada, et need teekonnad ei läbi ühtki tippu mitu korda. Saame kaks erinevat lihttsüklit

\[ u a_1 a_2 \ldots a_{k_a} v b_{k_b} \ldots b_2 b_1 u \text{ ja } u a_1 a_2 \ldots a_{k_a} v c_{k_c} \ldots c_2 c_1 u. \]

Nendel on ühine serv \(u a_1\), seega graaf ei saa olla kaktus.

Ü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 õppisime sildade leidmise juures tegema). Leidub vähemalt üks toeserv \(st\), millest "läheb üle" kaks erinevat naasvat serva \(ab\) ja \(cd\) (veenduda, et 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.

2.4. Ülesanne: servapaaridega katmine

Ülesanne. Olgu antud \(n\) tipu ja \(m\) servaga suunamata graaf \(G\). Igal käigul valitakse kolm tippu \(u, v, w\) nii, et leiduvad servad \(uv\) ja \(vw\). Seejärel eemaldatakse graafist servad \(uv\) ja \(vw\). Leia maksimaalne käikude arv ja viis, kuidas seda saavutada.

\(1 \le n, m \le 10^5\). [Allikas: CF 858 F]

2.5. Ülesanne: täpselt ühes tsüklis olevad servad

Lihttsükliks nimetatakse tsüklit, mis läbib iga tippu ülimalt ühe korra.

Ülesanne. Olgu antud \(n\) tipu ja \(m\) servaga suunamata graaf \(G\). Leia kõik servad, mis leiduvad täpselt ühes lihttsüklis.

\(1 \le n, m \le 10^5\). [Allikas: CF 962 F]