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í