3. Сетевые модели.

Граф G– это пара (V, E), где V- конечное множество помеченных вершин, а E  V  V - множество ребер. Если ребра ( v₁, v₂) и ( v₂, v₁) различают, то граф называют ориентированным (или орграфом), а его ребра ‑ дугами. Граф полный, если все пары вершины соединены ребрами (число ребер ); граф планарный, если его можно нарисовать на плоскости без пересечения ребер (число ребер планарного графа по теореме Эйлера не превосходит 3∙(n-1)).

К лассификация ребер орграфа. 1) Ребра дерева поиска (черные).

2) Обратные (Back) ребра соединяют вершину с предком + петли.

3) Прямые (Forward) ребра соединяют вершину с потомком, не входя в дерево.

4) Перекрестные (Cross) ребра – все остальные.

3.1. Способы задания графов.

Графический: вершины изображаются точками, а ребра – линиями между ними.

матрица смежности A = {aij}			матрица инцидентности B = {bij}
aij = 1  ( v1 , v2 )  E	граф неориентирован,  a ij = a ji , т.е. матрица симметрична			граф ориентирован,

Матричный: n = | V |, m = | E |.

Матрица смежности – лучший способ задания графов, близких к полным. Если граф планарен, то в каждой строке матрицы стоит в среднем ≈6 единиц. Выгоднее указать список всех ребер или список подсписков смежных вершин = {(номер вершины, {номера смежных вершин})},затрачивая log ₂ n бит на номер.

Ex: n = 1000. Матрица смежности занимает 1000  1000 = 1000000 бит, список ребер ‑ 3  1000  20 = 60000 бит (10 бит на номер, 20 на ребро).

Т.к. граф определяется своей матрицей смежности, то существует 2^n  n различных графов (= матриц смежности = наборов из n² нулей и единиц)!!!

Граф называется графом без петель, если в нем нет ребер вида ( v_i, v_i), т.е. на диагонали матрицы стоят нули. Число таких графов равно 2^n (n-1). Число неориентированных графов без петель равно ^n (n-1) (матрица симметрична).

Путь – последовательность ребер вида , т.е. конец предыдущего ребра, является началом следующего ребра. Цикл – это путь, у которого начало первого ребра совпадает с концом последнего, т.е. i_k = i₁.

Возведем в квадрат матрицу смежности. Что будет её элементами?

A = {a_ij {0,1}}, A²= {b_ij}, причем . = числу таких k, при которых a_ik = 1 и a_kj = 1,т.е. есть ребра (i, k) и (k, j), есть путь длины 2 из i в j.

Т.о. b_ij есть число различных путей длины 2 из i-й вершины в j-ую. A^k- число путей длины k из i в j, причем пути могут не быть простыми (= без циклов).

Граф связный, если между любыми двумя вершинами есть путь.

Дерево – связный граф без циклов = связный граф, содержащий n-1 ребро.

Сколько различных деревьев существует на n вершинах?

Степень вершины i – это число единиц в i–ой строке матрицы смежности.

№17. Алгоритм кодирования деревьев.

Степени вершин S	3	1	1	4	1	1	1	3	1
Номер вершины I (внизу - шага)	1	2	3	4	5	6	7	8	9
Отцовская вершина О	1	4	1	4	8	4	8	9
Удаляемая вершина U	2	3	5	1	6	7	4	8	9

П

усть есть дерево.

На k-м шаге выбираем в векторе степеней S самую левую вершину U_k с единичной степенью, удаляем ее, а у нее и ее отца O_k уменьшаем степень на 1.

На основе вектора S и картинки мы построим 2 вектора U и О (вместо картинки можно использовать матрицу смежности). Размерности векторов U и O = n-1. По построению пара (U_i, O_i) является ребром дерева. Все U_k – различны (удалить вершину можно только 1 раз), но в векторе U не хватает вершины 9, ее мы перекинем из O, и получим вектор O^*: dim(O^*)=n-2; и вектор U^*: dim(U^*)=n. Зная O^*, легко восстановить дерево. В самом деле, пусть N(i,A) - кратность числа i в векторе A. Очевидно, N(i,U^*)=1 для всех i. Восстанавливаем S: S_i = N(i,O) + N(i,U) = N(i,O^*) + N(i,U^*) = N(i,O^*) + 1. Зная S, вычислим U₁  1-е удаленное ребро графа = (U₁, O₁). Уменьшив на 1 степени вершин U₁ и O₁, найдем U₂ и 2-е ребро графа (U₂, O₂) и т.д. Получили алгоритм декодирования. Рисовать восстанавливаемые ребра удобно в порядке, обратном удалению!

Соответствие между O^* и деревом – взаимнооднозначное (докажите), число деревьев с помеченными вершинами = числу различных векторов O^* = n^n-2.

Напомним, что число неориентированных графов на n вершинах ‑2^n (n-1)/2.

Пример: Если n=3 и матрицу смежности неориентированного графа превратить в вектор из 0 и 1, то деревьям соответствуют 3 вектора из 8-ми: 110, 101 и 011.

Если n=4, то 4²=16 деревьев из 2⁶=64 неориентированных графов без петель.

Если n=5, то 5³=125 деревьев из 2¹⁰=1024 графов

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

Трудоемкость проверки изоморфности перебором нумераций равна O( n² n!).

Теорема. Графы изоморфны  наборы степеней вершин у них совпадают.

Сколько различных неизоморфных деревьев можно построить на n вершинах?

n =3 (1 дерево): n=5 (3 дерева):

n=4 (2 дерева):

Пусть S_i – степень вершин, R – количество ребер дерева   S_i = 2*R = 2*(n-1). Выпишем упорядоченные по убыванию вектора степеней вершин при n=4:

2 2 1 1 и 2 1 1 1. Они различны,  графы неизоморфны.  S_i =2*3 = 6.

Сколько различных упорядоченных векторов степеней вершин?

Есть n мест. На них нужно разместить 2(n-1) единиц (не менее одной на место).

n=5, n-2 = 3	n=6, 2(n-1)=10, n-2 = 4
3 0 0 0 0 2 1 0 0 0 1 1 1 0 0 сначала размещаем n-2 единицы	4 0 0 0 0 0 | 5 1 1 1 1 1 - 1 3 1 0 0 0 0 | 4 2 1 1 1 1 - 2 2 2 0 0 0 0 | 3 3 1 1 1 1 - 3 2 1 1 0 0 0 | 3 2 2 1 1 1 - 4 1 1 1 1 0 0 | 2 2 2 2 1 1 - 5 п отом - в каждую лунку добавим 1

Нарисуем эти деревья. Четвертому вектору соответствуют два неизоморфных дерева!!! В одном из них соседями единственной вершины степени 3 являются 2 висячих вершины и одна со степенью 2, а во второй – наоборот.