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

   Решение

Темы:    [ Ориентированные графы ] [ Связность и разложение на связные компоненты ]

Сложность: 5- Классы: 9,10,11

Прислать комментарий

Условие

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

Решение

  Рассмотрим граф, вершины которого соответствуют городам, а рёбра – дорогам, причём дорогам с односторонним движением поставим в соответствия ориентированные, а дорогам с двусторонним движением – неориентированные рёбра.
  Докажем, что в любой момент игры любое еще не ориентированное ребро можно ориентировать так, чтобы связность графа сохранилась. Из этого очевидно следует, что при правильной игре обоих игроков игра закончится вничью, и оба министра сохранят свои посты.
  Итак, пусть ребро между вершинами u и v еще не ориентированно.
  Заметим, что если между этими вершинами существует путь (не умаляя общности можно считать, что он ведёт от u к v), не проходящий по данному ребру, то ребро  (u, v)  можно ориентировать в направлении от v к u. Тогда в любом пути, проходившем по данному ребру в противоположном направлении, мы можем заменить это ребро на указанный выше путь от u к v, и связность графа не нарушится.
  Таким образом, нам достаточно рассмотреть ситуацию, когда между вершинами u и v не существует пути, не проходящего через ребро  (u, v) .
  Рассмотрим множество U всех вершин, до которых можно добраться из вершины u, не проходя по ребру  (u, v)  (включая и саму вершину u). Поскольку граф связен, для каждой вершины множества U существует путь, ведущий от неё до вершины v. По нашему предположению, этот путь проходит по ребру  (u, v). Из этого следует, что из каждой вершины множества U можно добраться до вершины u, не проходя по ребру  (u, v).  Но тогда из каждой вершины множества U можно добраться до любой другой вершины этого множества, не проходя по ребру  (u, v).
  Аналогичное множество для вершины v мы обозначим через V. Соответственно, из каждой его вершины также можно добраться до любой другой его вершины, не проходя по ребру  (u, v).
  Поскольку граф связен, каждая вершина принадлежит ровно одному из множеств U или V. Кроме того, поскольку исходный граф, в котором ребра не были ориентированы, сохранял связность при удалении ребра  (u, v),  между множествами U и V проходит еще хотя бы одно ребро, кроме ребра  (u, v).
  Пусть это ребро ведет из вершины  u₁ ∈ U  в вершину  v₁ ∈ V  (в данный момент игры это ребро может быть как ориентированным, так и неориентированным, но как минимум в одном из направлений, например, из u₁ в v₁, по нему пройти можно).
  Но тогда из вершины u мы можем добраться до вершины u₁, из u₁ до v₁ и из v₁ до v, не проходя при этом по ребру  (u, v) , что противоречит сделанному ранее предположению.

Ответ

Не может.

Источники и прецеденты использования