При решении прикладных задач часто возникает необходимость обхода вершин графа, связная с поиском вершин, удовлетворяющих определенным свойствам.
Пусть связный неориентированный граф T некоторый остов графа G, a некоторая фиксированная вершина, называемая корнем дерева T. Разместим вершины из M по этажам таким образом, чтобы корень a находился в верхнем этаже, смежные с ним вершины занимали этаж на единицу ниже, смежные с отмеченными вершинами еще на единицу ниже и т.д. (рис. 4.35). таким образом, получаем e(a) 1 этажей, где e(a) эксцентриситет вершины a.
a
1
2
3
4