Предложите линейный алгоритм, вычисляющий паросочетание в произвольном неориентированном графе без весов, отличающееся по размеру от наибольшего (по размеру) паросочетания в этом графе не более, чем вдвое. Напомним, что паросочетанием называется подмножество ребер графа, в котором ни у каких двух ребер нет одинаковых вершин. Докажите корректность алгоритма. Формат входного файла: на первой строке — разделенные пробелом число вершин n и число ребер m, на каждой следующей из m строк — разделенные пробелом номера вершин очередного ребра (от 1 до n).

задан 20 Окт '16 1:31

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

(20 Окт '16 9:35) falcao

Вроде это тривиально. Будем набирать дуги как попало (следя лишь за возможностью выбора очередной дуги). Такой алгоритм действительно приводит к цели. Докажите корректность сами.

(20 Окт '16 15:07) abc
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×696
×122

задан
20 Окт '16 1:31

показан
352 раза

обновлен
20 Окт '16 20:41

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

по почте:

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

по RSS:

Ответы

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

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