Здравствуйте, есть некоторый ориентированный граф без цикла и отрицательных весов. Стоят несколько задач.
Пример графа
•Найти все подграфы исходного и полученного из него неориентированного графа, являющиеся полуэйлеровыми;
•Найти все подграфы исходного и полученного из него неориентированного графа, являющиеся эйлеровыми;
•Найти все подграфы исходного и полученного из него неориентированного графа, являющиеся полугамильтоновыми;
•Найти все подграфы исходного и полученного из него неориентированного графа, являющиеся гамильтоновыми
Какой общий подход к решению таких задач? Алгоритмы поиска эйлеровых/гамильтоновых путей/циклов запрограммирован.

задан 16 Окт 14:39

изменен 16 Окт 14:40

@nurik040404: это человек должен искать или компьютер? Я так понимаю, имеет место второй случай, а тогда идёт обычный перебор. Правда, я не знаю, что означают эти понятия для случая ориентированных графов с весами.

(16 Окт 19:17) falcao

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

(17 Окт 1:39) nurik040404

@nurik040404: да, это я понял. Но мне пока не ясно, что означают понятия эйлерова и гамильтонова графа для ориентированного графа с весами.

(17 Окт 1:42) falcao

@falcao, ну, я так понимаю, веса опускаются в данному случае, а ориентированность есть в учебниках. пример - https://i.gyazo.com/1ccc491bf3f2f095a04cd13d8b050fd9.png
С гамильтоновыми путями -- перебором.

(17 Окт 2:24) nurik040404
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×179

задан
16 Окт 14:39

показан
42 раза

обновлен
17 Окт 2:25

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

по почте:

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

по RSS:

Ответы

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

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