4015209
| Pregunta | Respuesta |
| Definice vnoření zdrojového grafu G = ( V(G), E(G) ) do cílové sítě H = ( V(H), E(H) ) | Dvojice zobrazení \((\varphi,\xi)\), kde \[ \varphi:V(G)\to V(H) \qquad \mbox{a}\qquad \xi:E(G)\to P (H) \] \(P(H)\) = množina všech cest sítě |
| Zatížení cílového uzlu \(v\in V(H)\) | \[ load(v)=|\{u\in V(G);\varphi(u)=v\}|. \] |
| Zatížení vnoření \((\varphi,\xi)\) | \[ load(\varphi,\xi)=\max_{v\in V(H)}load(v). \] |
| Průměrné zatížení vnoření \((\varphi,\xi)\) | \[ \overline{load}(\varphi,\xi)=\frac{1}{|V(H)|}\sum_{v\in V(H)} load(v). \] |
| Vnoření \((\varphi,\xi)\) má stejnoměrné zatížení, pokud | \[ load(\varphi,\xi)=\lceil \overline{load}(\varphi,\xi)\rceil. \] |
| Expanze vnoření \(G \xrightarrow{ emb } H \) | ~ poměr velikostí grafů \[ vexp(\varphi,\xi)={|V(H)|\over|V(G)|}. \] |
| Dilatace zdrojové hrany \(e\in E(G)\) | dilatace = prodloužení ~natažení hrany, čím je hodnota větší, tím je komunikační doba delší \(dil(e)=len(\xi(e))\) |
| Dilatace vnoření \((\varphi,\xi)\) | \(dil(\varphi,\xi)=\max_{e\in E(G)} dil(e)\) |
| Průměrná dilatace vnoření \((\varphi,\xi)\) | \((\varphi,\xi): \overline{dil}(\varphi,\xi)=\frac{1}{|E(G)|}\sum_{e\in E(G)} dil(e) \) |
| Kdy má vnoření \((\varphi,\xi)\) stejnoměrnou dilataci? | Pokud \( dil(\varphi,\xi)=\lceil\overline{dil}(\varphi,\xi)\rceil \) |
| Co znamená, že \(G \xrightarrow{ emb } H \) má dil = load = 1? | \(G\subseteq H\) |
| Co znamená, že \(G \xrightarrow{ emb } H \) má dil = load = 1 && vexp = 1? | Pak G = kostra H |
| Linkové (hranové) zahlcení cílové linky \(e_2\in E(H)\) | \[ ecng(e_2)=|\{e_1\in E(G);e_2\subseteq\xi(e_1)\}|. \] ~ značí, kolik cest mi v cílovém grafu leze přes tuhle hranu ~ čím vyšší číslo, tím horší |
| Linkové (hranové) zahlcení vnoření \((\varphi,\xi)\) | \[ ecng(\varphi,\xi)=\max_{e_2\in E(H)} ecng(e_2). \] |
| Uzlové zahlcení cílového uzlu \(u_2\in V(H)\) | \[ vcng(u_2)=|\{e_1\in E(G);u_2\in\xi(e_1)\}|. \] |
| Kdy jsou dva grafy quasiisometrické? | Pokud existuje vnoření G->H i H->G s konstatními hodnotami měřítek vnoření. |
| Pokud jsou dva grafy výpočetně ekvivalentní, jsou quasiisometrické? | Ne, platí to naopak, quasiisometrické grafy jsou výpočetně ekvivalentní. |
| Spodní mez na zatížení | \[ load(\varphi,\xi)\geq \max\left(1,\lceil\frac{1}{vexp(\varphi,\xi)}\rceil\right) \] Př. pokud se bude vnořoval 300 uzlů do 100 uzlového, pak expanze bude 100/300=1/3, v ideálním případě se takhle rozloží i zátěž, líp to nejde |
| Dolní mez na dilataci vnoření | \[ dil( \varphi,\xi)\geq \lceil\frac{diam(H)}{diam(G)}\rceil. \] Grafy mají stejný počet uzlů, struktura může být jiná. Nejlepší možné pošéfování cesty délky průměru cílového grafu je, když se na něj namapuje průměr ze zdrojového grafu, pak bude dil nejmenší možná. Může být delší, ale lépe to nejde. Průměr H = 4, průměr G = 6, pak nejmenší dilatace je 4/6=2/3 (ceil)~> 1 |
| Dolní mez na hranové zahlcení | Jestliže \(k=\overline{dil}(\varphi,\xi)\) \[ ecng(\varphi,\xi)\geq \lceil\frac{k|E(G)|}{|E(H)|}\rceil\] Zdrojový graf má |E(G)| hran, v průměru se mi každá roztáhne na 'k' hran, čili potřebuju k*|E(G)| hran, jenže k dispozici mam jen |E(H)| hran v cíl. grafu. V nejlepším případě se mi zátěž rozloží rovnoměrně |
| Může mít kružnice v Qn lichou délku? | Ne. Protože u=v, pak počet inverzí musí být sudý. |
| Co platí pro délku hamiltonovské cesty v Qn? | Je lichá expl: Krychle má \(2^n\) uzlů, čili projdu přes \(2^n - 1 \) hran (jednu vynechám, ta vede na začátek) a to je liché číslo. |
| Jakými způsoby se dá vnořovat do hyperkrychle? | Dá se díky symetrii popsat pomocí značení uzlů: ohodnocení uzil ve V(G) n-bitovými adresami – značení hran: ohodnocení hran v E(G) čísly dimenzí 0,1,...,n-1 |
| Binární zrcadlový Grayův kód | Rekurzivní: 1)\(G_1=\{0,1\}\) 2) \(G_n=\{0G_{n-1},1G_{n-1}^R\}\), kde \(0G_i\) (\(1G_i\)) = každý prvek \(G_i\) dostane 1-bit. předponu \(0 (1)\), \(G_i^R\) = zrcadlově otočená posl \(G_i\) |
| \(CBT_n\) je podgrafem krychle jaké (nejmenší) dimenze? | CBT = complete binary tree \(Q_{n+2}\) (důkaz se nedělal, ale je tu problém s acykličností stromu) Čili vnoření má dil = 1 load = 1 protože je to PODGRAF. A zároveň 9 uzlů z 16 nevyužitých. |
| Proč nejde \(CBT_n\) vnořit do \(Q_{n+1}\) s dil=load=1? | Hledám podgraf. Ale nevejde se – je porušená parita (šachy s vykousnutými protilehlými políčky vs. kostičky domina) Strom hloubky 2: obarvím kořen a listy, celkem 5 uzlů, druhá barva 2 uzly. V krychli dim 3 mám 4 uzly jedné barvy a 4 uzly druhé barvy. Těch 5 nikam nenacpu. |
| jak jde \(CBT_n\) vnořit do \(Q_{n+1}\)? | Buď load=2 nebo dil=ecng=2. Load: \(CBT_2\) do kostky, dva z té skupiny 5 uzlů budou přes sebe (=totožné) Dil: a) indukční inorder číslování stromu (nesmí se začínat od 0) p5/s20 průměrná dil je 1.5 b) rozdělení kořene na dva uzly a vyrobení symetrie, kterou krychle vyžaduje, jen jedna hrana má dil=2 |
| Typy binárního n-úrovňového D&C výpočtu | Jednovlnový, vícevlnový |
| Jednovlnový D&C na hyperkrychli | Standardní vnoření \(CBT_n\) do \(Q_{n+1}\) půlka počítá a půlka jen posílá, blbá efektivita, proto se používá se binomiální kostra hypercube. Divide&Keep, barvičky sjednocují JEDEN uzel, který se postupně dělí o práci. |
| Vícevlnový D&C na hyperkrychli | Standardní vnoření \(CBT_n\) do \(Q_{n+1}\) je optimální. |
| (Ne vždy optimální) Vnoření mřížky do krychle s dil=load=1 | Rozdělení na kartézský součin Př.: M(27,100) = M(27)xM(100) Na M(27) potřebuju 5 bitů (graycode) na M(100) 7 bitů \( M(27) = Q_5\) \( M(100) = Q_7\) tj. \(M(27,100) \rightarrow Q_{12}\) |
| Vnoření mřížky do toroidu stejné velikosti | Simuluje bez zpomalení, mřížka je podgraf toroidu. Pro obecné velikosti jde o NP-úplný problém |
| Vnoření toroidu do mřížky stejné velikosti | Kartézská dekompozice: load = 1 dil = ecng = 2 |
| Vnoření hamiltonovské cesty a kružnice do mřížek a toroidů | Toroid má cestu i kružnici. Mřížka má vždy cestu, ale kružnici jen tehdy, je-li alespoň jedna dimenze sudá |
| Vnoření krychle do mřížky/toroidu | \(Q_{2k} \xrightarrow{emb} M(2^k,2^k)\) Mortonova křivka – rozseká krychli na 4 podkrychle (podle x a pak y), lexikograficky spojuje uzly. vexp = load = 1 Manhattanská vzdálenost 2 uzlů, lišísích se v bitu i \(d(u,u\oplus 2^i)=2^{\lceil\frac{i}{2}\rceil}\) dil = \(2^{k-1}\) |
| Vnoření toroidu do toroidu | Obecně problém. Jeden spec. případ: 2D kružnice do kružnice. Pro \(z_1\not=z_2\), \(\exists\) optimální vnoření \(K(z_1,z_2)\xrightarrow{emb} K(z_1z_2)\) s load=1, dil=\(min(z_1,z_2)\), ecng=dil+2 |
| Vnoření čtvercové mřížky do obdélníkové | Nechť \(z_1> z_2\) a \(w=\sqrt{z_1z_2}\). Pak \(S=M(w,w)\) lze vnořit do \(R=M(z_1,z_2)\) \(dil=\lceil \sqrt{z_1/z_2}\rceil\), \(load=2\) a \(ecng=1+\lceil \sqrt{z_1/z_2}\rceil\). |
| Vnoření obdélníkové mřížky do čtvercové | Nechť \(z_1> z_2\) a \(w=\sqrt{z_1z_2}\). Pak \(R=M(z_1,z_2)\) může být vnořena do \(S=M(w,w)\) s \(dil=1\) a \(load =ecng=2\) |
| Vnoření pole/kružnice do jakékoli sítě | 1) konstrukce kostry (~ strom) 2) rozdělit uzly podle patra na sudé a liché 3) DFS průchod stromem – když jsi v lichém uzlu poprvé, přidej ho do kružnice, když jsi v sudém uzlu a už se do něj nevrátíš, dej ho do kružnice load = 1 dil <= 3 ecng = 2 |
| Vnoření hyperkubických topologií | oBFn můžeme vnořit do wBFn s load=2 a dil 1 wBFn do oBFn s dil <= 3 |
¿Quieres crear tus propias Fichas gratiscon GoConqr? Más información.