В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Iscaaro — Fold Your Hands And Pray";
Здравствуйте, ansi, Вы писали:
A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
Здравствуйте, Eugene Sh, Вы писали:
ES>Здравствуйте, Eugene Sh, Вы писали:
ES>>Города: 1,2,...,7 ES>>Линии: 1-2, 1-3, 1-4, 2-5, 3-6, 4-7, 5-6, 6-7, 5-7
ES>Добавляем город 8. И соединяем его с 2,3 и 4.
а как тогда переедем из 5 в 8? меньше чем за 2 хопа не получается имхо...
а так, для семи получается так:
берём куб, и убераем одну вершину:
Здравствуйте, ansi, Вы писали:
A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
Бесконечное число городов: один в центре и сколько угодно по кольцу!
Здравствуйте, ansi, Вы писали:
A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
Вот для восьми.
Верхняя граница 10 — показать несложно, а вот точно — хез
Здравствуйте, tinytjan, Вы писали:
T>Здравствуйте, ansi, Вы писали:
A>>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?T>Вот для восьми. T>Верхняя граница 10 — показать несложно, а вот точно — хез
Могу доказать, что городов не 9 (так что остается лишь проверить десятку).
Наблюдение: Если существует город, из которого выходят только 2 линии, то всего городов не более 7 (тот, из которого выходят 2 линии, еще два, в которые ведут эти линии, и еще из каждого из них может выйти не более 2 новых линий). Так что, если городов больше 7, то из каждого обязано выходить ровно 3 линии. Если городов 9, то посчитаем линии: из каждого города выходит по линии, итого 3*9 = 27 линий, но каждая линия посчитана дважды (как соединяющая А и Б и как соединяющая Б и А), поэтому не могло получиться 27 (на 2 не делится). Это доказывает тот простой факт, что в графе с 9 вершинами не может из каждой вершины выходить ровно 3 ребра.
Re: Некоторое государство
От:
Аноним
Дата:
25.04.05 20:16
Оценка:
Здравствуйте, ansi, Вы писали:
A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
Здравствуйте, ansi, Вы писали:
A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, tinytjan, Вы писали:
T>>Здравствуйте, ansi, Вы писали:
T>>Верхняя граница 10 — показать несложно, а вот точно — хез
Для десяти надо всего лишь доказать что нельзя для следующего графа
так добавить связи чтобы выполнялось условие задачи.
А>Могу доказать, что городов не 9 (так что остается лишь проверить десятку). А>Наблюдение: Если существует город, из которого выходят только 2 линии, то всего городов не более 7 (тот, из которого выходят 2 линии, еще два, в которые ведут эти линии, и еще из каждого из них может выйти не более 2 новых линий). Так что, если городов больше 7, то из каждого обязано выходить ровно 3 линии. Если городов 9, то посчитаем линии: из каждого города выходит по линии, итого 3*9 = 27 линий, но каждая линия посчитана дважды (как соединяющая А и Б и как соединяющая Б и А), поэтому не могло получиться 27 (на 2 не делится). Это доказывает тот простой факт, что в графе с 9 вершинами не может из каждой вершины выходить ровно 3 ребра.
На доказательство это не очень похоже, все-таки наблюдениями утверждения не доказываются.
Но ели я не ошибаюсь, случай для девяти может быть представлен как случай для 10 только без одной крайней вершины. Тогда надо доказать то же самое, что и для 10.
Здравствуйте, tinytjan, Вы писали:
T>На доказательство это не очень похоже, все-таки наблюдениями утверждения не доказываются.
Да нет, это вполне нормальное доказательство.
Посмотри ещё раз:
1) Если городов 9, то не может случиться так, что из каждого из них выходит 3 линии. Это следует из того, что 27 — нечётное число.
Значит, есть город A, из которого выходит только 2 линии (или 1 — это ещё хуже)
2) Посмотрим, в какие города мы сможем долететь из города A за 2 перелёта.
Есть 2 города B1 и B2, в которые можно перелететь за 1 перелёт.
За 1 перелёт из города B1 мы можем попасть максимум в 3 города: A и ещё 2. Обозначим эти 2 города как C_1_1 и C_1_2.
Аналогично, для города B2 получаем ещё 2 города: C_2_1 и C_2_2.
3) Получается, что из города A не более, чем за 2 перелёта мы можем попасть только в города B1, B2, С_1_1, C_1_2, C_2_1 и C_2_2. То есть всего городов должно быть не больше 7. Противоречие.
Здравствуйте, Eugene Sh, Вы писали:
ES>3) Получается, что из города A не более, чем за 2 перелёта мы можем попасть только в города B1, B2, С_1_1, C_1_2, C_2_1 и C_2_2. То есть всего городов должно быть не больше 7. Противоречие.
Здравствуйте, ansi, Вы писали:
A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
10
Имеем:
Точку начала пути. Три точки, в которые можем попасть, из данной точки. Шесть точек (т.к. один путь занят под путь из точки начала пути в заданную точку), в которые можем попасть из точки начала пути. Итого: 1+3+6 = 10. Больше быть не может, в силу условия достижимости.
Здравствуйте, tinytjan, Вы писали:
T>Для десяти надо всего лишь доказать что нельзя для следующего графа T> T>так добавить связи чтобы выполнялось условие задачи.