Аннотация

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

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

В работах [1–3] был выделен ряд классов графов диаметра два и полученызна чения (оценки) числа элементов доминирующих множеств, что позволяет строить структуры коммуникаций с заданными характеристиками.

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

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