![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Методические указания к лабораторной работе 1Содержание книги
Поиск на нашем сайте
Понятие графа
Графом G=(X,U) называется пара двух конечных множеств: Х – множество точек (вершин) и U – множество линий (ребер), соединяющих некоторые пары точек. Если граф имеет ребро, у которого начало и конец совпадают, то это ребро называется петлей. Если ребро графа имеет направление, то оно называется дугой.
1.3.2 Виды графов
Существуют следующие виды графов: 1) Граф, состоящий из вершин и соединяющих их ребер, называется неориентированным (н-граф); 2) Граф, состоящий из вершин и соединяющих их дуг, называется ориентированным (орграф); 3) Ребра, соединяющие одну и ту же пару вершин, называются параллельными или кратными. Граф, содержащий кратные ребра называется мультиграфом; 4) Граф, в котором проведены все возможные ребра, но не имеющий петель и кратных ребер, называется полным; 5) Граф, содержащий как ребра, так и дуги называется смешанным;
1.3.3 Матричное представление графа
Матрицей смежности графа G - называется квадратная матрица порядка n, где n – число вершин графа G и определяется следующим образом:
Аnxn=[аij] = 1 – есть ребро (дуга) (хi; хj) или петля;
0 – нет ребра (дуги) (хi; хj).
Матрицей ициденции графа G с n вершинами и m дугами называется матрица
Вnxm=[bij] = -1, если хi – конец дуги (хi; xj), 0, если нет дуги (хi; xj).
В матрицу инциденции н-графа заносят 1, если ребро инцидентно соответствующей вершине, 0 – в противном случае.
Путь – это упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны.
Матрицей достижимости графа G называется квадратная матрица порядка n, где n – число вершин графа и определяется следующим образом:
1, если есть путь из хi в xj, Dnxn=[dij] = 0, если нет пути из хi в xj.
Граф не содержащий циклов называется ациклическим. Связанный ациклический граф называется деревом. Н-граф называется неориентированным деревом, если он связан и не содержит циклов, а значит петель и кратных рёбер. Дерево – это минимально связный граф, в том смысле, что при удалении хотя бы одного ребра он теряет связность.
Теорема: В дереве с n вершинами всегда n-1 ребро.
Ориентированным деревом или ордеревом, или корневым деревом называют орграф со следующими свойствами: 1) Существует единый узел, полустепень захода которого равна нулю, он называется корнем дерева; 2) Полустепень захода всех остальных узлов равна единице; 3) Каждый узел достижим из корня.
Остовом графа называется подграф являющийся деревом. Если граф полный, то в графе существует
1.3.4 Алгоритм Краскала
1) Строится нуль-граф (одни вершины без ребер). 2) Упорядочиваются ребра графа в порядке не убывания их весов. 3) Выбираются из упорядоченного списка ребра, такие чтобы они не образовывали цикл в графе. 4) Если выбрано n-1 ребро (n – число вершин графа), то алгоритм заканчивает работу. 5) Остов должен включать в себя все вершины графа.
Пример: Найти кратчайший остов в графе (рисунок 1) алгоритмом Краскала. X1 2 X2
X6 4 4 3 X3 44 4 1 1 X5 6 X4
Рисунок 1 – Взвешенный граф
Решение:
1) Построим таблицу ребер данного графа, в порядке неубывания их весов (таблица 1).
Таблица 1 – Список ребер графа в порядке неубывания весов
2) Из таблицы 1 выбираем ребра, которые не образуют цикл в графе и строим кратчайший остов (рисунок 2).
X1 X2 X6 X3
Х5 X4
Рисунок 2 – Кратчайший остов графа
3) Вычислим длину кратчайшего остова: d = 1+1+2+3+3 = 10
Для реализации алгоритма Краскала на ПК необходимо: 1) Построить матрицу смежности исходного графа; 2) Составить список ребер с их весами и отсортировать их одним из способов сортировки. Для того чтобы уменьшить время сортировки можно сортировать не весь список, а N-1 ребро, с минимальным весом; 3) Для проверки на цикл можно использовать построение матрицы достижимости после каждого добавления ребра. Добавляем ребро XiXj, смотрим есть ли единица в матрице достижимости на месте XiXj, если есть, то ребро XiXj не перебрасываем в матрицу смежности исходного остова, так как получаем цикл, если единицы нет, то ребро XiXj заносим в матрицу смежности остова.
1.3.5 Алгоритм Прима Данный алгоритм определяет кратчайший остов в графе. Суть данного метода заключается в том, что построение кратчайшего остова выполняется путем добавления к строящемуся остову некоторой ближайшей к нему вершины и соответствующего ребра. Обозначения: Ts – множество вершин строящегося остова As – множество ребер строящегося остова
Для вершины Х1 делаем пометку Х1*. Выписываем связи всех остальных вершин с помеченной вершиной: [помеченная вершина; вес] – если связь есть или [0;¥] – если связи нет. Среди имеющихся связей выбираем вершину, которая имеет с помеченной вершиной наименьшее соединение. Такую вершину добавляем к множеству Ts, а соответствующее ребро к множеству As. Алгоритм заканчивает свою работу, если n=N(Ts), где n – количество вершин графа, N(Ts) – количество вершин остова.
Пример: Найти кратчайший остов в графе (рисунок 3) алгоритмом Прима.
Х1 7 6 Х3 8 Х5 6 11 5 3 7 Х4 Х6 4 2 Х7
Рисунок 3 – Граф с весами
Решение: 1) Выписываем связи вершин графа с помеченной вершиной: X1*: X2*: X3*: x2-[x1; 2]-min x3-[x2; 6]-min x4-[x3; 6]-min x3-[0, ¥] x4-[0, ¥] x5-[0, ¥] x4-[0,¥] x5-[x2; 7] x6-[0, ¥] x5-[x1; 8] x6-[0, ¥] x7-[0, ¥] x6-[x1; 11] x7-[0, ¥] x7-[0,¥]
X4*: X7*: X6*: x5[x4; 5] x5[0, ¥] x5[x6; 3]-min x6[x4; 7] x6[x7; 2]-min x7[x4; 4]-min
Ts = {x1, x2, x3, x4, x7, x6, x5} As = { (x1;x2), (x2;x3),(x3;x4),(x4;x7),(x7;x6),(x6;x5)}
2) Используя найденные множества Ts и As, построим кратчайший остов данного графа (рисунок 4).
Х2 Х1 Х3
Х5 Х4 Х6 Х7
Рисунок 4 – Кратчайший остов графа
3) Найдем длину получившегося остова: d = 2+6+6+4+2+3 = 23
Задание для лабораторной работы 1 Составить постановку задачи, выбрав предметную область (составить граф не менее чем из 8 вершин). Решить задачу алгоритмами Краскала и Прима аналитически; Составить программу решения задачи в среде программирования Delphi (Реализация одного алгоритма - оценка «3» или «4»; реализация двух алгоритмов – оценка «5»);
1.5 Контрольные вопросы к защите лабораторной работы 1
1) Что называется графом? Приведите пример. 2) Какие графы называются ориентированными? Какие графы – неориентированные? 3) Какой граф называется взвешенным? 4) Что называется матрицей смежности, матрицей инциденции, матрицей достижимости. 5) Что называется полным графом? Какая закономерность между вершинами и ребрами в полном графе? 6) Что называется деревом? Приведите пример. 7) Что называется остовом? Приведите пример. 8) Какое количество остовов в полном графе? 9) Что называется кратчайшим остовом? 10) Что называется циклом в графе? 11) Алгоритм Краскала. 12) Алгоритм Прима.
|
|||||||||||||||||||
Последнее изменение этой страницы: 2017-02-07; просмотров: 252; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.216.30 (0.008 с.) |