Лабораторные. Черепанов
1 работа
Построить минимальный остов связного неориентированного взвешенного графа.
Метод решения
алгоритм Борувки-Краскла.
Пример
25
1-----2
4 | |0
+-----3-----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афе
Метод решения
сведение к задаче о максимальном потоке и использование поиска в глубину для поиска f-дополняющих цепей (М-че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ица.
Файл выходных данных
Y и во второй строке полное паросочетание, представленное массивом XПАРА, или N и во второй строке вершина xi, из которой поиск не удачен.