Дан неориентированный граф, для каждого ребра известен его вес (положительное целое число). Также дано положительное целое число K. Требуется ответить на вопрос: существует ли в графе такой цикл, что сумма весов ребер, входящих в этот цикл, не меньше K.

Как я понимаю, для доказательства необходимо свести к этой задаче Гамильтонов цикл, а именно по входным данным для гамильтонова цикла построить входные данные для поставленной задачи. Для этого я рассмотрела K = n, где n - это количество вершин в графе. Веса всех ребер взяты равные 1. А множество ребер и вершин в этих двух задачах одинаковые. Тогда в одну сторону доказательство очевидное (если есть гамильтонов, то есть и самый длинный). А в обратную совсем не понятно что делать, так как в условии задачи не сказано, что цикл обязательно простой.

Скорее всего я ошибаюсь со сводимостью, и нужно брать не одинаковые множества вершин и ребер в обоих этих задачах. Но пока что не получается придумать адекватного построения.

Может есть какие-нибудь идеи, как еще можно построить входные данные для моей задачи из входных данных задачи гамильтонова цикла?

задан 26 Ноя '17 16:57

@ivm23: по-видимому, это и подразумевалось. Ведь если разрешить любые циклы, то есть такие пути, где начало и конец совпадают, то можно сколь угодно долго ходить по одному и тому же месту, и сумма весов при этом будет сколь угодно велика.

(26 Ноя '17 18:19) falcao

@falcao я так понимаю, что цикл - это замкнутый путь, не содержащий одинаковых ребер. А простой цикл - цикл, все вершины которого встречаются ровно один раз (за исключением стартовой). Гамильтонов - простой, содержащий все вершины графа.

(26 Ноя '17 19:05) ivm23

@ivm23: слово "цикл" слишком многозначное. Мы ведь говорим "эйлеров цикл", "гамильтонов цикл", имея в виду совсем разные вещи. Поэтому имеет смысл уточнить, что именно имелось в виду. Ваша трактовка тоже возможна, и тогда получается задача с не вполне очевидным ответом. Там свойство уже ближе к эйлеровости, поэтому задача может оказаться и не NP-полной.

(27 Ноя '17 3:24) falcao

@falcao посмотрев английском оригинале, выяснилось, что там действительно простой цикл.

(27 Ноя '17 20:22) ivm23

@ivm23: я так в принципе и предполагал. То есть это упражнение на совсем простое применение задачи к частному случаю. Но "эйлеров" (условно) вариант, описанный выше, звучит весьма интересно. Скорее всего, это дело уже изучено, но ответ было бы интересно узнать.

(27 Ноя '17 20:36) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×135
×2

задан
26 Ноя '17 16:57

показан
199 раз

обновлен
27 Ноя '17 20:36

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru