Страница: << 85 86 87 88 89 90 91 >> [Всего задач: 1029]      

В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих рёбер равно 40.

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

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

Решение

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

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

Решение

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

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

Решение

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

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

Решение

На окружности даны 10 точек. Сколькими способами можно провести пять отрезков, не имеющих общих точек, с концами в данных точках?

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

Решение

Страница: << 85 86 87 88 89 90 91 >> [Всего задач: 1029]