Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

 

.

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

.

 

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

 

Рис.5.

 

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

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

 

,

что

,

 

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

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

 

.

 

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

 

Рис.6.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал