Версия для печати
Убрать все задачи

---

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

   Решение

Страница: << 50 51 52 53 54 55 56 >> [Всего задач: 383]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 30806

Темы:   [ Обход графов ] [ Деревья ] [ Четность и нечетность ] [ Индукция (прочее) ]

Сложность: 4 Классы: 8,9

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

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

Решение

---

Задача 30824

Темы:   [ Ориентированные графы ] [ Обход графов ] [ Индукция (прочее) ]

Сложность: 4 Классы: 8,9

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

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

Решение

---

Задача 31091

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

Сложность: 4 Классы: 6,7,8

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

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

Решение

---

Задача 31104

Темы:   [ Теория графов (прочее) ] [ Степень вершины ] [ Принцип крайнего (прочее) ] [ Неравенство Коши ] [ Разбиения на пары и группы; биекции ]

Сложность: 4 Классы: 6,7,8

а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?
б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?

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

Решение

---

Задача 66597

Темы:   [ Деревья ] [ Обход графов ] [ Теория алгоритмов (прочее) ]

Сложность: 4 Классы: 10,11

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

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

Решение

---

Страница: << 50 51 52 53 54 55 56 >> [Всего задач: 383]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями