Как выбрать лучшую структуру сети

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

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

В работе [2] приводятся результаты о полном количестве (р, q) - графов с р вершинами и q ребрами и о количестве связных (р, q) - графов. Таблицы с небольшими значениями р и q приводятся многими авторами в публикациях. Приведенные здесь таблицы 1, 2 заимствованы из [2, стр.281]. Эти таблицы могут служить отправным пунктом для многих исследований сетей в различных предметных областях. Разработка новых методов получения результатов не только существования таких графов (числа графов), но перечислительного представления (желательно визуального) самих графов имеет несомненный интерес для практики и может служить прекрасной мотивировкой исследований. Дело в том, что даже в предлагаемой работе [2] перечисление графов в задачах ограничено и не доводится до визуальной формы (до изображений), а часто завершается получением производящих функций. Поэтому тем, кто стремится проводить глубокий анализ структур сетей, необходим для такого анализа (и возможно синтеза) перечень конкретных графов (их рисунков), что позволяет привлекать когнитивные способности человеческого мозга к поиску наилучших решений.

Таблица 1 – Число (р, q) - графов

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

Таблица 2 – Число связных (р, q) -графов

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

Классификация графов

Определение графа. Обыкновенный граф G (V, U) порядка n представляет собой конечное непустое множество V, содержащее n = |V| вершин, и множество U неупорядоченных пар U ≤ V×V из р = |U| различных вершин (v_i, v_j); при таком определении автоматически исключаются петли при вершинах и параллельные (кратные) между парами вершин ребра. Пара вершин u_ij = (v_i, v_j), соединенных отрезком линии и принадлежащая множеству U, называется ребром графа G и говорят, что ребро u_ij соединяет вершины v_iи v_j. Вершины v_iи v_j называются при этом смежными.

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

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

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

Хорошая классификация должно обладать свойством предсказания, обеспечивать прогнозы, выполнение расчетов, например, объемов классов, перечисление его элементов и свойств. В публикации предлагается такой набор свойств: количество вершин, количество ребер, распределение степеней вершин (РСВ), изоморфизм. Примером класса (Табл. 6) в этой классификации могут быть: 6-вершинники с 8 ребрами, фиксированным РСВ <123334>, неизоморфные графы.

Подобная классификация просто описывается деревом с 4-мя ярусами: 1-й вершины, 2-й ребра, 3-й РСВ, 4-й изоморфизм. Решение прикладных задач с использованием классов в рамках подобной классификации предусматривает привлечение разнообразного математического инструментария: комбинаторного анализа сочетаний, разбиений числа, установления (проверки) изоморфизма графов, включаемых в конкретный класс.

Свойства графов и их элементов

Инцидентность. Пара вершин vi, vj являющихся оконечными в ребре u_ij = (v_i, v_j), называются инцидентными ребру, а ребро – инцидентным каждой из этих вершин.

Степень вершины. Каждой вершине vi графа с номером i, i = 1(1) n, инцидентно di ребер di = 0(1) n – 1. Переменная (величина) di называется степенью вершины графа. Множество вершин графа описывается характеристикой D = <d1, d2, d3, …, dn> – распределение степеней вершин (РСВ). Число вершин в графе, имеющих нечетные степени – четно, а сумма степеней всех вершин графа равна удвоенному количеству ребер D_σ = ∑_i≤ndi = 2р.

Главный подход (цель) при классификации – собрать в классы объекты с одинаковыми наборами, но с разными значениями показателей свойств. Визуально графы легко различаются значениями: n = |V| – количеством вершин, р = |U| – количеством ребер, di – значениями степеней вершины ( количеством ребер, сходящихся в одной i-й вершине ) и вектором D = <d1, d2, d3, …, dn> – распределением степеней вершин (РСВ) графа. Это существенно упрощает контроль принадлежности графа классу.

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

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

Векторы D с различными значениями n компонентов, сумма которых постоянна, удобно описывать разбиениями четного числа 2р на n блоков (частей). Для формирования конкретного класса графов необходим алгоритм генерации графов - элементов класса.

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

Пример. Ниже в таблице 6 приводится множество графов, образующих класс G (6, 8). В этом классе можно увидеть и выделить подкласс G (6, 8, D), где D =.<d1, d2, d3, …, d6>=<1,2,3,3,3,4>. Подкласс образуют графы с номерами G9, G10, G11, G13

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

Некоторые типы матриц для графа

Генерация графов заданного класса

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

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

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

В этой ситуации в ряде классов G (n, p, D) графы с одинаковыми D, n и р оказываются разными. Их структуры не совпадают (не совмещаются) при наложении графов одного на другой. Другими словами, существует признак, который делает графы, принадлежащие классу, а, следовательно, и структуры разными. Этот признак скорее качественный, чем количественный и называется изоморфизм. Разные по структуре графы – неизоморфны.

При известных числах вершин (n) и ребер (p) в классе G (n, p), его объем определяется как число сочетаний из числа ребер в полном n-вершиннике по заданному числу р ребер моделируемого класса.

Пример 1. Для класса обыкновенных графов G (n, p) = G (5, 7) получить множество всех графов. Необходимо генерировать для 5-вершинников все семиреберники. Решение этой задачи возможно несколькими путями, зависящими от формы представления графов: рисунками, сочетаниями, матрицами или как-то иначе. Выберем представление графа сочетанием ребер. Полный обыкновенный 5-вершинный граф (рис. 1) содержит р =10 ребер, но в задаче требуются 7-реберные графы, ребра которых должны связывать пары из 5 вершин и создавать разные структуры, следовательно, в полном графе необходимо для получения 7-реберника убрать 3 ребра. В класс попадает столько графов, сколько существует различных вариантов убрать три ребра из десяти.

Предварительно в полном 5-вершиннике пронумеруем позиции всех его десяти ребер (рисунок 1 полный 5-вершинник). Тогда каждому очередному графу сочетание из списка (табл. 3) укажет в какие позиции полного графа должны укладываться 7 заданных ребер. Таких сочетаний (следовательно, и структур графов) существует 120.

С другой стороны, для сочетаний справедливы 120 соотношений, из которых следует, что для получения семиреберников с 5 вершинами из полного 5-вершинника можно удалять 3 ребра. Для этого необходимо генерировать сочетания по три ребра из 10, и получаемые в списке сочетаний тройки с номерами ребер удалять из полного графа.

Таблица 3 – Нумерованные сочетания из 10 ребер по 3, которые удаляются из полного графа, чтобы получить все 5-вершинные 7-реберники

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

Изоморфизм графов. Два графа А и В с матрицами смежности n × n, называются изоморфными (обозначается А≈ В) тогда и только тогда, когда существует g-матрица (подстановочная) порядка n, соответствующая подстановке g ϵ S_n , для которой выполняется g А g^-1 = В. Здесь g и g^-1 прямая и обратная подстановочные матрицы порядка n × n. Для всех матриц А (G(n, p)) смежности графа в классе G(n, p)  вводится понятие «старшинство» матриц.

Любую (0, 1) -матрицу можно представить двоичным числом, выписывая последовательно ее строки одну за другой с 1-й до n-й. Эту (0, 1) -последовательность прочитывают как двоичное число. Для двух сравниваемых матриц старшей будет та, для которой число больше. Для симметрических матриц смежности графа можно (при преобразовании ее в число) ограничиться верхней треугольной частью. Наибольшее число старшей матрицы в классе называется кодом Харари матрицы.

Если при действии на А любой g-матрицей из симметрической группы S_nподстановок степени n ее старшинство в линейно-упорядоченном множестве матриц не возрастает, т.е. для любой g ϵS_n, g А g^-1 ≤ А, то А – каноническая матрица. Очевидно, две различные канонические матрицы смежности графов соответствуют неизоморфным графам.

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

Рисунок 2 -При получении 5-вершинников с одной вершиной степени di = 2 (РСВ D =<2 3 3 3 3>) из полного графа необходимо удалять три ребра: пару ребер инцидентных этой вершине и третье ребро, не инцидентное трем вершинам, удаляемых ребер. В полном графе с каждой вершиной инцидентны 4 ребра из чего следует шесть возможностей удаления двух из них 4(4 – 1)/2 = 6.

Другими словами, с каждой вершиной связаны 6 изоморфных графов, а вершин в графе 5, следовательно, получаем 6×5 = 30 изоморфных графов, в которых одна из вершин имеет степень два. Рисунок 2 поясняет приводимые рассуждения. Пятая вершина имеет степень два (d₅ = 2), удалены два инцидентных ребра с номерами 4 и 9. Этим двум ребрам инцидентны три вершины v₅, v₁, v₃ не инцидентное ребро связывает другие вершины v₂, v₄. Оно будет третьим удаляемым ребром.

Пример 2. Простейшими примерами неразличимости неизоморфных графов по трем признакам в таких классах могут быть:

6-вершинники с 6-ю ребрами и РСВ вида D = <2, 2, 2, 2, 2, 2>; пара графов: один граф цикл (кольцо), содержащий все вершины, другой – два треугольника;

8-вершинники с 8-ю ребрами и РСВ вида D = <2,2,2,2,2,2,2,2>, аналогично цикл (кольцо) или два четырехугольника. Наложение пар таких графов одного на другой покажет несовпадение их структур, т.е. пары графов неизоморфны. Второй граф в паре несвязен.

Граф (полный) 6-вершинник имеет 15 ребер. Мы рассматриваем два 6-вершинных 6-реберника: один граф – кольцо и второй – несвязный 6-вершинник – два треугольника. В полном списке графов 6-вершинников с шестью ребрами (их существует 5005) кольцо имеет код сочетания 1,5,6,10,13,15 и порядковый номер № 1613, а пары несвязных треугольников, например, с кодами 4, 5, 15, 6, 7, 10 и 1,2,6,12,13,15 получают соответственно № 4099 и № 587.

Разбиения числа. Как определить и задать РСВ графов? Степени вершин графа удобно описывать разбиениями четного числа (удвоенного числа ребер) на n блоков. Среди множества разбиений (табл.4) будут встречаться такие, которые представляют РСВ графов из классов с заданными количествами вершин и ребер. Степень di любой вершины обыкновенного графа G (V, P) не может превышать di ≤ n – 1 их число в графе.

Пример 3. Для класса G (5, 7) все возможные РСВ, содержащиеся в списке разбиений числа 14 на 5 частей помещены в таблице 4 ниже.

Таблица 4 – нумерованные разбиения четного числа 14 на 5 частей

Все разбиения подразделяются на графические и неграфические. Неграфическими разбиениями являются, содержащие блоки со значением n = 5 и более. Такие блоки не могут быть компонентами РСВ 5-вершинника. В таблице выше это разбиения с номерами: 1 – 11, 13 –16, 19, 20.

Следовательно, проверке разбиения на возможность стать РСВ должны подвергаться только разбиения с номерами: 12, 17, 18, 21–23. Построить графы с номерами компонентов РСВ 12 и 17 невозможно, поэтому остаются допустимыми только четыре РСВ: 18, 21–23, соответствующие неизоморфным графам.

Связность графа

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

Так в примере 2 задаются две пары графов: в первой паре оба графа имеют число (n = 6) вершин и число (p = 6) ребер графа равными, одинаковы у них и РСВ <222222> – распределение степеней вершин (РСВ), во второй паре графы также имеют число (n = 8) вершин и число (p = 8) ребер графа равными, одинаковы у них и РСВ <22222222> – распределение степеней вершин (РСВ), но вторые графы в этих парах генерируемых графов – несвязные (рис.3).

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

Определение. Вершинной связностью τ = τ(G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Это вершинная связность.

Определение. Реберной связностью λ =λ(G) графа G называется наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

Граф называется связным, если каждая пара его вершин связана. Это означает, что между каждой парой вершин существует путь.

 Алгоритмы установления (проверки) связности графа

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

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

– минимальная степень (d) вершин в графе;

– минимальное число ребер (р_min), образующих сечение в графе;

– минимальное число вершин (u_min), образующих сечение в графе, что соответствует гарантированному числу вершинно-независимых путей, связывающих произвольную пару вершин в графе;

– число деревьев (корневых) содержащихся в графе.

Для вероятностных графов в качестве показателей связности называются следующие:

– вероятность связности графа;

– вероятность существования хотя бы одного пути, связывающего произвольную пару вершин.

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

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

Это свойство следует из того, что если в графе выбрать пару вершин, которые наиболее удалены одна от другой и, «потянуть» за вершины в противоположные стороны, то все ребра цепи, связывающей эту пару вершин, выстроятся в одну линию. Очевидно, самая длинная цепь в графе, возникает тогда, когда она содержит все n его вершин, при этом она будет состоять из n – 1 ребра.

Пример 4. Задан размеченный граф (8-вершинник) с 16 ребрами (рис. 5). В нем выбрана пара не смежных вершин v = 3, v = 8. Результат эластичного растяжения графа и его ребер изображен на (рис. 5). Вершины v = 3, v = 8 связаны цепью, содержащей все остальные вершины графа и n – 1 ребро, следовательно, граф является связным.

Матричный алгоритм установления связности. Другое свойство графа связано с матрицей смежности А_[n] графа. Если матрицу графа последовательно возводить в степень k, k = 2(1)(n – 1), то элементы последовательно получаемых матриц описывают для соответствующих пар вершин число связывающих их цепей «длины» k, которая измеряется числом ребер.

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

Для связного графа матрица С_[n](n – 1) = 1_[n]+ ∑_к<nА^к_[n] не содержит нулевых элементов. Если это не так, то граф, для которого определена матрица С_[n] не является связным. Таким образом, алгоритм определения С_[n] (n – 1) позволяет установить факт связности (несвязности) графа.

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

Таблица 5 – Нумерованные разбиения четного числа 16 на 6 частей

Метод использует матрицу смежности А_[n] рассматриваемого графа. Если пара (vi, vj) вершин соединена ребром, то элемент матрицы а_ij = 1, если нет, то а_ij = 0. Подсчитывается количество единиц в каждой строке и подставляют эти значения вместо нулей на главной диагонали в той же строке. Все единицы, не лежащие на главной диагонали, заменяют на (–1). Теперь при отбрасывании любой вершины i, т. е. вычеркивания i-х строки и столбца получаем матрицу    В_[n-1]. Вычисляя значение определителя матрицы В_[n–1] определяем является ли граф связным или нет.

Если detВ_[n-1] >0, то граф является связным, если detВ_[n-1] ≤ 0, то граф не является связным. Этот алгоритм подробно описан в работе [1] и использован автором при вычислениях. Завершая изложение публикации, приведем пример построения всех (22 графа )связных графов класса G(6, 8), представляемых матрицами смежности и изображениями в одинаковом порядке. Над каждым изображаемым графом выписаны векторы D – распределения степеней его вершин.

Таблица 6 – Матричное представление нумерованных графов класса G (6, 8). Объем класса 22 графа, что можно увидеть в таблице 2.

Визуальные изображения графов класса G (6, 8) с указанием для каждого из них РСВ

Заключение. Пришло время ответить на вопрос, поставленный в задаче в начале текста. Как выбрать лучшую структуру для сети? Обратимся к рисунку 4. На нем представлен класс графов G(5,7) – это всего 4 изображения связных 5-вершинников с 7 ребрами. Из этих 4-х структур предстоит сделать выбор лучшей структуры для сети в смысле надежности ее функционирования в условиях возмущающих воздействий. Эти воздействия могут приводить к отказам линий связи: одной или более с вычисляемой вероятностью. Левая конфигурация отклоняется при выборе лучшей сразу, так как при ее выборе и отказе одной линии связи связь с вершиной 1 будет утрачена.

Сложнее ситуация, допускающая отказ двух связей. Наш пример подобран так, что и в этом случае ответ будет однозначным – это правая структура рисунка. Шанс утратить связь с одной из вершин при отказе двух линий в этой структуре наименьший из трех остающихся потенциально возможных для выбора структур. Дело в том, что в правой структуре имеется единственная вершина степени d = 2 и именно эта единственная вершина связана с остальными менее надежно. Слева от правой структуры расположена структура, имеющая две вершины со степенью два, а левее этой структуры расположена структура, имеющая три вершины степени два. Как видим шансы структуры остаться связной при отказе двух линий у этих трех структур различны. Поэтому выбор однозначен лучшая – это правая структура.

Литература

1. Авондо-Бодино Дж. Применение в экономике теории графов – М.: Прогресс,1966. –160с. 2. Харари Ф., Палмер Перечислительные задачи комбинаторного анализа. – М.: Мир, 1979. – 364 с.
3. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.