Caterpillar (graafiteoria)

Toukka tai toukkapuu  on puu , jonka kaikki kärjet ovat enintään 1:n etäisyydellä keskipolusta.

Harari ja Schwenk tutkivat ensin toukkakaavioita useissa julkaisuissa. Nimen ehdotti Arthur Hobbs [1] [2] . Kuten Harari ja Schwenk [3] kaunopuheisesti kirjoittivat , "Toukka on puu, joka muuttuu poluksi, jos kotelo poistetaan päätepisteistä" [1] .

Vastaavat kuvaukset

Seuraavat ominaisuudet kuvaavat toukkakaavioita:

Yleistykset

K - puu on sointugraafi , joka sisältää tarkalleen n − k maksimaalista klikkia , joista jokainen sisältää k + 1 kärkeä. K - puussa, joka ei itse ole( k + 1)-klikki , jokainen maksimiklikki joko jakaa graafin kahdeksi tai useammaksi komponentiksi tai sisältää ( k- )lehtipisteen, joka kuuluu vain yhdelle maksimaaliselle klikkille. K -polku on k - puu, jossa on enintään kaksi lehteä, ja k -toukka on k - puu, joka voidaan jakaa k -poluksi ja useiksi k - lehdiksi , joista jokainen on k -klikin erottimen vieressäpolku. Tässä terminologiassa 1-toukka on sama kuin toukkagraafi, ja k -toukka ovat reuna-maksimaalikaavioita, joiden polunleveys on k [ 7] .

Rapu  on puu , jonka kaikki kärjet ovat enintään 2:n etäisyydellä keskipolusta [9]

Luettelo

Toukat ovat harvinainen tapaus graafisen laskennan ongelmista, kun tarkka kaava tiedetään - jos n  ≥ 3, toukkien lukumäärä n kärjellä on [1] .

Kun n = 1, 2, 3, … toukkien lukumäärä n kärkeä on

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … (sekvenssi A005418 OEIS : ssä ).

Laskennallinen monimutkaisuus

Sopivan toukan löytäminen on NP-täydellinen ongelma . Vastaava optimointitehtävä on minimikontraktiotoukkaongelma (MPCT), jossa hinnat on annettu reunoilla ja tavoitteena on löytää hinnat minimoiva toukka. Tässä toukan hinta määritellään sen reunojen hintojen summana, ja jokaisella reunalla on kaksi hintaa riippuen siitä, onko se lehti vai sisäreuna. SMSH:lle ei ole f(n) -approksimaatioalgoritmia , ellei P = NP täyty . Tässä f(n) on mikä tahansa n:n funktio, joka on laskettu polynomiajassa, ja n on graafin kärkien lukumäärä [10] .

On olemassa parametroitu algoritmi, joka löytää optimaalisen ratkaisun GSGM:lle graafista, jonka puuleveys on rajoitettu . Siten sekä supistuvan toukkaongelman että minimaalisen supistuvan toukkaongelman kanssa on lineaariset aikaalgoritmit , jos graafi on ulkotasoinen , rinnakkainen peräkkäinen tai Halinin graafi [10] .

Sovellukset

Toukkia käytetään kemiallisessa graafiteoriassa edustamaan bentsenoidihiilivetyjen molekyylirakennetta . Tässä esityksessä molekyylit muodostavat toukkia, joissa jokainen reuna vastaa 6 hiiliatomin rengasta ja kaksi reunaa osuu kärkeen, jos vastaavat bentseenirenkaat kuuluvat lineaarisesti toisiinsa liittyvien renkaiden sarjaan. El-Bazil kirjoittaa: "On yllättävää, että melkein kaikki graafit, joilla on tärkeä rooli siinä, mitä nykyään kutsutaan "kemialliseksi graafiteoriaksi", yhdistetään toukkakaavioihin." Tässä yhteydessä toukkakaavioita kutsutaan myös bentsoidipuiksi tai Gutmann-puiksi Ivan Gutmanin tällä alalla tekemän työn mukaan [2] [11] [12] .

Muistiinpanot

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

Kirjallisuus

Linkit