{ "id": "lehman-shannon-switching-game-two-spanning-trees", "title": "Игра Шеннона: критерий двух остовных деревьев", "kind": { "primary": "theorem", "secondary": [ "classical_tool", "game" ] }, "language": "ru", "authors": [ { "name": "Alfred Lehman", "status": "source_verified" } ], "problem_profile": { "objects": [ "finite_multigraph", "edge_claiming_game", "spanning_tree", "edge_disjoint_spanning_trees" ], "methods": [ "strategy_stealing", "induction", "edge_contraction", "cut_crossing_edge" ], "transformations": [ "maker_edge_contraction", "breaker_edge_deletion" ], "goal": [ "characterize_second_player_win" ], "auxiliary_graph_type": [], "invariants": [ "two_edge_disjoint_spanning_trees_after_each_round" ], "keywords": [ "shannon_switching_game", "maker_breaker_connectivity_game", "lehman_theorem", "two_spanning_trees" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-lehman-criterion", "title": "Критерий победы соединяющего игрока вторым ходом", "text": "Пусть \\(G\\) -- конечный связный мультиграф. Два игрока по очереди забирают ещё не занятые рёбра, по одному за ход; первым ходит Разрушитель, вторым -- Соединитель. Ребро Разрушителя считается удалённым, а ребро Соединителя -- закреплённым. После распределения всех рёбер Соединитель выигрывает, если его закреплённые рёбра содержат связный остовный подграф, то есть остовное дерево.\n\nДокажите критерий Лемана: Соединитель, играя вторым, имеет выигрышную стратегию тогда и только тогда, когда \\(G\\) содержит два не имеющих общих рёбер остовных дерева.", "source_id": "src-lehman-shannon-switching-game", "status": "source_verified", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "multigraph", "connected_graph", "spanning_tree" ] } ], "graph_theory": [], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-delete-and-contract", "title": "Удалить ход Разрушителя и стянуть ответ Соединителя", "text": "Если Разрушитель рвёт одно из двух остовных деревьев, второе содержит ребро через возникший разрез. Соединитель закрепляет это ребро и стягивает его; после одного полного раунда снова остаются два непересекающихся по рёбрам остовных дерева в меньшем мультиграфе.", "tags": [ "trees", "graph_cut", "induction" ], "status": "ai_checked" }, { "id": "idea-double-strategy-stealing", "title": "Выигрышную стратегию второго игрока можно запустить для обоих цветов", "text": "Для необходимости Разрушитель после произвольного первого ребра сам имитирует стратегию Соединителя, поменяв роли местами. Монотонность цели позволяет считать первое ребро лишним бонусом; в специально построенной партии оба набора рёбер оказываются связными.", "tags": [ "goal_strategy_game" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-lehman-induction", "title": "Доказательство стратегическим заимствованием и стягиванием", "text": "Сначала докажем необходимость. Предположим, что у Соединителя есть выигрышная стратегия \\(S\\) при игре вторым. Построим одну полную партию, в которой связные остовные подграфы получат оба игрока. Разрушитель первым берёт произвольное ребро. Далее Соединитель играет по \\(S\\) обычным образом, считая ходы Разрушителя ходами соперника. Разрушитель со своего второго хода тоже применяет \\(S\\), но с переставленными ролями: ходы Соединителя он считает ходами первого игрока. Его самое первое ребро при этом служит дополнительным бонусом. Если воображаемая стратегия попросит взять уже принадлежащее ему бонусное ребро, Разрушитель берёт любое свободное ребро и продолжает считать требуемое ребро уже полученным; наличие лишнего своего ребра не может помешать монотонной цели связности.\n\nСтратегия \\(S\\) гарантирует, что в конце реальные рёбра Соединителя содержат связный остовный подграф. Та же стратегия с переставленными ролями гарантирует это для рёбер Разрушителя. Из каждого из двух непересекающихся наборов выберем по остовному дереву. Получатся два остовных дерева без общих рёбер.\n\nТеперь докажем достаточность индукцией по числу вершин. При стягивании ребра параллельное ему ребро может превратиться в петлю. Поэтому индукционное утверждение временно рассматриваем для мультиграфов, в которых разрешены петли: петля никогда не входит в остовное дерево и остаётся обычным игровым ребром. Если Разрушитель выбирает петлю, это ровно случай \\(e\\notin T_1\\cup T_2\\) ниже; Соединитель отвечает ребром дерева, а выбранная петля удаляется. Сам Соединитель петель не выбирает. Таким образом, все промежуточные стягивания входят в область индукции. Для графа из одной вершины утверждение очевидно. Пусть в \\(G\\) есть два непересекающихся по рёбрам остовных дерева \\(T_1,T_2\\), и Разрушитель первым берёт ребро \\(e\\).\n\nЕсли \\(e\\in T_1\\), то лес \\(T_1-e\\) имеет две компоненты. Дерево \\(T_2\\) связно, поэтому в нём есть ребро \\(f\\), соединяющее эти компоненты. Соединитель закрепляет \\(f\\). Удалим \\(e\\) и стянем \\(f\\). Образ \\(T_1-e\\) после стягивания является остовным деревом меньшего мультиграфа: две его компоненты склеились в одной вершине. Образ \\(T_2-f\\) также является остовным деревом: удаление \\(f\\) разбило \\(T_2\\) на две компоненты, а стягивание концов \\(f\\) снова склеило их. Эти два дерева по-прежнему не имеют общих рёбер. Случай \\(e\\in T_2\\) симметричен.\n\nЕсли \\(e\\notin T_1\\cup T_2\\), Соединитель закрепляет любое ребро \\(f\\in T_1\\). После удаления \\(e\\) и стягивания \\(f\\) граф \\((T_1-f)/f\\) является остовным деревом. Образ связного графа \\(T_2\\) после стягивания остаётся связным и содержит некоторое остовное дерево; оно не пересекается по рёбрам с образом \\(T_1-f\\). Значит, и в этом случае в меньшем мультиграфе есть два непересекающихся остовных дерева.\n\nПосле первого раунда Соединитель применяет индукционную стратегию к полученному меньшему мультиграфу. Стягивание закреплённого ребра означает, что если его последующие закреплённые рёбра соединят все вершины стянутого графа, то вместе с \\(f\\) они соединят все вершины исходного графа. Поэтому Соединитель выигрывает. Обе импликации доказаны.", "idea_ids": [ "idea-delete-and-contract", "idea-double-strategy-stealing" ], "standard_idea_ids": [ "induction" ], "status": "ai_checked", "definition_ids": [ "multigraph", "connected_graph", "spanning_tree", "graph_cut" ] } ], "difficulty": { "main": "classical_tool", "local_score": 7, "comment": "Классический критерий позиционной игры. Достаточность даёт короткая, но содержательная индукция со стягиванием рёбер; необходимость использует двойное стратегическое заимствование.", "status": "ai_checked" }, "tags": [ "trees", "connectivity", "graph_cut", "induction", "goal_strategy_game", "goal_characterization", "classical_theorem" ], "properties": { "central_method": { "value": [ "two_edge_disjoint_spanning_trees", "delete_contract_induction", "strategy_stealing" ], "status": "ai_checked" }, "result": { "value": "Два не имеющих общих рёбер остовных дерева.", "status": "ai_checked" } }, "sources": [ { "source_id": "src-lehman-shannon-switching-game", "role": "primary_theorem_source", "status": "source_verified", "statement_ids": [ "stmt-lehman-criterion" ] } ], "editorial": { "created_by": "ai", "created_at": "2026-08-15", "review_status": "ai_checked", "public_ready": true, "notes": [ "Использована остовная форма игры Шеннона: Разрушитель ходит первым, Соединитель -- вторым.", "Полное доказательство перенесено в карточку; в нём явно разобран также случай, когда первый удалённый ход не принадлежит ни одному из двух выбранных остовных деревьев.", "В индукции явно сохранены петли, возникающие при стягивании параллельных рёбер; ход Разрушителя на петле обработан как ребро вне двух остовных деревьев." ], "relations_status": "deep_done", "graph_theory_duplicate_removed": true, "solution_classification": { "type": "classical_self_contained", "label": "классическое самодостаточное доказательство", "status": "ai_checked", "confidence": 0.96, "basis": "Критерий Лемана доказан внутри карточки через стандартную индукцию удаления--стягивания и стратегическое заимствование.", "notes": "Внешние теоремы в доказательстве не используются.", "audit_source": "manual-proof-review-2026-08-15" } } }