Выиграть стратегию для данной игры на графиках

Question

Игра идет следующим образом. Два игрока играют в игру, игрок 1 и игрок 2, в котором первый игрок начинается, называя герою $ h_1 $ , то плеера 2 отвечает злодеем $ v_1 $ Кто играл в фильме с $ h_1 $ . Тогда игрок 1 отвечает другим героем $ h_2 $ Кто играл в фильме вместе с $ v_1 $ , и так далее. Каждый герой и злодей можно использовать максимум один раз. Первый игрок, который не может назвать какой-либо персонаж (доступные герои / злодеи не имеют общего фильма с последним выбором другого игрока), теряет игру. Игрок 1 всегда начинает игру.

Вход - это набор героев $ h $ , набор злодеев $ v $ ( $ | h |= | v | \ geq 1 $ ) и семейство фильмов $ m $ , Где каждый фильм - это набор героев и злодеев, которые появлялись в этом фильме.

Вопрос: Можете ли вы, на основе $ h $ , $ v $ и $ m $ , решить, какой игрок выигрывает игру, предполагая, что оба игрока играют оптимально?

---

Пример:

Учитывая следующие данные: Герои Железный человек , Captain America , Thor и Spider-Man Отказ Злопенности Whiplash , Ultron , TASOS и Стервятность . Фильмы Мстители: Бесконечная война (Звезды Железный Человек, Капитан Америка, Тор, Танаус и Человек Паука) и Человек-паук: HomeComing (звезды Железный Человек, Стервятник и Человек-паук). Можете ли вы решить, какой игрок есть выигрышная стратегия?

---

Мой подход - использовать максимальное количество двусторонних сопоставлений, чтобы узнать, какой проигрыватель имеет выигрышную стратегию, потому что мы можем разделить данные в два набора, а именно $ h $ и $ V $ и имеют отношения между этими двумя наборами. Алгоритм Hopcroft-Karp может принимать два таких набора и выяснить максимальную кардинальность. Пожалуйста, поправьте меня, если я ошибаюсь: в случаях, в котором есть идеальное совпадение, игрок 2 выигрывает и иначе игрок 1 выигрывает. Всякий раз, когда есть идеальное совпадение, это означает, что игрок 2 всегда имел ответы на герой, который игрок 1 имени.

Как бы вы решили это? Есть ли лучший, более эффективный раствор, чем некоторые максимальные бипарттовые сопоставления.

Answer 1

Короткий ответ, игрок два победа, если и только если соответствующий график допускает соответствие, что «охватывает» набор $ h $ .

---

Вот немного объяснения.

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

Так что давайте начнем с той стороны, пропущенной от вашего ответа. Предположим, что данный экземпляр соответствует графику, который допускает идеальное совпадение. Согласно вашей стратегии, игрок 2 выигрывает в этом случае, который прав. Сейчас предположим, что тот же экземпляр предоставляется с еще одним злодением, или десять более злодеев или одна тысяча. Очевидно, что игрок два до сих пор выигрывает с момента добавления злодеев, независимо от того, как мы им назначим, только помогает второму игроку. Так что ваша претензия не всегда держит. Однако ваш ответ очень близко к моей претензии и имеет ту же интуицию. Только отсутствует немного формальности.

Претензия. Предполагая, что оба игрока играют оптимально, игрок 1 выигрывает, если и только тогда, когда, учитывая экземпляр $ i $ , соответствующий График не допускает подходящего насыщения набора $ h $ .

Так что это значит? Соответствие насыщает набор вершин $ S $ , если каждая вершина в $ S $ инцидент вершина в сопоставлении. Теперь мы докажем претензию. Мы показываем две выигрышные стратегии один для того, чтобы игрок два, когда график допускает подходящую насыщенную насыщенную установку $ h $ и один для плеера, когда график не допускает такого совпадения. ,

<Сильное> Доказательство. Теперь предположим, что граф допускает такое совпадение. Пусть это соответствие будет $ m $ . Стратегия идет следующим образом. Пока игрок не проиграл, для каждого выбора $ h \ in h $ для игрока один, выберите $ v \ В V $ вершина соответствует $ h $ в $ m $ .

правильность следует непосредственно из того факта, что каждая вершина плеера два уникальна и рядом с выбором игрока одного (из-за свойств совпадения). Интуитивно, игрок, у которого у них будет кончается шаги (возможно, после выбора всех героев в наборе $ h $ ).

Теперь, если предположить, что график не допускает соответствующий насыщающий $ h $ , согласно теореме Холла, существует подмножество $ A \ subsretq h $ , такое, что $ | n (a) | . Выберите такой набор, который минимальный включение-мудрый. Мы утверждаем, что есть соответствующий $ m '$ , который насыщает $ n (A) $ . Предполагая, что иное, снова из-за зала, есть подмножество $ S \ subsEtq n (a) $ такое, что $ | n (Ы) | , но затем удаление $ n (s) \ cap A $ от $ A $ И $ S $ из $ n (a) $ дает подмножество $ a $ , который также противоречит состоянию зала, который образует противоречие на выбор $ a $ , чтобы быть минимальным. Следовательно, есть соответствующий $ m '$ , который насыщает $ n (A) $ .

Теперь стратегия идет как следует. Выберите вершину в $ a $ , который не инцидент для любого края в $ m $ . Такая вершина существует с момента $ | n (a) | <| A | $ . Сначала выберите эту вершину и для каждого выбора $ V \ V $ Fix Two, выберите вершину $ h \ in H $ сопоставлено на $ v $ в $ m '$ .

Опять же, легко увидеть, что два проигрывателя покончит из ходов в какой-то момент (возможно, после выбора всех вершин в $ N (A) $ ) и Следовательно, игрок один выигрывает.