Try   HackMD

ADS B - Polosouvislý graf

Existuje-li mezi

u,v silná souvislost, pak stačí testovat polosouvislost pouze pro jeden z těchto vrcholů. Pokud bych tak provedl kondenzaci, výsledný graf již bude obsahovat pouze jednosměrné cesty.
Není-li takový graf ani slabě souvislý, pak je odpověď triviální. V opačném případě se jedná o DAG. Ten nebude polosouvislý v případě, bude-li se cesta ze zdrojové komponenty větvit.

Důkaz: Vezmu si dva vrcholy za větvením. Budu-li hledat cestu podle směru šipek, musí se v některém vrcholu cesty spojit. Jelikož však v takovém grafu není cyklus, musí obě šipky směřovat do daného vrcholu a nemohu tedy v cestě pokračovat. Naopak budu-li hledat cestu proti směru šipek, pak se dostanu k vrcholu, kde se cesta rozdělovala, a tak opět nemohu pokračovat dále.

◻

To zároveň znamená, že se cesty ze zdrojových komponent nesmí ani spojovat. Požaduju-li slabou souvislost, pak výsledkem musí být pouze cesta. Tzn.: polosouvislý graf je takový, který je slabě souvislý a grafem komponent silné souvislosti je cesta.

Problém je v tom, že samotná kondenzace (kontrakce hran podle silné souvislosti) je náročná.
Mohu si však zaznamenat, z které komponenty jsem tuto komponentu objevil (což je pro DFS triviální záležitost). Navíc, objevím-li vrchol

v z vrcholu
u, pak vrchol
u objevím z
v jen v případě, že leží ve stejné komponentě. Díky těmto informacím již mohu vytvořit graf komponent silné souvislosti (hrana
AB existuje, vede-li alespoň jeden vrchol z
A do vrcholu z
B; obráceně nemůže, neboť vy vzniknul cyklus). Budu-li se držet algoritmu z Průvodce:

1. Otočím orientaci hran v grafu.
2. Spouštím DFS z neprozkoumaných vrcholů.
3. Jakmile otevřu vrchol, poznačím si, odkud jsem jej otevřel.
4. Uzavřené vrcholy vložím do zásobníku.
5. Jsou-li všechny vrcholy uzavřeny, jdu dál. Jinak
→1.
6. Vyndám vrchol ze zásobníku. Nemám-li označeno, v jaké komponentě leží, provedu DFS a objevené vrcholy označím číslem komponenty.
7. Není-li zásobník prázdný,
→5. Jinak vytvoř prázdný (bezhranový) graf, kde vrcholy=komponenty.
8. Pro každý vrchol zjisti, v jaké komponentě leží vrchol, který jej otevřel (otec - v
2).
9. Leží-li v jiné komponentě než momentální vrchol, vytvoř hranu otec
→momentální vrchol
10. Jakmile jsou všechny vrcholy prozkoumány, zjisti, zdali je graf cesta. Pokud ano, graf je slabě souvislý.

Složitost: DFS je lineární s velikostí grafu; ačkoli jej musím spouštět vícekrát, jdu pouze přes neprozkoumané vrcholy. Zaznamenávání vstupu je lineárně závislé na počtu vrcholů, stejně tak jako konstrukce finálního grafu.

Last changed by 
 
Daar543
0
117

Read more

ADS úlohy E - podobne

Nejprve je potřeba si rozmyslet, zda přidání dalšího prvku na konec posloupnosti ovlivní dosavadní posloupnosti: Budu-li postupovat v posloupnosti od konce do začátku, mohu najít první číslo, jehož rozdíl s posledním číslem přesáhne toleranci ($k$). Pro další výpočty pak mi stačí uvažovat pouze úsek napravo od tohoto čísla. Zároveň je však potřeba si uvědomit, že i předposlední číslo již vyhradilo jakýsi úsek, ve kterém má smysl zkoumat podposloupnosti - budu se tak zabývat kratším z těchto úseků. Nyní vezmu následující situaci: mám posloupnost $P$ s finálním prvkem $P_{n+1}$, pro nějž je zarážka na pozici $s_1$. Jelikož se jedná o první zarážku, celá posloupnost od $0$ do $n$ je platná a tuto posloupnost nelze rozšířit zleva ani zprava. Označím tak $t_0=n$ a $s_0=0$, což znamená, že podposloupnost má délku $t_0 - s_0$. Dále, mezi $P_{s+1}$ a $P_{n+1}$ nevznikla žádná zarážka, a tak mohu postup opakovat (jako bych opět počítal od nuly), dokud nevznikne další zarážka.

Jun 18, 2020
ADS úlohy E - Matsoucin

Vím-li, jak efektivně uzávorkovat $n$ matic, pomůže mi to k tomu, abych věděl, jak uzávorkovat $n+1$ matic? Příklad: součin délky 4+1: $ABCDE=(ABCD)(E)=(ABC)(DE)=(AB)(CDE)=(A)(BCDE)$ Z něj je vidět, že nemohu postupovat tak, že zjistím uzávorkování pro první matice, přidám k nim další a pak provedu triviální výpočet. Musím postupovat slučováním - nejprve zjistím složitost pro všechny součiny délky 2, pak délky 3... Dále je vidět, že pro hledání složitosti násobení $n+1$ matic musím provést $n+1$ porovnání pro danou posloupnost. Vytvořím si tak následující tabulku: $\begin{pmatrix}A & B & C & D & E \ AB & BC & CD & DE \ ABC & BCD & CDE \ ABCD & BCDE \ ABCDE\end{pmatrix}$

Jun 16, 2020
ADS úlohy E - prank

Permutaci čísel zde budu označovat jako řetězec. Je-li na posledních $p$ pozicích řetězce rostoucí posloupnost, pak prvek těsně před touto posloupností se změní až v $p!$-té následující permutaci. Aby se totiž na pozicích od $n-p$ do $n-1$ (indexuji od nuly) změnila posloupnost na klesající, budou se muset vystřídat všechny permutace na těchto pozicích - od lexikograficky první do lexikograficky poslední. Jak toto pomůže při sestavování dané permutace? Příklad (pořadí, řetězec): $0: 123$ $1: 132$ $2: 213$ $3: 231$ $4: 312$

Jun 13, 2020
Lineární algebra 2 DÚ - sada 8

1. 1) Jedná se o zobrazení z $R^1$ do $R$. Linearita násobení: $(\alpha x * y)=(x * \alpha y)=(\alpha x y) = \alpha(x * y)$. Linearita sčítání: $((x+z)y)=(xy+zy)=(xy)+(zy)$ (a obdobně $(x(z+y))$). Matice zobrazení: $\begin{pmatrix} 1 \end{pmatrix}$ 2) Linearita násobení: Násobení $\alpha x$ (nebo $\alpha y$) vynásobí $\alpha$ každou složku vektoru $x$. Tím pádem $a(\alpha x,y)= \alpha x_1 y_1 + 2 \alpha x_2 y_1 + 3 \alpha x_2 y_2 = \alpha(x_1 y_1 + 2x_2 y_1 + 3 x_2 y_2) = \alpha a (x,y)$. Tentýž výsledek produkuje i $a(x,\alpha y)$, jelikož násobení je komutativní.

Jun 5, 2020
Read more from Daar543
Published on HackMD