- Главная
- Математика
- Степени вершин графа. (Лекция 15)
Содержание
- 6. По степенной последовательности можно построить графы
- 7. Задача 1 Доказать, что если в графе с n вершинами (n>2) ровно две вершины имеют одинаковую
- 8. Задача 2 Существуют ли графы с данной степенной последовательностью? Ответ пояснить. 1) (1;2;3;4); 2) (13;22;3;5); 3)
- 9. Задача 3 а) Опишите n вершинный однородный граф степени 2. б) Опишите n вершинный однородный граф
- 10. Подграфы. Операции над графами
- 13. 4
- 24. Скачать презентацию
Слайд 2
Слайд 3
Слайд 4
Слайд 5
Слайд 6
По степенной последовательности можно построить графы
По степенной последовательности можно построить графы
Слайд 7
Задача 1
Доказать, что если в графе с n вершинами (n>2)
ровно две
Задача 1
Доказать, что если в графе с n вершинами (n>2)
ровно две
вершины имеют одинаковую степень,
то в этом графе либо в точности одна вершина степени 0,
либо в точности одна вершина степени (n-1).
Решение. Допустим противное.
1) В графе ровно две вершины одинаковой степени, и это вершины степени 0. Тогда, удалив из графа эти изолированные вершины, получим граф, степени всех вершин которого различны, что невозможно по теореме 3.
2) Если же в графе ровно две вершины одинаковой степени, и это вершины степени (n-1), то перейдя к дополнению , получим противоречие, аналогично пункту 1).
то в этом графе либо в точности одна вершина степени 0,
либо в точности одна вершина степени (n-1).
Решение. Допустим противное.
1) В графе ровно две вершины одинаковой степени, и это вершины степени 0. Тогда, удалив из графа эти изолированные вершины, получим граф, степени всех вершин которого различны, что невозможно по теореме 3.
2) Если же в графе ровно две вершины одинаковой степени, и это вершины степени (n-1), то перейдя к дополнению , получим противоречие, аналогично пункту 1).
Слайд 8
Задача 2
Существуют ли графы с данной степенной последовательностью? Ответ пояснить.
1) (1;2;3;4);
2)
Задача 2
Существуют ли графы с данной степенной последовательностью? Ответ пояснить.
1) (1;2;3;4);
2)
(13;22;3;5);
3) (0;1;2;3;42);
4) (12;23;32;4);
5) (12;32;4).
Решение.
1) Не существует, так как все степени различные (смотри теорему 7).
2) Не существует, так как число вершин нечетной степени нечетно, а именно 5 ( смотри теорему 6).
3) Не существует(смотри задачу 1).
4) Построим граф, имеющий данную степенную последовательность
5) Не существует, так как, соединив вершину степени 4 с четырьмя из оставшихся вершин, убеждаемся, что для вершин степени 3 не достаточно смежных вершин.
3) (0;1;2;3;42);
4) (12;23;32;4);
5) (12;32;4).
Решение.
1) Не существует, так как все степени различные (смотри теорему 7).
2) Не существует, так как число вершин нечетной степени нечетно, а именно 5 ( смотри теорему 6).
3) Не существует(смотри задачу 1).
4) Построим граф, имеющий данную степенную последовательность
5) Не существует, так как, соединив вершину степени 4 с четырьмя из оставшихся вершин, убеждаемся, что для вершин степени 3 не достаточно смежных вершин.
Слайд 9
Задача 3
а) Опишите n вершинный однородный граф степени 2.
б) Опишите n
Задача 3
а) Опишите n вершинный однородный граф степени 2.
б) Опишите n
вершинный однородный граф степени n-1.
Решение.
а) Многоугольник с n вершинами.
б) Полный n вершинный граф.
Решение.
а) Многоугольник с n вершинами.
б) Полный n вершинный граф.
Слайд 10
Подграфы.
Операции над графами
Подграфы.
Операции над графами
Слайд 11
Слайд 12
Слайд 13
4
4
Слайд 14
Слайд 15
Слайд 16
Слайд 17
Слайд 18
Слайд 19
Слайд 20
Слайд 21
Слайд 22