Периферийные и псевдопериферийные узлы графа. Понятие корневой структуры уровней

Эффективность алгоритма RCM критическим образом зависит от выбора начального узла. Значительный практический опыт свидетельствует, что в качестве начальных в алгоритме Катхилла-Макки имеет смысл использовать узлы, удаленные друг от друга на максимальное или достаточно большое расстояние.

Вспомним некоторые понятия теоии графов. Расстояние между двумя узлами графа - это длина кратчайшего пути, соединяющего узлы. Эксцентриситет узла - это величина, определяемая в соответствии с формулой:

.

Диаметр графа – это

.

Узел называется периферийным, если его эксцентриситет равен диаметру графа. На рис.5 приведен пример графа с 8-ю узлами, диаметр которого равен 5. Пр этом узлы - периферийные.

Рис.5.

Целью является нахождение эффективного (эвристического) алгоритма для определения узлов с большим эксцентриситетом. Эвристический алгоритм не дает гарантии, что будет найден периферийный узел или хотя бы узел, близкий к периферийному. Тем не менее, получаемые узлы, как правило, имеют большой эксцентриситет и являются хорошими начальными значениями для использующих их алгоритмов. Кроме того, отыскание периферийных узлов, представляет собой «дорогостоящий» по вычислительной сложности процесс: наилучший известный алгоритм для этой задачи имеет в качестве оценки временной сложности величину .

Основной конструкцией, необходимой далее, является корневая структура уровней графа. При заданном узле корневой структурой уровней графа с корнем в узле называется такое разбиение множества

,

что

,

где — эксцентриситет узла ; — множество узлов графа, не принадлежащих , но смежных хотя бы с одним узлом из .

Эксцентриситет узла по отношению к структуре уровней называется длиной , а ширина структуры определяется как

.

На рис.6 показана корневая структура уровней для графа, приведенного на рис.5. Корень находится в узле . При этом , а .

Рис.6.