THE MEDIAN TREE

Abstract

Mathematical models in which objects have a finite discrete structure are used to solve a wide range of practical problems. Such are, for example, many problems in automatic design, operation research, control theory, network planning, and computational geometry. Often, oriented or non-oriented graphs are considered as such models, which can adequately describe the structure of the problem of interest to us. Among these tasks, a certain place is occupied by tasks related to network issues of optimal placement of warehouses, certain service points, emergency, medical services, etc. When studying such issues, it becomes necessary to identify, in a certain sense, the central objects in the networks under consideration, and in order to find them, the concept of the shortest path between these two given elements plays an essential role.

A definition of the medial vertex of a graph is provided in the article – the vertex whose sum of distances to the others is minimal. The median of a non-oriented tree consisting of medial vertices is considered, and it is proved that the median of each such tree has either one vertex or two connected by an edge. This result is a definite generalization of a similar property of the center of a tree consisting of central vertices. The question of the relationship between the center and median of the same tree is also studied. The examples of trees with ten vertices show that such a direct connection does not exist, and there can be all four logically possible cases: the same tree can contain one or two central and one or two medial vertices.