Κλαδοπλάτος

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

Για κάθε ακμή  του , το γράφημα  αποτελείται από δύο δέντρα 
 και , τα φύλα των οποίων ορίζουν (μέσω της )
μια διαμέριση  του συνόλου των ακμών του  την οποία καλούμε -διαμέριση.

Πλάτη
Το πλάτος μιας -διαμέρισης είναι το πλήθος των κορυφών του   που  πρόσκεινται συγχρόνως 
σε τουλάχιστον μια ακμή του  και  σε τουλάχιστον μια ακμή του .

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

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

Αναφορές

 .

Κατηγορία:Θεωρία γράφων