{ "id": "lktg-2026-project2-problem09-bollobas-szabo-oriented-cycle-game", "title": "Игра Боллобаша-Сабо: плотное ядро и принудительный ориентированный цикл", "kind": { "primary": "theorem_problem", "secondary": [ "game", "extremal_graph_theory", "classical_theorem" ] }, "language": "ru", "authors": [ { "name": "B. Bollobás", "role": "author_of_primary_source", "status": "source_verified", "note": "Имя перенесено из библиографической строки официального PDF проекта." }, { "name": "T. Szabó", "role": "author_of_primary_source", "status": "source_verified", "note": "Имя перенесено из библиографической строки официального PDF проекта." } ], "problem_profile": { "objects": [ "orientation_game", "four_regular_graph", "minimal_dense_core", "quadrangulated_orientable_surface", "toroidal_grid" ], "methods": [ "euler_tour_pairing", "hall_type_assignment", "deferred_edge_strategy", "minimal_dense_subgraph", "euler_characteristic", "local_indistinguishability_construction" ], "transformations": [ "euler_tour_to_edge_pairs", "dense_graph_to_minimal_dense_core", "edge_assignment_to_pairing_strategy", "square_grid_ball_to_toroidal_grid_ball" ], "goal": [ "force_directed_cycle", "prove_bollobas_szabo_theorem", "handle_both_move_orders", "construct_finite_local_countermodels" ], "auxiliary_graph_type": [ "minimal_dense_core", "bipartite_assignment_graph", "cartesian_product_of_cycles" ], "invariants": [ "every_pair_center_is_protected_from_becoming_sink", "at_most_one_deferred_edge", "edge_slot_hall_condition" ], "keywords": [ "bollobas_szabo_1998", "oriented_cycle_game", "two_n_minus_two_edges", "minimal_dense_core", "toroidal_grid_local_ball" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-problem09", "title": "Шесть шагов к теореме об игре ориентированного цикла", "text": "На неориентированном графе \\(G\\) игроки Циклист и Ациклист по очереди выбирают ещё не ориентированное ребро и направляют его в любую сторону. Циклист выигрывает немедленно, как только появляется ориентированный цикл длины не менее 3; если все рёбра ориентированы и цикла нет, выигрывает Ациклист.\n\nСток - вершина, из которой не выходит ни одной стрелки; источник - вершина, в которую не входит ни одной стрелки. Через \\(v(H)\\) и \\(e(H)\\) обозначим число вершин и число рёбер графа \\(H\\). Конечный простой граф \\(H\\) назовём минимальным плотным ядром, если \\(v(H)\\ge3\\), \\(e(H)=2v(H)-2\\), но для каждого собственного подграфа \\(F\\subsetneq H\\) с \\(v(F)\\ge3\\) выполнено \\(e(F)\\le2v(F)-3\\).\n\nа) Докажите, что на любом конечном простом 4-регулярном графе Циклист, ходя первым, имеет выигрышную стратегию.\n\nб) Игра идёт на минимальном плотном ядре \\(H\\). Первым ходит Ациклист, вторым - Циклист. В этом пункте игроки ориентируют все рёбра \\(H\\), даже если ориентированный цикл появился раньше. Докажите, что Циклист может гарантировать, что итоговая ориентация \\(H\\) не имеет стоков.\n\nв) На минимальном плотном ядре \\(H\\) Циклист ходит первым. Докажите, что он может играть так, чтобы либо появился ориентированный цикл, либо после ориентации всех рёбер итоговая ориентация не имела стоков или не имела источников.\n\nг) Выведите теорему Боллобаша-Сабо: если конечный простой граф \\(G\\) имеет \\(N\\ge3\\) вершин и не менее \\(2N-2\\) рёбер, то Циклист, ходя первым, имеет выигрышную стратегию.\n\nд) Докажите, что на любом конечном простом 4-регулярном графе Циклист выигрывает независимо от того, кто сделал первый ход. Далее пусть простой граф с \\(N\\) вершинами клеточно вложен в замкнутую связную ориентируемую поверхность рода \\(g\\ge1\\), а граница каждой грани имеет длину 4. Найдите число его рёбер и докажите, что Циклист выигрывает при обоих порядках хода.\n\nе) Корневым шаром радиуса \\(R\\) назовём подграф, порождённый вершинами на расстоянии не более \\(R\\) от отмеченного центра. Для каждого \\(R\\ge0\\) постройте конечный простой граф \\(G_R\\) и вершину \\(v_R\\), для которых корневой шар радиуса \\(R\\) с центром \\(v_R\\) изоморфен корневому шару радиуса \\(R\\) квадратной решётки, но при каждом из двух порядков хода победитель на \\(G_R\\) противоположен победителю в соответствующей игре на бесконечной решётке. Все параметры конструкции укажите явно.", "source_id": "src-lktg-2026-project2-problems-ru", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "orientation", "cycle", "outdegree", "indegree", "degree", "eulerian_cycle", "distance", "induced_subgraph" ] } ] }, "ideas": [ { "id": "idea-euler-pairs", "title": "Эйлеров обход разбивает рёбра 4-регулярного графа на пары", "text": "После ориентации эйлерова обхода в каждую вершину входят два эталонных ребра; Циклист защищает центр каждой пары хотя бы одной исходящей стрелкой.", "tags": [ "eulerian_graphs", "invariant" ], "status": "ai_checked" }, { "id": "idea-edge-slot-assignment", "title": "Распределение рёбер по двум местам каждой вершины", "text": "Минимальная плотность ядра даёт условие Холла для назначения каждого ребра одному из концов с двумя местами у каждой вершины, кроме начала первой стрелки.", "tags": [ "matching", "extremal_graph_theory" ], "status": "ai_checked" }, { "id": "idea-deferred-edge", "title": "Одно отложенное ребро связывает ответы между парами", "text": "Если Ациклист берёт отложенное ребро, Циклист открывает следующую пару; если ход сделан в нетронутой паре, Циклист немедленно защищает её центр вторым ребром.", "tags": [ "invariant", "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-minimal-dense-core", "title": "Минимальный плотный подграф локализует игру", "text": "Из графа с не менее чем \\(2N-2\\) рёбрами выделяется минимальное плотное ядро; ходы Ациклиста вне ядра обрабатываются как пропуски.", "tags": [ "minimal_counterexample", "extremal_graph_theory" ], "status": "ai_checked" }, { "id": "idea-quadrangulation-count", "title": "Подсчёт рёбер квадрангуляции", "text": "Из \\(4f=2e\\) и \\(N-e+f=2-2g\\) получается \\(e=2N+4g-4\\), чего достаточно для плотностной теоремы при обоих порядках.", "tags": [ "double_counting", "planar_graphs" ], "status": "ai_checked" }, { "id": "idea-toroidal-local-model", "title": "Торическая решётка с большим нечётным периодом", "text": "Граф \\(C_{2R+3}\\square C_{2R+3}\\) 4-регулярен, но его шар радиуса \\(R\\) ещё не видит склейки тора и совпадает с шаром квадратной решётки.", "tags": [ "construction", "graph_symmetry" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-problem09-complete", "title": "Полное решение пунктов а-е", "text": "а) В каждой компоненте 4-регулярного графа построим замкнутый обход, проходящий по каждому ребру ровно один раз. Начнём идти по неиспользованным рёбрам. Застрять не в начальной вершине нельзя: до очередного входа в вершину использовано чётное число её рёбер, а сразу после входа - нечётное, то есть не все четыре. Если после возвращения остались рёбра, начнём такой же обход из вершины старого обхода, инцидентной неиспользованному ребру, и вклеим новый замкнутый кусок. Так получается эйлеров обход.\n\nНаправим каждое ребро эталонно по ходу обхода. В каждую вершину входят ровно два ребра; объединим их в пару с центром в этой вершине. Все рёбра разбились на пары. Циклист первым берёт одно ребро любой пары и направляет его из центра, а второе временно откладывает. Далее на ход Ациклиста в нетронутой паре он берёт второе ребро этой пары и направляет его из центра. Если Ациклист берёт отложенное ребро, Циклист открывает новую пару: одно её ребро направляет из центра, а второе объявляет новым отложенным. Если новых пар уже нет, ход Ациклиста на последнем отложенном ребре завершает ориентацию, и ответ не нужен. В результате из центра каждой пары выходит хотя бы одна стрелка, то есть стоков нет. В конечном ориентированном графе без стоков есть ориентированный цикл: двигаясь каждый раз по выходящей стрелке, мы когда-нибудь повторим вершину. В простом графе такой ориентированный цикл имеет длину не менее 3. Значит, Циклист выигрывает.\n\nДля остальных пунктов докажем две леммы.\n\nЛемма 1. Пусть каждому из конечного набора предметов разрешено занять некоторые места. Если для любого набора из \\(q\\) предметов совокупно доступно хотя бы \\(q\\) мест, то все предметы можно расставить по различным допустимым местам.\n\nДоказательство. Расставим наибольшее возможное число предметов. Если предмет \\(p\\) не расставлен, отметим его, затем все доступные ему места, затем все предметы, уже стоящие на отмеченных местах, и будем повторять последние два шага. Если встретилось свободное отмеченное место, вдоль получившейся чередующейся цепочки можно последовательно передвинуть предметы и поставить также \\(p\\), вопреки максимальности. Значит, свободного отмеченного места нет. Тогда все отмеченные места заняты, а отмеченных предметов на один больше: владельцы этих мест и первоначальный предмет \\(p\\). Все места, доступные отмеченным предметам, тоже отмечены. Получилось меньше доступных мест, чем предметов, что противоречит условию.\n\nЛемма 2. Пусть \\(H\\) - минимальное плотное ядро, а первое отмеченное ребро направлено \\(a\\to b\\). Тогда: 1) можно приписать каждое ребро одному из его концов так, чтобы вершине \\(a\\) не было приписано ни одного ребра, каждой другой вершине было приписано ровно два ребра, а ребро \\(ab\\) было приписано \\(b\\); 2) если есть ещё одно отличное от \\(ab\\) ребро \\(c\\to d\\), причём \\(a\\ne c\\), распределение можно выбрать так, чтобы дополнительно \\(cd\\) было приписано \\(c\\). Два ребра, приписанные одной вершине, будем называть её парой.\n\nДоказательство. Сделаем для каждой вершины, кроме \\(a\\), по два свободных места. Ребро разрешается положить только на место одного из его концов. В первом случае заранее кладём \\(ab\\) на место вершины \\(b\\). Во втором дополнительно кладём \\(cd\\) на место вершины \\(c\\); если \\(b=c\\), эти рёбра занимают два разных места одной вершины. Проверим условие леммы 1 для оставшихся рёбер.\n\nВозьмём любой набор оставшихся рёбер \\(Q\\), а через \\(X\\) обозначим множество всех их концов, кроме \\(a\\). Все рёбра \\(Q\\) входят в число \\(e_H(X\\cup\\{a\\})\\). Если \\(X\\cup\\{a\\}\\) - собственное множество вершин и \\(|X|\\ge2\\), то по минимальности ядра\n\\[e_H(X\\cup\\{a\\})\\le2(|X|+1)-3=2|X|-1.\\]\nЕсли \\(b\\in X\\), ребро \\(ab\\) посчитано слева, но уже не входит в \\(Q\\). Поэтому\n\\[|Q|\\le2|X|-1-\\mathbf 1_{b\\in X}.\\]\nВ первом случае у вершин \\(X\\) осталось \\(2|X|-\\mathbf 1_{b\\in X}\\) мест, то есть мест достаточно. Во втором случае осталось \\(2|X|-\\mathbf 1_{b\\in X}-\\mathbf 1_{c\\in X}\\) мест. Если \\(c\\in X\\), это равно правой части последней оценки; если \\(c\\notin X\\), мест на одно больше. Строгая единица в оценке плотности оплачивает потерю места в \\(c\\), даже если заранее положенное ребро \\(cd\\) не лежит внутри \\(X\\cup\\{a\\}\\).\n\nЕсли \\(X\\cup\\{a\\}=V(H)\\), число всех оставшихся рёбер точно равно числу всех оставшихся мест: соответственно \\(2v(H)-3\\) и \\(2v(H)-4\\), поэтому мест хватает и для \\(Q\\). При \\(X=\\varnothing\\) набор \\(Q\\) пуст. При \\(X=\\{x\\}\\) в простом графе \\(Q\\) может содержать только ребро \\(ax\\). В первом случае свободно \\(2-\\mathbf1_{x=b}\\) мест, а при \\(x=b\\) ребро \\(ax=ab\\) уже занято. Во втором случае свободно \\(2-\\mathbf1_{x=b}-\\mathbf1_{x=c}\\) мест; ноль возможен только при \\(x=b=c\\), но тогда \\(ax=ab\\) уже занято. Все случаи условия леммы 1 проверены, поэтому оставшиеся рёбра можно расставить. Лемма доказана.\n\nЗафиксируем механизм пар и отложенного ребра. Если два ребра пары приписаны вершине \\(x\\), Циклист защищает \\(x\\) от превращения в сток, направляя хотя бы одно из них из \\(x\\). В некоторый момент имеются нетронутые пары и, возможно, одно отложенное ребро, центр которого уже защищён. Если Ациклист берёт ребро нетронутой пары, Циклист берёт второе и направляет его из центра. Если Ациклист берёт отложенное ребро, Циклист начинает любую нетронутую пару, одно ребро направляет из центра, а второе объявляет новым отложенным. Если нетронутых пар уже нет, ход на последнем отложенном ребре завершает ориентацию. Так постепенно защищаются все центры.\n\nб) Пусть первый ход Ациклиста - \\(a\\to b\\). Применим первую часть леммы 2. Вершина \\(a\\) уже не является стоком. Ребро \\(ab\\) входит в пару вершины \\(b\\). Циклист немедленно берёт второе ребро этой пары и направляет его из \\(b\\). После каждого дальнейшего хода Ациклиста Циклист берёт второе ребро той же пары и направляет его из её центра. Поэтому каждая вершина, кроме уже защищённой \\(a\\), получает выходящую стрелку. Итоговая ориентация не имеет стоков. По условию пункта стратегия продолжается до конца даже при более раннем появлении цикла.\n\nв) Пусть Циклист первым направил \\(a\\to b\\), а Ациклист ответил \\(c\\to d\\). Сначала предположим, что \\(a\\ne c\\). Применим вторую часть леммы 2: ребро \\(ab\\) приписано \\(b\\), а \\(cd\\) - вершине \\(c\\). Вершина \\(a\\) защищена первым ребром, вершина \\(c\\) - вторым. Если \\(b\\ne c\\), Циклист берёт второе ребро пары вершины \\(b\\) и направляет его из \\(b\\), а неиспользованное второе ребро пары вершины \\(c\\) объявляет отложенным. Если \\(b=c\\), два первых ребра уже составляют пару этой вершины и защищают её центр; тогда Циклист открывает любую нетронутую пару и оставляет её второе ребро отложенным. Далее действует механизм пар и отложенного ребра. В итоге стоков нет, если ориентированный цикл не появился раньше.\n\nОстался случай \\(a=c\\). Тогда \\(b\\ne d\\), поскольку ходы сделаны на разных рёбрах. Мысленно развернём все стрелки. Первые две стрелки станут \\(b\\to a\\) и \\(d\\to a\\), то есть их начала различны. Уже разобранная стратегия для случая различных начал гарантирует отсутствие стоков в развёрнутой ориентации, а значит, в исходной ориентации не будет источников. Каждый дальнейший предписанный ход развёрнутой стратегии реализуется выбором того же ребра с противоположным направлением. Ориентированный цикл при развороте всех стрелок остаётся ориентированным циклом. Поэтому Циклист обеспечивает одну из требуемых альтернатив.\n\nг) Среди подграфов \\(G\\), имеющих не менее \\(2v-2\\) рёбер и хотя бы три вершины, выберем минимальный по включению и обозначим \\(H\\). Тогда \\(e(H)=2v(H)-2\\): при большем числе можно удалить одно ребро и сохранить требуемое неравенство. Каждый собственный подграф \\(F\\subsetneq H\\) с \\(v(F)\\ge3\\) имеет не более \\(2v(F)-3\\) рёбер, иначе он был бы выбран вместо \\(H\\). Следовательно, \\(H\\) - минимальное плотное ядро.\n\nЦиклист играет только на \\(H\\) и начинает с произвольной стрелки \\(a\\to b\\). Ход Ациклиста вне \\(H\\) рассматривается как пропуск внутри \\(H\\). Если первый ответ Ациклиста сделан в \\(H\\), применяется построение пункта в; после следующего хода Циклиста внутри \\(H\\) остаются нетронутые пары и одно отложенное ребро. Если первый ответ сделан вне \\(H\\), применяем первую часть леммы 2 к \\(a\\to b\\): Циклист берёт второе ребро пары \\(b\\) и направляет его из \\(b\\), после чего остаются только нетронутые пары.\n\nДальнейшие пропуски обрабатываются так. Если отложенного ребра нет и Ациклист ходит вне \\(H\\), Циклист открывает новую пару и оставляет второе ребро отложенным. Если отложенное ребро есть и Ациклист снова ходит вне \\(H\\), Циклист ориентирует отложенное ребро, после чего отложенного ребра снова нет. На ход в нетронутой паре он отвечает на втором ребре; на ход на отложенном ребре открывает следующую пару. Если подходящих рёбер нет, все рёбра \\(H\\) ориентированы. В ветви без источников все направления ответов меняются на противоположные: стрелки направляются в центры пар.\n\nИтак, независимо от ходов вне \\(H\\), Циклист получает на \\(H\\) ориентацию без стоков или без источников, если цикл не возник раньше. Конечная ориентация без стоков содержит ориентированный цикл при движении по выходящим стрелкам; без источников - по тому же аргументу после разворота всех стрелок. Следовательно, Циклист выигрывает. Это и есть теорема Боллобаша-Сабо.\n\nд) У 4-регулярного графа на \\(N\\) вершинах сумма степеней равна \\(4N\\), поэтому \\(2e=4N\\) и \\(e=2N\\). Если Циклист начинает, он выигрывает по пункту а или г. Если начинает Ациклист, забудем о его первом ориентированном ребре. Неориентированными остались \\(2N-1\\ge2N-2\\) рёбер, и среди них теперь первым ходит Циклист. Пункт г даёт ориентированный цикл, целиком состоящий из этих оставшихся рёбер.\n\nТеперь пусть граф клеточно вложен в замкнутую связную ориентируемую поверхность рода \\(g\\ge1\\), и каждая грань имеет длину 4. Пусть число граней равно \\(f\\). Каждое ребро граничит с двумя гранями, поэтому \\(4f=2e\\) и \\(f=e/2\\). Для клеточного разбиения выполняется\n\\[N-e+f=2-2g.\\]\nОбоснуем формулу. Величина \\(V-E+F\\) не меняется, если поставить новую вершину на ребре: \\(V\\) и \\(E\\) увеличатся на 1. Она также не меняется, если провести внутри грани простую дугу и разделить грань надвое: \\(E\\) и \\(F\\) увеличатся на 1. Любые два конечных клеточных разбиения одной поверхности имеют общее измельчение: рёбра можно слегка сдвинуть, отметить точки пересечения и разделить оставшиеся области дугами. Поэтому \\(V-E+F\\) можно вычислить на стандартном разбиении поверхности рода \\(g\\): многоугольнике с \\(4g\\) сторонами, склеенными в \\(2g\\) пар. После склейки у него одна вершина, \\(2g\\) рёбер и одна грань, так что \\(V-E+F=1-2g+1=2-2g\\).\n\nПодставляя \\(f=e/2\\), получаем\n\\[e=2N+4g-4.\\]\nПри \\(g\\ge1\\) это не меньше \\(2N\\). Если Циклист ходит первым, применяем пункт г. Если первым ходит Ациклист, после его хода остаётся не менее \\(2N-1\\ge2N-2\\) неориентированных рёбер, и к ним снова применяется пункт г. Циклист выигрывает при обоих порядках.\n\nе) Из задачи 8а известно и там полностью доказано, что на бесконечной квадратной решётке при обоих порядках выигрывает Ациклист. Построим конечные графы, на которых при обоих порядках выигрывает Циклист. Для заданного \\(R\\ge0\\) положим\n\\[L=2R+3,\\qquad G_R=C_L\\square C_L.\\]\nТо есть \\(V(G_R)=(\\mathbb Z/L\\mathbb Z)^2\\), а две вершины соединены, если они отличаются на \\(\\pm1\\) ровно в одной координате. Возьмём \\(v_R=(0,0)\\). Тогда\n\\[|V(G_R)|=L^2=(2R+3)^2,\\qquad |E(G_R)|=2L^2=2(2R+3)^2.\\]\nПоскольку \\(L\\ge3\\), граф прост и 4-регулярен. По пункту д Циклист выигрывает на нём при обоих порядках.\n\nПроверим корневой шар. Каждая вершина шара радиуса \\(R\\) имеет единственного представителя \\((x,y)\\in\\mathbb Z^2\\) с \\(|x|+|y|\\le R\\). Два разных таких представителя не совпадают по модулю \\(L\\), потому что абсолютная разность каждой их координаты не превосходит \\(2R