K-strom

K - strom je neorientovaný graf vytvořený z úplného grafu s ( k  + 1) vrcholy, s postupným přidáváním vrcholů tak, že každý přidaný vrchol v má přesně k sousedů U , takže k  + 1 vrcholů (vrchol v + vrcholy U ) tvoří kliku [1] [2] .

Popisy

k -Stromy jsou přesně maximální grafy s danou šířkou stromu , tedy grafy, ke kterým nelze přidat hranu bez zvětšení šířky stromu [2] . Toto jsou také přesně akordické grafy , jejichž všechny maximální kliky jsou stejné velikosti a všechny jejich oddělovače minimálních klik jsou také stejné velikosti k [1] .

Propojené třídy grafů

1-Stromy jsou stejné jako nezakořeněné stromy . 2-stromy jsou maximální paralelně-sekvenční grafy [3] a zahrnují také maximální vnější rovinné grafy . Planární 3-stromy jsou také známé jako sítě Apollonius [4] .

Grafy, které mají šířku stromu nejvýše k , jsou přesně podgrafy k -stromů, az tohoto důvodu se nazývají částečné k -stromy [2] .

Grafy tvořené hranami a vrcholy k - rozměrných blokových mnohostěnů , tedy mnohostěnů vytvořených z simplexu postupným lepením ploch simplicí, jsou k -stromy if [5] . Tento proces lepení napodobuje konstrukci k -stromů přidáním vrcholů do kliky [6] . K - strom je blokový polyedrový graf právě tehdy, když žádné tři kliky s ( k  + 1) vrcholy nemají k společných vrcholů [7] .

Poznámky

  1. ↑ 12 Patil , 1986 , s. 57–64.
  2. ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2008 , str. 390.
  3. ↑ Hwang, Richards, Winter, 1992 .
  4. ↑ Vzdálenosti v náhodných apollónských síťových strukturách Archivováno 21. července 2011 na Wayback Machine , diapozitivy přednášky Oliviera Bodiniho, Alexise Darrasse, Michèle Soria z přednášky na FPSAC 2008, přístup 2011-03-06
  5. ↑ Koch a Perles, 1976 , s. 420.
  6. ↑ Níže, De Loera, Richter-Gebert .
  7. ↑ Kleinschmidt, 1976 , s. 663–667.

Literatura