Распределенные вычислительные системы
Оптимизационные задачи и распределенная среда
А. М. Раппопорт, Л. С. Гнеденко "Метрические характеристики композиции графов диаметра два"
Прикладные задачи распределенных вычислений
А. М. Раппопорт, Л. С. Гнеденко "Метрические характеристики композиции графов диаметра два"

Аннотация

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

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

При проектировании различного рода сетевых структур нередко возникает необходимость объединения ряда локальных подсистем с известными метрическими характеристиками в единую, также удовлетворяющую определенным метрическим требованиям. Развитие этого направления приводит к изучению метрических характеристик графа, получающегося в результате такой процедуры.

Эта задача в общем случае не имеет простого решения, (нахождение числа доминирования, в частности, — NP- полно). Ранее в работах [1]–[4] был получен ряд конструктивных условий на графы с заданными диаметром и числом доминирования и предложены способы их построения.

В статье представлена общая конструкция, объединяющая совокупность графов с известными метрическими характеристиками в единую структуру, для которой удается оценить диаметр и число доминирования. Их значения также находятся в ряде конкретных ситуаций, когда диаметр исходных графов не превосходит двух.

 

Скачать статью в формате pdf

2019-69-2
2019-69-1
2018-68-4
2018-S1

© ФИЦ ИУ РАН 2008-2018. Создание сайта "РосИнтернет технологии".