Основы теории графов
Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Лекции по Дискретной математике
Лекция 4
Основы теории графов
Конструкция графа
Бинарное отношение не
дискретном множестве
V={v1, v2, …, vk} – вершины (узлы) графа
EVV={(vi,vj)| vi, vjV} – ребра (дуги) графа
vi – начало ребра, vj – конец ребра
G=
Способы задания графов
n Списки множеств
G= |V={v1, v2,…}, E={e1, e2, …}
n Списки ребер
V
E
v1v2 e1
v1v3 e2
…
n Диаграмма
n Матрицы соответствий
Пример графа: списки и диаграмма
G=
n V={a, b, c, d, e} E={1, 2, 3, 4, 5, 6, 7}
n V ab
E 1
ac
2
dc
3
1
a
ee
4
ba
5
bd
6
b
5
2
c
6
7
3
d
e
4
ce
7
Пример орграфа
G=
n V={a, b, c, d, e} E={1, 2, 3, 4, 5, 6, 7}
n V (a,b) (a,c) (d,c) (e,e) (b,a) (b,d) (c,e)
E
1
2
3
5
a
4
5
6
b
1
2
c
6
7
3
d
e
4
7
Элементы множества ребер
n Дуга – направленное ребро
(vi, vj)(vj, vi)
Граф, все ребра которого направлены, называется
ориентированным (орграф)
n Петля – начало и конец ребра совпадают
ei=(vj, vj)
Граф с петлей называется псевдограф
n Кратные ребра образуются одной парой вершин
ei=(vk, vl), ej=(vk, vl)
Граф с кратными ребрами называется мультиграф
Примеры диаграмм графов
Виды графов
n Конечный граф, если |V|=n
n Безреберный граф (груда), если |E|=0
n Полный граф, если E - полное отношение
n Двудольный граф, если V=V1V2, причем
V1V2= и e=(vi, vj)| viV1, vjV2
Образцы видов графов
а
б
б
г
в
а
г
в
Соответствия в графе
n Смежность (граф)
Smv VV
Sme EE
n Инци(н)дентность
In1 VE
In2 EV
Матрицы соответствий графа
n Матрица смежности вершин
M [i, j ] =
1, если vi Sm v j
0, если vi Sm v j
n Матрица смежности ребер
M [i, j ] =
1, если ei Sm e j
0, если ei Sm e j
n Матрица инцидентности
- 1, если vi конец ребра е j
M [i, j ] = 1, если vi начало ребра е j
0, если vi In е j
Пример графа: смежность вершин
Sm a
b
c
d
e
a
1
1
b
1
1
c
1
1
1
d
1
1
e
1
1
1
a
b
5
2
c
6
7
3
d
e
4
Пример графа: смежность рёбер
Sm 1
2
3
4
5
6
7
1
1
1
1
2
1
1
1
1
3
1
1
1
4
1
5
1
1
1
6
1
1
1
7
1
1
1
1
b
5
2
a
c
6
3
7
d
e 4
Пример графа: инцидентность
In
1
2
3
4
5
6
7
a
1
1
1
b
1
1
1
c
1
1
1
d
1
1
e
2
1
1
b
5
2
a
c
6
3
7
d
e 4
Пример орграфа: соответствия
G= V={a, b, c, d, e} E={1, 2, 3, 4, 5, 6, 7}
V (a,b) (a,c) (d,c) (e,e) (b,a) (b,d) (c,e)
E 1
2
3
4
5
6
7
In
1
2
3
4
5
6
7
Sm
a
b
c
d
e
a
1
1
-1 0
a
1
1
b
-1 0
1
1
c
-1 -1 0
1
b
1
1
d
1
-1 0
c
1
e
2
d
1
e
1
-1
Вершины графа
n Вершина, инцидентная только одному ребру,
называется висячей.
n Вершина, имеющая только петли называется
изолированной, а не имеющая инцидентных
.
ребер – голая.
n Каждому неориентированному графу можно
поставить в соответствие орграф с кратными
противоположно направленными ребрами. Такое
соответствие называется каноническим.
Степень вершины графа
n Степенью вершины (s(v)) называется количество
рёбер, инцидентных данной вершине
n Порядок, заданный на множестве степеней
вершин графа определяет вектор степеней.
n Граф, у которого степени всех вершин равны k,
называется однородным степени k (k-связным).
n У орграфа различают степень входа (s-(v)) и
степень выхода (s+(v)).
Если s-(v)=0, то вершина – источник,
если s+(v) =0, то вершина – сток.
n Сумма степеней вершин всегда четна. Если в
графе есть вершины с нечетной степенью, то
количество таких вершин четно.
Определение степени вершины
3
c
b
4
3
2
a
d
1
сток
c
b
источник
2
a
4
d
1
S(1)=2
S(2)=1
S(3)=3
S(4)=2
S-(1)=2
S-(2)=1
S-(3)=1
S-(4)=0
S=(1, 2, 2, 3)
S- =(0, 1, 1, 2)
S+ =(0, 0, 2, 2)
сток
S+(1)=0
S+(2)=0
S+(3)=2
S+(4)=2
Изоморфизм графов
n Графы, которые отличаются только нумерацией
вершин, называются изоморфными.
n У изоморфных графов матрицы совпадают при
применении к ним элементарных операций.
n Числовая характеристика, сохраняющаяся при
изоморфизме, называется инвариат.
n Степень графа является инвариантом.
Части графа
Граф G’=(V’,E’) – часть графа G=(V,E), если
V’ V , E’ E.
n Если V’ V , E’ E, то это подграф.
n Если V’= V , E’ E, то это суграф.
n Граф V’= V, E’=Е \ I, то это
дополнительный граф.
Части графа
3
3
c
b
4
d
1
2
a
b
4
1
Дополнительный граф
3
c
b
d
4
Суграф
3
Подграф
2
a
2
у
1
4
х
1
Операции с графами
Операции с графами
Операции с графом
3
G1
G2
b
c
b
3
2
a
1
4
4
G1 G2
3
a
4
d
1
G1 G2
b
c
b
3
2
d
1
4
1
Операции с графом
G
3
G+v
2
a
3
c
b
1
1
4
G+v+e
3
c
b
4
2
a
5
2
a
3
2
a
c
b
c
b
1
4
5
4
1
Операции с графом
G
3
G-v
2
a
3
c
b
b
1
4
4
G-e
3
2
c
b
4
2
a
32
c
b
1
4
1
