ВиС 8 класс 21 урок

2.

Граф - это изображение объектов и связей между ними
с помощью точек и линий.

4.

Точки в графе называют
вершинами графа. Некоторые
(не обязательно все) вершины
соединены
линиями.
Эти
линии называют ребрами.

5.

Степень вершины в графе - это
количество исходящих из нее
рёбер. Определите степени всех
вершин графа, изображенного на
рисунке.
Б
А
В
Е
Д
Г

Предположим, что в некотором графе
можно по рёбрам “пройти” из
вершины А в вершину В, то есть G
существует последовательность рёбер,
соединяющих вершины А и В. Такую
последовательность называют путём
из вершины А в вершину В.
F
E
D
B
A
C

7.

Найдите возможные пути из
вершины А в вершину В.
ACB
ADFEB
ADCADCB и т.д.
G
A
-простые пути или цепи, потому что в них
вершины и рёбра не повторяются.
F
E
D
B
C

8.

Цикл
в
графе
это
замкнутый путь, у которого
начало и конец в одной
вершине,
а
рёбра
и
промежуточные вершины не
повторяются.
F
G
E
D
B
A
C

9.

Граф
называется
связным, если две
любые
вершины
соединены путём.
а) связный граф
б) несвязный граф

10.

ТЕМА УРОКА:
ДЕРЕВЬЯ
§ 46

11.

Определение:
Дерево циклов.
связный
граф
без

12.

Определение:
Цепь - это дерево.
Одна вершина - это простейшее
дерево.

13.

Определение:
Корневая вершина
Концевые вершины

14.

Задание:
Является ли граф, изображённый на рисунке,
деревом?
Ответ: нет.
Граф, изображённый на рисунке, содержит цикл, а
значит, не является деревом.

15.

16.

Задание:
Является ли граф, изображённый на рисунке,
деревом?
Ответ: да.
Граф, изображённый на рисунке, не содержит цикл, а
значит, является деревом.

17.

Задание:
На рисунке изображён граф.
1. Является ли граф, изображённый
на рисунке, деревом?
Ответ: да.

18.

Задание:
На рисунке изображён граф.
2. Сколько рёбер у данного графа?
Ответ: 7.

19.

Задание:
На рисунке изображён граф.
3. Сколько вершин у графа,
изображённого на рисунке?
Ответ: 8.

20.

Задание:
На рисунке изображён граф.
4. Сколько концевых вершин у
графа, изображённого на рисунке?
Ответ: 5.

21.

Одноклассницы Оля, Валя и Катя дежурят по школе.
Сколькими способами классный руководитель может
расставить девочек по одной на каждом их трёх этажей
школы? Изобразите решение с помощью дерева
возможных вариантов.

22.

Классный руководитель
1-й этаж
О
В
К
2-й этаж
В
К
О
К
О
В
3-й этаж
К
В
К
О
В
О

23.

1. Спортивной команде предлагают футболки трёх
цветов – красного, зелёного и синего, а шорты двух
цветов – белого и жёлтого. Сколько вариантов
выбора формы есть у команды?
2. У Тани есть четыре платья и две пары туфель.
Сколько у Тани есть вариантов выбрать наряд?
3. В отряде космонавтов есть три пилота и два
инженера. Сколько существует способов составить
экипаж, состоящий из одного пилота и одного
инженера?

English Русский Rules