Граф. степени вершин. Пути, цепи, циклы.

Тема . Граф. Степени вершин. Пути, цепи, циклы.

Цель: продолжить формировать умение находить степень вершины, определять пути, различать цепи и циклы.

Ход урока

1. Организационный момент.

2. Урок-лекция

1. Граф – это представление объектов и связей между ними. Объекты обозначаются точками (вершины графа), связи –это отрезки (ребра графа).

Стр. 47 рис.27. Посчитать количество вершин и ребер данного графа

Стр.48 рис.28. посмотреть применение графа в жизни.

1. Рис. 29. Граф и его матрица смежности. Если между объектами есть связь, то в матрице смежности пишут 1, если связи нет, то пишут 0. Данная матрица симметрична.

2. Стр. 49 рис.30. Данный граф от предыдущего отличается только стрелочками, т.е. появляется направление связей между объектами. Такой граф называют ориентированным. Матрица смежности уже не будет симметричной.

3. Рис. 31. Над каждым ребром написали числа – вес ребра. Такой граф называют взвешенным. И в матрицах смежности уже пишут не 0 и 1, а вес ребра.

4. Стр. 50 рис.32. Проведено несколько ребер между одной и той же парой вершин. Такой граф называют мультиграфом, а количество ребер между одной и той же парой вершин называют кратностью ребер. Посчитать кратность каждого ребра на этом рисунке.

5. Стр. 50 рис.33. Граф с петлями. Петля – это ребро, которое соединяет вершину с этой же вершиной. Граф показывает, как последняя цифра числа преобразуется после его возведения в квадрат.

6. Рис. 34. Примеры простых графов. Простой граф – это неориентированный, невзвешенный граф без петель и без кратности ребер.

7. Вспомнить определение степени вершины.

Стр. 51. Прочитать определение. Рис.35. Найти степени каждой вершины.

1. Если степень вершины равна 0, то вершину называют изолированной.

2. Стр. 52. Прочитать теоремы и следствие из теоремы. Выполнить №67, №68.

3. Стр. 53. Прочитать определение пути

4. Стр.54. Определение цикла.

5. Стр.54 рис.38. По рисунку найти пути из а в е, назвать цепь и цикл.

6. Эйлеров цикл и эйлеров путь.

7. Выполнить задания №72, №73.

Учащиеся в тетрадь записывают термины, которые рассматриваем на уроке.

В тетрадях у учащихся записано:

1. Вершины

2. Ребра

3. Матрица смежности

4. Ориентированный граф

5. Взвешенный граф

6. Мультиграф

7. Петли

8. Простой граф

9. Степень вершины

10. Изолированная вершина

11. Путь

12. Цепь

13. Цикл

14. Эйлеров путь

1. Домашнее задание

§3, знать определения терминов и теоремы, №75.