Дискра ДЗ 2. Серия Деревья
 Скачать 62.64 Kb.
|
|
Серия 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 вершинах (все вершины считаются одинаковыми)? |