Паросочетание. 
Методика построения графов в программном комплексе Maple

Разберем на примере алгоритм решения задачи о паросочетаниях в двудольном графе.

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

Рис. 16.

Рис. 17.

Остов наименьшего веса

Приведем независимую программу решения задачи. Сначала определяется число остовов, затем для отыскания остова используется оператор из пакета networks. Число остовов. В специализированном пакете networks имеется функция counttrees (G) для определения числа остовов графа. Другой способ — вычисление алгебраического дополнения любого элемента матрицы Кирхгофа, полученной по формуле (4.1) со с. 77. Для выполнения операций с матрицами (перемножения, умножения на число, вычитания, транспонирования) необходимо подключить. пакет LinearAlgebra. Чтобы не дублировать вывод результатов, уже приведенных на с. 77, операторы вычисления матриц инцидентности (incidence) и смежности (adjacency) завершаются двоеточием. Перемножить матрицы в Maple можно с помощью точки 1 (In.Transpose (In)-2*A), сразу получив матрицу, либо с помощью комбинации знаков &* и функции evalm: > B:=evalm (In&*Transpose (In)-2*A); В последнем случае результат не имеет тип Matrix, в чем можно убедиться, применяя оператор type (B, Matrix) проверки типа. Поэтому для дальнейших действий необходима конвертация: B:=convert (B, Matrix). Кроме того, для перемножения матриц A и B в пакете LinearAlgebra есть оператор MatrixMatrixMultiply (A, B). Если матрица Кирхгофа строится по формуле (4.2), то сначала надо получить какую-либо ориентацию графа. Это делается заменой фигурных скобок { } множества на квадратные скобки [ ] упорядоченной пары в описании ребер. Оператор op снимает фигурные скобки, после чего результат заключается в квадратные скобки. Все это выполняется в цикле по i: E1:=seq ([op (ends (edges (G)[i], G))], i=1.n). Имея список дуг E1 и вершин, можно создать новый (уже ориентированный) граф и для него получить матрицу инцидентности. Параметр r введен для описания формата вывода рисунка графа в операторе draw. Отметим, что в 10-й версии Maple оператор Minor по умолчанию выдает значение определителя, поэтому дополнительного использования Determinant не требуется.

Рис. 18.