Алгоритмы и структуры данных (графы). Основные определения. Простейшие свойства графов

1.

http://ivt.0861.ru
Алгоритмы и структуры данных (графы)
Лекция 1
Графы. Основные определения. Простейшие
свойства графов. Пути и цепи в графах. Связность,
k-связность. Деревья, корневые деревья.
Остовные деревья
ст. препод. каф. ПОВТиАС
Голубничий Артем Александрович
[email protected]
Абакан, 2022

2.

Определение графа
(Неориентированным) графом G называется пара (V,E), где V —
непустое конечное множество вершин; E — конечное множество
ребер, причем каждому ребру e ∈ E сопоставлена неупорядоченная
пара вершин, т.е. e = (v,w), где v,w ∈ V.
Обозначения:
V(G) — множество вершин графа G,
E(G) — множество ребер графа G
2

3.

Пример: сеть
Сеть — p узлов c соединениями между некоторыми из них.
3

4.

Петли и кратные ребра
Ребро e = (v,v), где v ∈ V, называется петлей.
Ребра e1 = (v,w) и e2 = (v,w), где v,w ∈ V и e1 ̸= e2, называются
кратными ребрами.
Граф, в котором допускаются и петли, и кратные ребра иногда
называется псевдографом.
Граф без петель, но, возможно, с кратными ребрами называется
мультиграфом.
Граф без петель и кратных ребер называется простым, или
обыкновенным графом.
Мы будем, как правило, рассматривать простые графы, т.е.
графы без петель и кратных ребер. Дальнейшие определения
будут вводится, в основном, только для таких графов.
4

5.

Изоморфизм графов
Два графа (без петель и кратных ребер) G1 = (V1,E1) и G2 = (V2,E2)
называются изоморфными, если найдется такое взаимно
однозначное отображение φ : V1 → V2, что для любой пары
вершин v , w ∈ V1 верно соотношение:
(v,w) ∈ E1 тогда и только тогда, когда (φ(v),φ(w)) ∈ E2.
5

6.

Смежность
Говорят, что ребро e = (v,w) соединяет вершины v и w, или
исходит из вершины v (и из вершины w), или вершины v и w
инцидентны ребру e.
При этом вершины v и w называются концами ребра e, или
смежными (соседними) по ребру e.
6

7.

Полные графы
Полным графом называется граф, в котором любые две
различные вершины смежны;
Kn – полный граф с n вершинами, K3 – треугольник.
7

8.

Двудольные графы
Двудольным графом называется граф, в котором вершины
можно разбить на две части (доли) так, что смежны только
вершины из разных долей.
Полный двудольный граф – двудольный граф, в котором
смежны любые две вершины из разных долей;
Km,n – полный двудольный граф с долями из m и n вершин.
8

9.

Степень вершины
Степенью dG (v ) вершины v ∈ V в графе (без петель и кратных
ребер) G = (V , E ) называется число исходящих из нее ребер.
Если dG (v ) = 0, то вершина v называется изолированной в
графе G , если dG (v ) = 1, то вершина v называется висячей, или
концевой в графе G.
Обозначения: δ(G) = min dG(v) и ∆(G) = max dG(v) –
v∈V(G)
v∈V(G)
соответственно, наибольшая и наименьшая степени вершин в
графе G.
9

10.

Формула Эйлера для степеней вершин
10

11.

Изображение графов
11

12.

Пути в графах
12

13.

Циклы в графах
13

14.

Свойства путей и цепей
14

15.

Свойства путей и цепей
15

16.

Свойства путей и цепей
16

17.

Свойства путей и цепей
17

18.

Подграфы
18

19.

Связность
19

20.

Пример: связная сеть
20

21.

Свойства связных графов
21

22.

Свойства связных графов
22

23.

Свойства связных графов
23

24.

Число компонент связности
24

25.

Число компонент связности
25

26.

k-связность
26

27.

Деревья
27

28.

Свойства деревьев
28

29.

Свойства деревьев
29

30.

Корневые деревья
30

31.

Поддеревья в корневом дереве
31

32.

Корневые деревья
32

33.

Остовные деревья
33

34.

Остовные деревья
34

35.

Задача о неизбыточной сети
35

36.

Последовательная нумерация вершин
36