об одной игре на графах

[avva]

Недавно мне задали следующую задачу. Рассмотрим игру на произвольном конечном неориентированном графе. Первый игрок выбирает вершину графа. Второй выбирает вершину, связанную ребром с той, что выбрал первый. Первый выбирает вершину, связанную ребром с той, что только что выбрал второй. И так далее. Возвращаться в уже выбранные любой стороной вершины нельзя. Проигрывает тот, кто не может сделать очередной ход.

Ясно, что на любом графе либо у первого игрока есть стратегия гарантированной победы, либо у второго. Задача: охарактеризовать графы, в которых побеждает первый игрок (каким-нибудь более интересным/естественным способом, чем "графы, в которых побеждает первый игрок", разумеется).

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

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

Доказательство в одном направлении тривиально: если есть совершенное паросочетание, то второй игрок на любой ход первого просто выбирает свой ответ по нему.

В другом направлении надо чуть поработать. Пусть у второго игрока есть выигрышная стратегия, и пусть у нас уже есть какое-то паросочетание, еще не совершенное; используя стратегию второго игрока, мы его увеличим еще на две вершины (или одно ребро, что то же самое). Пусть S - множество вершин, уже участвующее в паросочетании, а A - любая вершина вне S. Начнем игру первым игроком с вершины A. У второго игрока всегда будете ответ на ходы первого, т.к. у него есть стратегия победы. Если второй игрок ответит в вершину B тоже вне S, то ребро A-B можно добавить в паросочетание, это простой случай. Если же второй игрок ответит вершиной внутри S, то мы за первого теперь будем отвечать согласно паросочетанию, и продолжать так делать, пока игра остается внутри S. Рано или поздно второму игроку придется выйти за пределы S в вершину B. Теперь у нас есть маршрут между A и B, начинающийся и заканчивающийся вне S, состоящий из нечетного числа ребер, например 2n+1, среди которых второе, четвертое и так далее, всего n четных ребер, находятся внутри паросочетания. Если мы все эти n четных ребер маршрута выбросим из паросочетания, а n+1 нечетных ребер маршрута добавим, то это все равно останется паросочетанием, все вершины, что были в нем, остались в нем, и еще добавились A и B.

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

После того, как я нашел этот критерий, мне пришло в голову следующее небольшое наблюдение. В доказательстве того, что этот критерий эквивалентен тому, что у второго игрока есть стратегия, нигде не используется то, что первый игрок *обязан* выбирать вершину, соединенную с предыдущим выбором второго. Используется то, что он *может* так выбрать, если захочет, но не то, что обязан - обязательность такого выбора использутся только у второго игрока. Что это значит? Сравните две игры:

Игра номер 1 (вышеприведенная). Каждый игрок выбирает вершину, соединенную с предыдущим ходом соперника.

Игра номер 2. Первый игрок каждым своим ходом выбирает любую вершину, что ему вздумается (из еще не выбранных никем), а второй - вершину, соединенную с предыдущим ходом первого.

На первый взгляд кажется, что вторая игра должна быть намного выгоднее для первого игрока - хотя бы на некоторых графах - потому что второй игрок теряет всякий шанс загнать первого в тупик. Но из вышеприведенного доказательства немедленно следует, что эти игры эквивалентны в том смысле, что на любом графе либо у первого игрока есть стратегия победы в обеих играх, либо у второго в обеих играх. Эта эквивалентность кажется весьма неинтуитивной и неочевидной, более неочевидной, чем сам вышеописанный критерий победы и его доказательство.

Comments

[mathclimber.livejournal.com]

Забавно, как раз вчера видел в арХиве статью про эту игру: http://arxiv.org/abs/1505.07485

[edd-l.livejournal.com]

Там по основной ссылке http://ac.els-cdn.com/009589567490029X/1-s2.0-009589567490029X-main.pdf?_tid=f61bf82e-0701-11e5-8fe2-00000aab0f26&acdnat=1433014251_84824fe80f27851990bf0e37dee6a49f немного другая игра, когда первый игрок выбирает ребро, а не вершину, из-за этого критерий получается более сложный

[enjoy-reading.livejournal.com]

Мне кажется, на этот счет тоже есть теорема. Что-то вроде: совершенное паросочетание существует iff Гамильтонов путь существует, хотя могу и перепутать

[enjoy-reading.livejournal.com]

(Там, конечно, должно быть нечто про четность числа вершин, а может и вообще, двукрашенность.)

[edd-l.livejournal.com]

Про гиперкуб, точнее http://www.sciencedirect.com/science/article/pii/S0095895607000354

[enjoy-reading.livejournal.com]

может быть.

[avva.livejournal.com]

Этого я не знаю, но есть красивая теорема Tutte:

Граф обладает совершенным паросочетанием iff для каждого подмножества вершин S верно, что если удалить из графа S и всего его ребра, в оставшемся графе будет не более |S| нечетных по размеру компонент связности.

(Я в процессе поиска критерия выигрыша второго игрока дошел до частного случая этого критерия для |S|=1, но потом нашел контрпримеры и не придумал, как это исправить. А если бы придумал, то переоткрыл бы теорему :))

[enjoy-reading.livejournal.com]

:)

[edd-l.livejournal.com]

Речь идёт, видимо, о связном графе. В несвязном второй игрок выигрывает iff каждая компонента связности обладает совершенным паросочетанием

[avva.livejournal.com]

Надо ли это выделять в отдельный случай? Каждая компонента обладает совершенным паросочетанием iff весь граф обладает совершенным паросочетанием.

[edd-l.livejournal.com]

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

[avva.livejournal.com]

Может, вы правы и следовало это точнее оформить, но мне неочевидно, что тут "жульничество", поскольку в док-ве второго направления первый игрок это "мы". Пока у нас нет совершенного паросочетания (на всем графе), мы можем продолжать выбирать за первого игрока начальные ходы вне имеющегося до сих пор паросочетания, не обращая внимание на то, лежит оно в одной компоненте связности или многих, выбираем мы первый ход в одной компоненте с паросочетанием или в разных... Мы можем специально оставаться внутри одной компоненты и закончить паросочетание в ней, а можем вообще не обращать внимания на компоненты и просто приращать паросочетание на всем графе, пока не получим совершенное.

Про явную стратегию первого игрока: следует построить максимальное паросочетание (в смысле maximum matching, а не maximal matching: т.е. максимальное по числу ребер, а не такое, к которому нельзя прибавить ребер). Это можно сделать с помощью http://en.wikipedia.org/wiki/Blossom_algorithm. Потом первый игрок начинает вне этого паросочетания и отвечает согласно ему.

[edd-l.livejournal.com]

Ага, про явную стратегию понятно, получается, что обоим игрокам нужно наибольшее паросочетание. Ну это если они оба умные. А если один из них глупый, то как другому попытаться выиграть (при неудачном для него начальном графе)? Можно, конечно, каждый раз строить наибольшее паросочетании в оставшемся подграфе, ну а если компьютера нет под рукой (был только перед игрой, когда начальный граф объявили), как тогда?

[edd-l.livejournal.com]

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

[falcao.livejournal.com]

Красиво!

[edd-l.livejournal.com]

Возможно, найденное соответствие между игрой 1 (когда взятые вершины образуют связный путь) и игрой 2 (когда вместо пути только куски из неинцидентных рёбер) есть отражение Теоремы Бержа: Паросочетание в двудольном графе (не в двудольным не знаю) является наибольшим тогда и
только тогда, когда не существует увеличивающей относительно него цепи.

А для нахождения просто ответа относительно того кто выиграл (сколько ребер в наибольшем паросочетании), наверное, лучше не сложный детерминированный алгоритм, а более изящный рандомизированный O(n^3), основанные на идее того же Татта http://e-maxx.ru/algo/tutte_matrix

[avva.livejournal.com]

Спасибо, почитаю.