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

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

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

Цель

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

ПОВТОРЕНИЕ

Геометрическое представление графа — это схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых

Графом G(V, E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества E двухэлементных подмножеств множества V (E — множество рѐбер)

вершина

ребро

дуга

Как записать название данного графа в виде G(V, E) ?

а1

а2

а5

а4

а3

G(5;6)

а1

V(а1, а2, а3, а4, а5)

МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ. ОПРЕДЕЛЕНИЯ

Маршрутом в графе называется последовательность ребер, такая, что два соседних ребра имеют общую вершину (движение по рёбрам, без разрывов)

Маршрут в котором все ребра различны, называется цепью (путь)

Цепь называется простой, если и все вершины в ней различны

Замкнутая простая цепь называется циклом

МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ. Внешний вид

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

Маршрут? Цепь ? Цикл?

V0-V2-V4-V3-V6-V7

Цепь, в которой все вершины различны, кроме, может быть, ее концов, называется простой.



Маршрут

Цепь (простая)

Маршрут? Цепь ? Цикл?

V0-V1-V2-V6-V3-V0

Маршрут

Цепь

Цикл

Задание. Ответьте на вопросы

1

2

---

3

4

5

6) 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 и решить задачу ниже. Задача. Перенесите граф в тетрадь, запишите все возможные пути из А в К. Например: АГВК;… В ответ запишите количество всех возможных путей.

---