Решения практических заданий по курсу "Комбинаторные алгоритмы".
На шахматной доске стоят белый конь и черная пешка. Напечатать маршрут коня позволяющий уничтожить пешку.
Примечание: пешка — неподвижная, конь не должен попадать под удар пешки.
Метод решения: Поиск в глубину.
Определить, является ли данный граф ацикличным.
Метод решения: Поиск в ширину.
Найти v-w путь в сети с неотрицательными весами, решающий задачу о пути наибольшего веса, где вес пути равен сумме весов дуг.
Метод решения: алгоритм построения пути в бесконтурной сети.
Построить минимальный остов связного неориентированного взвешенного графа.
Метод решения: алгоритм Ярника-Прима-Дейкстры.
Найти, если оно есть, полное паpосочетание в двудольном гpафе
Метод решения: сведение к задаче о максимальном потоке и использование поиска в глубину для поиска f-дополняющих цепей (М-чеpедующихся).