Рейтинг@Mail.ru
Rambler's Top100




Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

реферат на тему: Aлгоритмы на графах

скачать реферат

До построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет. Докажем, что описанный алгоритм получает в точности минимальное решение. Для доказательства нам понадобится очень простое утверждение: Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро. Действительно, пусть добавлено ребро (u, v) “добавлено” означает, что ребро новое, что раньше его в дереве не было. Поскольку дерево является связанным графом, то существует цепь C(u, …, v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u, v) замыкает цепь, превращая ее в цикл. Теорема. Алгоритм ПримаКраскала получает минимальное остовное дерево. Доказательство. Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т.е. ранее не связанные. Этот граф связный, потому что после проведения 1-го ребра осталось n-1 разных цветов, …, после проведения (n-1)-го ребра остался один цвет, т.е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер и n вершин. Следовательно, граф есть остовное дерево. Осталось доказать, что оно имеет минимальную длину. Пусть {, , …, } ребра остовного дерева в том порядке как их выбирал алгоритм, т.е. . Предположим для простоты доказательства, что все ребра сети имеют разную длину, т.е. <<…< (1) Если полученное дерево не минимально, то существует другое дерево, заданное набором из n-1 ребер {, , …, }, такое что сумма длин меньше суммы длин . С точностью до обозначений <<…< (2) Может быть =, = и т.д., но так как деревья разные, то в последовательностях (1) и (2) найдется место, где ребра отличаются. Пусть самое левое такое место k, так что . Поскольку выбиралось по алгоритму самым малым из не образующих цикла с ребрами , , …, , то <. Теперь добавим к дереву (2) ребро ; в нем появится цикл, содержащий ребро и, может быть, какие-то (или все) ребра , , …, , но они сами не образуют цикла, поэтому в цикле будет обязательно ребро d из набора , …, , причем d>. Выбросим из полученного графа с одним циклом ребро d; мы снова получим дерево, но оно будет на d- короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами. Для реализации алгоритма понадобятся: Matrix матрица расстояний, значение пересечении i-ой строки и j-го столбца равно расстоянию между i-ой и j-ой вершинами. Если такого ребра нет то значение равно Infinity просто большому числу (машинная бесконечность); Color массив цветов вершин; Ribs в этом массиве запоминаются найденные ребра; a, b вершины, соединяемые очередным минимальным ребром len длина дерева. Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на первой строке количество вершин n, а остальные n строк по n чисел в каждой матрица расстояний. Если расстояние равно 1000 (Infinity), то такого ребра нет.

Program Algorithm_PrimaKrascala; Uses Crt; Const MaxSize =100; Infinity =1000; Var Matrix: array[1..MaxSize, 1..MaxSize] of integer; Color: array[1..MaxSize] of integer; Ribs: array[1..MaxSize] of record a, b: integer; end; n, a, b, k, col, i, len: integer;

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ





Procedure Init; Var f: text; i, j: integer; Begin Assign(f, 'INPUT.MTR'); Reset(f); Readln(f, n); For i:=1 to n do Begin For j:=1 to n do read(f, matrix[i, j]); Readln(f) End; For i:=1 to n do color[i]:=i; len:=0 End;

Procedure Findmin(var a, b: integer); Var min, i, j: integer; Begin min:=infinity; For i:=1 to n-1 do For j:=i+1 to n do If (Matrix[i, j]color[j]) then Begin min:=Matrix[i, j]; a:=i; b:=j End; len:=len+min end;

Begin Clrscr; Init; For k:=1 to n-1 do Begin Findmin(a, b); Ribs[k].a:=a; Ribs[k].b:=b; col:=Color[b]; For i:=1 to n do If color[i]=col then color[i]:=color[a]; End; For i:=1 to n-1 do Writeln(ribs[i].a, ' ', ribs[i].b); Writeln('Length= ', len); Readkey End. Для такого входного файла 8 0 23 12 1000 1000 1000 1000 1000 23 0 25 1000 22 1000 1000 35 12 25 0 18 1000 1000 1000 1000 1000 1000 18 0 1000 20 1000 1000 1000 22 1000 1000 0 23 14 1000 1000 1000 1000 20 23 0 24 1000 1000 1000 1000 1000 14 24 0 16 1000 35 1000 1000 1000 1000 16 0 программа напечатает: 13 57 78 34 46 25 12 Length= 125.

Алгоритм Дейкстры. Дана дорожная сеть, где города и развилки будут вершинами, а дороги ребрами. Требуется найти кратчайший путь между двумя вершинами. Можно предложить много процедур решения этой задачи, например, физическое моделирование такого рода: на плоской доске рисуется карта местности, в города и в развилки вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются веревками, которые привязываются к соответствующим кольцам. Чтобы найти кратчайшее расстояние между кольцом i и кольцом k, нужно взять i в одну руку, взять k в другую и растянуть. Те веревки, которые натянутся и не дадут разводить шире, и образуют кратчайший путь между i и k. Однако, математическая процедура, которая промоделирует эту физическую, выглядит очень сложно. Известны алгоритмы попроще, например, предложенный Дейкстрой еще в 1959 г. Этот алгоритм решает более общую задачу: В ориентированной, неориентированной или смешанной сети найти кратчайший путь из заданной вершины во все остальные вершины. Алгоритм использует три массива из n чисел каждый. Первый массив Visited содержит метки с двумя значениями: False (вершина еще не рассмотрена) и True (вершина уже рассмотрена); второй массив Len содержит расстояния от текущие кратчайшие расстояния от начальной до соответствующей вершины; третий массив C содержит номера вершин k-ый элемент C есть номер предпоследней вершины на текущем кратчайшем пути из начальной вершины в k-ю. Используется также Matrix матрица расстояний. Опишем алгоритм Дейкстры: 1 (инициализация). В цикле от 1 до n заполнить значением False массив Visited; заполнить числом i массив C (i номер стартовой вершины); перенести i-ю строку матрицы Matrix в массив Len; Visited[i]:=True; C[i]:=0; 2 (общий шаг). Найти минимум среди неотмеченных (т.е. тех к, для которых Visitid[k]=False); пусть минимум достигается на индексе j, т.е. Len[j]Len[k]; Затем выполнять следующие операции: Visited[i]:=True; если Len[k]>Len[j]+Matrix[j, k], то (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j) {Если все Visited[k] отмечены, то длина пути от до равна C[k]. Теперь надо перечислить вершины, входящие в кратчайший путь}. 3 (выдача ответа). {Путь от до выдается в обратном порядке следующей процедурой:} 3.1 z:=C[k]; 3.2 Выдать z 3.3 z:=C[z]. Если z =0, то конец, иначе перейти к 3.2. Теорема. Алгоритм Дейкстры корректен. Доказательство. Теорему докажем по индукции.

скачать реферат
1 2 3 4

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

Внимание! Студенческий отдых и мегатусовка после сессии!


Обратная связь.

IsraLux отзывы Израиль отзывы