3.8. Вопросы для самоконтроля

1. Алгоритмы сортировки 3-х чисел.

2. Сортировка вставками. Оценка наихудшего и среднего случая.

3. Пузырьковая сортировка. Оценка наихудшего случая.

4. Сортировка Шелла.

5. Корневая сортировка: достоинства и недостатки.

6. Сортировка методом индексов.

7. Быстрая сортировка. Анализ наихудшего случая.

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

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

Граф может быть ориентированным (подобно улице с односторонним движение); взвешенным (каждой дороге приписана стоимость путешествия по ней).

4.1. Основные понятия теории графов

С формальной точки зрения граф представляет собой пару G = (V, E) множеств, первое из которых (V) состоит из вершин (узлов), а второе (E) – из его ребер. Ребро связывает между собой две вершины, т.е. EVV.

Если e  E  е =(u,v); u,v V, и пара вершин u и v соединены ребром e, причем e – неупорядоченная пара, то такой граф называется неориентированным. Если пара вершин (u,v) упорядочена, то граф называется ориентированным (орграфом), и ребра такого графа называются дугами, а вершины - узлами.

О бычно для наглядности графы изображают на рисунке, где круги соответствуют вершинам, а линии, их соединяющие, – ребрам (рис.4.1, 4.2). Внутри кружков пишут метки вершин. Ребра ориентированного графа (орграфа, рис.4.2) изображают в виде стрелок.

Для орграфа ребро - упорядоченная пара вершин: первая вершина это начало ребра, а вторая - его конец.

Полный граф - это граф, в котором каждая вершина соединена со всеми остальными. Число ребер в полном графе без петель – N(N-1)/2.

В полном орграфе разрешается переход из любой вершины в любую другую, следовательно, в полном орграфе – N (N - 1) ребер.

Подграф (V_s, E_s) графа или орграфа (V, E) состоит из некоторого множества вершин V_s  V, и некоторого подмножества ребер Е_s  Е, соединяющих эти вершины.

При работе с графами часто возникает задача, как проложить путь из ребер от одной вершины графа к другой. Говорят о «движении по ребру» – это значит, что мы переходим из вершины u графа в другую вершину v, связанную с ней ребром. В этом случае говорят, что u примыкает к v, или что эти две вершины – соседние.

Путь в графе - это последовательность ребер, по которым можно поочередно прохо­дить. С формальной точки зрения путь из вершины V_i в вершину V_j - это последова­тельность ребер V_i V_i+1, V_i+1V _i+2, V_i+2 V_i+3, … , V_j-1 V_j. Если V_i = V_j, тогда путь будет замкнутым (цикл, петля), то есть цикл - это путь, который начинается и заканчивается в одной и той же вершине.

В ациклическом графе циклы отсутствуют.

Обычно требуется, чтобы любая вершина встречалась на пути не более чем однажды.

У всякого пути есть длина - число ребер в нем.

Во взвешенном графе или орграфе каждому ребру приписано число, называемое весом ребра. На рисунке вес пишут рядом с ребром. При формальном описании вес будет дополнительным элементом упорядоченной или неупорядоченной пары вершин (триплет). Стоимость пути по взвешенному графу равна сумме весов всех ребер пути.

Кратчайший путь во взвешенном графе - это путь с минимальной стоимостью (весом), даже если число ребер в пути и можно уменьшить. (Если, например, путь P1 состоит из 5 ребер с общим весом 24, а Р2 - из 3-х ребер с весом 32, то P1 считается более коротким).

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

Связный ациклический граф называется деревом.