ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 8 9 10 11 12 13 14 >> [Всего задач: 78]      



Задача 115396

Темы:   [ Наименьшее или наибольшее расстояние (длина) ]
[ Обход графов ]
[ Подсчет двумя способами ]
[ Планарные графы. Формула Эйлера ]
Сложность: 4-
Классы: 8,9,10,11

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

Прислать комментарий     Решение

Задача 30823

Темы:   [ Ориентированные графы ]
[ Обход графов ]
[ Степень вершины ]
Сложность: 4
Классы: 8,9

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

Прислать комментарий     Решение

Задача 30824

Темы:   [ Ориентированные графы ]
[ Обход графов ]
[ Индукция (прочее) ]
Сложность: 4
Классы: 8,9

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

Прислать комментарий     Решение

Задача 31091

Темы:   [ Степень вершины ]
[ Обход графов ]
[ Принцип крайнего (прочее) ]
[ Доказательство от противного ]
Сложность: 4
Классы: 6,7,8

В графе 20 вершин, степень каждой не меньше 10. Доказать, что в нём есть гамильтонов путь.

Прислать комментарий     Решение

Задача 31095

Темы:   [ Степень вершины ]
[ Обход графов ]
[ Четность и нечетность ]
[ Деревья ]
[ Индукция (прочее) ]
Сложность: 4
Классы: 6,7,8

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

Прислать комментарий     Решение

Страница: << 8 9 10 11 12 13 14 >> [Всего задач: 78]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .