Κλαδοπλάτος

Στην θεωρία γράφων, μια κλαδοαποσύνθεση (branch decomposition) ενός γραφήματος $G=(V,E)$ είναι ένα ζεύγος $(T,\tau )$ όπου το $T$ είναι ένα τριαδικό δέντρο (ένα δέντρο με όλες τις εσωτερικές κορυφές βαθμού 3) και το $\tau$ είναι μια 1-1 και επί αντιστοιχία των φύλλων του $T$ με τις ακμές του $G$.

Για κάθε ακμή $e$ του $T$, το γράφημα $T/e$ αποτελείται από δύο δέντρα $T_{1}$ και $T_{2}$, τα φύλα των οποίων ορίζουν (μέσω της $\tau$) μια διαμέριση $(E_{1},E_{2})$ του συνόλου των ακμών του $G$ την οποία καλούμε $e$-διαμέριση.

Πλάτη

Το πλάτος μιας $e$-διαμέρισης είναι το πλήθος των κορυφών του $G$ που πρόσκεινται συγχρόνως σε τουλάχιστον μια ακμή του $E_{1}$ και σε τουλάχιστον μια ακμή του $E_{2}$.

Το πλάτος μιας κλαδοαποσύνθεσης είναι το μέγιστο πλάτος μιας $e$-διαμέρισης'.

Το κλαδοπλάτος του $G$ είναι το ελάχιστο πλάτος μιας κλαδοαποσύνθεσης του $G$.

Αναφορές

• Robertson, N.; Seymour, P.D. (1991), «Graph minors. X. Obstructions to tree-decomposition», Journal of Combinatorial Theory 52 (2): 153–190, doi:10.1016/0095-8956(91)90061-N .