hello everyone , I want to know if a tree has a single centroid because I encounter some cases where I find 2 centroids...
thanks in advance ...
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:18:50
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:18:50
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 18:16:12 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Obviously no, check this one : 1-2-3-4
The reason of my question was being confused by jordan 1869 theorem : " there exists a vertex whose removal partitions the tree into components, each with at most N/2 nodes. " I didn't know if it is talking about only one vertex or more ... thanks a lot ...
"There exists" means that there is at least one, but there could me multiple ones.
Actually, there can be at most 2 centroids in a tree and this happens when there's an edge whose deletion splits the tree in half.
a tree either has a single centroid or two neighbouring centroids.
If your question is that is there any tree with one centriod:
yes a star( V=1..n , E=(1,n),(2,n)...(n-1,n) ).
else
tree has at most 2 centroids that if they are 2 they are connected!