Нужно определить максимальное количество рёбер в простом двудольном графе, который не имеет паросочетаний размера k и не содержит звезд из l рёбер.
Там формула есть, поищи просто.
Прямо со звездами?
а что именно у тебя не получилось?
Формулу вывести.
а как ты это делал
Никак, я не понимаю каким боком тут звезды. Ну то есть понятно что у нас могут быть паросочетания размером k - 1 и еще сюда можно каким-нибудь образом приплести реберное покрытие графа, но пока у меня идей нет.
ну смотри, тебе надо насыпать в граф ребра, пока не будет либо степень l, либо паросочетания твои.
соответственно берем k-1 пару, дальше из одной из вершин делаем звезду, получаем сколько-то ребер. это уже оценка снизу, которую мы конструктивно можем соорудить.
>>242875730
Окей, допустим что у нас граф на четырех вершинах. В таком графе у нас 2 паросочетания, k = 1.
Вершины 2 и 3 являются звездами с двумя ребрами, значит наше l = 1. Пока не сходится.
не, падажжи, у тебя в условии ничего про количество вершин нет, ты начинаешь с k l, и потом максимизируешь ребра. сколько у тебя вершин при этом получится вообще говоря хз, пока мы не научились делать самые хорошие графы.
тот граф, который нарисовал говорит нам только о том, что твой F(k,l) который мы ищем, такой что F(3,3)>=3
>В таком графе у нас 2 паросочетания, k = 1.
нет, если у тебя два паросочетания, значит граф не содержит паросочетания размера 3
>нет, если у тебя два паросочетания, значит граф не содержит паросочетания размера 3
Так, ну это ошибку я понял.
>>242876229
Да, спасибо Анон, ты действительно помог. Три часа сидел над этим.
okay, допустим у тебя k=2, тогда получается 2*(l-1) ребер. и одно паросочетание. как это должно работать?
Представь, что ты одну отметил одну вершину и еще миллион. И соединил эту вершину с миллионом остальных. Тогда в графе максимальное паросочетание из одного ребра, но вершин миллион плюс один.
очень хорошо, но х2 так не получить.
>>242879557
А если у нас наф типа пикрелейтед, у него нет паросочетаний (k = 1), есть одна звезда на 2 ребра -> l = 3;
Тогда число ребер = (k - 1)(l - 1) = 0 2 = 0
Зведочки отклеились.
(k - 1)x(l - 1) = 0x2 = 0
По условию k паросочетаний нет, k-1 - максимальное паросочетание, l-1 максимальное количество ребер в звезде
>максимальное паросочетание
Равное нулю, оно ноль. Если нет k паросочетаний, то k - 1 можт быть равно нулю, нет?
Да, там действительно ошибка. Возьмем две вершины и максимального паросочетания, соединенные ребром, если каждая из них соединена ребром не из паросочетания, то ребро, соединяющее две вершины можно заменить на два, и тогда паросочетание оказывается не максимальным. Поэтому вершины можно добавлять только из одной доли. Итого выходит 2(k-1) + (k-1)(l-2) = (k-1)*l, k-1 - максимальное паросочетание, l-1 - максимальная звезда. Надеюсь, понятно написал)
Ну в условии есть ограничение, что паросочетаний из k ребер нет. Любое другое количество возможно ( при этом конечно, меньшее). Если k=1, то максимальное паросочетание равно 0, а граф простой, т. е. вершин нулевой степени нет. Тогда и вершин 0
>вершины можно добавлять только из одной доли.
это утверждение следует доказать. по факту оно тут наиболее интересный кусок задачи, т.к. конструктивно собрать хороший граф это более-менее лайтово раз даже мы тут это потянули по идее нужна конструкция вида, пусть вот у нас максимальное паросочетание размером k-1, при этом ребер (k-1)x(l-1)+1, максимальная степень l-1, и дальше как-то приходить к противоречию по паросочетанию. для k=2 вроде выше получилось, но надо общий случай.
Так ошибочное доказательство вот здесь >>242879262, а вот тут >>242881716 объяснение, почему оно ошибочное и как оно исправимо. Добавляем к максимальному паросочетанию вершины, если добавим сразу в обе доли, то паросочетание уже не максимальное. Добавляем только к одной, получаем такой ответ. Максимальность из построения напрямую следует
падажжи, там доказательство почему нельзя дальше увеличивать ту конструкцию которую ты придумал, ниоткуда не следует что в общем случае граф должен выглядеть именно так.
(3 - 1)(3 - 1) = 4, а ребра 3. Где подвох? Или считаются все ребра, входящие во все звезда? Тогда это 3 ребра, а l = 4.
изучаю графы третий день, не пинайте сильно
то что формула это оценка сверху, а твой граф до нее не дотягивает. но утверждение состоит в том, что никакой граф с данными ограничениями эту формулу не переплюнет и не даст например 5 ребер.
Там нет никакой конструкции. Возьмем произвольный граф с условиями на паросочетания и звезды. Возьмем в нем максимальное паросочетание из k-1 ребра и 2(k-1) вершин. Пусть есть еще какие-то вершины. Эти вершины не могут быть соединены между собой, иначе паросочетание не максимальное. В каждой паре вершин из максимального паросочетания только одна может быть соединена с вершинами не из этого паросочетания, иначе оно не максимальное. Каждая такая вершина может быть соединена не более чем с l-2 вершинами по условию. Вот и выходит, 2(k-1) + (k-1)(l-2)
В итоге граф это набор звезд
действительно, так вроде норм.
А, понял, это формула не для точного вычисления ребер, а для максимально возможного.
А ты где учишься? Чет интересно стало
я нигде, я тот анон, который начал опу помогать в начале треда.
А оп спать лег видимо, да и ладно
Не лег. Курсы прохожу на степике, вкатываюсь в математику.