Компоненты сильной связности графа

Рассмотрим орграф, содержащий, очевидно, три компоненты сильной связности: (1, 2), (3, 4), (5, 6). Дуги задаются списком, например [1, 2], а не множеством, как в неографе: {1, 2}. К сожалению, в Maple рисунки орграфа и неографа не отличаются Рис. 1 (дуги стрелками не выделяются). Поэтому рисунок, полученный оператором draw (G), непохож на рис. 1 (дуги туда и обратно сливаются в одну). В программе определяется матрица достижимости M, несимметричная для орграфа. Строки матрицы соответствуют вершинам, от которых идет путь, а столбцы — вершинам, в которые путь приходит. Рассматривая матрицу M, замечаем, что из вершин 1 и 2 достижимы все вершины графа (строки 1 и 2 не содержат нулей), сами же вершины 1 и 2 достижимы из множества {1, 2}. Пересечением множеств {1, 2, 3, 4, 5, 6} и {1, 2} является множество {1, 2}. Это множество и является компонентой сильной связности графа. Операция пересечения множеств эквивалентна замене элементов матрицы достижимости произведением элементов и их симметричных образов. Это и выполнено в программе в двойном цикле по i и j. Начальные значения переменных цикла from и шаг by, по умолчанию равные 1, по обыкновению, не пишутся. В полученной матрице в последнюю строку дописываются номера вершин. Следует отметить характерную для Maple конструкцию определения и одновременного вызова функции, создающей последовательность номеров вершин: (j) -> j. Ориентация вектора номеров создается опцией row. Далее, просматривая первую строку получившейся матрицы, заносим в первый список связности номера столбцов с ненулевыми элементами и вычеркиваем соответствующие строки и столбцы. Эта операция повторяется в цикле по j до исчерпания матрицы. Используются операторы DeleteColumn и DeleteRow из пакета LinearAlgebra. Эти операторы не могут вычеркивать последние строку и столбец из матрицы, поэтому в программу введен условный оператор if nV1n.

Рис 4.

Рис. 5.