Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Veyron
105 / 105 / 4
Регистрация: 02.06.2009
Сообщений: 579
#1

Максимальное паросочетание или что-то еще - C++

25.04.2013, 23:40. Просмотров 843. Ответов 0
Метки нет (Все метки)

Задача в следующем:
Есть двудольный граф, и в нем у каждой вершины степень не меньше 1. Нужно поудалять ребра из этого графа так, чтобы осталось минимальное множество ребер, и любая вершина первой доли была бы связана с какой-то вершиной второй доли (и обратно). Предлагается решение - искать максимальное паросочетание этого графа и выводить его мощность. Я не могу понять, каким макаром здесь прикручиваются паросочетания, ведь у нас может быть так, что из одной вершины будет выходить несколько ребер.
Плюс к этому есть еще вариант решения, видимо неверный - просто удалять, пока возможно, ребра, которые примыкают к вершинам, каждая из которых имеет степень больше чем 1.
Какой может быть контрпример к этому решению? И как здесь можно прикрутить задачу о поиске максимального паросочетания в двудольном графе?
Заранее спасибо за помощь и советы! :-)

PS: Это задача Timus 1109.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 23:40     Максимальное паросочетание или что-то еще
Посмотрите здесь:

Conversion from 'size_t' to 'int' и еще кое-что C++
C++ Максимальное или минимальное значение
Задумываюсь чтоб начать сразу с Qt(пока еще ни во что не углублялся). C++
C++ Предел int или что то еще ?
посоветуйте какую-то книгу или даже видео курс,ну или еще что-то, ну чтобы с самого начала ,с нуля объяснялось. C++
Visual C++ CFileDialog и кое-что еще
Что нужно еще сделать для комфортной работы пользователей с моей программой? C++
C++ Кроме Round и Floor еще есть что?
C++ If vs. If else - миф или что-то еще?
Что еще можно параллельно изучать вместе с С++? C++
Нужен ли хостинг или что то еще, для работы программ клиент-сервер(TCP/IP) на разных компьютерах? C++
Программа на Ваше обозревание, что можно еще добавить? Тру критика C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 20:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru