Tree Centroid Properties Clarification
The paper is devoted to the tree centroid properties clarification. Attention of the authors was attracted by the popular problem of (binary) partition of a graph. The solution is known only by brute force algorithm. It was found that for a ”economical” partition of a tree it makes sense to consider...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2017-08-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/531 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849240841350021120 |
|---|---|
| author | Yurii A. Belov Sergei I. Vovchok |
| author_facet | Yurii A. Belov Sergei I. Vovchok |
| author_sort | Yurii A. Belov |
| collection | DOAJ |
| description | The paper is devoted to the tree centroid properties clarification. Attention of the authors was attracted by the popular problem of (binary) partition of a graph. The solution is known only by brute force algorithm. It was found that for a ”economical” partition of a tree it makes sense to consider partitions in the neighborhood of centroid vertices, the definition of which is presented. In the paper, we proposed proofs connected with the limitation of their weight. It is also proved that if there are two centroid vertices in a tree, they are adjacent. In what follows, it is noted that three such vertices can not be in the tree. The corresponding statements are made. According to the first one, any vertex of a tree with a certain restriction on its weight is centroid. According to one of the points of the second statement, if there are two centroid vertices in the tree, the order of the tree is an even number. The third statement says that if a tree has a centroid vertex of limited weight, there is another centroid vertex of the same weight and adjacent to the first one. To prove the propositions, we consider the branch of greatest weight with a centroid vertex and take in this branch another vertex adjacent to the centroid. In this paper, Jordan’s theorem is used, three images are used in the presentation of the material. |
| format | Article |
| id | doaj-art-ea6b4abc2caf4cfeb74277bd7acc702b |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2017-08-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-ea6b4abc2caf4cfeb74277bd7acc702b2025-08-20T04:00:26ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172017-08-0124441041410.18255/1818-1015-2017-4-410-414377Tree Centroid Properties ClarificationYurii A. Belov0Sergei I. Vovchok1P.G. Demidov Yaroslavl State UniversityP.G. Demidov Yaroslavl State UniversityThe paper is devoted to the tree centroid properties clarification. Attention of the authors was attracted by the popular problem of (binary) partition of a graph. The solution is known only by brute force algorithm. It was found that for a ”economical” partition of a tree it makes sense to consider partitions in the neighborhood of centroid vertices, the definition of which is presented. In the paper, we proposed proofs connected with the limitation of their weight. It is also proved that if there are two centroid vertices in a tree, they are adjacent. In what follows, it is noted that three such vertices can not be in the tree. The corresponding statements are made. According to the first one, any vertex of a tree with a certain restriction on its weight is centroid. According to one of the points of the second statement, if there are two centroid vertices in the tree, the order of the tree is an even number. The third statement says that if a tree has a centroid vertex of limited weight, there is another centroid vertex of the same weight and adjacent to the first one. To prove the propositions, we consider the branch of greatest weight with a centroid vertex and take in this branch another vertex adjacent to the centroid. In this paper, Jordan’s theorem is used, three images are used in the presentation of the material.https://www.mais-journal.ru/jour/article/view/531entroidtree centroid |
| spellingShingle | Yurii A. Belov Sergei I. Vovchok Tree Centroid Properties Clarification Моделирование и анализ информационных систем entroid tree centroid |
| title | Tree Centroid Properties Clarification |
| title_full | Tree Centroid Properties Clarification |
| title_fullStr | Tree Centroid Properties Clarification |
| title_full_unstemmed | Tree Centroid Properties Clarification |
| title_short | Tree Centroid Properties Clarification |
| title_sort | tree centroid properties clarification |
| topic | entroid tree centroid |
| url | https://www.mais-journal.ru/jour/article/view/531 |
| work_keys_str_mv | AT yuriiabelov treecentroidpropertiesclarification AT sergeiivovchok treecentroidpropertiesclarification |