Файл: Шнепс, М. А. Численные методы теории телетрафика.pdf

графа Gp, не принадлежащие контуру у, с сохранением обозначений

зультате перехода от |G3>к Gp+1число вершин уменьшается, но мно­ жество всех индексов не изменяется, так как все индексы отбрасы­ ваемых вершин xj- появляются у новой вершины хj. В описывае­

мом ниже алгоритме построения последовательности Go, G1... каж­ дый граф получается из предыдущего путем стягивания некоторого контура. Поэтому каждый из графов последовательности имеет то же множество индексов N, как и исходный граф Go=G.

Для установления свойств достижимости в графах Gp будет по­ лезным перенести это понятие на индексы обозначений вершин. Именно, пусть i^N и k£N. Будем говорить, что в Gp /е достижи­ ма из £, и писать, что

шин xj, хк достижима из другой, то будем пользоваться обозначе­ нием

Докажем две леммы.

Лемма 1. Граф G' сильно связан тогда и только тогда, когда все его вершины лежат на одном контуре.

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

Обратно, пусть \G' — сильно связный граф, например, сильно связная компонента некоторого графа G. Тогда существует контур, проходящий через все вершины G'. Действительно, пусть а и b — две вершины G'. В силу сильной связности в G' существуют пути а(а,..., Ь) и а). Следовательно, и объединение этих путей — контур afi(a,..., b,..., а), проходящий через а и Ь.

Если в G' имеется вершина с, через которую не проходит контур сф, то в G' существуют пути у (а,..., с) н 6 (с,..., а). Следовательно, и контур афуб проходит через а, Ь, с и т. д. Путем таких последова­ тельных дополнений после конечного числа шагов получим контур, проходящий через все вершины графа G'.

С л е д с т в и е . Каждая отдельная вершина графа G" является сильно связной компонентой тогда и только тогда, когда G" не содержит контуров.

Лемма 2. Пусть из графа G= G0 путем повторного применения операции стятивания контуров получена последовательность гра­

60

фов: Gi,..., Gp>... и пусть = { 1 я} — множество индексов назва­ ний вершин этих графов. В каждом из этих графов множество со­ отношений (5) и (6) для элементов множества одно и то же.

Действительно, рассмотрим переход от G к Gt. Пусть в |G i< z k . Это значит, что в G существует путь из х, в х/4. Если этот путь не проходит через вершины стягиваемого контура у, то он остается без 'изменений и i < k также и в Gi. Если же указанный путь прохо­ дит через хотя бы одну вершину Xj контура у, то как в IG, так и в G1 мы имеем i < . j < . k и i < k также и в Gi.

Аналогичным путем устанавливается сохранение всех соотноше­ ний (5) при сравнении Gt и G, а также lGp и Gp+1 в обоих направ­ лениях. Так как каждое соотношение (6) эквивалентно двум соот­ ношениям (5), то сохраняются и все соотношения (6).

Если исследуемый граф G сильно связный, тогда iG будет со­ стоять только из одной вершины. В общем случае, когда граф G не

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

G будет иметь, по крайней мере, одну входящую или исходящую

дугу. Целесообразно разделить все вершины G на три типа: 1) исходные, имеющие только исходящие дуги; 2) промежуточные, имеющие дуги обоих видов;

3) стационарные, имеющие только входящие дуги.

Такие же названия мы дадим и соответствующим компонентам графа G. В качестве примера приводим на рис. 4.2 граф G для графа, представленного на рис. 4.1. Вершина 6 на рис. 4.2 — исход­

2. В рассматриваемом графе IGp берем непомеченную вершину г'ь любую из непомеченных вершин A'i в качестве и'2, г3 6А 2 и т. д. После конечного числа шагов переходим к этапу За или 36.

За. Для рассматриваемой вершины х,- все вершины Ас,- помече­

61

ны. У вершины Xi ставим пометку «п» с очередным номером. По­

is,—, in) — контур с непомеченными вершинами.

Пусть / = {4,..., is...\ — объединение множеств индексов вершин этого контура. Стягиваем контур в новую вершину x j , получаем граф Gp+u Для него строим матрицу Rp+i: в Rp отбрасываем все строки и столбцы, соответствующие вершинам, стянутым в X j, а для последней вершины вводим новый столбец и строку с элементами

уменьшается, то после конечного числа шагов все вершины будут помечены. Полученный граф Gs с помеченными вершинами и есть

искомый граф G. Действительно, Gs не содержит контуров; контур в любом графе Gp состоит только из непомеченных вершин, так как ни одна из вершин контура не может быть помечена первой. В силу следствия леммы 1 каждая вершина Gs — сильно связная компонента; соотношение (6) имеет место только для индексов, со­ ответствующих одной и той же вершине Gs. Так как в силу леммы 2 система соотношений (6) та же для Gs и G, то каждой вершине Gs соответствует по одной компоненте графа G. Нетрудно видеть, что

в графе G= GS вершины с пометками «и», «п» и «с» являются, соот­ ветственно, исходными, промежуточными и стационарными.

Если граф G легко обозрим, то вопрос о достижимости одних индексов из других решается непосредственно. В противном случае можно использовать матрицу T = R S + E, где Е — единичная матри­ ца. Логическим умножением и сложением возводим Т в степень до первого такого показателя а, для которого 7’“+1= Г а . В получен­ ной матрице элемент tjL—\ тогда и только тогда, когда любой из индексов 1(ЦЬ достижим из любого индекса £6/.

Граф G= GS с помеченными вершинами позволяет найти нумера­ цию вершин G, при которой матрица А приобретает сравнительно простой канонический вид. Начинаем с подходящей нумерации

вершин G. Вершины с пометками «и» в числе k получают номера: 1, 2.... k в произвольном порядке. Можно, например, сохранить по­

рядок, полученный при построении G. Вершины с пометками «п» в числе I получают следующие номера: £ + 1,..., k + l, причем очеред­ ной текущий номер присваивается только такой вершине у, для ко­ торой уже получили номера все предшествующие вершины х (т. е. такие, для которых существует дуга (х, у ) ). В силу отсутствия кон­ туров в G такая нумерация всегда возможна. Наконец, вершины с пометками «с» в числе пг получают номера: k + l+ \ r...r k + 1+tn в произвольном порядке.

62

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

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

где В, С, D — квадратные неразложимые блочные матрицы; 0 — нулевые матрицы; б — матрицы, различные в общем случае, кото­ рые могут быть как нулевыми, так и содержать ненулевые элемен­ ты. Однако в каждом блочном столбце и блочной строке, где фигу­ рируют матрицы типа б, хотя бы одна из них не нулевая. В графе

G каждой ненулевой матрице б соответствует дуга и наоборот.

Из вида матрицы (7) непосредственно следует, что характерис­ тический полином матрицы А можно представить произведением характеристических полиномов для всех матриц В, С и D.

3. Теорема о связи главных миноров матрицы А с множеством корневых лесов

Установим одно свойство главных миноров матрицы:

*¥=/

лениях. Для его формулировки рассмотрим граф G с множеством N —{ 1,..., п} индексов вершин, представляющий матрицу А описан­ ным в п. 2 способом. Введем понятие корневого леса.

Пусть / — некоторое истинное подмножество N, а X j — множе­ ство вершин графа G с индексом из /. Корневым лесом множест­ ва J (или Xj) будем называть любой частичный подграф G' графа G, т. е. некоторое подмножество дуг и их вершин графа G, имеющее следующие свойства:

1)из каждой 'вершины х EXj исходит точно одна дуга Gr\

2)любая дуга графа G' имеет начальной вершиной некоторую вершину из Xj;

3)G' не содержит контуров.

63