61. Графы. Основные определения.

Графом G(V,E) называется совокупность двух множеств непустого множества вершин V и множества E неупорядоченных пар различных элементов множества V.

E – множество ребер.

V – множество вершин.

Число вершин – р

Число ребер – q

Между элементами множеств V и E определены отношения инцидентности:

eE инцидентен ровно 2 элементам V и VV.

2 ребра инцидентны 1 вершине называются смежными.

2 вершины инцидентны 1 ребру также называются смежными.

В некоторых задачах инцидентные ребра неоднозначны. Они рассматриваются в определенном порядке, когда каждому ребру приписывается направление. Ребро называется дугой, а граф называется ориентированным.

Обычно рассматривается конечные графы, а вообще они могут быть и бесконечными

Если множество Е не является множеством (не содержит повторяющихся одинаковых элементов) то эти элементы называются кратными ребрами, а граф, содержащий такие ребра – мультиграфом.

Если элементы множества Е являются недвуэлементным подмножеством, то такие ребра называются гипердугами, а граф – гиперграфом.

Если каждому элементу множества Е или V поставлен в соответствие элемент множества М или N, то граф называется помеченным.

62. Способы представления графов.

Задать граф значит описать множество его вершин и ребер, а также отношения инцидентности.

Отношением инцидентности, определяющей матрицей E_ij, имеющей m строк и n столбцов.

Если ребро ei инцидентно вершине V_j, то в матрице элемент E_ij=1, иначе элемент равен 0.

ei\Vj	I	II	III	IV	V	VI
1	1	1	0	0	0	0
2	1	0	1	0	0	0
3	0	1	0	1	0	0
4	1	0	0	0	0	1
5	0	1	0	0	1	0
6	0	0	1	0	0	1
7	0	0	0	1	1	0
8	0	0	0	0	1	1
9	0	0	1	1	0	0

Для того, чтобы описать ориентированный граф, в матрице инцидентности используют следующее выражение

если ребро e_i инцидентно V_j, при этом V_j является началом ребра, то E_ij=-1, если V_j является концом ребра, то E_ij=1, иначе E_ij=0.

Если ребро является петлей, то в матрице инцидентности элемент E_ij=а, где а>1

ei\Vj	I	II	III	IV	V
1	-1	1	0	0	0
2	0	-1	1	0	0
3	0	-1	0	1	0
4	0	-1	0	0	1
5	0	0	0	0	2

В памяти ЭВМ матрицы инцидентности задается двумерным массивом.

Способ представления матрицы инцидентности не является экономным, так в строке значатся только 2, а остальные нули.

Поэтому существует другие методы

Список ребер

Список ребер имеет структуру списка, каждая строка содержит номера вершин, инцидентных ребру:

ei\Vj
1	I	II
2	I	III
3	II	IV
4	I	V
5	II	V

Если граф неориентирован, то порядок вершин не существенный, если граф ориентирован, то первым указывается начало ребра, втором – конец.

Представление более компактно.

Матрицы смежности.

Матрица размера nn, строки и столбцы нумерованы в соответствии с номерами вершин на пересечении строки и столбца ставится 1, если вершины смежные и 0, если они не смежные.

ei\ej	I		III	IV	V	VI
I	0	1	1	0	0	1
II	1	0	0	1	1	0
III	1	0	0	1	0	1
IV	0	1	1	0	1	0
V	0	1	0	1	0	1
VI	1	0	1	0	1	0

ei\ej	I	II	III	IV	V
I	0	1	0	0	0
II	0	0	1	1	1
III	0	0	0	0	0
IV	0	0	0	0	0
V	0	0	0	0	0

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

В памяти ЭВМ матрица смежности представляется двумерным массивом, содержащим 0 и 1, если V_i смежно с V_j , иначе – 0