pdm_05
.pdf
Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Дискретная математика
|
|
курс лекций |
|
|
лекция 5 |
|
|
|
|
|
Элементы теории |
Кафедра |
графов |
|
«Проектирования и безопасности компьютерных систем» Гришенцев А. Ю. www.moveinfo.ru
Санкт-Петербург
2014 |
1 |
|
Практика применения графов
Структура программ
|
Структуры данных |
Картография |
и информации |
Электрическая и электронная схемотехника Социум
Вычислительные сети
2
Определение графа
Определение Граф – это некоторое множество вершин V = {v1, v2, …, vn} и некоторое множество рѐбер E = {e1, e2, …, em}, соединяющих пары различных вершин, причѐм одну пару вершин может соединить максимум одно ребро.
e |
↔ {v , v } |
v4 |
|
|
Вместо термина вершина (vertex) часто |
|
7 |
3 |
4 |
|
|
|
употребляют термин узел (node). |
|
|
|
e4 ↔ {v5, v4} |
|||
|
|
|
Вместо термина ребро (edge), |
|||
|
v3 |
|
|
|
|
|
e8 ↔ |
|
|
|
|
используют термины: дуга (arc), связь |
|
|
|
e5 ↔ |
v5 |
|
(link), ветвь (branch). |
|
↔ {v3, v2} |
|
|
|
|
|
|
e6 ↔ |
|
↔ {v1, v4} |
e3 ↔ {v5, v6} |
|||
|
|
|||||
|
↔ {v1, v3} |
e2 ↔ {v1, v6} |
|
|||
v2 |
|
|
|
|||
|
|
v1 |
|
|
v6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Кроме стандартного графа существуют: |
|
|
|
|
|
|
мультиграфы – допускающие кратные |
|
|
|
|
|
|
рѐбра и не допускающие петель; |
v8 |
|
|
|
e1 ↔ {v7, v6} |
псевдографы – допускающие кратные |
|
|
|
|
рѐбра и петли; |
|||
|
|
v7 |
|
|
||
|
|
|
|
|
орграфы – графы в которых множество |
|
|
рѐбра ориентированы т.е. образованны |
|
V = {v1, v2, v3, v4, v5, v6, v7, v8} |
упорядоченными двойками. |
|
|
|
|
E = {e1, e2, e3, e4, e5, e6, e7, e8} ↔ |
|
|
↔ {{v7, v6}, {v1, v6}, {v5, v6}, {v5, v4}, {v1, v4}, {v1, v3}, {v3, v4}, {v3, v2}} |
3 |
|
|
|
|
Определения
Теорема Граф, состоящий из n вершин, содержит рѐбер m не более m ≤ n(n -1)/2.
Доказательство Общее количество возможных пар вершин равно n2 из них n петель, а рѐбра между различными вершинами учитываются дважды, но граф не допускает кратные рѐбра, следовательно: m ≤ (n2 - n)/2 = n(n-1)/2.
Определение Если две вершины соединены общим ребром, то такие вершины называют смежными. Ребро соединяющее смежные вершины инцидентно (принадлежит) этим вершинам.
Определение Степень вершины v – это количество рѐбер, инцидентных вершине v, степень вершины v выражается числом, обозначается deg(v). Определение Подграф G2 – это подмножество рѐбер некоторого графа G1 (и связанных с ним вершин), которые сами образуют граф. Граф G1 по отношению к подграфу G2 называют надграфом.
Определение Полный граф – это такой граф у которого все вершины смежные.
G1 =(V1, E1) |
G =(V , E ) |
Смежные вершины в G2: |
|
|||
|
|
2 |
2 |
2 |
{2,3}, {0,3}, {0,4}. |
|
1 |
|
|
|
|
|
|
2 |
1 |
|
2 |
Степень вершин в G2: |
|
|
|
|
|
||||
|
надграф |
|
|
|
deg(0)=2; deg(1)=0; deg(2)=1; |
|
|
|
|
4 |
deg(3)=2; deg(4)=1. |
|
|
3 |
4 |
3 |
|
|
||
|
подграф |
|
|
|
Вершины степень которых |
|
|
|
|
|
|
равна единице называют |
4 |
|
0 |
|
|
0 |
висячими. |
|
|
|
|
|
|||
|
|
|
|
|
||
Ориентированный граф
Определение Ориентированный граф (орграф) есть такой граф G = (V,E), в
котором множество E рѐбер, образованно упорядоченными множествами пар вершин (vi, vj) V. 
0 
1
3 
2
Ориентированный
граф
E = {(0,2),(1,0), (1,2),(3,0),(3,2)}
0 
1
3 
2
Ориентированный
мультиграф
E = {(0,1),(0,2),(1,0), (1,2),(3,0),(3,2)}
0 
1
3 
2
Ориентированный
псевдограф
E = {(0,1),(0,2),(1,0), (1,2),(2,2),(3,0),(3,2)}
Вершина из которой выходит ребро называется истоком, вершина в которую ребро входит - стоком.
5
Изоморфность графов
Определение Графы G1 = (V1, E1) и G2 = (V2, E2) изоморфны, если существует взаимно однозначное соответствие φ: V1 → V2, сохраняющее отношение смежности вершин т.е. если (vi, vj) E1 ↔ (φ (vi), φ (vj)) E2.
Пример изоморфные графы
5 |
6 |
|
7 |
|
|
|
1 |
|
2 |
|
|
|
|
|
φ(v) = 7 – v |
|
|
|
|
|
|
|
|
|
3 |
4 |
|
(vi, vj) E1 ↔ |
|
|
|
↔ (φ (vi), φ (vj)) |
E2 |
||
|
|
|
|||
0
G1=(V1, E1)
V1 = {0,1,2,3,4,5,6,7}
E1 = {{0,2}, {0,3}, {0,4}, {1,2}, {2,3}, {3,4}, {5,6}, {6,7}}
4 5
6
2
3 7
1 |
0 |
G2=(V2, E2)
V2 = φ(V1) = {7,6,5,4,3,2,1,0} E1 = {{7,5}, {7,4}, {7,3}, {6,5}, {5,4}, {4,3}, {2,1}, {1,0}}
Изоморфизм является общим понятием обозначающим |
|
подобие, равенство. |
6 |
Задание графов
Граф возможно задать при помощи:
-списка (перечисления элементов множеств) вершин и рѐбер; - таблично или в виде матриц; -графически изобразив граф в виде геометрической фигуры.
В программах графы задают в виде массивов, массивов структур, структур или классов.
Не существует оптимального способа задания графа «на все случаи жизни», поэтому выбирают наиболее подходящий способ задания графа, при этом учитывая особенности обработки данных и специфику самих данных для которых используются графы. Сам по себе выбор способа задания графа может быть нетривиальной задачей.
Графы в которых имеет значение геометрическая форма, масштаб называют евклидовыми графами. Такие графы применяют в картографии, в электротехнике, например, при моделировании электрических или тепловых параметров токоведущих элементов печатной платы и др.
7
|
|
|
|
|
Матрица смежности |
|||||
Матрица смежности – один из способов задания графа, для графа с конечным |
||||||||||
числом вершин (p) размеры матрицы смежности p x p. |
||||||||||
Матрица смежности : |
|
|
|
|
||||||
a11 |
a12 ... |
|
a1 p |
|
|
|
|
|||
a21 |
a22 ... |
|
a2 p |
|
|
aij =1, если i смежная с j |
||||
A = ... ... ... |
|
... , |
где |
aij =0, если i не смежная с j |
||||||
ap1 |
ap 2 ... |
|
app |
|
|
|
На практике часто применяют |
|||
|
|
|
|
|
|
|
|
|
||
G = (V, E) |
|
|
|
вершины |
|
расширенные виды матрицы |
||||
1 |
|
в |
|
0 |
1 |
2 |
3 |
4 |
смежности. Такие матрицы могут |
|
|
|
|
|
|
|
|
||||
2 |
0 |
0 |
0 |
1 |
1 |
1 |
содержать кроме бинарного |
|||
|
||||||||||
|
|
е |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
|
|
р |
признака смежности, например, |
|||||||
3 |
4 |
ш |
2 |
1 |
1 |
0 |
1 |
0 |
значение веса и ориентацию ребра |
|
|
|
и |
3 |
1 |
0 |
1 |
0 |
1 |
или иную информацию. При такой |
|
|
|
н |
||||||||
|
|
ы 4 |
1 |
0 |
0 |
1 |
0 |
дополненной трактовке, матрицы |
||
|
|
|
|
|
|
|
|
|
||
|
0 |
Матрица смежности |
смежности возможно использовать |
|||||||
|
задана в виде таблицы |
для задания: мульти-, псевдо- и |
||||||||
|
|
|||||||||
|
|
|
|
|
|
|
|
|
оргафов. |
|
|
|
|
|
|
|
|
|
|
8 |
|
Матрица инцидентности
Матрица инцидентности – для графа с (p) вершинами и (q) рѐбрами есть матрица размера p x q.
Матрица инцидентности :
a11 a12 ... a1q
|
a21 |
a22 |
|
B = ... ... |
|||
|
ap1 |
ap 2 |
|
G = (V, E) |
|
|
|
1 |
0 |
|
|
|
|
2 |
|
|
1 |
|
|
|
|
|
|
3 |
2 |
4 |
|
|
3 |
||
|
|
|
|
4
5
0
... |
|
a2q |
, где |
aij =1, если vi ej |
|||||||
... |
|
... |
aij =0, если |
иначе |
|||||||
... |
|
apq |
|
|
|
|
|
|
|
|
|
|
|
|
|
рёбра |
|
|
|
|
|
||
в |
|
0 |
1 |
2 |
3 |
|
4 |
5 |
|
|
Расширение множества |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
|
|
||
|
|
возможных значений матрицы |
|||||||||
е |
|
|
|
|
|
|
|
|
|
||
1 |
1 |
0 |
0 |
0 |
|
0 |
0 |
|
|||
р |
|
|
|
инцидентности позволяет |
|||||||
|
|
|
|
|
|
|
|
|
|
||
ш 2 |
1 |
1 |
0 |
1 |
|
0 |
0 |
|
задавать при помощи матрицы |
||
и |
3 |
0 |
1 |
1 |
0 |
|
0 |
1 |
|
||
|
|
|
|
||||||||
н |
|
|
|
инцидентности: мульти-, |
|||||||
|
|
|
|
|
|
|
|
|
|
||
ы 4 |
0 |
0 |
1 |
0 |
|
1 |
0 |
|
|
псевдо- и оргафы. |
|
Матрица инцидентности |
|
||||||||||
|
|
||||||||||
задана в виде таблицы |
|
|
|||||||||
9
Операции над графами
Для графа G = (V,E)
Удаление вершины v из G даѐт подграф графа G без вершины v и
инцидентных ей рѐбер G – v = (V – {v}, E – {e0,…en}), (e0,…en) v.
Удаление ребра e из G даѐт подграф графа G без ребра e G – e = (V, E – e). Добавление ребра e = (u,v) к графу G содержащему вершины u и v даѐт надграф G + e = (V, E {e}).
Добавление вершины v к графу G даѐт надграф G + v =(V {v}, E).
1 2
3 
4
0
1 2
3 
4
0
1 2
0 
3 
4
1 2
{1,2} 3 4
0
1 |
|
2 |
1 |
|
2 |
|
|
|
|||
|
|
|
|
||
|
|
|
{2,4} |
|
|
|
|
|
|
|
|
3 |
4 |
|
3 |
4 |
|
1 |
|
2 |
1 |
|
2 |
|
|
|
|||
|
|
|
|
||
|
|
|
{5} |
|
|
|
|
|
|
5 |
|
3 |
4 |
|
3 |
4 |
|
|
|
В специальных приложениях теории графов вводят дополнительные операции над графами.
10