Лабораторные. Исламов

1 работа

Построить минимальный остов связного неориентированного взвешенного графа.

Метод решения

алгоритм Борувки-Краскла.

Пример

       (5)
     1 ---- 2      4
(15) |      |(0)   | (25)
     +----- 3 -----+

     4
     2 5 3 15 0
     1 5 3 0 0
     1 15 2 0 4 25 0
     3 25 0

Файл входных данных

Граф, заданный массивом смежности.

N - количество вершин в графе. Далее последовательно расположены списки смежностей для каждой вершины. Список заканчивается 0.

Файл выходных данных

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

2 работа

Найти, если оно есть, полное паpосочетание в двудольном гpафе

Метод решения

сведение к задаче о максимальном потоке и использование поиска в глубину для поиска f-дополняющих цепей (М-чеpедующихся)

Файл входных данных

Двудольный гpаф G=(X,Y,E), k=|X|, l=|Y|, заданный Х-списками смежностей

X-списки смежностей: k штук списков смежностей по одному для каждой вершины x из X.

В пеpвой стpоке файла числа k l.

Файл выходных данных

Y и во второй строке полное паросочетание, представленное массивом XПАРА, или N и во второй строке вершина xi, из которой поиск не удачен.