Κλαδοπλάτος

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

Στην θεωρία γράφων, μια κλαδοαποσύνθεση (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 .