Цель:

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

Цепь и цикл. Путь в графе.

Представление о связанности графа

• путь,
• цепь,
• цикл,
• связанный граф

ПОВТОРЕНИЕ

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

Графом G(V, E) называется совокупность двух множеств

множества V (множества вершин) и

множества E (множество рёбер)

вершина

ребро

Как записать название данного графа

в виде G(V, E) ?

а1

а2

а5

а4

а3

G(5;6)

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

Ответ:

Путь (или цепь) - конечная последовательность вершин, в которой каждая вершина (кроме последней) соединена ребром со следующей вершиной.

​

Путь АВ

Путь АК

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?��

Цепь – это путь в графе, у которого не повторяются вершины.

Цепь A – C – D – B или AC – CD - DB

Цикл – путь, у которого совпадают начало и конец, а промежуточные рёбра и вершины не повторяются.

Цикл A – B - C – A или A - B - C – А

G, H, E, B, A - ВИСЯЧИЕ ВЕРШИНЫ

Деревом называется связный граф, у которого нет циклов

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

Формула для нахождения рёбер в полном

графе, у которого n вершин:

5 школьных команд по волейболу сыграли серию игр. Каждая команда провела с другими командами по одному матчу. Сколько всего матчей было сыграно?

Устно ответьте на вопросы по рисунку:

В

A

C

D

F

E

Есть ли в графе путь из вершины А в вершину С?

Есть ли в графе путь из вершины В в вершину F ?

Связанный этот граф или несвязанный?

C

F

B

A

D

E

Назовите три цепи, которые ведут из

вершины А в вершину В

C

F

B

A

D

E

Назовите три разных цикла

Какие графы являются

цепями

циклами

несвязными графами

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Эйлеровы пути и эйлеровы графы

Эйлеров граф – это граф,

в котором есть эйлеров путь.

Эйлеров путь – это путь, который

проходит ровно один раз по

каждому ребру.

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

Д/з. Задача �Развозчик пиццы из города V0 должен доставить товар в 7 городов, которые соединены дорогами (схема на графе) и вернуться к себе в город. Начало его пути обозначено красной ломаной, продолжите его маршрут красным цветом так, чтобы он являлся циклом.

Подсказка:

нельзя проходить по тем же дорогам, можно проходить через те же вершины, вернуться нужно в V0, направление движения покажите стрелками.