Question

В Морском государстве 10 городов, которые соединены 37 паромными переправами (каждая пара городов соединена не более чем одной паромной переправой). Докажите, что из любого города можно добраться в любой другой.

Answer 1

Ответ:

Пошаговое объяснение:

Предположим, что есть какой-то изолированный город, до которого нельзя добраться на паромных переправах.

Тогда все 37 переправ соединяют только 9 городов из 10.

Но, если провести переправы из каждого города во все остальные, то получится 9*8/2 = 36 переправ.

Значит, 37-ая переправа должна соединять один 9 городов с 10-ым городом.

Таким образом, мы доказали, что из любого города можно попасть в этот выделенный город (один из 9), а из него - в изолированный город.

А также из любого города из этих 9 можно попасть в любой другой, из этих же 9 городов.

В итоге - из любого города можно попасть в любой другой.

Answer 2

Для доказательства того, что из любого города Морского государства можно добраться в любой другой, мы можем воспользоваться принципом связности.

Допустим, у нас есть 10 городов и 37 паромных переправ. Пусть граф представляет собой сеть городов, а рёбра графа представляют собой паромные переправы. Таким образом, у нас есть граф с 10 вершинами и 37 рёбрами.

Так как каждая пара городов соединена не более чем одной паромной переправой, и у нас есть 37 паромных переправ, то мы можем утверждать, что в графе нет изолированных вершин. Это следует из того, что каждый город соединен хотя бы с одним другим городом.

Теперь воспользуемся принципом связности. В связном графе из любой вершины можно добраться до любой другой вершины. Таким образом, из любого города Морского государства мы можем добраться до любого другого города, и доказательство завершено.