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 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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!