Caterpillar (teoria grafurilor)

O omidă sau un arbore de omidă  este un copac în care toate vârfurile sunt la o distanță de cel mult 1 de calea centrală.

Graficele Caterpillar au fost studiate pentru prima dată într-o serie de lucrări de Harari și Schwenk. Numele a fost sugerat de Arthur Hobbs [1] [2] . După cum au scris elocvent Harari și Schwenk [3] , „O omidă este un copac care se transformă într-o potecă dacă coconul este îndepărtat de la vârfurile terminale” [1] .

Descrieri echivalente

Următoarele caracteristici descriu graficele caterpillar:

Generalizări

Un arbore K este un grafic de cordoane care conține exact n - k clicuri maxime , fiecare conținând k + 1 vârfuri. Într -un arbore k , care nu este el însuși o clică ( k + 1) , fiecare clică maximă fie împarte graficul în două sau mai multe componente, fie conține un vârf de frunză ( k- ) care aparține unei singure clicuri maxime. O cale k este un copac k cu cel mult două frunze, iar o omidă k este un arbore k care poate fi împărțit în k -căi și mai multe k -frunze, fiecare adiacent separatorului k -clică al k . - cale. În această terminologie, o omidă cu 1 omidă este la fel cu un grafic omidă, iar k - omizi sunt grafice maxime de margine cu lățimea de cale k [ 7] .

Un crab  este un copac în care toate vârfurile se află la o distanță care nu depășește 2 de calea centrală [9]

Enumerare

Omizile sunt un caz rar de probleme de enumerare a graficelor când formula exactă este cunoscută - dacă n  ≥ 3, numărul de omizi cu n vârfuri este [1] .

Pentru n = 1, 2, 3, … numărul de omizi cu n vârfuri este

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … (secvența A005418 în OEIS ).

Complexitate computațională

Găsirea unei omidă contractantă este o problemă NP-completă . Problema de optimizare corespunzătoare este problema minimă contracției caterpillar (MPCT), în care prețurile sunt date pe margini și scopul este de a găsi o omidă care să minimizeze prețurile. Aici prețul unei omizi este definit ca suma prețurilor marginilor sale, iar fiecare margine are două prețuri, în funcție de faptul că este o frunză sau o margine internă. Nu există un algoritm de aproximare f(n) pentru SMSH decât dacă P = NP este satisfăcut . Aici f(n) este orice funcție a lui n calculată în timp polinomial, iar n este numărul de vârfuri ale graficului [10] .

Există un algoritm parametrizat care găsește soluția optimă pentru GSGM într-un grafic cu o lățime de arbore mărginită . Astfel, atât problema omidă contractantă, cât și problema omidă contractantă minimă au algoritmi de timp liniari dacă graficul este exterior planar , paralel-secvențial sau graficul lui Halin [10] .

Aplicații

Omizile sunt folosite în teoria grafurilor chimice pentru a reprezenta structura moleculară a hidrocarburilor benzenoide . În această reprezentare, moleculele formează omizi, în care fiecare muchie corespunde unui inel de 6 atomi de carbon, iar două muchii sunt incidente unui vârf dacă inelele benzenice corespunzătoare aparțin unei secvențe de inele conectate liniar. El-Bazil scrie: „Este surprinzător că aproape toate graficele care joacă un rol important în ceea ce se numește acum „teoria grafurilor chimice” sunt asociate cu graficele omizi”. În acest context, graficele de omizi sunt cunoscute și sub denumirea de arbori benzoizi sau arbori Gutmann , după munca lui Ivan Gutman în acest domeniu [2] [11] [12] .

Note

  1. ↑ 1 2 3 Harary, Schwenk, 1973 , p. 359–365.
  2. ↑ 1 2 3 El-Basil, 1987 , p. 153–174.
  3. ↑ Harary, Schwenk, 1973 .
  4. ↑ 1 2 3 4 5 Harary, Schwenk, 1971 , p. 138–140.
  5. ↑ Harary, Schwenk, 1972 , p. 203–209.
  6. ↑ Raychaudhuri, 1995 , p. 299–306.
  7. ↑ 1 2 Proskurowski, Telle, 1999 , p. 167–176.
  8. ↑ Eckhoff, 1993 , p. 117–127.
  9. ^ Weisstein , Eric W. Lobster  pe site- ul Wolfram MathWorld .
  10. ↑ 12 Khosravani , 2011 .
  11. ↑ Gutman, 1977 , p. 309–315.
  12. ↑ El-Basil, 1990 , p. 273–289.

Literatură

Link -uri