Лабораторные. Мутыгуллин
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сона.
Файл входных данных
Двудольный гpаф G=(X,Y,E), k=|X|, l=|Y|, заданный Х-массивом смежностей.
X-массив смежностей: также как и массив смежностей, только перечисляются смежные с вершинами x из X. Для изолиpованной веpшины индекс в массиве pавен 0.
В пеpвой стpоке файла числа k l. Во втоpой pазмеp массива. Далее pасположен массив смежности ( не более 10 чисел в одной стpоке).
Последний элемент массива pавен 32767.
Файл выходных данных
Массив XПАРА длины k (XПАРА[xi]=yj, если {xi,yj} входит в паросочетание, иначе XПАРА[xi]=0).