Читать

Урок 21. Пути в графе. Связные графы (7 класс)

Cкачать презентацию: Урок 21. Пути в графе. Связные графы (7 класс)

Читать публикацию

Скачать презентацию

Вставить эту публикацию

Прочитать другие публикации на CdnPdf

Вставить код

Ничего не найдено.

Презентация по слайдам:

Слайд #1

Урок 21
Вероятность и статистика 8 класс

Слайд #2

1. Что такое степень вершины графа?
2. Может ли степень вершины равняться 0?
3. Сформулируйте теорему о сумме степеней вершин.
4. Существует ли граф, в котором только 3 вершины со степенями
1, 2 и 2?
Приведите пример такого графа или объясните, почему такого не
может быть.

Вопросы

Слайд #3

Проверка домашнего задания
п. 19;

Слайд #4

Классная работа
Пути в графе. Связные графы
... 12. 23

Слайд #5

Граф — это изображение объектов и связей между ними с помощью точек
и линий.
Точки в графе называются вершинами графа. Некоторые (не обязательно все) вершины соединены линиями.
Эти линии называются рёбрами графа.

Слайд #6

Цепи и циклы

Слайд #7

Предположим, что в некотором графе можно по рёбрам «пройти» из вершины А в вершину В, то есть существует последовательность рёбер, соединяющих вершины А и В.
Такую последовательность называют путём из вершины А в вершину В.

Слайд #8

Путь между двумя вершинами последовательность рёбер, которая
их соединяет.
В графе, показанном на рисунке 28,
есть несколько путей из вершины А в вершину В.

Слайд #9

Например, есть путь, состоящий из рёбер АС и СВ.
Этот путь можно обозначить тремя буквами — АСВ.
Есть более длинный путь АDFЕВ.
Можно придумать более сложный путь, который заставит нас немного «покружить», — АDСАDСВ.

Слайд #10

В путях АСВ и АDFЕВ вершины не повторяются.
Такие пути называют простыми путями или цепями.
Цепь (простой путь) — это путь в графе из одной вершины в другую, в котором вершины и рёбра не повторяются.
Если граф состоит из одной-единственной цепи, то такой граф также называют цепью.
Граф без рёбер, состоящий из единственной вершины, также считают цепью.

Слайд #11

Путь АDСАDСВ идёт «по кругу», проходя дважды через вершины
А, D и С.
Путь, не являющийся простым.

Слайд #12

Иногда возникает необходимость выйти из вершины и вернуться в неё же.
Такие возвращающиеся в начальную точку пути называют циклами.
Цикл в графе — это замкнутый путь, у которого начало и конец в одной вершине, а рёбра и промежуточные вершины не повторяются.

Слайд #13

Простейший цикл — петля, которая состоит из одной вершины и одного ребра (см. рис. 25).

Слайд #14

Начальной вершиной цикла можно считать любую вершину.

Граф на рисунке имеет цикл АDСА.
Этот же цикл можно обозначить DСАD, или САDС, или просто АDС, как мы обычно обозначаем треугольники в геометрии.
Если граф состоит из одного-единственного цикла, то такой граф также называют циклом.

Слайд #15

Связные графы

Слайд #16

Граф называется связным, если две любые вершины в этом графе соединены путём.
На рисунке 29 показаны два графа — слева связный, а справа — несвязный, который можно представить как два отдельных связных графа.

Слайд #17

Вопросы:
1. Своими словами объясните, что такое путь в графе.
2. Объясните, что такое цепь.
3. Может ли в цепи рёбер быть больше, чем вершин?
4. Объясните, что такое цикл.
5. Может ли в цикле рёбер быть меньше, чем вершин?
6. Какой граф называют связным?