6.16. Сети связи

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

Рис. 6.38.

Ориентированный граф рис. 6.38 показывает возможности связи между некоторыми лицами или пунктами, соответствующими вершинам, причем стрелки показывают направления возможной передачи сообщений. Матрица вершин этого графа имеет вид

(см. скан)

(см. скан)

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

Замечание. На сильно связных графах определяется интересная мера, называемая индексом центральности. Она характеризует степень разброса вершин графа. Если мы определим матрицу отклонений, элементы которой задают минимальную длину пути от вершины до вершины и вычислим то индекс центральности вершины есть

Глобальный индекс центральности графа получается суммированием по всем

Упражнение 6.23. Вычислите индексы центральности и глобальный индекс центральности для нескольких графов. Сравните с понятием радиуса.

Синтез сети связи

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

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

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

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

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

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

и позволяет записать в виде

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

Опишем следующий процесс, предложенный в [12], [63], как необходимое и достаточное условие реализуемости матриц. Перегруппируем рассматриваемую матрицу, как это сделано с матрицей где Та и терминальные матрицы пропускных способностей.

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

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

В задаче синтеза сумма неизвестных пропускных способностей ребер, которые соответствуют разрезу с минимальной пропускной способностью,

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