Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

[Spoiler (click to open)]Паросочетанием (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. Первый игрок каждым своим ходом выбирает любую вершину, что ему вздумается (из еще не выбранных никем), а второй - вершину, соединенную с предыдущим ходом первого.

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments