Лабораторные. Безушко

1 работа

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

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

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

Пример

      (25)
    1------2
    |      |(0)
    +------3--------4
      (4)      (7)

22
 6 10 14 20 22  2 25  3  4  1
25  3  0  1  4  2  0  4  7  3
 7 32767

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

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

N - число элементов в массиве. Далее построчно расположен массив смежности (не более 10 чисел в одной строке). Последний элемент массива равен 32767.

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

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

2 работа

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

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

Сведение к задаче о максимальном потоке и использование алгоpитма Фоpда-Фалкеpсона.

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

Двудольный граф G=(X,Y,E), k=|X|, l=|Y|,заданный матрицей смежностей размера |X|x|Y|, т.е. kxl, где a[i,j]=1, если {xi,yj} из E (и =0 в противном случае).

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

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

Массив XПАРА длины k (XПАРА[xi]=yj, если {xi,yj} входит в паросочетание, иначе XПАРА[xi]=0).