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

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

Вершины не повторяются Начало и конец совпадают Начало и конец совпадают Вершины не повторяются Повторение Путь, цепь и цикл

Повторение Определите, является ли верным утверждение 1.Степенью графа называется количество ребер, исходящих из его вершин. 2. Вершина называется четной, если из нее выходит четное количество ребер. 3. Вершина называется нечетной, если из нее выходит нечетное количество ребер. 4. Сумма степеней всех вершин графа равна количеству ребер. 5. Сумма степеней вершин графа всегда является нечетным числом. 6. Число нечетных вершин графа всегда четно. 7. Путем в графе от вершины А до вершины В называется последовательность ребер графа и его вершин, такие, что каждые два последовательных ребра имеют общую вершину, и никакое ребро не встречается более одного раза. А называется началом пути, В – концом. 8. Если в пути не повторяются вершины, то такой путь называется цепью (простым путем).

9. Если граф состоит из единственной цепи и только из нее, то этот граф тоже называется цепью. 10 . Если граф состоит из единственной вершины и не содержит ребер, то этот граф тоже называется цепью. 11. Циклом в графе называется цепь, у которой начало и конец совпадают. 12. Простым циклом в графе называется цепь, у которой начало и конец совпадают. 13. Если граф состоит из единственного цикла и только из него, то этот граф тоже называется циклом.

Связность графа Граф называется связным, если для любой его вершины найдется путь, связывающий ее с любой другой вершиной этого графа. Количество ребер в пути называется длиной этого пути.

Ориентированный граф Ориентированный граф (или орграф) – это граф, ребра которого имеют направления. Ребра такого графа называются дугами. Если есть некоторая дуга AB, то говорят, что дуга АВ выходит из вершины А и входит в вершину В. На чертежах направление дуги обозначается стрелкой к вершине В. Например, 21 – дуга графа, а вот 12 не является его дугой. Дуга 21 выходит из вершины 2 и входит в вершину 1.

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

Задание 2. Перечислите ребра графа изображенного на рисунке. Определите исходящие и входящие степени каждой вершины графа. Входящие вершины: вх(1) = 1, вх(2)=0, вх(3) = 2, вх(4) = 2, вх(5) = 0. Ответ: Рёбра графа: 23, 41, 13, 34, 54. Исходящие вершины: Исх(1) = 1, исх(2) = 1, исх(3) = 1, исх(4) = 1, исх(5) = 1.

На рисунке изображен граф. Какова наибольшая длина его простого цикла? Задание 3. Ответ: 3 (EGFE)

Задание 4. На рисунке изображен граф. Какова наибольшая длина его простого цикла? Ответ: 6

Задание 5. На рисунке изображен граф. Какова наибольшая длина его цикла? Ответ: 7

Задание 6. На рисунке изображена сетка, по которой бегают муравьи. Сколько есть кратчайших путей, чтобы добраться из пункта К в пункт Q? Ответ: 3 (KMRSPQ, KMNSPQ, KMNOPQ)

Задание 7. Будки Бобика, Шарика, Дружка и Тузика стоят по кругу. Известно, что будка овчарки (не Бобика и не Шарика) находится между будкой лайки и будкой Тузика. Будка хаски находится между будкой таксы и будкой Шарика. Какая порода у каждой из собак?                 Ответ: Дружок-овчарка; Шарик-лайка; Бобик-хаски; Тузик-такса