Презентация урока вероятности и статистики в 7 классе по теме "Пути в графе. Цепь и цикл"

Тема урока: Пути в графе. Цепь и цикл. Вероятность и статистика 7 класс М С В А К

Повторение 1. Что называется графом? 2. Что называется вершиной графа? 3. Что называется смежными вершинами? 4. Что называется ребром графа? 5. Что называется смежными ребрами? 6. Что называется изолированной вершиной? 7. Как понять, что два графа одинаковы?

Основные понятия Путем в графе от вершины А до вершины F называется последовательность ребер графа и его вершин, такие, что каждые два последовательных ребра имеют общую вершину, и никакое ребро не встречается более одного раза. А называется началом пути, F – концом. Вершины повторяться могут. Например, ABCDECF и ABCEDCF – пути от точки А к точке F. А B C D E F G Путь

Цепь и цикл Если в пути не повторяются вершины, то такой путь называется цепью (простым путем). Циклом в графе называется путь, у которого начало и конец совпадают. Простым циклом в графе называется цепь, у которой начало и конец совпадают. Например, ABCF – цепь от точки А к точке F; CGDCEBC – цикл; EBCDE – простой цикл.

Путь, цепь и цикл То есть отличие цикла от простого цикла в том, что цикл – это путь, в котором вершины могут повторяться, а простой цикл – это путь, в котором вершины не повторяются. Составим схему для упрощения запоминания новых терминов: Вершины не повторяются Начало и конец совпадают Начало и конец совпадают Вершины не повторяются

Цепь и цикл Если граф состоит из единственной цепи и только из нее, то этот граф тоже называется цепью. Если граф состоит из единственной вершины и не содержит ребер, то этот граф тоже называется цепью. Если граф состоит из единственного цикла и только из него, то этот граф тоже называется циклом.

Задание 1. Назовите 3 пути (не простых) графа, изображенного на рисунке. M K L J H I Например, I M L K J L H, L M I L K, J L I M L

Задание 2. Назовите 3 любых цепи графа, изображенного на рисунке. Например, DFA, BDE, CDFA

Задание 3. Назовите 3 цикла (не простых) графа, изображенного на рисунке. Например, H I L K J L H, L M K L J O I L, H I L M K L H

Задание 4. Назовите 3 любых простых цикла графа, изображенного на рисунке. Например, E G F E, E B F E, E B A C E

Среди графов, изображенных на рисунке, найдите те, которые являются: Задание 5. а) цепью; б) простым циклом. Ответ: а) 1, 2; б) 3; 5.

Задание 6. На рисунке изображен граф. Найдите путь из вершины А в вершину В. Например, ACDEB

Задание 7. На рисунке изображен граф. Найдите цепь из вершины С в вершину В. Например, CADB

Задание 8. На рисунке изображен граф. Найдите простой цикл, содержащий в себе точку А. Например, ADEBA