Теория графов. Маршруты, пути, цепи, циклы

1.

Теория графов
Маршруты, пути, цепи, циклы.

2.

Н-граф
Пусть G – неориентированный граф.
Маршрутом
в
G
называется
такая
последовательность ребер (a1, a2,... an), что каждые
соседние два ребра ai и ai+1 имеют общую
инцидентную вершину.
Одно и то же ребро может встречаться в маршруте
несколько раз.

3.

Н-граф. Маршруты, цепи, циклы
Вершина X1, инцидентная ребру a1, но не
инцидентная ребру a2, называется началом
маршрута, а вершина Xn, инцидентная ребру an,
но не инцидентная ребру an–1, называется концом
маршрута.
Маршрут, в котором начало и конец совпадают,
называется циклическим.

4.

Н-граф. Маршруты, цепи, циклы
Длиной маршрута называется число ребер,
входящих в маршрут, причем каждое ребро
считается столько раз, сколько оно входит в данный
маршрут.
Маршрут, в котором все ребра разные, называется
цепью.
Цепь, не пересекающая себя, т.е. не содержащая
повторяющихся вершин, называется простой цепью.
Циклический маршрут называется циклом, если он
не содержит повторяющихся ребер.
Цикл, не содержащий повторяющихся вершин,
называется простым циклом.

5.

Н-граф. Маршруты, цепи, циклы
Маршрут
Циклический маршрут
(Начало и конец совпадают)
Цепь
Все ребра разные
Простая цепь
Все вершины разные
Цикл
Все ребра разные
Простой цикл
Все вершины разные

6.

Н-граф. Связность
Неориентированный граф называется связным,
если между любыми его вершинами есть маршрут.
Две вершины называются связанными, если между
ними существует маршрут.

7.

Н-граф. Связность

8.

Н-граф. Связность.
Ребро связного графа G называется мостом, если
после его удаления граф G станет несвязным и
распадется на два связных графа.

9.

Н-граф. Метрические
характеристики
Расстоянием между двумя вершинами d(v1,v2)
называется минимальная длина из всех возможных
маршрутов между этими вершинами при условии,
что существует хотя бы один такой маршрут.
Матрица D=(dij), в которой dij=d(vi,vj), называется
матрицей расстояний.
D

10.

Н-граф. Метрические
характеристики
Для фиксированной вершины u максимальное из
расстояний от этой вершины до любой другой
вершины графа называется эксцентриситетом
вершины u.
e(u)=max d(u,v)
v VG

11.

Н-граф. Метрические
характеристики
Максимальный среди всех эксцентриситетов
вершин называется диаметром графа G и
обозначается через d(G).
d(G) =max e(u)
v VG
Вершина u
e(u)=d(G).
называется
периферийной,
если

12.

Н-граф. Метрические
характеристики
Минимальный из эксцентриситетов вершин связного
графа называется его радиусом и обозначается
через r(G):
r(G) =min e(u)
v VG
Вершина v называется центральной, если e(v)=r(G).

13.

Н-граф. Метрические
характеристики
Множество всех центральных
называется его центром.
вершин
графа
Граф может иметь единственную центральную
вершину или несколько центральных вершин.
Наконец, центр графа
множеством всех вершин.
может
совпадать
с

14.

Орграф. Пути, цепи, циклы

15.

Орграф. Пути, цепи, циклы
Путь называется контуром, если его начальная
вершина совпадает с конечной вершиной.
Контур называется циклом, если он не содержит
повторяющихся ребер.
Цикл, не содержащий повторяющихся
называется простым циклом.
вершин,

16.

Орграф. Пути, цепи, циклы.
Путь
Контур
(Начало и конец совпадают)
Цепь
Все ребра разные
Простая цепь
Все вершины разные
Цикл
Все ребра разные
Простой цикл
Все вершины разные

17.

ДЕРЕВЬЯ. ЛЕС. БИНАРНЫЕ
ДЕРЕВЬЯ

18.

Неориентированное дерево
Неориентированным деревом (или просто деревом)
называют конечный связный граф, не имеющий
циклов
Пример дерева
Граф не является деревом

19.

Ярус вершины
Для каждой пары вершин дерева — узлов — существует
единственный
маршрут,
поэтому
вершины
удобно
классифицировать по степени удаленности от корневой
вершины.
Расстояние до корневой вершины V0 называется ярусом s
вершины, s= d(V0,V).
Висячие вершины, за исключением корней, называются листьями.

20.

Лес
Лес – это граф, компоненты связности которого
являются деревьями.
Дерево
Лес

21.

Цикломатическое число графа
Пусть задан неориентированный граф G. Цикломатическим
числом графа называется число
v( G) = m(G) + c(G) - n(G),
где m(G) — число его ребер; c(G) — число связных компонент
графа; n(G) — число вершин.
Цикломатическое число дерева равно нулю.
Цикломатическое число леса равно сумме цикломатических
чисел составных связных компонент — деревьев и,
следовательно, тоже равно нулю.
Для остальных графов цикломатические числа —
положительные.

22.

Двоичное дерево
• Двоичное (бинарное) дерево – дерево, в котором
каждый родительский узел имеет не более двух
потомков.

23.

Остов связного графа
• Остовом (каркасом) связного графа G называется
любой его подграф, содержащий все вершины
графа G и являющийся деревом (говорят:
«покрывающим его деревом»).

24.

Ориентированное дерево
Ориентированный_граф G=(V,E) называется (ориентирова
нным) деревом, если
• в нем есть одна вершина в которую не входят ребра; она
называется корнем дерева;
• в каждую из остальных вершин входит ровно по одному
ребру; все вершины достижимы из корня.

25.

Ориентированное дерево
• примеры неориентированного дерева G1
и ориентированного дерева G2, которое получено из G1 с
помощью выбора вершины c в качестве корня и ориентации
всех ребер в направлении "от корня".

26.

Эйлеровы графы

27.

Эйлеровы графы
Теорема. Граф G является эйлеровым тогда и
только тогда, когда G — связный граф, имеющий
все четные вершины.

28.

Планарные графы
• Граф G называется планарным (плоским), если
существует изоморфный ему граф G', в
изображении которого на плоскости ребра
пересекаются только в вершинах. Иными
словами, у планарного графа никакие два ребра
не имеют общих точек, кроме общих вершин.

29.

Теорема Эйлера
Связный плоский граф с n вершинами и m ребрами
разбивает плоскость на r областей (включая
внешнюю), причем
n - m + r = 2.

30.

Гамильтонов граф