Hernyó (gráfelmélet)

A hernyó vagy hernyófa  olyan fa , amelynek minden csúcsa legfeljebb 1 távolságra van a központi úttól.

A hernyógráfokat először Harari és Schwenk tanulmányaiban tanulmányozták. A nevet Arthur Hobbs [1] [2] javasolta . Ahogy Harari és Schwenk [3] ékesszólóan írta : "A hernyó olyan fa, amely ösvényré változik, ha a gubót eltávolítják a végpontokról" [1] .

Egyenértékű leírások

A következő jellemzők írják le a hernyógráfokat:

Általánosítások

A K - fa egy akkordgráf , amely pontosan n − k maximális klikket tartalmaz, amelyek mindegyike k + 1 csúcsot tartalmaz. Egy k -fában, amely önmagában nem ( k + 1)-klikk , minden maximális klikk vagy két vagy több komponensre bontja a gráfot, vagy tartalmaz egy ( k- )levelű csúcsot, amely csak egy maximális klikkhez tartozik. A k -út egy k -fa legfeljebb két levelével, a k -hernyó pedig egy k -fa, amely k -útra és több k -levélre osztható, mindegyik a k k -klikk elválasztójával szomszédos. - út. Ebben a terminológiában az 1-hernyó ugyanaz, mint a hernyógráf, a k -hernyók pedig k útszélességű él-maximális gráfok [ 7] .

A rák  olyan fa , amelynek minden csúcsa legfeljebb 2 távolságra van a központi úttól [9]

Felsorolás

A hernyók ritka esetei a gráffelszámítási problémáknak , ha a pontos képlet ismert - ha n  ≥ 3, akkor az n csúcsú hernyók száma [1] .

n = 1, 2, 3, … esetén az n csúcsú hernyók száma

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … ( A005418 sorozat az OEIS -ben ).

Számítási összetettség

A szerződő hernyó megtalálása NP-teljes probléma . A megfelelő optimalizálási probléma a minimum kontrakciós hernyó probléma (MPCT), amelyben az árak a széleken vannak megadva, és a cél egy olyan hernyó megtalálása, amely minimalizálja az árakat. Itt a hernyó árát a szélei árának összegeként határozzuk meg, és minden élnek két ára van, attól függően, hogy levélről vagy belső élről van szó. Nincs f(n) -közelítő algoritmus az SMSH-hoz, hacsak nem teljesül a P = NP . Itt f(n) n tetszőleges függvénye, amelyet polinomiális időben számítanak ki, n pedig a gráf csúcsainak száma [10] .

Létezik egy parametrizált algoritmus, amely egy korlátos faszélességű gráfban megtalálja a GSGM optimális megoldását . Így mind az összehúzódó hernyóproblémának, mind a minimális összehúzódó hernyóproblémának van lineáris idő algoritmusa, ha a gráf síkon kívüli , párhuzamos-szekvenciális vagy Halin -gráf [10] .

Alkalmazások

A hernyókat a kémiai gráfelméletben használják a benzenoid szénhidrogének molekulaszerkezetének ábrázolására . Ebben az ábrázolásban a molekulák hernyókat alkotnak, amelyek mindegyik éle egy 6 szénatomos gyűrűnek felel meg, és két él egy csúcsba esik, ha a megfelelő benzolgyűrűk lineárisan kapcsolódó gyűrűk sorozatához tartoznak. El-Bazil ezt írja: "Meglepő, hogy szinte minden gráf, amely fontos szerepet játszik abban, amit ma "kémiai gráfelméletnek" neveznek, a hernyógráfokhoz kapcsolódik." Ebben az összefüggésben a hernyógráfokat benzoid fákként vagy Gutmann fákként is ismerik Ivan Gutman e területen végzett munkája nyomán [2] [11] [12] .

Jegyzetek

  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  a Wolfram MathWorld webhelyén .
  10. ↑ Khosravani 12. 2011 .
  11. ↑ Gutman, 1977 , p. 309–315.
  12. ↑ El-Basil, 1990 , p. 273–289.

Irodalom

Linkek