3. Случайные графы

В прошедшие два десятилетия для решения ряда вероятностных задач комбинаторики использовалась так называемая обобщённая схема размещения частиц.

Рассмотрим последовательность n независимых испытаний с N равновероятными исходами 1, 2, , N. Пусть - число появлений исхода i в этой последовательности, i = 1, 2, , N. Случайные величины , , имеют полиномиальное распределение: если , , - неотрицательные числа, такие, что +  + = n, то

. (1)

Полиномиальное распределение появляется в равновероятной схеме размещения частиц. Если n частиц последовательно независимо одна от другой размещаются с равными вероятностями в N ячеек, занумерованных числами 1, 2, , N, то заполнения ячеек , , имеют полиномиальное распределение (1).

В схеме размещения частиц, приводящей к полиномиальному распределению, заполнения ячеек получаются путём независимых последовательных размещений частиц. Если отказаться от требования, чтобы заполнения получались путём некоторого последовательного размещения частиц, управляемого каким-либо простым вероятностным правилом, то любой набор неотрицательных целочисленных случайных величин , , , таких, что +  + = n, можно рассматривать как размещение n частиц в N ячейках и интерпретировать как число частиц в ячейке с номером i, i = 1, 2, , N.

Некоторые задачи комбинаторики можно изучать, используя обобщённые схемы размещения, в которых совместное распределение заполнений ячеек , , может быть представлено в виде

, (2)

где , , - независимые одинаково распределённые целочисленные случайные величины.

Итак, обобщённая схема размещения частиц по ячейкам задаётся параметрами n и N и распределением независимых случайных величин, ,, , которое в силу соотношения (2) определяет совместное распределение заполнений ячеек , , . За равновероятной схемой размещения частиц, приводящей к полиномиальному распределению (1), утвердилось название классическая схема размещения.

Пример 1. Рассмотрим однозначные отображения конечного множества в себя. Однозначное отображение s множества в себя можно представить в виде таблицы

,

где есть образ k, k = 1, 2, , n, при отображении s. С отображением s естественным образом связан ориентированный граф с множеством вершин и дугами , где дуга направлена из в , k = 1, 2, , n, Число дуг, входящих в вершину в графе , равное числу прообразов элемента в отображении s, называется кратностью вершины .

Пусть - множество всех однозначных отображений множества в себя и - множество всех графов этих отображений. Число элементов множества очевидно равно . Зададим на множестве равномерное распределение, тогда мы получим вероятностное пространство с множеством элементарных событий , вероятность любого множества из равна числу его элементов, делённому на . Случайное отображение равно любому из различных отображений с вероятностью . Если

,

где - случайный образ элемента i, i = 1, 2, , n, то для любого s

.

Таким образом, случайные величины ,, независимы и принимают значения 1, 2, , n с равными вероятностями.

Обозначим кратность вершины r в случайном отображении , r = 1, 2, , n. Величина равна числу случайных величин ,, , принимающих значение r. Таким образом, для неотрицательных чисел ,, , таких, что +  + = = n, вероятность по всем ,, , среди которых ровно величин равны r, r = 1, 2, , n. Число слагаемых в этой сумме, очевидно, равно , поэтому

.

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

,

где ,, - независимые одинаково распределённые случайные величины, распределённые по закону Пуассона с произвольным параметром.

Число вершин кратности r в случайном отображении соответствует числу ячеек, содержащих ровно r частиц в классической схеме размещения n частиц в n ячейках.

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

Пусть - число графов в множестве , а - число связных графов в . Обозначим подмножество графов из ровно с N связными компонентами. Заметим, что компоненты графа, принадлежащего , не упорядочены, поэтому будем рассматривать только такие характеристики графа, которые не зависят от порядка компонент. Для того, чтобы обойти эту трудность в применении обобщённой схемы размещения, вместо исходного множества будем рассматривать множество комбинаторных объектов, которые получаются, если упорядочить всеми возможными способами компоненты каждого исходного графа из . Элементы этого множества представляют собой упорядоченный набор N компонент, а общее число вершин во всех компонентах равно n. Вершины графа из занумерованы и, следовательно, все компоненты графа различны, поэтому число элементов в равно , где - число элементов в множестве , состоящем из неупорядоченного набора N компонент.

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

Положим а₀ = 1, b₀ = 0 и введём производящие функции

, .

Лемма 1. Если свойство R разложимо, то

, (3)

где суммирование проводится по неотрицательным целым числам ,, , таким, что +  + = n.

Лемма 2. Если свойство R разложимо, то

.

Теорема 1. Если ряд

(4)

имеет ненулевой радиус сходимости, то случайные величины ,, могут рассматриваться как заполнения ячеек в обобщённой схеме размещения, в которой распределение независимых одинаково распределённых случайных величин ,, задаётся формулами

, (5)

где положительное значение х из области сходимости ряда (4) может быть выбрано произвольно.

Пример 2. Дерево – это связный граф, не имеющий циклов. В качестве возьмём множество всех лесов, состоящих из N деревьев, сообщим числом занумерованных вершин, равным n. Деревья леса не упорядочены. Свойство R, выделяющее этот класс графов, состоит в том, что граф неориентирован и не содержит циклов. Свойство R разложимо. Число b_n связных графов с n вершинами, обладающих свойством R, равно числу некорневых деревьев с n вершинами и , так что производящая функция В(х) имеет вид

.

Таким образом, для изучения случайных лесов из множества можно использовать обобщённую схему размещения, в которой определяющие её случайные величины ,, имеют распределение

.

Вопросы для повторения.

1. Источник. Сток.

2. Пропускная способность дуги.

3. Поток. Условие сохранения потока.

4. Остаточная пропускная способность дуги. Насыщенная дуга.

5. Разрез. Ориентированный разрез. Пропускная способность (величина) разреза.

6. Теорема Форда-Фалкерсона.

7. Алгоритм Форда-Фалкерсона построения максимального потока и минимального разреза.

Задачи для самостоятельного решения.

1. По данной матрице пропускных способностей дуг графа G найти максимальный поток от вершины s = x₁ до вершины t = x₇ и указать минимальный разрез, отделяющий s от t.

ПРИЛОЖЕНИЕ

ГРАФЫ В ПРИЛОЖЕНИИ К ОПИСАНИЮ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

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

(П.1)

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

, (П.2)

которое означает, что ребро соединяет вершины и . Вершины и называются смежными, а ребро - инцидентным этим вершинам в графе.

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

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

& & ; (П.3)

(П.4)

& & (П.5)

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

,

что удобно для описания макромоделей ИО.

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

Элементами графа могут быть цепи и циклы. Цепью называется последовательность

элементов графа, для которой справедливо высказывание

.

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

(П.6)

для которой истинно высказывание

.

В качестве количественных характеристик пути для описания ИО уместно использовать такие понятия, как длина пути и вес пути . Число ребер, образующих путь, называется длиной пути. Для пути (П.6) длина . Вес пути - произведение весов образующих его ребер, для пути (П.6) вес

.

Путь может быть конечным и бесконечным; он называется простым, если в нем ни одно ребро не встречается дважды. Путь , в котором ни одна из вершин не встречается дважды, называется элементарным. При описании ИО следует использовать простые элементарные пути. Поэтому в дальнейшем для описания ИО под термином «путь» будем подразумевать простоя элементарный путь.

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

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

,

,

где - число дуг, исходящих из вершины ; - число дуг, входящих в вершину .

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

.

Весом прадерева называется произведение весов всех входящих в него дуг.

Частным случаем прадерева является звезда - совокупность простых путей с общей конечной или начальной вершиной; эту вершину назовем центром звезды. Если центром звезды является начальная вершина путей , т.е.

,

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

,

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

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

Далее рассмотрим части графов. Пусть имеем два графа

и ,

где и ; - предикат, индуцированный инцидентором на множествах и . Если

,

то является частью . К числу частей относится и сам граф ; прочие его части обычно называют собственными. Для практики наибольшее значение имеют следующие два типа частей графа. Подграфом графа называется часть графа , порожденная подмножеством вершин , если подмножество ребер удовлетворяет следующему условию:

.

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

Если является суграфом графа , то сам граф называется сверхграфом; если - подграф, то - надграф, и если - часть графа, то - объемлющий граф.

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

,

где - число петель, инцидентных вершине .

Униграфом называется граф , не содержащий кратных ребер, т. е. такой, что каждая пара его вершин соединена не более чем одним ребром:

,

где - число ребер, соединяющих вершины и .

Граф, не являющийся униграфом, называется мультиграфом. Для моделирования ИО удобнее использовать униграфы, а не мультиграфы.

Когда никакая пара вершин не соединена более чем ребрами , т.е.

,

граф называется - графом. Отсюда следует, что - граф – это пустой граф, а - граф – это униграф.

Объединением графов называется граф , для которого

и предикат индуцирован предикатами .

Пересечением графов следует считать граф , в котором

и предикат индуцирован предикатами .

Известны также и другие операции над графами.

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

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

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

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

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

;

,

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

. . .

. . .

. . .

…

…

…

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

Достоинством матрицы следует также считать ее соответствие системе однородных уравнений, применяемой для описания ИО,

(П.7)

или в матричной форме

,

где - вектор переменных, соответствующих вершинам.

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

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

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

В этом случае системы уравнений могут быть записаны в виде следующего матричного соотношения:

,

где , - квадратная матрица коэффициентов; , и , - -мерные векторы-столбцы независимых переменных и .

Коэффициенты (параметры информационных потоков) могут зависеть от и . Поэтому такую систему параметров допустимо применять для линейных моделей ИО.

Часто встречается на практике при линейном моделировании, в т.ч. ИО, уравнение типа

, (П.8)

где - входная переменная; - выходная переменная.

Для аналоговых интегрирующих и дифференцирующих операций также справедливо (П.8) при и соответственно, где - оператор Лапласа; - постоянная времени звеньев.

Примером также может служить сумматор, описываемый уравнением

(П.9)

где - входные, а - выходные напряжения сигнала; - коэффициенты суммирования.

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

(П.10)

где - значение входного сигнала в момент времени ; - значение выходного сигнала в момент времени ; - выходной сигнал в момент времени ; - период квантования сигнала по времени.

Выражение (П.10) называется рекурсивным. Нерекурсивным (П.10) станет, если принять при .

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

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

Пусть система состоит из уравнений с искомыми переменными и задающими переменными , т.е.

Граф Мэзона строится на основании причинно-следственной формы исходных уравнений:

(П.11)

Вершины графа, соответствующие переменным , называют истоками. Каждая дуга графа имеет нормированный вес 1 или , поэтому такая форма представления сигнального графа получила название нормализованной. Существует еще одна форма представления графа Мэзона, которой соответствуют следующие уравнения:

(П.12)

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

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

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

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

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

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

, (П.13)

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

Для различных типов графов вес пути равен

,

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

При вычислении определителей может быть использована следующая обобщенная формула:

, (П.14)

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

, (П.15)

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

Выражения (П.14) и (П.15) справедливы также и для определителя дополняющего подграф . Как видно из формул (П.13) - (П.15), специфика используемого для расчета графа играет роль лишь при формировании (П.14) и расчете весов (П.15) элементар­ных графов. Рассмотрим эту процедуру для различных типов графов.

Для графа Мэзона элементарный граф состоит из множества некасающихся контуров; фактор равен количеству некасающихся контуров, входящих в состав данного элементарного графа. Вес элементарного графа в этом случае

, (П.16)

где - вес -го контура, входящего в состав данного элементарного графа.

Из (П.15) следует

, (П.17)

где - вес -й дуги, входящей в состав -го контура; - длина -го контура. Следует заметить, что исходный граф может содержать несколько элементарных графов с одним и тем же фактором. Исключение составляет единственный элементарный граф с фактором , который следует считать множеством контуров, вырожденных в вершину, имеющую вес, равный 1. Поэтому с учетом (П.16), (П.17) формула для расчета определителя сигнального графа (Мэзона) часто записывается в следующем виде:

, (П.18)

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

Формула (П.18) нашла широкое применение при решении нормализованных графов и в дальнейшем будет весьма полезна при анализе ИО.

После описания основных подходов к моделированию ИО можно перейти непосредственно к рассмотрению моделей конкретных процессов.