ПОИСК БЛИЖАЙШЕГО ДВУДОЛЬНО-ПОРОГОВОГО ГРАФА К ЗАДАННОМУ ДВУДОЛЬНОМУ ГРАФУ
Аннотация
Объектом исследования является двудольного-пороговый граф.
Целью работы является реализация жадного алгоритма приведения двудольного графа к двудольно-пороговому графу и исследование жадного алгоритма на корректность и оптимальность с помощью метода полного перебора.
Реализация поставленной цели потребовала решения следующих задач:
- Изучить двудольные и двудольно-пороговые графы, их свойства
- Изучить вращение ребер в двудольном графе
- Реализовать жадный алгоритм приведения двудольного графа к двудольно-пороговому графу
- Реализовать проверку жадного алгоритма на корректность и оптимальность с помощью метода полного перебора
В данной работе использованы такие методы, как теоретический анализ, исследование, сравнение.
В результате работы были программно реализованы жадный алгоритм и алгоритм полного перебора и произведено их сравнение
Целью работы является реализация жадного алгоритма приведения двудольного графа к двудольно-пороговому графу и исследование жадного алгоритма на корректность и оптимальность с помощью метода полного перебора.
Реализация поставленной цели потребовала решения следующих задач:
- Изучить двудольные и двудольно-пороговые графы, их свойства
- Изучить вращение ребер в двудольном графе
- Реализовать жадный алгоритм приведения двудольного графа к двудольно-пороговому графу
- Реализовать проверку жадного алгоритма на корректность и оптимальность с помощью метода полного перебора
В данной работе использованы такие методы, как теоретический анализ, исследование, сравнение.
В результате работы были программно реализованы жадный алгоритм и алгоритм полного перебора и произведено их сравнение