ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
4.17. Раскраска графа Пусть задан граф G = (V,E) и натуральное число k. Вершинной раскраской графа называется функция, ставящая в соответствие каждой вершине из множества V натуральное число (цвет) из множества {1.. k}. Другими словами, раскраска задает цвет каждой вершине графа. Раскраска называется правильной, если никакие две смежные вершины не окрашены в один цвет. В дальнейшем под раскраской будем понимать только правильную раскраску. Граф называется раскрашиваемым, если для него существует правильная раскраска. Хроматическим числом графа называется минимальное число цветов, требующееся для правильной раскраски графа. Правильная раскраска графа в хроматическое число цветов называется минимальной. Очевидны следующие факты. 1. Хроматическое число графа G = (V,E), в котором E = , равно 1. 2. Хроматическое число полного графа G = (V,E) равно n = |V|. 3. Если мощность наибольшей клики графа G = (V,E) равна n, то его хроматическое число не меньше n. 4. Множество вершин графа G = (V,E), окрашенных в один цвет является независимым множеством. Пусть требуется получить все раскраски графа G = не более чем в k цветов. Раскраску будем хранить в массиве m, m i — цвет й вершины графа. Если я вершина графа не окрашена, то m i = 0. Обозначим через Г) множество цветов, которыми окрашены вершины, смежные й вершине графа. Тогда цвет, в который может быть окрашена я вершина, принадлежит множеству {1.. k} – Г. Получить все раскраски графа не более чемв k цветов можно, используя метод поиска с возвращением. В исходном состоянии все вершины графа не окрашены и все элементы массива m равны нулю. Вершины графа будем окрашивать последовательно, начиная с первой. Окраску й вершины опишем рекурсивным алгоритмом 4.21, блок-схема которого представлена на рис. В цикле перебираются цвета, в которые может быть окрашена я вершина. Если окрашена последняя я вершина (n = |V|), то раскраска получена и выводим ее, иначе окрашиваем следующую i + ю вершину по алгоритму 4.21. Когда выполняется шаг назад, к окраске i – й вершине, я вершина становится неокрашенной, поэтому процедура имеет дополнительный параметр m. Алгоритм 4.21 получения всех раскрасок графа G = (V,E) не более чем в k цветов. Вход i — окрашиваемая вершина m — текущая раскраска. 216 Выход последовательность всех раскрасок графа в k цветов, если граф G раскрашиваемый. + Рис. Рекурсивный алгоритм получения всех раскрасок графав k цветов Пусть требуется получить одну раскраску графа G = не более чем в k цветов. Для решения этой задачи можно использовать алгоритм с небольшой модификацией после получения первой раскраски закончить алгоритм. Такая модификация позволит получить решение, но для повышения эффективности можно учитывать следующее 1. ю вершину (i < можно окрашивать в цвет, не превышающий i. 2. В первую очередь окрашивать вершины, принадлежащие наибольшей клике. 3. Остальные вершины окрашивать в порядке невозрастания степеней. Учитывая вышесказанное, получим более эффективный алгоритм 4.22 получения одной раскраски графа G = не более чем в k цветов. Отметим, что если граф не является раскрашиваемым, то раскраска в k цветов не будет получена, в остальных же случаях будет получена раскраска, близкая к минимальной. Для получения минимальной раскраски графа можно использовать следующий алгоритм. Раскраска (i,m) Г := x i=n Конец Раскраска (i+1, m ) m 217 Алгоритм 4.23 получения минимальной раскраски графа. Вход:граф G = (V,E). Выход Mmin — минимальная раскраска. 1 Получить раскраску m не более чем в k = |V| цветов по алгоритму 4.22. Присвоить k наибольший цвет в раскраске m. 2. Если раскраска m в k цветов получена, выполнять 2.1. Сохранить в Mmin раскраску m. 2.2. k:=k – 1. 2.3. Получить раскраску m не более чем в k цветов по алгоритму 4.22. 4. Конец алгоритма. Любой граф может быть раскрашен в число цветов, равное количеству вершин в графе. В п по алгоритму 4.22 получаем раскраску m, близкую к минимальной и сохраняем количество цветов k в ней. В п пытаемся получить раскраску в меньшее число цветов, предварительно запомнив ранее полученную в качестве претендента на минимальную. Минимальной раскраской будет последняя полученная. Рассмотрим задачи, решение которых сводится к нахождению минимальной раскраски графа. Задача 4.14. Имеется город G, который связан авиамаршрутами с городами. Маршрут GG i G обслуживается в интервале времени. Требуется определить минимальное количество самолетов, достаточное для обслуживания всех маршрутов. Решение. Построим граф, множество вершин которого соответствует множеству маршрутов. Две вершины смежны тогда, когда временные интервалы соответствующих маршрутов пересекаются. Хроматическое число этого графа равно минимальному количеству самолетов, достаточному для обслуживания всех маршрутов, а минимальная раскраска определяет распределение самолетов по маршрутам маршруты, соответствующие вершинам, окрашенным в один цвет, могут обслуживаться одним самолетом. Задача 4.15. Требуется составить расписание уроков так, чтобы заданное множество занятий было проведено за минимально возможное время. Решение. Построим граф, множество вершин которого соответствует множеству занятий. Две вершины смежны тогда, когда соответствующие занятия нельзя проводить одновременно (один и тот же преподаватель, кабинет или класс. Минимальная раскраска графа определяет требуемое расписание на первом уроке проводятся занятия, соответствующие вершинам, окрашенным в первый цвет, на втором — занятия, соответствующие вершинам, окрашенным во второй цвет и т.д. Задача 4.16. Заданы множества работ и механизмов. Для выполнения работ требуется время (одинаковое для всех работ) и некоторые механизмы. Никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно организовать процесс выполнения всех работ за минимально возможное время. Решение. Построим граф, множество вершин которого соответствует множеству работ. Две вершины смежны, если для соответствующих работ нужен хотя бы один общий механизм. Получим минимальную раскраску графа. Работы, соответствующие вершинам графа, окрашенным в первый цвет, выполняются одновременно в первую очередь, затем одновременно выполняются работы, соответствующие вершинам, окрашенным во второй цвет и т.д. Задача 4.17. Граф на рис представляет схему электрических соединений вершины соответствуют клеммам, ребра — прямым металлическим полоскам проводников. Проводники не должны пересекать друг друга, поэтому необходимо их распределить по нескольким параллельным платам, в каждой из которых проводники не пересекались бы. Клеммы доступны на всех платах. Рис. Схема электрических соединений Необходимо определить наименьшее число плати распределить проводники по платам. Решение. Построим граф, множество вершин которого соответствует множеству проводников. Две вершины смежны, если соответствующие им проводники пересекаются. Получим минимальную раскраску графа. Проводники, соответствующие вершинам графа, окрашенным в первый цвет, располагаются на первой плате, проводники, соответствующие вершинам, окрашенным во второй цвет, располагаются на второй плате и т.д. клеммы клеммы проводники 219 Практическое занятие 4.1 Маршруты Цель занятия изучить основные понятия теории графов, способы задания графов, научиться программно реализовывать алгоритмы получения и анализа маршрутов в графах. Задания 1. Представить графы G 1 и G 2 (см.‖Варианты заданий, па) матрицей смежности, матрицей инцидентности, диаграммой. 2. Определить, являются ли последовательности вершин (см. Варианты заданий, п.б) маршрутом, цепью, простой цепью, циклом, простым циклом в графах G 1 и G 2 (см.‖Варианты заданий, па. 3. Написать программу, определяющую, является ли заданная последовательность вершин (см. Варианты заданий, п.б) маршрутом, цепью, простой цепью, циклом, простым циклом в графах G 1 и G 2 (см.‖Варианты заданий, па. 4. Написать программу, получающую все маршруты заданной длины, выходящие из заданной вершины. Использовать программу для получения всех маршрутов заданной длины в графах G 1 и G 2 (см.‖Варианты заданий, па. 5. Написать программу, определяющую количество маршрутов заданной длины между каждой парой вершин графа. Использовать программу для определения количества маршрутов заданной длины между каждой парой вершин в графах G 1 и G 2 (см.‖Варианты заданий, па. 6. Написать программу, определяющую все маршруты заданной длины между заданной парой вершин графа. Использовать программу для определения всех маршрутов заданной длины между заданной парой вершин в графах G 1 и G 2 (см.‖Варианты заданий, па. 7. Написать программу, получающую все простые максимальные цепи, выходящие из заданной вершины графа. Использовать программу для получения всех простых максимальных цепей, выходящих из заданной вершины в графах G 1 и G 2 (см.‖Варианты заданий, па. 220 5 6 7 Варианты заданий Варианта) диаграмма графа матрица смежности графа G 2 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 б) последовательности вершин 1. (2, 1, 7, 6, 3, 5) 2. (7, 6, 3, 5, 6, 2, 1) 3. (6, 5, 4, 3, 6) 4. (7, 6, 5, 3, 6, 5) 5. (3, 6, 7, 1 ,6 , 5, 3) 1 2 3 4 221 Варианта) матрица смежности графа G 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 диаграмма графа G 2 2 3 1 6 4 7 5 б) последовательности вершин 1. (6, 2, 1, 7) 2. (1, 2, 6, 5, 3, 6, 2) 3. (1, 2, 6, 7, 1) 4. (6, 7, 1, 2, 5, 1, 6) 5. (1, 2, 6, 7, 2, 6, 3) 222 Варианта) диаграмма графа матрица инцидентности графа б) последовательности вершин 1. (6, 7, 1, 4, 3, 2) 2. (2,1, 7, 6, 1, 4) 3. (1, 2, 3, 4, 1) 4. (1, 2, 3, 4. 2, 1) 5. (2. 1, 6. 7, 1. 4, 2) 1 2 3 4 5 6 7 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 223 6 2 5 1 4 3 Варианта) матрица инцидентности графа диаграмма графа б) последовательности вершин 1. (2, 3, 4, 1, 5) 2. (4, 3, 6, 5, 3, 4, 2) 3. (6, 1, 2, 5, 1, 7) 4. (1, 7, 6. 2, 1) 5. (2, 1. 7, 6, 1. 4, 3, 2) 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 7 224 Варианта) диаграмма графа G 1 1 2 3 4 7 6 5 матрица смежности графа G 2 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 б) последовательности вершин 1. (5, 3, 6, 7, 1, 2) 2. (1, 2, 6, 5, 3, 6, 7) 3. (6, 3, 4, 5, 6) 4. (5, 6, 3, 5, 6, 7) 5. (3, 5, 6, 1, 7, 6, 3) 225 Варианта) матрица смежности графа G 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 диаграмма графа G 2 2 3 1 6 4 7 5 б) последовательности вершин 1. (1, 7, 6, 3, 5) 2. (6, 5, 3, 6, 7, 1) 3. (7, 6, 3, 2, 1, 7) 4. (4, 3, 5, 3, 6, 5) 5. (1, 2, 7, 6, 2, 1) 226 Варианта) диаграмма графа G 1 2 7 3 5 1 4 6 матрица инцидентности графа б) последовательности вершин 1. (7, 6, 5, 3, 4) 2. (1, 7, 6, 2, 5, 6) 3. (7, 1, 2, 3, 6, 7) 4. (5, 6, 3, 5, 3, 4) 5. (1, 2, 6. 7, 2, 1) 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 227 Варианта) матрица смежности графа G 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 диаграмма графа G 2 1 2 3 4 7 6 5 б) последовательности вершин 1. (3, 5, 6, 7, 1, 2) 2. (3, 6, 7, 1, 2, 6, 5) 3. (4, 3. 6. 5, 4) 4. (5, 5, 7, 6, 3, 5) 5. (5, 3, 6, 7. 1, 6, 5) 228 Варианта) диаграмма графа матрица инцидентности графа G 2 0 1 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 б) последовательности вершин 1. (1, 2, 6, 7) 2. (2, 6, 1, 2, 3, 4) 3. (7, 6, 2, 1, 7) 4. (6, 2, 1, 7, 2, 6) 5. (7, 6, 2, 1, 6, 2, 3) 1 2 3 4 5 6 7 229 Варианта) матрица инцидентности графа G 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 диаграмма графа G 2 6 4 7 1 2 3 5 б) последовательности вершин 1. (2, 3, 4, 1, 7, 6) 2. (4, 1, 6, 7. 1, 2) 3. (1, 4, 3, 2, 1) 4. (1, 2, 4, 3, 2, 1) 5. (2, 4. 1, 7, 6, 1, 2) 230 Варианта) диаграмма графа G 1 3 2 4 1 5 7 6 матрица инцидентности графа G 2 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 б) последовательности вершин 1. (5, 1, 4, 3, 2) 2. (2, 4, 3, 5, 6, 3, 4) 3. (7, 1, 5, 2, 1, 6) 4. (1, 2, 6, 7, 1) 5. (2, 3, 4, 1, 6, 7, 1, 2) 231 5 6 7 Варианта) матрица смежности графа G 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 диаграмма графа б) последовательности вершин 1. (7, 6, 2, 1) 2. (2, 6, 5, 3, 6, 2, 1) 3. (6, 7, 1, 2, 6) 4. (7, 1, 5, 2, 1, 6, 7) 5. (3, 6, 2, 7, 6, 2, 1) 1 2 3 4 232 Варианта) диаграмма графа G 1 2 7 3 5 1 4 6 матрица инцидентности графа G 2 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 б) последовательности вершин 1. (7, 1, 2, 6) 2. (2, 6, 3, 5, 6, 2, 1) 3. (1, 7, 6, 2, 1) 4. (6, 1, 5, 2, 1, 7, 6) 5. (3, 6, 2, 7, 6, 2, 1) 233 Варианта) матрица инцидентности графа G 1 0 1 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 диаграмма графа б) последовательности вершин 1. (2, 6, 7, 1) 2. (4, 3, 2, 1, 6, 2) 3. (7, 1, 2, 6, 7) 4. (6, 2, 7, 1, 2, 6) 5. (3, 2, 6, 1, 2, 6, 7) 1 2 3 4 5 6 7 234 Варианта) диаграмма графа G 1 3 2 4 1 5 7 6 матрица инцидентности графа G 2 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 б) последовательности вершин 1. (3, 4, 1, 6, 7) 2. (5, 3, 4, 1, 6, 7, 1, 2) 3. (2, 3, 4, 1, 6, 7, 1, 2) 4. (6, 7, 1, 2, 6) 5. (1, 4, 3, 2, 1, 7, 6, 1) 235 Практическое занятие 4.2 Циклы Цель занятия изучить разновидности циклов в графах, научиться генерировать случайные графы, определять их принадлежность к множеству эйлеровых и гамильтоно- вых графов, находить все эйлеровы и гамильтоновы циклы в графах. Задания 1. Разработать и реализовать алгоритм генерации случайного графа, содержащего n вершин и m ребер. 2. Написать программу, которая а) в течение десяти секунд генерирует случайные графы, содержащие вершин и m ребер б) для каждого полученного графа определяет, является ли он эйлеровым или гамильтоновым; в) подсчитывает общее количество сгенерированных графов и количество графов каждого типа. Результат работы программы представить в виде таблицы табл. 4.6). Таблица 4.6 Результат работы программы Количество вершин Количество ребер Количество графов эйлеровых гамильтоновых всех n n n n + 1 n n + 2 n 2 n C 3. Выполнить программу при n = 8, 9, и сделать выводы. 4. Привести пример диаграммы графа, который является эйлеро- вым, ноне гамильтоновым. Найти в нем все эйлеровы циклы. 5. Привести пример диаграммы графа, который является гамильто- новым, ноне эйлеровым. Найти в нем все гамильтоновы циклы. 6. Привести пример диаграммы графа, который является эйлеро- вым и гамильтоновым. Найти в нем все эйлеровы и гамильтоновы циклы. Привести пример диаграммы графа, который не является ни эй- леровым, ни гамильтоновым. 236 Практическое занятие 4.3 Связность Цель занятия изучить алгоритм Краскала построения покрывающего леса, научиться использовать его при решении различных задач. Задания 1. Реализовать алгоритм Краскала построения покрывающего леса. 2. Используя алгоритм Краскала, разработать и реализовать алгоритм решения задачи (см. варианты заданий. 3. Подобрать тестовые данные. Результат представить в виде диаграммы графа. Варианты заданий 1. Найти все мосты в связном графе. 2. Найти минимальное множество ребер, удаление которых из связного графа делает его несвязным. 3. Найти минимальное множество вершин, удаление которых из связного графа разбивает его натри связные компоненты. 4. Получить все покрывающие деревья связного графа G = (V,E), исключая всеми способами |E| – |V| + 1 ребер графа. 5. Найти в эйлеровом графе эйлеров цикл, используя алгоритм Флери, по которому выбираются и нумеруются непронумерованные ребра графа последующим правилам 1. Произвольно выбрать некоторую вершину v 1 и ребро {v 1 ,v 2 }, инцидентное вершине v 1 . Этому ребру присвоить номер 1. Перейти в вершину v 2 2. Находясь в вершине v i , следует не выбирать ребро {v i ,v 1 }, если имеется возможность другого выбора. 3. Находясь в вершине v i , следует не выбирать ребро {v i ,v j }, которое является мостом, если имеется возможность другого выбора. 4. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл, порядок нумерации состветствует последовательности обхода ребер. 6. Найти все множества вершин, исключение которых из связного графа разбивает его на две связные компоненты, причем каждая компонента не содержит изолированных вершин. 7. Найти все элементные множества ребер, исключение которых из связного графа разбивает его на две связные компоненты. 237 8. Найти все множества ребер, исключение которых из связного графа разбивает его на две связные компоненты, причем каждая компонента не содержит изолированных вершин. 9. Найти максимальное множество ребер, исключение которых из связного графа разбивает его на две связные компоненты. 10. Найти минимальное множество ребер, удаление которых из связного графа разбивает его натри связные компоненты. 11. Найти минимальное множество вершин, удаление которых из связного графа делает его несвязным. 12. Найти все точки сочленения в связном графе. 13. Найти все элементные множества вершин, исключение которых из связного графа разбивает его на две связные компоненты. 14. Найти максимальное множество вершин, исключение которых из связного графа разбивает его на две связные компоненты. 15. Найти все максимальные множества ребер, исключение которых из связного графа разбивает его на две связные компоненты. Практическое занятие 4.4 Анализ алгоритмов построения покрывающего дерева минимальной стоимости Цель занятия изучить алгоритмы построения покрывающего дерева минимальной стоимости и выполнить их сравнительный анализ. Задания 1. Разработать и реализовать алгоритм построения случайного связного взвешенного графа с заданным числом вершин n и ребер m. 2. Реализовать алгоритмы построения оптимального покрывающего дерева 1. Сортировка + алгоритм Краскала. 2. Алгоритм Краскала с выбором очередного ребра минимального веса. 3. Алгоритм Прима. 3. Разработать и написать программу, которая генерирует 100 случайных связных взвешенных графов с заданным числом вершин n и ребер, для каждого графа строит покрывающее дерево минимальной стоимости тремя алгоритмами и определяет время выполнения каждого алгоритма. Выполнить программу при n = 10, 15 и 20. Результат для каждого n представить в виде таблицы (табл. 238 Таблица 4.7 Время выполнения алгоритмов Количество ребер в графе n (n 2 + 3n) / 6 n 2 / 3 (n 2 – n) / 2 min max min max min max min max Сортировка + алгоритм Краскала Алгоритм Краскала с выбором очередного ребра минимального веса Алгоритм Прима Практическое занятие 4.5 Анализ алгоритмов поиска кратчайшего пути во взвешенном орграфе между заданной парой вершин Цель занятия изучить алгоритмы поиска кратчайшего пути во взвешенном орграфе между заданной парой вершин и выполнить их сравнительный анализ. Задания 1. Разработать и реализовать алгоритм построения случайного слабо связного взвешенного орграфа с заданным числом вершин n и дуг m. 2. Реализовать алгоритмы поиска кратчайшего пути во взвешенном орграфе между заданной парой вершин 1. Перебор простых цепей. 2. Метод ветвей и границ. 3. Алгоритм Дейкстры. 3. Разработать и написать программу, которая генерирует 100 случайных слабо связных взвешенных орграфов с заданным числом вершин и дуг m, для каждого орграфа находит кратчайший путь между каждой парой вершин тремя алгоритмами и определяет время выполнения каждого алгоритма. Выполнить программу при n = 8, 9 и 10. Результат для каждого n представить в виде таблицы (табл. Таблица 4.8 Время выполнения алгоритмов Количество дуг в графе (n 2 + 3n) / 6 n 2 / 3 (n 2 – n) / 2 min среднее max min среднее max min среднее max Перебор простых цепей Метод ветвей и границ Алгоритм Дейкстры 239 Практическое занятие 4.6 Кратчайшие пути во взвешенном орграфе Цель занятия:изучить алгоритм Дейкстры нахождения кратчайших путей между вершинами взвешенного орграфа, научиться рационально использовать его при решении различных задач. Задания 1. Изучить алгоритм Дейкстры нахождения кратчайших путей между вершинами взвешенного орграфа. 2. Используя алгоритм Дейкстры, разработать и реализовать алгоритм решения задачи (см. варианты заданий. 3. Подобрать тестовые данные. Результат представить в виде диаграммы графа. |