PAR4

Question 1

Vnoreni G→H

Answer 1

dvojice zobrazeni (φ;ξ); kde φ : V (G) → V (H) a ξ : E(G) → P(H) a (P(H) je mnozina všech cest grafu H)

Question 2

zatizeni ciloveho uzlu v z H

Answer 2

load(v) = |{u ∈ V (G); φ(u) = v}|

Question 3

zatizeni vnoreni

Answer 3

load(φ; ξ) = max load(v)

Question 4

prumerne zatizeni vnoreni

Answer 4

load’(φ; ξ) = 1/|V(H)|SUMA[v z H]load(v)

Question 5

stejnosmerne zatizeni vnoreni

Answer 5

load(φ; ξ) = [‘load’(φ; ξ)]

Question 6

expanse vnoreni G do H

Answer 6

vexp(φ;ξ)= |V(H)|/|V (G)|

Question 7

dilatace zdrojove hrany e z E(G)

Answer 7

dil(e) = len(ξ(e))

Question 8

dilatace vnoreni

Answer 8

dil(φ; ξ) = maxe∈E(G) dil(e)

Question 9

prumerna dilatace vnoreni

Answer 9

dil(φ; ξ)’ = 1/|E(G)|SUMA[e z E(G)] (dil(e))

Question 10

stejnosmerna dilatace vnoreni

Answer 10

dil(φ; ξ) = ‘dil(φ; ξ)’

Question 11

linkove zahlceni cilove linky e2 z H

Answer 11

ecng(e2) = |{e1 ∈ E(G); e2 ⊆ ξ(e1)}|

Question 12

linkove zahleceni vnoreni

Answer 12

ecng(φ; ξ) = max ecng(e2)

Question 13

uzlove zahlceni ciloveho uzlu u2 z H

Answer 13

ncng(u2) = |{e1 ∈ E(G); u2 ∈ ξ(e1)}|

Question 14

simulace se zpomalenim h

Answer 14

H simuluje G se zpomalenim h; jestlize jeden krok vypoctu na G muze byt simulovan v O(h) krocich na H.

Question 15

vypocetne ekvivalentni site

Answer 15

G a H jsou vypocetne ekvivalentni site; pokud G dokaze simulovat H s konstantnim zpomalenim a naopak.

Question 16

optimalni hyperkrychle

Answer 16

Qn je optimalni hyperkrychle pro G->Qn s load = 1 prave tehdy když n = ‘log|V(G)|’

Question 17

Normalni hyperkubicky alg

Answer 17

v kazdem kroku alg jsou pouzity pouze hrany jedne dimenze hyperkrychle – v posobe jdoucich krocich jsou pouzivany po sobe jdouci dimenze

Question 18

quaziizometricke grafy G a H

Answer 18

jsou, pokud existuji vnoreni G->H i H->G s konstantnimi hodnotami meritek vnoreni