Файл: Урок 24 Тема. Представление о связности графа. Обход графа (Эйлеров путь).pptx

Вероятность и статистика Урок №24

Тема. Представление о связности графа. Обход графа (Эйлеров путь)

Цель

• Познакомиться с понятиями: «маршрут», «путь», «цепь», «цикл», «связанный граф».
• Научиться определять характер последовательности вершин.
• Применять данный теоретический материал для решения задач.

ПОВТОРЕНИЕГеометрическое представление графа — это схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривыхГрафом G(V, E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества E двухэлементных подмножеств множества V (E — множество рѐбер)вершинаребродугаКак записать название данного графа в виде G(V, E) ?а1а2а5а4а3G(5;6)а1V(а1, а2, а3, а4, а5)МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ. ОПРЕДЕЛЕНИЯМаршрутом в графе называется последовательность ребер, такая, что два соседних ребра имеют общую вершину (движение по рёбрам, без разрывов)Маршрут в котором все ребра различны, называется цепью (путь)Цепь называется простой, если и все вершины в ней различныЗамкнутая простая цепь называется цикломМАРШРУТЫ, ЦЕПИ, ЦИКЛЫ. Внешний вид

• Почему пунктиром показан «не путь»?
• Как ещё можно назвать маршрут?
• Является ли маршрут, обозначенный красной ломаной, простым?
• Почему этот маршрут не является циклом?
• Является ли цикл, обозначенный голубым цветом, простым?
• Является ли цикл маршрутом, цепью, путём?

Маршрут? Цепь ? Цикл? V0-V2-V4-V3-V6-V7Цепь, в которой все вершины различны, кроме, может быть, ее концов, называется простой. Маршрут Цепь (простая) Маршрут? Цепь ? Цикл? V0-V1-V2-V6-V3-V0МаршрутЦепь ЦиклЗадание. Ответьте на вопросы12

---

3456) 2,3,4,5,1,2- цикл?1) 2,3,5,4 – маршрут? НЕТ2) 2,3,4,5,1,4,3- маршрут?ДАа путь?НЕТ3) 3,1,4,5,1,2- путь?ДАон простой?НЕТ4) 2,3,1,4,3,1,2 – цикл?НЕТмаршрут? ДА5) 2,3,1,4,5,1,2- цикл?ДАон простой?НЕТДАон простой?ДАРАССТОЯНИЯ И МЕТРИЧЕСКИЕ ХАРАКТЕРИСТИКИДлиной маршрута называется количество ребер в немРасстоянием между вершинами u, v (обозначается s(u,v)) называется наименьшая длина цепи < u,v >s(a,d)=2, кратчайшая цепь, например, abd.Определите расстояние s(a, f)СВЯЗНОСТЬ ГРАФОВДве вершины в графе связны, если существует соединяющая их цепь (отличаем от смежных!)Граф называется связным, если для любых двух его вершин имеется путь, соединяющий эти вершины (из любой вершины можно попасть в любую)

• Что такое маршрут? В чем измеряется длина маршрута?
• Что такое цепь? Простая цепь?
• Что такое путь? Чем он отличается от цепи?
• Что такое цикл? Простой цикл?

ИТОГДомашнее задание. Изучить материал презентации, ответить на вопросы слайда 11 и решить задачу ниже. Задача. Перенесите граф в тетрадь, запишите все возможные пути из А в К. Например: АГВК;… В ответ запишите количество всех возможных путей.

---