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

08.04.2014, 19:54. **Показов** 3651. **Ответов** 2

Author24 — интернет-сервис помощи студентам

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

@kabenyuk · 09.04.2014, 06:53

Равносильная формулировка. Каждый граф связен, либо имеет связное дополнение. Вот коротко решение вашей задачи. Допустим, что для автобуса. Выберем все города X, которые связаны автобусным сообщением (считая пересадки) с фиксированным городом А. Если это все, то вид транспорта найден. Если нет, то пусть Y - остальные города. Тогда каждый город из Х соединен с каждым городом из Y жд. Тогда по жд можно проехать между любой парой городов.

@Alex5 · 10.04.2014, 14:54

Докажем индукцией по числу городов.
Число городов n = 2. Верно.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?n \geq 3$
Выберем какие-нибудь n-1 городов. По предположению индукции найдётся вид транспорта Т₁, который связывает эти (n-1) городов. Имеется две возможности:
1) n-й город тоже связан с помощью транспорта Т₁ с к.-н. городом. Значит транспорт Т₁ связывает все города.
2) n-й город ни с каким другим городом не связан с помощью Т₁. В этом случае n-й город соединенён с любым городом маршрутом типа Т₂.

man9n9
		1
	Докажите, что существует вид транспорта, которым можно доехать из любого города страны в любой другой 08.04.2014, 19:54. Показов 3651. Ответов 2 Метки нет (Все метки) В одной стране каждая пара городов соединена только одним транспортным маршрутом: или железнодорожным, или автобусным. Докажите, что существует вид транспорта, которым можно доехать из любого города страны в любой другой (возможно, с пересадками)

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	09.04.2014, 06:53	2
	Равносильная формулировка. Каждый граф связен, либо имеет связное дополнение. Вот коротко решение вашей задачи. Допустим, что для автобуса. Выберем все города X, которые связаны автобусным сообщением (считая пересадки) с фиксированным городом А. Если это все, то вид транспорта найден. Если нет, то пусть Y - остальные города. Тогда каждый город из Х соединен с каждым городом из Y жд. Тогда по жд можно проехать между любой парой городов. 3

@Alex5 1130 / 789 / 232 Регистрация: 12.04.2010 Сообщений: 2,012
	10.04.2014, 14:54	3
	Докажем индукцией по числу городов. Число городов n = 2. Верно. $https://www.cyberforum.ru/cgi-bin/latex.cgi?n \geq 3$ Выберем какие-нибудь n-1 городов. По предположению индукции найдётся вид транспорта Т₁, который связывает эти (n-1) городов. Имеется две возможности: 1) n-й город тоже связан с помощью транспорта Т₁ с к.-н. городом. Значит транспорт Т₁ связывает все города. 2) n-й город ни с каким другим городом не связан с помощью Т₁. В этом случае n-й город соединенён с любым городом маршрутом типа Т₂. 0

Опции темы