Составители:
88
Если в матрице R
q
нет пустых столбцов, то первоначальный но-
мер (индекс) может быть присвоен любому столбцу матрицы R
q
.
Столбец, которому присвоен индекс, будем называть отмеченным.
5-й шаг. Просматривают отмеченный столбец матрицы R
q
сверху
вниз. Встретив элемент столбца, не равный нулю, вычеркивают все
не равные нулю элементы строки, на пересечении с которой находит-
ся встреченный элемент, в том числе и сам элемент. Просматрива-
ют столбцы, в которых находились вычеркнутые элементы. Если эти
столбцы оказались пустыми (не осталось ни одного не равного нулю
элемента), то этому столбцу и соответствующей ему строке присва-
ивают тот же индекс (номер), что и отмеченному столбцу. Этот ин-
декс проставляется на соответствующих местах в столбце N
нач
таб-
лицы дуг реберного графа. Данный шаг выполняют до тех пор, пока
отмеченный столбец не станет пустым.
6-й шаг. Присваивают очередной номер (индекс) следующему
неотмеченному столбцу и соответствующей строке, заносят этот но-
мер (индекс) в соответствующее место столбца N
нач
таблицы дуг
реберного графа и для рассматриваемого столбца матрицы R
q
вы-
полняют операции пятого шага.
Пятый и шестой шаги повторяют до тех пор, пока в матрице не
останется ни одного не вычеркнутого элемента.
7-й шаг. Заполняют столбец N
кон
таблицы дуг реберного графа.
Это можно выполнить следующим образом. Просматривают после-
довательно все столбцы матрицы R
q
. Для тех строк, для которых в
просматриваемом столбце имеются ненулевые элементы, простав-
ляют в столбце N
кон
таблицы новый, присвоенный в процессе выпол-
нения четвертого, пятого, шестого шагов, номер (индекс) просмат-
риваемого столбца.
После выполнения седьмого шага таблица дуг реберного графа
оказывается заполненной полностью. При этом в столбце N
нач
ука-
заны номера (индексы) начальных вершин, из которых исходят дуги
реберного графа, в столбце N
кон
– номера (индексы) конечных вер-
шин, в которые заходят дуги реберного графа, а в столбце N
в
– номе-
ра вершин исходного графа, эквивалентные соответствующим дугам
реберного графа. Если для какого-либо номера из столбца N
в
табли-
цы в исходном графе нет соответствующей вершины, то дуги ребер-
ного графа, сопоставляемые данному номеру, считаются фиктивными.
Страницы
- « первая
- ‹ предыдущая
- …
- 86
- 87
- 88
- 89
- 90
- …
- следующая ›
- последняя »
