- •Предназначено студентам очной формы обучения.
- •Введение
- •1. Оценки сложности алгоритмов
- •1.1. Определение понятия алгоритм
- •1.2. Оценка сложности алгоритмов
- •2. Линейные структуры данных
- •2.1. Методы организации и хранения линейных списков
- •2.2. Операции со списками при последовательном хранении
- •2.3. Операции со списками при связном хранении
- •2.4. Организация двусвязных списков
- •Задания для самоконтроля
- •2.5. Стеки и очереди
- •2.6. Сжатое и индексное хранение линейных списков
- •3. Сортировка и слияние
- •3.1. Пузырьковая сортировка
- •3.2. Сортировка вставкой
- •3.3. Сортировка посредством выбора
- •3.4. Сортировка квадратичной выборкой
- •3.5. Слияние списков
- •3.6. Сортировка списков путем слияния
- •3.7. Быстрая и распределяющая сортировки
- •4. Поиск
- •4.1. Последовательный поиск
- •4.2. Бинарный поиск
- •4.4. Методы вычисления адреса
- •4.5. Выбор в линейных списках
- •5. Рекурсия
- •6. Алгоритмы на графах и сетях
- •6.1. Исходные понятия
- •6.2. Матричные представления графов
- •6.3. Другие представления графов
- •6.4. Поиск в глубину как система исследования графа
- •6.5. Перебор цепей поиском в глубину
- •6.6. Взвешенные графы. Ориентированные графы
- •6.7. Нахождение фундаментального множества циклов
- •6.8. Выявление мостов и точек сочленений
- •6.9. Поиск в ширину как система исследования графа
- •6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим
- •6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе
- •6.12. Улучшения алгоритма Дейкстры
- •6.13. Построение кратчайшего каркаса
- •6.14. Нахождение всевозможных кратчайших путей в графе
- •6.15. Потоковые задачи
- •6.16. Пример практической задачи на графах
- •7. Генераторы случайных и псевдослучайных последовательностей
- •7.1. Общая постановка задачи
- •7.3. Генератор случайных чисел, поставляемый с системой
- •7.4. Генератор с малым кодом
- •7.5. Генератор Парка-Миллера
- •7.6. Улучшенная версия генератора Парка-Миллера
- •7.7. Быстрый генератор для 32-битового представления целых и действительных чисел
- •7.8. Алгоритм л'Экюера, комбинирующий две последовательности
- •Оглавление
- •7. Генераторы случайных и псевдослучайных последовательностей 144
- •394026 Воронеж, Московский просп., 14
6. Алгоритмы на графах и сетях
6.1. Исходные понятия
Методы решения задач на графах - прекрасная область для иллюстрации идей программирования, а их программы - для демонстрации рационального применения различных структур данных.
Изучая системы, мы выделяем их части (узлы) и осмысливаем связи, о т н о ш е н и я между узлами. Таких д и с к р е т н ы х систем, различных по своей природе, великое множество. Например, можно рассматривать сеть трубопроводов или железнодорожные узлы и связующие их участки железных дорог. Граф - это абстрактное представление дискретной системы, состоящее из узлов (вершин) и ребер, выражающих отношения узлов. Ребро изображают линией, не обязательно прямой, узел - небольшим кружком. В нашем примере отношение выражает наличие или отсутствие непосредственной связи узлов.
Итак, граф G- это пара (V,E), где V - конечное непустое множество узлов, а Е - множество ребер, т.е. пар { vi, vj } вершин, называемых смежными, для которых отношение выполняется. В графе, изображенном ниже, например, есть ребра {2,1}, {2,5}, {2,6}, но нет ребер {2,4}, {2,3}:
Говорят, что ребро { vi, vj } инцидентно узлам vi, vj. Степень р узла равна числу ребер, инцидентных i-му узлу. Число узлов в графе будем далее обозначать n, число ребер в нем - m. Для изображенного выше графа Gn = 6, m = 7.
Подграф графа G содержит некоторое подмножество узлов из V и в с е связующие их ребра. Например, узлы 1, 2, 5 вместе с соединяющими их тремя ребрами составляют подграф графа G, а вершины 2,4 - другой подграф, не имеющий ребер.
Маршрут между узлами v0, vk - это последовательность узлов v0, v1, v2, ..., vk, такая, что для любого j = l...k существует ребро { vj-1, vj }. Следовательно, маршрут - это также и последовательность ребер, число которых называют длиной маршрута. Цепь - маршрут без повторения ребер. В простой цепи все узлы различны. Цепь между узлами vi, vj будем обозначать vi, vj .
Цикл - это замкнутая цепь, т.е. узел vk - тот же, что и v0. Простой цикл - это замкнутая простая цепь, например, цикл 1, 2, 6, 5, 1 или цикл 1, 2, 5, 6, 1 в графе G. Минимальная длина цикла равна 3; например, маршрут 3, 4, 3 не считают циклом.
Граф связен, если для любой пары узлов есть соединяющая их цепь. Несвязный граф состоит из k> 2 компонент связности - максимальных связных подграфов; например, в графе G - две компоненты G' и G". Граф или подграф называют полным, если для любых его узлов vi, vj в нем имеется ребро { vi, vj } . Например, подграф (компонента) G' - полон. В полном графе m =(n2 - n)/2 ребер. Узел, не смежный ни с одним узлом графа, называют изолированным. Назовем полнотой графа отношение 2m/(n2 - n); в процентах – 200*m /(n2 – n).
Связный граф (подграф) без циклов (ациклический) называют деревом. Если в несвязном графе все компоненты - деревья, его называют лесом. Идея дерева и леса знакома вам по гл.1. В графе-дереве имеется в точности n-1 ребро, т.е. m=n-l. Добавьте в него новое ребро и возникнет цикл. В любом связном графе (подграфе) можно выделить (обычно не единственным образом) дерево, содержащее все узлы графа (подграфа) - каркас или остов. Ребра, не принадлежащие каркасу, называют хордами. Например, в подграфе G' можно выделить каркас, включающий ребра {2, 1}, {2, 5}, {2,6}. При таком каркасе ребра {1, 6}, {1, 5}, {5, 6} будут считаться хордами.
Каркас и каждая хорда однозначно определяют некоторый цикл в графе (подграфе), содержащий одну лишь эту хорду и ребра каркаса. Множество этих циклов является фундаментальным, поскольку на его основе можно найти и все прочие циклы. В связном графе мощность множества фундаментальных циклов (цикломатическое число) равна
m - n + 1, ибо из m ребер n - 1 ребро образует каркас, а прочие m - n + 1 ребер - хорды.
Задание 6.1.
Выразите через n и k число ребер в лесе, содержащем k деревьев, и цикломатическое число для графа, в котором k компонент связности (здесь используйте также и m).