19. Основные понятия и определения теории графов.
Граф – совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Пара G=(V,E), где V – вершины, а E – семейство пар ei=(vi1,vi2) принадлежит V, называемых ребрами. V(G)={1,2,3,4}, E(G)={(1,2), (1,3), (2,3),(3,4)}.
Неориентированный граф – граф, у ребер которого нет направления. Если есть путь из вершины v в w, то есть путь из w в v.
Пример неориентированного графа:
Ориентированный граф (орграф) – граф, ребрам которого присвоено направление. Направленные ребра именуются также дугами, а иногда просто ребрами. Если есть путь из вершины v в w, то не факт, что есть путь из w в v.
Пример ориентированного графа:
Смешанный граф – граф, в котором некоторые ребра могут быть ориентированными, а некоторые неориентированными. Ориентированный и неориентированный графы являются частными случаями смешанного.
Мультиграф – граф, где между двумя заданными вершинами может быть несколько дуг.
Пример мультиграфа:
Псевдограф – граф, в котором существует петля, т.е. ребро, соединяющее вершину саму с собой.
Пример псевдографа:
Подграф – какая-либо часть графа.
Если мощность множества V равна n, то число n называется порядком графа.
Если мощность множества V равна n, а мощность множества E равна m, то граф называется (n,m) – графом.
Две вершины графа называются смежными, если они соединены ребром.
Два ребра называются смежными, если они выходят из одной вершины.
Ребро и вершина называются смежными, если они выходят из одной вершины.
Ребро и вершина называется инцидентными, если данная вершина является концом данного ребра.
Граф называется пустым, если в нем нет ребер.
Граф называется полным, если любые две вершины соединены ребром.
Число ребер в полном графе порядка n равно n*(n-1)/2.
Из каждой вершины в полном графе выходит (n-1) ребро.
20. Способы хранения графов в памяти эвм.
1. матрица смежности.
Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).
|
1 |
2 |
3 |
4 |
5 |
1 |
0 |
1 |
1 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
0 |
3 |
1 |
0 |
0 |
1 |
0 |
4 |
0 |
1 |
1 |
0 |
1 |
5 |
1 |
0 |
0 |
1 |
0 |
Этот же граф, только изображен графически:
2. матрица инцидентности.
Матрица инцидентности – одна из форм представления графа, в которой указываются связи между инцидентными элементами графа ребром и вершиной. Столбцы матрицы соответствуют ребрам, строки – вершинам. Ненулевое значение в ячейке матрицы указывает на связь между вершиной и ребром.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
2 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
3 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
5 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
3. массив ребер.
Пусть в графе M ребер. Заведем массив размером M*2, в котором будем хранить ребра парами вершин, которые они соединяют.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
M |
1 |
2 |
1 |
3 |
2 |
1 |
2 |
3 |
3 |
1 |
3 |
2 |
4. массивы смежности.
Массив смежности для хранения графа представляет собой одномерный массив, имеющий неоднородную структуру. Первые N элементов массива содержат числа, являющиеся индексами последующих элементов данного массива. Последующие элементы содержат номера вершин, смежных с данной.
Например:
N=3, массив А:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
A |
1 |
3 |
5 |
2 |
3 |
1 |
3 |
1 |
5. список ребер.
Список ребер – тип представления графа, подразумевающий, что каждое ребро представляется двумя числами – номерами вершин этого ребра.
нач вершина |
1 |
2 |
3 |
кон вершина |
2 |
3 |
1 |
6. список смежности.
Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин.
1: (2,1), (3,1), (4,1)
2: (1,2), (3,1)
3: (1,3), (2,3), (5,3)
4: (1,4)
5: (3,5)
