K-träd

Ett k -träd är en oriktad graf bildad av en komplett graf med ( k  + 1) hörn, med successiv addition av hörn så att varje adderad vertex v har exakt k grannar U så att k  + 1 hörn (vertex v + hörn U ) bilda en klick [1] [2] .

Beskrivningar

k -Träd är exakt de maximala graferna med en given trädbredd , det vill säga grafer till vilka en kant inte kan läggas till utan att öka trädbredden på grafen [2] . Dessa är också exakt ackordsgrafer , vars alla maximala klick är av samma storlek och alla vars minimala klickseparatorer också är av samma storlek k [1] .

Anslutna klasser av grafer

1-Träd är samma som orotade träd . 2-träd är maximala parallell-sekventiella grafer [3] , och de inkluderar också maximala ytterplanära grafer . Plana 3-träd är också kända som Apollonius-nätverk [4] .

Grafer som har trädbredd som mest k är exakt subgrafer av k -träd, och av denna anledning kallas de partiella k -träd [2] .

Grafer som bildas av kanter och hörn av k - dimensionella blockpolyedrar , det vill säga polyedrar som bildas, utgående från en simplex , genom successiv limning av ytor av simpliceringar, är k -träd om [5] . Denna limningsprocess efterliknar konstruktionen av k -träd genom att lägga till hörn till en klick [6] . Ett k -träd är en blockpolyedergraf om och endast om inga tre klick med ( k  + 1) hörn har k gemensamma hörn [7] .

Anteckningar

  1. ↑ 12 Patil , 1986 , sid. 57–64.
  2. ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2008 , sid. 390.
  3. ↑ Hwang, Richards, Winter, 1992 .
  4. ↑ Avstånd i slumpmässiga Apolloniska nätverksstrukturer Arkiverad 21 juli 2011 på Wayback Machine , samtalsbilder av Olivier Bodini, Alexis Darrasse, Michèle Soria från ett föredrag på FPSAC 2008, åtkoms 2011-03-06
  5. ↑ Koch och Perles, 1976 , sid. 420.
  6. ↑ Nedan, De Loera, Richter-Gebert .
  7. ↑ Kleinschmidt, 1976 , sid. 663–667.

Litteratur