 |
|
|
 
|
|
Максимальное паросочитание 
| Lomir |
|
|||
|
Шустрый  Профиль Группа: Участник Сообщений: 58 Регистрация: 30.1.2007 Где: Lithuania::Kaunas Репутация: нет Всего: 1 |
Нужна информации по алгоритму максимально паросочетание в НЕдвудольном графе. Желательно на русском языке или реализация алгоритма. На английском нашел описание алгоритма, но там немного непонимаю 1 момемта, поэтому ищу информацию на русском.
Если у кого есть реализация, поделитесь. Думаю что смогу разобраться. |
|||
|
||||
Загрузка ...
| JackYF |
|
|||
 полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: нет Всего: 162 |
Что есть недвудольный граф? И что в нём есть паросочетание?
|
|||
|
||||
| Lomir |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 58 Регистрация: 30.1.2007 Где: Lithuania::Kaunas Репутация: нет Всего: 1 |
Есть любой граф G = (V, E)
Паросочитатие в графе это такое подмножество Е, что любые 2 элемента из подмножества не смежны с одной и той же вершиной из V. Максимальное парасочитание - парасочитание в котором мощность подмножества максимальна. На двудольной графе задача решаеться максимальным потоком. А вот что делать с обычными графами. |
|||
|
||||
| JackYF |
|
|||
|
полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: нет Всего: 162 |
всё, проблему понял. Решение, правда, в голову хорошее не приходит.
|
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Извиняюсь, а в книгах по теории графов вы не пробовали искать?
 Если нужна конкретная книга - например в Кристофидесе ("Теория графов. Алгоритмический подход"). А вообще задача настолько классическая, что наверно есть в каждой серьезной книге по графам... |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.6720 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |