K-træ

Et k -træ er en urettet graf dannet ud fra en komplet graf med ( k  + 1) hjørner, med successiv tilføjelse af knudepunkter, således at hvert tilføjet knudepunkt v har nøjagtigt k naboer U , således at k  + 1 knudepunkter (hjørnepunkt v + spidser U ) danne en klike [1] [2] .

Beskrivelser

k -Træer er præcis de maksimale grafer med en given træbredde , det vil sige grafer, hvortil en kant ikke kan tilføjes uden at øge træbredden af ​​grafen [2] . Disse er også præcis akkordgrafer , hvis maksimale kliker er af samme størrelse og alle deres minimale klikseparatorer også er af samme størrelse k [1] .

Forbundne klasser af grafer

1-træer er det samme som træer uden rod . 2-træer er maksimale parallel-sekventielle grafer [3] , og de inkluderer også maksimale ydreplanære grafer . Plane 3-træer er også kendt som Apollonius-netværk [4] .

Grafer, der har træbredde højst k er nøjagtigt undergrafer af k -træer, og af denne grund kaldes de partielle k -træer [2] .

Grafer dannet af kanter og hjørner af k - dimensionelle blokpolyedre , det vil sige polyedre dannet, startende fra et simpleks , ved successiv limning af flader af simplicer, er k -træer, hvis [5] . Denne limningsproces efterligner konstruktionen af ​​k -træer ved at tilføje toppunkter til en klike [6] . Et k -træ er en blokpolyedergraf, hvis og kun hvis ingen tre kliker med ( k  + 1) knudepunkter har k fælles knudepunkter [7] .

Noter

  1. ↑ 12 Patil , 1986 , s. 57-64.
  2. ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2008 , s. 390.
  3. ↑ Hwang, Richards, Winter, 1992 .
  4. ↑ Afstande i tilfældige Apollonske netværksstrukturer Arkiveret 21. juli 2011 på Wayback Machine , talk slides af Olivier Bodini, Alexis Darrasse, Michèle Soria fra en tale på FPSAC 2008, tilgået 2011-03-06
  5. ↑ Koch og Perles, 1976 , s. 420.
  6. ↑ Nedenfor, De Loera, Richter-Gebert .
  7. ↑ Kleinschmidt, 1976 , s. 663-667.

Litteratur