Nella teoria dei grafi, un k-albero è un grafo non orientato formato partendo da un grafo completo con (k+1) vertici e quindi aggiungendo ripetutamente vertici in modo tale che ogni vertice aggiunto v abbia esattamente k vicini U tali che, insieme, i k+1 vertici formati da v e U costituiscano una cricca.
Caratterizzazioni I k-alberi sono esattamente i grafi massimali con una treewidth pari a k ("massimale" significa che non è possibile aggiungere altri archi senza aumentare la loro treewidth). Essi sono anche esattamente i grafi cordali le cui cricche massimali hanno tutte la stessa dimensione k + 1 e anche quelli per i quali tutti separatori di cricca minimi hanno anche la stessa dimensione k.
Classi di grafi correlate Gli 1-alberi sono alberi. I 2-alberi sono grafi serie-paralleli massimali, e includono anche i grafi planari esterni massimali. Gli 3-alberi planari sono anche noti come reti apollinee.
I grafi che hanno treewidth massima pari a k sono esattamente i sottografi di k-alberi e per tale motivo sono chiamati k-alberi parziali.
I grafi formati dagli archi e dai vertici di politopi impilati k-dimensionali, politopi formati partendo da un simplesso e poi incollando ripetutamente i simplessi sulle facce del politopo, sono k-alberi quando k ≥ 3. Questo processo di incollaggio imita la costruzione di k-alberi aggiungendo vertici a una cricca. Un k -albero è il grafo di un politopo impilato se e solo se non ci sono tre (k + 1) cricche di vertici che hanno k vertici in comune.
Note
Collegamenti esterni
Categoria:Famiglie di grafi Categoria:Alberi (teoria dei grafi)