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 ...
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.09.2024 14:56:27 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
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!