В стране имеются города некоторые из которых

В стране имеются города некоторые из которых

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

Решение

Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог, в которой начало очередной дороги совпадает с концом предыдущей. Каждый из этих двух городов по условию соединен не менее, чем с семью другими; при этом все упомянутые города различны – ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города.
Таким образом, мы насчитали не менее 16 городов. Противоречие.

Источники и прецеденты использования

web-сайт
задача
книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: «АСА»
Издание	1
глава
Номер	6
Название	Графы-1
Тема	Теория графов
задача
Номер	014

Проект осуществляется при поддержке и .

В стране имеются города некоторые из которых

Задача 14:

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

Решение:

Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог, в которой начало очередной дороги совпадает с концом предыдущей. Каждый из этих двух городов по условию соединен не менее, чем с 7 другими; при этом все упомянутые города различны – ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города.

Таким образом, мы указали не менее 16 городов. Противоречие.

Задача 15:

Докажите, что граф с n вершинами, степень каждой из которых не менее (n – 1)/2, – связен.

Решение:

Рассмотрим две произвольных вершины и предположим, что они не соединены путем, то есть такой последовательностью ребер, в которой начало очередного ребра совпадает с концом предыдущего. Каждая из этих двух вершин по условию соединена не менее, чем с (n – 1)/2 другими; при этом все упомянутые вершины различны – ведь если какие-то две из них совпадают, то есть путь, соединяющий исходные вершины.

Таким образом, мы указали не менее вершин. Противоречие.

Задача 16:

В Тридевятом царстве лишь один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов – по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).

Решение:

Рассмотрим компоненту связности графа ковролиний, содержащую столицу. Нам нужно доказать, что она содержит также и город Дальний. Предположим противное. Тогда в этой компоненте связности из одной вершины (столицы) выходит 21 ребро, а из всех остальных вершин – по 20 ребер. Таким образом в этом графе (компоненте связности) ровно одна нечетная вершина. Противоречие!

Задача 17:

В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.

Решение:

Если закрыта дорога AB, то нам достаточно доказать, что и после этого можно добраться из A в B. Если это не так, то в компоненте связности, содержащей A, все вершины, кроме A, – четные. Но наличие ровно одной нечетной вершины противоречит теореме о числе нечетных вершин.

Задачная база >> Разное >> Математический кружок. 1-й год >> Графы-1 >> Связность

Убрать решения

Имеются n городов, некоторые из них соединены дорогами; определить, из каждого ли города можно попасть в остальные

Граф задан матрицей смежности; определить, из каждого ли города можно попасть в остальные
Граф представляется матрицей смежности (или матрицей весов), структура хранения – статический.

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

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

В стране n городов, некоторые из них соединены авиалиниями
Здравствуйте! помогите пожалуйста решить задачку. В стране n городов, некоторые из них.

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Определить множества городов, в которые не можно попасть, передвигаясь из города X в город Y
Автобусные рейсы заданы массивом, индексами которого есть города, в каких начинается рейс, а.

В стране некоторые пары городов соединены авиалиниями
2. В стране некоторые пары городов соединены авиалиниями, причем каждый город соединен не менее.

Задача про графы: Проверить, из каждого ли города можно попасть в любой.
Помогите, пожалуйста, написать программу. Между городами проложены дороги. Проверить, из каждого.

Определить множество городов, в которые можно попасть автобусом
Пусть дан фрагмент программы. Опишите процедуру МожноПопасть(Р, Н, К), которая по рейсам Р (Р —.

В стране имеются города некоторые из которых

Задача 41:

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

Решение:

Указание: Общее количество «втекающих» рек должно быть равно общему количеству «вытекающих» рек.

Задача 42:

В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

Решение:

Пусть в столицу входит a дорог. Тогда общее число «входящих дорог равно 21 • 100 + a, а общее количество «выходящих» дорог не больше 20 • 100 + (100 – a). Поэтому 21 • 100 + a ≤ 20 • 100 + (100 – a), то есть 2a ≤ 0. Таким образом, a = 0.

Задача 43:

В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?

Решение:

Занумеруйте города и направьте движение от городов с меньшими номерами к городам с большими номерами.

Задача 44:

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

Решение:

Рассмотрите сначала вершины, соединенные с любой фиксированной вершиной A, затем – новые вершины, соединенные с ними и т.д. При этом ребра, соединяющие добавляемые вершины с уже рассмотренными, ориентируем в направлении к новым вершинам.

Задача 45:

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

а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой;

б) для каждой вершины числа входящих и выходящих ребер равны.

Решение:

Рассмотрим эйлеров цикл, проходящий по всем ребрам графа, и ориентируем все ребра в соответствии с порядком прохождения цикла.

Задача 46:

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

Решение:

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

Задача 47:

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

Решение:

Индукция по числу городов. База очевидна. Для доказательства индукционного перехода удалим сначала один из городов. В силу индукционного предположения есть город А с требуемым свойством. Вспомним теперь про удаленный город. Если в него ведет хотя бы одна дорога, то город А – искомый. В противном случае сам удаленный город удовлетворяет требуемому свойству.

Задача 48:

Несколько команд сыграли между собой круговой турнир по волейболу. Будем говорить, что команда А сильнее команды В, если либо А выиграла у В, либо существует команда С такая, что А выиграла у С, а С – у В.

а) Докажите, что есть команда, которая сильнее всех.

б) Докажите, что команда, выигравшая турнир, сильнее всех.

Решение:

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

Задача 49:

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

Решение:

База – для трех городов. Для доказательства индукционного перехода удалите город, имеющий и входящие и выходящие дороги.

Задача 50:

20 команд сыграли круговой турнир по волейболу. Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я – у 3-й, …, 19-я у 20-й.

Задача 51:

Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В и С такие, что А выиграла у В, В выиграла у С, а С выиграла у А.

Решение:

Пусть А и В набрали одинаковое количество очков, причем В выиграла у А. Тогда если для любой команды С, у которой выиграла А, выиграла и В, то у В должно быть очков больше, чем у А. Следовательно, есть команда С такая, что А выиграла у С, а С выиграла у В.

Задача 52:

В некотором государстве 101 город.

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

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

Решение:

Пусть из города А нельзя доехать до города В. Рассмотрите города, в которые входят дороги из А, и города, из которых выходят дороги в В. б) Вычислите общее количество дорог, выходящих из первой группы городов. Заметьте, что этих дорог достаточно много для того, чтобы хотя бы одна из них кончалась в городе из второй группы.

Задача 53:

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

Решение:

Пусть удалено ребро между вершинами А и В. Выберем две произвольные вершины. Рассмотрите три случая: обе эти вершины не совпадают с А или В, одна из них совпадает с А или с В, эти вершины – А и В.

Задачная база >> Разное >> Математический кружок. 2-й год >> Графы-2 >> Ориентированные графы

Убрать решения