Составители:
92
сваиваем им 7, а в дополнительном столбце в строках 3, 4, 5 проставля-
ем единицы.
Справа от матрицы R
q
строим таблицу начальных и конечных вер-
шин дуг реберного графа, заполняя сразу столбец N
в
каждой строки.
3-й шаг. Пустому столбцу 6 матрицы R
q
присваиваем индекс "а".
Этот же индекс присваиваем строке 6 и проставляем в столбце N
нач
в
строке, соответствующей строке 6 матрицы R
q
. Следующему столбцу
1 присваиваем индекс "b", который проставляется против строки 1 и в
соответствующую строку столбца N
нач
таблицы.
4-й шаг. Просматривая столбец 1, находим единицу в строке 6 и
вычеркиваем ее, а также единицу на пересечении этой строки и столб-
ца 2. Столбец 2 оказывается после этого пустым, поэтому присваиваем
ему, а также строке 2 индекс "b". Этот же индекс заносим в соответ-
ствующую строку столбца N
нач
таблицы дуг.
5-й шаг. Присваиваем индекс "с" столбцу 3 и строке с тем же номе-
ром. Заносим индекс "с" в соответствующую строку столбца N
нач
таб-
лицы. Просматриваем столбец с индексом "с" матрицы R
q
. Первый
единичный элемент находится на пересечении этого столбца со стро-
кой 1. Вычеркиваем все единицы в строке 1. Второй единичный эле-
мент находится на пересечении столбца со строкой 2. Вычеркиваем
все единицы этой строки. Столбцы 4 и 5 после этого оказываются пус-
тыми. Поэтому присваиваем им, а также строкам 4 и 5 индекс "с", по-
мещая его на соответствующие места в столбце N
нач
таблицы.
6-й шаг. Присваиваем индекс "d" последнему составляющему стол-
бцу 7, строке 7 и заносим его в столбец N
нач
таблицы.
На этом нумерация столбцов, а следовательно, и вершин реберного
графа заканчивается.
7-й шаг. Заполняем столбец N
кон
таблицы следующим образом. В
столбцах "b" матрицы R
q
единицы находятся только в строке "а", поэто-
му в столбец N
кон
заносим индекс "b" в строку, которая содержит ин-
декс "а" в столбце N
нач
. Столбцы "с" матрицы содержат единицы толь-
ко в строках "b", поэтому заносим индекс "с" в соответствующие строки
столбца N
кон
таблицы. Столбец "d" содержит единицы в строках "с",
поэтому индекс "d" проставляется в соответствующих строках столбца
N
кон
таблицы, а в пустой строке столбца N
кон
ставим прочерк.
На этом заполнение таблицы заканчивается. В результате имеем
таблицу дуг реберного графа, заданных своими начальными и конечны-
ми вершинами. Первоначальные номера строк матрицы R
q
, занесенные
Страницы
- « первая
- ‹ предыдущая
- …
- 90
- 91
- 92
- 93
- 94
- …
- следующая ›
- последняя »
