Levélhatvány

Innen: testwiki
Ugrás a navigációhoz Ugrás a kereséshez
Egy fa (felül) és a hozzá tartozó 3-levélhatványa (alul)

A matematika, azon belül a gráfelmélet területén egy T fa Sablon:Mvar-adik levélhatványa az a G gráf, melynek csúcsai a T levelei, élei pedig azokat a levélpárokat kötik össze, melyek T-beli távolsága legfeljebb k. Más megfogalmazásban G a Tk gráfhatvány egy feszített részgráfja, melyet T levelei feszítenek ki. Egy ilyen módon konstruált G gráf esetén az eredeti T fát G Sablon:Mvar-adik levélgyökének nevezik. Egy gráf levélhatvány, ha egy gráf k-levélhatványa valamely k értékre.Sablon:Sfnp Az ilyen gráfoknak a filogenetikus (leszármazási alapú) rendszertan evolúciós fáinak rekonstrukciójában van szerepe.

Kapcsolódó gráfcsaládok

Mivel az erősen merev körű gráfok hatványai is erősen merev körűek, valamint a fák is erősen merev körűek, ezért a levélhatványok mindig erősen merev körű gráfok.[1] Valójában a levélhatványok az erősen merev körű gráfok valódi részhalmazai; egy gráf pontosan akkor levélhatvány, ha egy fixed tolerance NeST gráf (neighborhood subtree tolerance gráf),[2] melyek viszont az erősen merev körű gráfok valódi részhalmazai.[3] Sablon:Harvtxt megmutatják, hogy az intervallumgráfok, valamint a gyökeres irányított útgráfok nagyobb osztálya is levélhatvány. Az egység-intervallumgráfok pontosan azok a levélhatványok, melyek alapjait hernyófák képezik. A Sablon:Mvar-levélhatványok korlátos Sablon:Mvar-ra korlátos klikkszélességűek, de korlátlan kitevőre ez nem igaz.[4]

Struktúra és felismerés

Sablon:Megoldatlan Egy gráf akkor és csak akkor 2-levélhatvány, ha előáll klikkek diszjunkt uniójaként (tehát klasztergráf).Sablon:Sfnp Egy gráf pontosan akkor 3-levélhatvány, ha egy (bull,dart,gem)-mentes merev körű gráf.[5] Ilyen és hasonló karakterizációk alapján a 3-levélhatványok lineáris időben felismerhetők.Sablon:Sfnp A 4-levélhatványok karakterizációját Sablon:Harvtxt és Sablon:Harvtxt adják meg, ez szintén lehetővé teszi a lineáris idejű felismerést. A k ≥ 5 hatványokra a k-levélhatványok felismerése még nyitott kérdés, így az is, hogy általában a levélhatványok polinom időben felismerhetők-e.

Fordítás

Jegyzetek

Sablon:Reflist

Sablon:Refbegin

Sablon:Refend

Sablon:Portál

  1. ↑ Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt.
  2. ↑ Sablon:Harvtxt; Sablon:Harvtxt.
  3. ↑ Sablon:Harvtxt; Sablon:Harvtxt.
  4. ↑ Sablon:Harvtxt; Sablon:Harvtxt.
  5. ↑ Sablon:Harvtxt; Sablon:Harvtxt
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Levélhatvány&oldid=3775”