Файл: Серия Деревья .pdf

Серия 2. Деревья +
1. В связном графе нашлись три простых пути максимальной длины, каждые два из которых пересе- каются ровно по одной вершине. Докажите, что у всех трех путей есть общая вершина.
2. В связном графе нет циклов длины менее 5 и степени всех вершин не менее 10. Докажите, что в нем не менее 101 вершин.
3.Выпуклый n-угольник разрезан непересекающимися диагоналями на треугольники.
a) Докажите что при n ≥ 4 найдутся две диагонали, отрезающие от многоугольника треугольники.
б) Докажите что при n ≥ 6 найдется диагональ, отрезающая четырёхугольник или пятиугольник.
4. Докажите, что у дерева может быть не более двух центров.
5. Пусть G — связный граф, причем отличный от дерева. Докажите, что G имеет хотя три вершины,
удаление любой из которых не нарушает связности.
6. Дан связный граф, у которого 200 вершин нечетной степени, а остальные имеют четную степень. До- кажите, что вершины этого графа можно покрыть 100 путями (не обязательно простыми!), не имеющими общих рёбер.
7. Дано дерево. За ход разрешается стереть одно ребро, ведущее в висячую вершину, и соединить эту вершину ребром с любой другой вершиной. За какое наименьшее число ходов можно из одного заданного дерева на n вершинах гарантированно получить другое заданное дерево на n вершинах (все вершины считаются одинаковыми)?
Серия 2. Деревья +
1. В связном графе нашлись три простых пути максимальной длины, каждые два из которых пересе- каются ровно по одной вершине. Докажите, что у всех трех путей есть общая вершина.
2. В связном графе нет циклов длины менее 5 и степени всех вершин не менее 10. Докажите, что в нем не менее 101 вершин.
3.Выпуклый n-угольник разрезан непересекающимися диагоналями на треугольники.
a) Докажите что при n ≥ 4 найдутся две диагонали, отрезающие от многоугольника треугольники.
б) Докажите что при n ≥ 6 найдется диагональ, отрезающая четырёхугольник или пятиугольник.
4. Докажите, что у дерева может быть не более двух центров.
5. Пусть G — связный граф, причем отличный от дерева. Докажите, что G имеет хотя три вершины,
удаление любой из которых не нарушает связности.
6. Дан связный граф, у которого 200 вершин нечетной степени, а остальные имеют четную степень. До- кажите, что вершины этого графа можно покрыть 100 путями (не обязательно простыми!), не имеющими общих рёбер.
7. Дано дерево. За ход разрешается стереть одно ребро, ведущее в висячую вершину, и соединить эту вершину ребром с любой другой вершиной. За какое наименьшее число ходов можно из одного заданного дерева на n вершинах гарантированно получить другое заданное дерево на n вершинах (все вершины считаются одинаковыми)?
Серия 2. Деревья +
1. В связном графе нашлись три простых пути максимальной длины, каждые два из которых пересе- каются ровно по одной вершине. Докажите, что у всех трех путей есть общая вершина.
2. В связном графе нет циклов длины менее 5 и степени всех вершин не менее 10. Докажите, что в нем не менее 101 вершин.
3.Выпуклый n-угольник разрезан непересекающимися диагоналями на треугольники.
a) Докажите что при n ≥ 4 найдутся две диагонали, отрезающие от многоугольника треугольники.
б) Докажите что при n ≥ 6 найдется диагональ, отрезающая четырёхугольник или пятиугольник.
4. Докажите, что у дерева может быть не более двух центров.
5. Пусть G — связный граф, причем отличный от дерева. Докажите, что G имеет хотя три вершины,
удаление любой из которых не нарушает связности.
6. Дан связный граф, у которого 200 вершин нечетной степени, а остальные имеют четную степень. До- кажите, что вершины этого графа можно покрыть 100 путями (не обязательно простыми!), не имеющими общих рёбер.
7. Дано дерево. За ход разрешается стереть одно ребро, ведущее в висячую вершину, и соединить эту вершину ребром с любой другой вершиной. За какое наименьшее число ходов можно из одного заданного дерева на n вершинах гарантированно получить другое заданное дерево на n вершинах (все вершины считаются одинаковыми)?