В моем местном сквош-клубе есть лестница, которая работает следующим образом.
- В начале сезона мы строим таблицу с именами каждого члена клуба на отдельной строке.
- Затем мы записываем количество выигранных игр и количество игр, сыгранных рядом с каждым именем (в форме: игрок выигрывает / игры).
Таким образом, в начале сезона таблица выглядит так:
Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0
Любые два игрока могут сыграть матч, при этом один игрок выигрывает. Если игрок, ближайший к нижней части стола, выигрывает, то положение игроков меняется. Затем мы повторяем шаг 2., обновляя количество побед и игр рядом с каждым игроком. Например, если Алиса побеждает Билли, у нас есть
Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0
Эти матчи продолжаются в течение всего сезона и в итоге приводят к тому, что игроки перечисляются в порядке приблизительной силы.
К сожалению, обновление происходит довольно случайно, поэтому ошибки допускаются. Ниже приведены некоторые примеры недопустимых таблиц, то есть таблиц, которые не могли быть созданы путем правильного выполнения вышеуказанных шагов для некоторого начального порядка (мы забыли порядок, который мы использовали в начале сезона), а также последовательности матчей и результатов:
Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0
Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0
Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1
Учитывая таблицу, как мы можем эффективно определить, является ли она действительной? Мы могли бы начать, отметив следующее:
Порядок имен не имеет значения, так как мы забыли исходный стартовый порядок.
Общее количество побед должно составлять половину суммы сыгранных игр. (Это показывает, что первый пример выше недействителен.)
- Предположим, что таблица действительна. Затем есть мультиграф - граф, допускающий множество ребер, но без петель - с каждой вершиной, соответствующей игроку, и каждым ребром с сыгранным совпадением. Тогда общее количество игр, сыгранных каждым игроком, соответствует степени вершины игрока в мультиграфе. Так что если нет мультиграфа с соответствующими степенями вершины, то таблица должна быть недействительной. Например, нет мультиграфа с одной вершиной степени один и одной вершины степени три, поэтому второй пример недопустим. [Мы можем эффективно проверить наличие такого мультиграфа.]
Таким образом, у нас есть две проверки, с которых мы можем начать, но это по-прежнему допускает неверные таблицы, такие как третий пример. Чтобы увидеть, что эта таблица недействительна, мы можем работать задом наперед, исчерпав все возможные способы, которыми могла возникнуть таблица.
Мне было интересно, может ли кто-нибудь придумать алгоритм полиномиального времени (по количеству игроков и количеству игр), решающий эту проблему?
источник
Ответы:
Это не полный ответ. Я даю более простое изложение проблемы и некоторые замечания.
Начнем с графа, где вершины помечены .[n]
У нас есть операция, которая добавляет направленный край от к к графику, и если переключает их метки.u l a b e l ( v ) < l a b e l ( u )v u label(v)<label(u)
Имея ориентированный мультиграф с вершинами и ребрами, проверьте, можно ли его получить, используя вышеописанную операцию.н еG n e
Легко видеть , что проблема заключается в : сертификат является (полином размера) последовательность операций , приводящих к . GNP G
наблюдение
Кажется, что мы можем предположить без ограничения общности, что все ребра к последней вершине добавляются в конце последовательности, а все ребра из нее добавляются в начале последовательности. Это может быть обобщено на другие вершины. Предположим, что мы удалили все вершины с метками больше . Все ребра к добавляются в конце последовательности, а все ребра из добавляются в начале последовательности.v vlabel(v) v v
Я думаю, что было бы возможно объединить это наблюдение с Гавелом-Хакими, чтобы получить алгоритм полиномиального времени.
источник
Я не решил проблему, но у меня есть частичные результаты, утверждения которых приведены ниже. Я напишу доказательства, если кому-то будет интересно.
Предложение . Предположим, что в лэддере (1) более одного игрока (2) содержит равное количество побед и поражений; и (3) таков, что каждый игрок выиграл по меньшей мере одну игру и проиграл по меньшей мере одну игру. Тогда лестница действительна.
источник