Страница:
<< 29 30 31 32
33 34 35 >> [Всего задач: 393]
В некоторой стране 30 городов, причём каждый соединён с каждым дорогой.
Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в любой другой?
Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее рёбрами так, чтобы он остался связным.
|
|
|
Сложность: 4
Классы: 8,9,10
|
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками).
Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.
Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.
Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий.
Докажите, что либо "красный", либо "синий" граф не является плоским.
Страница:
<< 29 30 31 32
33 34 35 >> [Всего задач: 393]
Фильтр
