| Abstrakt: | V našej práci sme zaviedli nový model konštrukcie grafov. Náš model je
inšpirovaný modelom
používaným na skúmanie algoritmického prehľadávania grafov, ktorému
môže poslúžiť ako duálny problém. Taktiež môže nájsť priame uplatnenie v
praxi.
Náš model obsahuje agenta v počiatočnom vrchole grafu.
Agent môže sekvenčne vykonávať tri operácie.
Prvou je presun po hrane s lokálnym číslom
konca hrany $k$. Druhou je vytvorenie novej hrany z
vrchola, kde sa práve nahádza s novým vrcholom na jej konci. Agent sa po
vykonaní tejto operácie nachádza v novom vrchole. Treťou
operáciou je otvorenie portu so značkou $l$. Ak sú naraz
otvorené dva porty s rovnakou značkou, okamžite medzi nimi vznikne hrana.
Úlohou agenta je vytvoriť všetky vrcholy a
hrany zadaného grafu. Mierou efektívnosti algoritmu agenta je
počet krokov - presunov po vrcholoch grafu. Skúmali sme vplyv veľkosti
množiny značiek portov, ktorú môže agent použiť, na počet krokov optimálneho
riešenia.
Skúmali sme tri konkrétne triedy grafov - hyperkocku, mriežku ($P_{n}
\times P_{m}$) a cyklickú
mriežku ($C_{n} \times C_{m}$). Pri všetkých troch sme dokázali koľko
značiek pre porty agent potrebuje, ak konštruuje graf na najnižší možný
počet krokov. Tiež sme ukázali ako takáto konštrukcia vyzerá.
Pri n-rozmernej hyperkocke agent potrebuje pre
nepárne n $\frac{2^{n+1} - 1}{3}$ a pre
párne n $\frac{2^{n+1} - 2}{3}$ značiek portov. Pri mriežke $n \times m$
potrebuje $m$ portov, kde $m <= n$. Pri cyklickej mriežke sme ukázali, že
agent potrebuje v tomto prípade $2m + 1$ portov, kde $m <= n$. Pri cyklickej
mriežke sme ďalej dokázali, že existuje hrana pri konštrukcii ktorej agent vykoná aspoň $m - 1$ krokov
a hrana pri konštrukcii ktorej vykoná aspoň $n - 1$ iných krokov. Čím sme
zlepšili dolný odhad zo základných troch krokov na hranu, čo je dĺžka
najkratšej kružnice, na ktorej leží hrana cyklickej mriežky, ak oba jej
rozmery sú aspoň štyri.
|
|---|