Блог пользователя ChemliYoussef

centroid of a tree
Автор ChemliYoussef, история, 8 лет назад, По-английски

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 ...

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Obviously no, check this one : 1-2-3-4

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ...

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      "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.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

a tree either has a single centroid or two neighbouring centroids.

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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!

→ Ответить