Аннотация

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

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

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

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

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

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