Definice vnoření zdrojového grafu G = ( V(G), E(G) ) do cílové sítě H = ( V(H), E(H) )
Zatížení cílového uzlu \(v\in V(H)\)
Zatížení vnoření \((\varphi,\xi)\)
Průměrné zatížení vnoření \((\varphi,\xi)\)
Vnoření \((\varphi,\xi)\) má stejnoměrné zatížení, pokud
Expanze vnoření \(G \xrightarrow{ emb } H \)
Dilatace zdrojové hrany \(e\in E(G)\)
Dilatace vnoření \((\varphi,\xi)\)
Průměrná dilatace vnoření \((\varphi,\xi)\)
Kdy má vnoření \((\varphi,\xi)\) stejnoměrnou dilataci?
Co znamená, že \(G \xrightarrow{ emb } H \) má dil = load = 1?
Co znamená, že \(G \xrightarrow{ emb } H \) má dil = load = 1
&&
vexp = 1?
Linkové (hranové) zahlcení cílové linky \(e_2\in E(H)\)
Linkové (hranové) zahlcení vnoření \((\varphi,\xi)\)
Uzlové zahlcení cílového uzlu \(u_2\in V(H)\)
Kdy jsou dva grafy quasiisometrické?
Pokud jsou dva grafy výpočetně ekvivalentní, jsou quasiisometrické?
Spodní mez na zatížení
Dolní mez na dilataci vnoření
Dolní mez na hranové zahlcení
Může mít kružnice v Qn lichou délku?
Co platí pro délku hamiltonovské cesty v Qn?
Jakými způsoby se dá vnořovat do hyperkrychle?
Binární zrcadlový Grayův kód
\(CBT_n\) je podgrafem krychle jaké (nejmenší) dimenze?
Proč nejde \(CBT_n\) vnořit do \(Q_{n+1}\) s dil=load=1?
jak jde \(CBT_n\) vnořit do \(Q_{n+1}\)?
Typy binárního n-úrovňového D&C výpočtu
Jednovlnový D&C na hyperkrychli
Vícevlnový D&C na hyperkrychli
(Ne vždy optimální) Vnoření mřížky do krychle s dil=load=1
Vnoření mřížky do toroidu stejné velikosti
Vnoření toroidu do mřížky stejné velikosti
Vnoření hamiltonovské cesty a kružnice do mřížek a toroidů
Vnoření krychle do mřížky/toroidu
Vnoření toroidu do toroidu
Vnoření čtvercové mřížky do obdélníkové
Vnoření obdélníkové mřížky do čtvercové
Vnoření pole/kružnice do jakékoli sítě
Vnoření hyperkubických topologií
