Caterpillar (grafteori)

En larv eller larvträd  är ett träd där alla hörn är på ett avstånd av högst 1 från den centrala banan.

Caterpillar-grafer studerades först i en serie artiklar av Harari och Schwenk. Namnet föreslogs av Arthur Hobbs [1] [2] . Som Harari och Schwenk [3] vältaligt skrev , "En larv är ett träd som förvandlas till en väg om kokongen tas bort från de slutliga hörnen" [1] .

Motsvarande beskrivningar

Följande egenskaper beskriver larvdiagram:

Generaliseringar

Ett K - träd är en ackordsgraf som innehåller exakt n − k maximala klick , var och en innehåller k + 1 hörn. I ett k -träd, som i sig inte är en ( k + 1)-klick , delar varje maximal klick antingen upp grafen i två eller flera komponenter eller innehåller en ( k- ) bladvertex som bara tillhör en maximal klick. En k -bana är ett k -träd med högst två löv, och en k -larv är ett k - träd som kan delas upp i k -banor och flera k -blad, var och en intill k -klickavskiljaren på k . - väg. I denna terminologi är en 1-larv detsamma som en larvgraf, och k -larver är kantmaximala grafer med vägbredd k [ 7] .

En krabba  är ett träd där alla hörn är på ett avstånd som inte överstiger 2 från den centrala banan [9]

Uppräkning

Larver är ett sällsynt fall av grafräkningsproblem när den exakta formeln är känd - om n  ≥ 3 är antalet larver med n hörn [1] .

För n = 1, 2, 3, … är antalet larver med n hörn

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … (sekvens A005418 i OEIS ).

Beräkningskomplexitet

Att hitta en sammandragande larv är ett NP-komplett problem . Motsvarande optimeringsproblem är minimum contraction caterpillar problem (MPCT), där priserna anges på kanterna och målet är att hitta en larv som minimerar priserna. Här definieras priset på en larv som summan av priserna på dess kanter, och varje kant har två priser, beroende på om det är ett löv eller en inre kant. Det finns ingen f(n) -approximationsalgoritm för SMSH om inte P = NP är uppfylld . Här är f(n) vilken funktion som helst av n beräknad i polynomtid, och n är antalet grafens hörn [10] .

Det finns en parametriserad algoritm som hittar den optimala lösningen på GSGM i en graf med en begränsad trädbredd . Således har både det sammandragande larvproblemet och det minimala sammandragande larvproblemet linjära tidsalgoritmer om grafen är outerplanar , parallellsekventiell , eller Halins graf [10] .

Applikationer

Larver används i kemisk grafteori för att representera molekylstrukturen hos bensenoidkolväten . I denna representation bildar molekylerna larver, där varje kant motsvarar en ring med 6 kolatomer, och två kanter faller in i en vertex om motsvarande bensenringar tillhör en sekvens av linjärt sammankopplade ringar. El-Bazil skriver: "Det är förvånande att nästan alla grafer som spelar en viktig roll i det som nu kallas "kemisk grafteori" är förknippade med larvgrafer." I detta sammanhang är larvgrafer även kända som bensoidträd eller Gutmannträd , efter Ivan Gutmans arbete inom detta område [2] [11] [12] .

Anteckningar

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

Litteratur

Länkar