======= Vnořování  =======

====== Příklady za 2 body ======

===== Spodní mez uzlového zatížení(load) při vnoření 3D mřížky M(z1,z2,z3) do 2D toroidu T(w1,w2) =====

Určete spodní mez  na uzlové zatížení (load)  vnoření 3-D mřížky <math>M(z_1, z_2, z_3)</math> do 2-D toroidu <math>K(w_1, w_2)</math>.

★ //Bylo ve zkoušce: [[škola:předměty:mi-par:par_zkouska_2013-01-30|2013-01-30]], [[škola:předměty:mi-par:par_zkouska_2013-12-20|2013-12-20]]//

==== Řešení ====

Dle mého názoru se jedná o obecnou spodní mez pro load, který vnikne vnořením jednoho grafu do druhého.

Takže jednoduše poměr počtu uzlů grafu vnořovaného (M(...)) k počtu uzlů grafu, do kterého vnořujeme (T(...)).

<math>max(1, \frac{{z_1}{\cdot}{z_2}{\cdot}{z_3}}{{w_1}{\cdot}{w_2}}) == \lceil \frac{{z_1}{\cdot}{z_2}{\cdot}{z_3}}{{w_1}{\cdot}{w_2}} \rceil</math>

Edit: Kdyz tam das horni celou cast, uz nemusis resit nejaky max(1,...), vzdy ten <math>\lceil zlomek \rceil</math> vyjde minimalne 1
===== Spodní mez pro uzlové zatížení (load) vnoření wBFn do M(n,n). =====

★ //Bylo ve zkoušce: [[škola:předměty:mi-par:par_zkouska_2014-01-13|2014-01-13]]//

==== Řešení ====

Stejně jak předchozí, akorát s jinými hodnotami

 - Motýlek dimenze ''n'' má více uzlů než mřížka ''M(n,n)'', proto uzlové zatížení musí být nutně větší nebo rovno poměru počtu uzlů obou grafů: \\ <math>|V(wBF_n)| = n*2^n \\ |V(M(n,n))| = n*n \\ load(\varphi , \xi ) \geq \lceil \frac{|V(wBF_n)|}{|V(M(n,n))|} \rceil = \lceil \frac{n*2^n}{n*n} \rceil = \lceil \frac{2^n}{n} \rceil</math>

<math>\frac{2^n}{n} \geq 2</math>, proto není třeba dělat max(1, load)