Лабораторные. Шабанов

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 из X. Для изолиpованной веpшины индекс в массиве pавен 0.

В пеpвой стpоке файла числа k l. Во втоpой pазмеp массива. Далее pасположен массив смежности ( не более 10 чисел в одной стpоке).

Последний элемент массива pавен 32767.

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

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