Второй метод разбивки графа на слои

Определение 12. Транзитивным замыканием вершины графа именуется подмножество вершин графа, содержащее те вершины и вершину, к каким существует путь из .

Определение 13. Матрицей транзитивного замыкания графа ( ) назовем матрицу такую, что , в случае если из — ой вершины имеется путь в — ую вершину и в случае если из — ой вершины не сущствует путь в — ую вершину.

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

Разглядим произведение матрий смежности S, в которых по диоганали дописаны 1. Пускай S* = S´S, тогда элемент данной матрицы определяется из равенства

Каждое слагаемое в данной сумме равняется единице, в случае если и . Но в этом случае существует путь из — ой вершины в — ую вершину длиной (в смысле определения 9) не более, чем 2. Пускай матрица S2 получается из матрицы S* заменой ненулевых элементов на 1. Тогда элементы матрицы S2 , в случае если существует путь длиной не более чем 2 из в и в другом случае. Умножим сейчас матрицу S2 на себя и снова заменим ненклевые элементы единичными. Полученная матрица укажет нам вершины, соединяемые методом длиной не более чем 4. Продолжим данный процесс , пока матрица по окончании замены и умножения ненулевых элементов на 1 не изменится. В этом случае будет взята матрица транзитивного замыкания.

Выберем в матрице строчка, которые содержат тольку одну единицу, соответствующие вершины отнесем к слою 0. Строки и столбцы соответствующие этим вершинам вычеркнем из матрицы. В новой матрице выделим строки, которые содержат лишь соответствующие вершины и одну единицу отнесем к слою 1 и т.д.

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

Разглядим работу этого метода на примере графа, матрица смежности которого приведена в таблице 2. Потом приведены матрицы

, и . Матрица оказалась равной матрице , следовательно, матрица , транзитивного замыкания графа на рис. 5 , будет совпадать с матрицой . В матрице единственная строка (соответствующая вершине 11) имеет одну единицу. Помещаем вершину 11 в первоначальный слой. Вычеркиваем из матрицы = соответствующие вершине 11 последний столбец и последнюю строку, получа-


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

Использование ЭВМ в обработке сетевого графика требует упорядочить не только вершины но и дуги.

Определение 14. Дуги вида именуются предшествующими дуге .

Для упорядочения дуг используются те же два способа, лишь вместо матрицы смежности употребляется матрица предшествования дуг. Для графа, заданного на рис.1, эта матрица — матрица .

Управление страницами в Компас 3D v11 (29/49)


Также читать:

Понравилась статья? Поделиться с друзьями: