| Abstrakt: | Antidilatácia je jedným z mnohých problémov označovania vrcholov v grafe. Cieľom je nájsť také vnorenie vrcholov grafu G do vrcholov grafu H, aby susedné vrcholy grafu G boli od seba čo najviac vzdialené v grafe H. Vo všeobecnosti je tento problém NP-ťažký.
V práci sa venujeme problému antidilatácie cesty do stromov. Analyzujeme hlavne antidilatáciu cesty do pavúčich grafov, teda grafov, ktoré majú jeden vrchol stupňa aspoň 3 a ostatné vrcholy stupňa najviac 2. Uvádzame niekoľko metód na odhadovanie antidilatácie zhora a polynomiálne algoritmy na nájdenie optimálnych vnorení (vzhľadom na hodnotu antidilatácie) ciest do niektorých špeciálnych pavúčich grafov. Dokazujeme niekoľko dolných odhadov antidilatácie cesty na všeobecné pavúčie grafy. Nakoniec analyzujeme antidilatáciu cesty do húsenicových grafov.
|
|---|