Question

В королевстве есть города, некоторые из которых соединены между собой дорогами с односторонним движением. К сожалению, дороги построили так, что невозможно объехать все города, даже если посещать один и тот же город несколько раз. В связи с этим было принято решение разделить королевство на два княжества A и B, отнеся каждый город к одному из двух княжеств (в каждом княжестве должен быть хотя бы один город). Докажите, что можно сделать это так, чтобы из княжества A нельзя было попасть в княжество B

Answer 1

Ответ:

рассмотрим город А из него ми можем попасть в некоторие города . Из этих некоторие ( ранее изпользиваная група) городов кроме А и их самих некуда нельзя не куда попасть иначе из А вте города можно попасть противоречие=> если все остольное города пойдут в иное княжество(А) а эти в оставшиеся с оставшейся городов не попасть в города из княжества А

Answer 2

Для доказательства этого утверждения рассмотрим следующий алгоритм разделения королевства на два княжества A и B так, чтобы из A нельзя было попасть в B:

1. Выберем любой город и добавим его в княжество A.

2. Рассмотрим все города, которые можно достичь из выбранного города по односторонним дорогам. Добавим их в княжество A.

3. Повторим шаг 2 для всех городов, которые находятся в княжестве A и доступны по односторонним дорогам. Постепенно расширяем княжество A.

4. Города, которые остались в королевстве и не включены в княжество A, добавляем в княжество B.

Этот алгоритм гарантирует, что из княжества A можно добраться только до городов, которые были добавлены в это княжество в процессе выполнения алгоритма. Города, которые не были добавлены в княжество A, будут находиться в княжестве B. Это означает, что из A нельзя будет попасть в B, так как нет односторонних дорог, соединяющих города из A с городами из B.

Таким образом, мы доказали, что можно разделить королевство на два княжества A и B так, чтобы из A нельзя было попасть в B.