Definice z 5. přednášky

Description

Definice z 5. přednášky MI-PAR
秀一 幽遊
Flashcards by 秀一 幽遊, updated more than 1 year ago
秀一 幽遊
Created by 秀一 幽遊 over 8 years ago
13
0

Resource summary

Question Answer
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
Show full summary Hide full summary

Similar

Definice z 2. přednášky
秀一 幽遊
Definice ze 4. přednášky (topologie)
秀一 幽遊
Definice ze 4. přednášky (grafy)
秀一 幽遊
Definice z 6. přednášky
秀一 幽遊
Grafy II.
Michal Roch
FITNESS
Montse Em
Statistics - topic 2
David Klingenber
Algebra
秀一 幽遊
sport
Saki Kuwae
Fundamentos
luis lopez
1. okruh
David Klingenber