Some scripts written for my university course.
Определить, является ли данный связный неориентированный граф двудольным.
Метод решения: Поиск в ширину.
Файл исходных данных: Граф, заданный матрицей смежности. N - количество вершин в графе. Далее построчно расположена матрица смежности размерности N x N.
Файл результатов: Если граф не двудольный, то в файл результатов необходимо записать "N", иначе "Y" и далее вершины входящие в доли графа. Вершины в долях должны быть упорядочены по возрастанию номеров. Первой печатается доля в состав которой входит вершина с минимальным номером. Доли разделяются нулем и печатаются каждая с новой строки
На шахматной доске стоят белый конь и черная пешка. Напечатать маршрут коня, позволяющий уничтожить пешку.
Примечание: пешка - неподвижная, конь не должен попадать под удар пешки.
Метод решения: Поиск в глубину.
Файл исходных данных: Координаты коня и пешки.
Сначала располагаются координаты коня затем пешки. Координаты даются в шахматной нотации, т.е. в виде AB, где A может принимать значения от a до h, B от 1 до 8.
Файл результатов: Маршрут в шахматной нотации. Маршрут должен начинаться координатами коня и заканчиваться координатами пешки. Каждый ход записывается с новой строки.
Найти кратчайший v-w путь в бесконтурной сети.
Метод решения: алгоритм построения пути в бесконтурной сети.
Файл исходных данных: Сеть, заданная матрицей весов. N - количество вершин. Далее построчно расположена матрица весов размерности NxN. В конце файла записаны источник и цель. Число 32767 означает, что данная дуга от- сутствует.
Файл результатов: В случае отсутствия пути в файл результатов необходимо записать "N", при наличии пути - "Y" и далее с новой строки весь путь. Путь начинается источником и заканчивается целью. Узлы отделяются друг от друга пробелами, вес пути вычисляется как сумма весов всех дуг, входящих в него и записыва- ется в третьей строке.
Построить минимальный остов связного неориентированного взвешенного графа.
Метод решения: алгоритм Ярника-Прима-Дейкстры.
Файл исходных данных:
- Граф, заданный массивом смежности.
- N - число элементов в массиве. Далее построчно расположен массив смежности (не более 10 чисел в одной строке). Последний элемент массива равен 32767.
Пример входа:
22
6 10 14 20 22 2 25 3 4 1
25 3 0 1 4 2 0 4 7 3
7 32767
Файл результатов: Остов, заданный списками смежностей. Внутри каждого списка упорядочить вершины по возрастанию номеров. В последней строке записать вес остова.
Найти наибольшее па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).