Лабораторные. Журба

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афе

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

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

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

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

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

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

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

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