Тақсимоти марказӣ

Тақсимоти сентроидӣ

Муқаддима ба Декомпозитсияи Сентроид

Декомпозитсияи Сентроид як техникаест, ки барои ҷудо кардани дарахт ба маҷмӯи зердарахтон тавассути такроран хориҷ кардани гиреҳҳои сентроид истифода мешавад.

Таърифи Сентроид

Сентроид дар дарахт гиреҳест, ки пас аз хориҷ кардани он, дарахт ба зердарахтоне ҷудо мешавад, ки ҳеҷ як зердарахт аз нисфи шумораи умумии гиреҳҳои дарахти аслӣ зиёд нест.

Ба таври расмӣ, гиреҳи $v$ сентроид аст, агар ҳар як зердарахте, ки бо хориҷ кардани $v$ ҳосил мешавад, ҳадди аксар $\frac{N}{2}$ гиреҳ дошта бошад, ки дар он $N$ шумораи умумии гиреҳҳо дар дарахт аст.