Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Задача на паросочетание
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Народ, у кого-нибудь есть идеи на задачу: на доске NxN (N<=50) надо раcставить максимальное количество коней так, чтобы они не били друг друга, причем некоторые клетки могут быть вырезаны. Как можно найти число коней максимальным паросочетанием?
Заранее спасибо.
вроде задача на ТЦ была, да и на нашем сете я делал похожую.
Строим двудольный граф по белым и черным клеткам( в левой доле былые, а в правой - черные ) потом добавляем ребра между клетками, которые бьют друг друга ( выжженые пропускаем ). Затем находим максимальное паросочетание - это и есть ответ. Вроде это задача о вершинном покрытии еще называется)
Не совсем понятно. Возможно я что-то не так понял. Такое паросочетание даст нам - макс. количество пар (черная + белая клетка которые друг-друга бьют, на одной из них должен находиться конь). Но ведь может позникнуть "конфликт" между парами. Клетки одной пары могут бить клетки из другой пары
Просто размер максимального паросочетания равен размеру максимального независимого множества.
Как в двудольном графе с помощью паросочетания найти вершины обр. минимальное покрытие?
Просто размер максимального паросочетания равен размеру максимального независимого множества.
Разве размер макс. независимого это не N-MaxMatch, где N-кол-во вершин в графе, а MaxMatch - размер макс. паросочетания?
Размер макс. паросочетания равен размеру минимального покрывающего множества.
Ну может быть 
В любом случае нам надо максимальное независимое множество, а оно как-то там зависит от макс паросочетания 
UPD: вспомнил, максимальное независимое множество является дополнением к минимальному контролирующему/покрывающему множеству.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Задача на паросочетание