Κλαδοπλάτος

Πρότυπο:Χωρίς παραπομπές Πρότυπο:Ορφανό Στην θεωρία γράφων, μια κλαδοαποσύνθεση (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$.

Αναφορές

• Πρότυπο:Citation.