Методы внешней сортировки.

1. Сбалансированное двухпоточное слияние.

2. Сбалансированное многопоточное слияние.

3. Многофазное слияние.

4. С фибоначчиевым распределением.

Сбалансированное двухпоточное слияние.

Этап	F1	F2	F3	F4	Примечание
Исходное состояние	-	-	-	16
Разбиение Слияние Слияние. Слияние	1111 1111 44 16	1111 1111 44	- Сливаются 2222 8	- 2222 8	Распределение с сортировкой.

Многофазное слияние.

Добавляется распределение на 3 этапе. Далее, снова слияние.

С фибоначчиевым распределением.

Алгоритмы на графах.

Г раф представляет собой сеть. Узлы и дуги. С помощью графов, можно подсчитывать статистику. Граф представляет собой совокупность двух понятий: G=(V,E) – множество вершин и ребер. Есть понятие порядок графа – число вершин. Вершины могут быть смежными, если соединены ребром. Ребро является инцидентным. Тест по теории графов(!!!). Если ребро направленно – называется дугой. Если есть – то граф ориентированный. Если есть и то, и то – смешанный граф.

Мультиграф – несколько ребер между вершинами. Псевдограф.

Взвешенный граф – каждому ребру соответствует вес, какое-то числовое значение.

Цикл – путь, у которого начальная и конечная точка совпадают.

Путь. Маршрут – неориентированный граф.

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

Е – множество пар, ребер.

Ребро – неупорядоченная пара вершин, соединенных между собой.

Степень вершины – число инцидентных ей ребер.

Порядок графа – число вершин.

Размер графа – число ребер.

Инцидентными являются ребро и узлы, соединенные с ним.

Смежными или соседними являются ребра (вершины), соединенные общей вершиной (ребром).

Кратными называются ребра, концевые вершины которых совпадают.

Петля – ребро, вершины (концы) которого совпадают.

Мультиграф

Псевдограф

Простой граф – без кратных ребер и без петель.

Ориентированный граф – все дуги.

Смешанный – ребра и дуги.

Взвешанный или нагруженный – каждому ребру соответствует число, называемое его весом.

Сеть – взвешенный орграф.

Маршрут – последовательность вершин и ребер, в которой каждая вершина кроме последней соединена со следующей.

Путь – маршрут в орграфе.

Длина маршрута – число составляющих ребер графа не сост или сумма весов для взвешенного.

Цикл – цепь, в которой первая и последняя вершина совпадают.

Цепь – маршрут, в котором нет одинаковых ребер.

Простой путь – нет повторов.

Контур – цикл в орграфе.

Ациклический граф - граф без циклов.

Эйлеров цикл – цикл, проходящий по каждому ребру ровно один раз.

Связный граф – в котором существует путь из любой вершины в любую.

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

Две вершины достижимы.

Полный граф – граф, в котором любые две вершины соединены ребром.

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

Разреженный или ненасыщенный – число ребер намного меньше квадрата порядка.

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

Матрица смежности или матрица примыканий – матрица, у которой число строк и столбцов равно числу вершин, а на пересечении i-строки с j-столбцом стоит 1, если данные вершины связаны. Больше 1 – для мультиграфов; +2 – для каждой петли.

Матрицы инцидентности – количество строк равно количеству вершин, а количество – количеству ребер. Если вершина концевая, то -1, иначе +1.

Матрица весов – на основе инцидентности, если в нее вместо единичек поставить веса.

Списки примыкания – количество списков равно количеству вершин. Порядковый номер для начала каждого списка. Строятся списки связности.

Обход графа в глубину.

Заносятся в стек посещенные вершины, помечаются флажками. Если посещали вершину, флаг меняется.

1

2

3

9

8

5

6

7

4

1, 2, 3, 4, 5, 6, 7, 8, 9.

Узлы первого уровня.

1 – 2, 8 – 3, 5 – 4, 6 – 9, 10, 7.

При программировании использовать лучше очередь, а не стек.

Алгоритм определения транзитивного замыкания.

Транзитивное замыкание – обозначается со *.

У матрицы А строится матрица А² – будет содержать 1-ки в тех точка на пересечении i-строки и j-го столбца, между которыми есть путь длины не более 2. Для того, чтобы найти n³. Трудоемкость n*n³. O(n³*log n). Умножение заменяется на операцию «И», сложение на «ИЛИ». Алгоритм Уоршелла.

Матрицы связности – матрица связности будет содержать единичку в том случае, если из i-вершины в j-ю есть путь,  ставится единичка.

15.04.2010 г.

Поиск сильносвязных компонентов в ориентированном графе.

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

R = ||r_ij||

Q = ||q_ij||

H = ||h_ij||

Матрицы взаимной достижимости.

П

V3

ример.

V1

V4

V2

V7

V5

V6

1111000

1111000

1111000

1111000

0000110

0000110

0000001

Поиск кратчайших путей.

Алгоритмы Флойда и Дейкстры. Поиск кратчайшего пути (вес, цена и т.д.). матрица, в которой найдены пути определенной длины. Когда мы суммируем два пути через промежуточный узел, меняем значение только в том случае, если сумма оказывается меньше. После этого берем еще один промежуточный и т.д., до тех пор, пока не переберем все варианты. Три цикла, по i, j и k.

Метод обхода графа в глубину.

Можно так же искать кратчайшие пути, но этот метод будет приближенным. Распределяются все узлы в порядке возрастания либо убывания. Потом берем вершину, которая имеет самое маленькое значение. Там есть ребра различной длины, начальный граф. Далее выбирается из оставшихся ребер то ребро, из них тоже берется минимально. Связываются. Берем то ребро, которое самое короткое. Кратчайший путь между первой и последней вершиной.

Между двумя вершинами существует два пути. Если одна связь порвалась, то есть резервный путь.

А

C

E

G

D

B

H

F

I

Поиск минимальных остовов деревьев.

Ребра, сумма весов которых минимальна. Остов и обрамление остова. Остов – те узлы графа, которые уже обошли. Обрамление – на расстоянии одного ребра.

Алгоритм Крусскалла (Красскалла).

добавляется до тех пор, пока не закончатся вершины и граф не станет связным.

Терминология.

Эйлеров цикл

Граф неориентированный

Дерево

Ребро

Степень вершины

Порядок графа

Размер графа

Инцидентные ребра и узлы

Смежные

Кратные

Петля

Мультиграф

Псевдограф

Простой граф

Дуга

Ориентированный граф

Смешанный граф

Взвешенный или нагруженный граф

Сеть

Маршрут

Путь – маршрут в орграфе

Длина маршрута

Цикл – цепь, в которой первая и последняя

Эйлеров цикл

Гамильтонов путь (цикл)

Контур – цикл в орграфе

Простой путь или цепь

Ациклический граф

Связный граф или односвязный

Компонента связности графа

Сильно связный граф

Полный граф – в котором две вершины соединены ребром

Плотный граф

Разреженный или ненасыщенный граф

Матрица смежности или примыкания

Матрица инцидентности

Списки примыкания или смежности

29.04.10 г.