K-arborele

Un k -arbore este un graf nedirecționat format dintr-un graf complet cu ( k  + 1) vârfuri, cu adăugare succesivă de vârfuri astfel încât fiecare vârf adăugat v să aibă exact k vecini U astfel încât k  + 1 vârfuri (vârf v + vârfuri U ) formează o clică [1] [2] .

Descrieri

k -Arborii sunt exact graficele maxime cu o lățime de arbore dată , adică grafice la care nu se poate adăuga o muchie fără a crește lățimea arborelui graficului [2] . Acestea sunt, de asemenea, exact grafuri de acorduri , ale căror clicuri maxime sunt de aceeași dimensiune și toți separatorii de clicuri minime sunt, de asemenea, de aceeași dimensiune k [1] .

Clase conectate de grafice

1-Copacii sunt la fel cu copacii nerădăcinați . 2-arborele sunt grafice maximale paralele-secvențiale [3] și includ, de asemenea, grafice maxime exterioare planare . Arborii planari 3 sunt cunoscuți și ca rețele Apollonius [4] .

Graficele care au lățimea arborilor de cel mult k sunt exact subgrafe ale k -arborilor și din acest motiv sunt numite k -arbori parțiali [ 2] .

Graficele formate din muchii și vârfuri ale poliedrelor bloc k -dimensionale , adică poliedre formate, începând de la un simplex , prin lipirea succesivă a fețelor simplexelor, sunt k -arbori dacă [5] . Acest proces de lipire imită construcția de k -arbori prin adăugarea de vârfuri la o clică [6] . Un k -arbore este un graf cu poliedru bloc dacă și numai dacă nu există trei clicuri cu ( k  + 1) vârfuri care au k vârfuri comune [7] .

Note

  1. ↑ 12 Patil , 1986 , p. 57–64.
  2. ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2008 , p. 390.
  3. ↑ Hwang, Richards, Winter, 1992 .
  4. ↑ Distances in random Apollonian network structures Arhivat 21 iulie 2011 la Wayback Machine , diapozitive de discuție de Olivier Bodini, Alexis Darrasse, Michèle Soria dintr-o discuție la FPSAC 2008, accesat 2011-03-06
  5. ↑ Koch și Perles, 1976 , p. 420.
  6. ↑ Mai jos, De Loera, Richter-Gebert .
  7. ↑ Kleinschmidt, 1976 , p. 663–667.

Literatură