Информатика | 10 - 11 классы
Города соединены авиалиниями.
Известно, как бы ни разделить города на две группы, всегда найдется авиалиния, соединяющая какой - нибудь город одной группы с каким - то городом второй группы.
Доказать на графах что можно перелететь из любого города страны в любой другой город.
Определите, какой из представленных на рисунке кругов соответствует множеству :а)"европейский город" ;б)"город в Англии" ;в)"столичный европейский город"?
Определите, какой из представленных на рисунке кругов соответствует множеству :
а)"европейский город" ;
б)"город в Англии" ;
в)"столичный европейский город".
Перечислите города - объекты, являющиеся элементами представленных на рисунке множеств.
Какие города начинаются на м?
Какие города начинаются на м.
На конкурс поступило 16 проектов из трёх городов : А, В, С?
На конкурс поступило 16 проектов из трёх городов : А, В, С.
Для проверки наудачу выбирается один проект.
Сообщение "выбран проект из города А или из города В" несёт 3 бита информации.
Сколько проектов поступило из города А и В вместе?
В стране есть 21 городов?
В стране есть 21 городов.
Некоторые пары городов соединены двусторонними дорогами.
Известно, что из любого города в любой другой можно добраться ровно одним способом (способом называется путь, состоящие из городов, никакие два города в нем не повторяются).
Сколько всего дорог в стране?
Помогите создать ориентированный или неориентированный граф по карте любого города любой страны в виде рисунка Paint или в виде презентации в PowerPoint?
Помогите создать ориентированный или неориентированный граф по карте любого города любой страны в виде рисунка Paint или в виде презентации в PowerPoint.
В стране есть 19 городов?
В стране есть 19 городов.
Некоторые пары городов соединены одной двусторонней дорогой.
Известно, что из любого города в любой другой можно добраться ровно двумя различными способами (способом называется путь, состоящий из городов ; никакие два города в нем не совпадают).
Сколько всего дорог в стране?
В стране есть несколько городов, соединенных двусторонними дорогами?
В стране есть несколько городов, соединенных двусторонними дорогами.
Каждую дорогу можно за некоторое количество денег (оно указано на рисунке возле дороги) превратить в скоростную магистраль.
За какое минимальное количество денег можно добиться того, чтобы из любого города можно было попасть в любой другой, передвигаясь только по скоростным магистралям?
Помогите с графами по ИКТ?
Помогите с графами по ИКТ.
2) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город З?
На рисунке - схема дорог связывающих города А Б В Г Д Е Ж И К М?
На рисунке - схема дорог связывающих города А Б В Г Д Е Ж И К М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует путей, ведущих из города А в город М и НЕ проходящих через город Г?
В каком городе был создан компьютер?
В каком городе был создан компьютер.
На этой странице находится ответ на вопрос Города соединены авиалиниями?, из категории Информатика, соответствующий программе для 10 - 11 классов. Чтобы посмотреть другие ответы воспользуйтесь «умным поиском»: с помощью ключевых слов подберите похожие вопросы и ответы в категории Информатика. Ответ, полностью соответствующий критериям вашего поиска, можно найти с помощью простого интерфейса: нажмите кнопку вверху страницы и сформулируйте вопрос иначе. Обратите внимание на варианты ответов других пользователей, которые можно не только просмотреть, но и прокомментировать.
Переформулируем задачу на теорию графов :
Если все вершины графа разделить на два множества, то найдется ребро, соединяющее вершину одного множества с вершиной другого.
Доказать, что граф связный.
Докажем от противного.
Пусть граф несвязный, тогда у него есть как минимум две компоненты связности.
Тогда возьмем такое разбиение графа на группы : в первой группе будут только вершины первой компоненты связности, а в другой группе будут все остальные вершины.
В таком случае, по условию задачи существует ребро из вершины первой группы в вершину второй, но это невозможно, так как вершины принадлежат кразным компонентам связности, а по определению между двумя разными компонентами связности нет ребер.
Противоречие, следовательно, граф связный.
Что и требовалось доказать.