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 ...
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 151 |
9 | maroonrk | 151 |
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 ...
Name |
---|
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!