Κλαδοπλάτος

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

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

Πλάτη[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

  • 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 .