Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Выделение минимального остовного дерева - файл деревья.doc


Выделение минимального остовного дерева
скачать (88.5 kb.)

Доступные файлы (1):

деревья.doc254kb.18.06.2007 16:08скачать

содержание

деревья.doc

Уфимский государственный авиационный технический университет

Кафедра АПРиС

Курсовая работа

по дискретной математике

«Выделение минимального остовного дерева»


Выполнила:

Габбасова Альфия

ИВТ-125

Проверил:

Ошмарин А.А.

Оглавление:


Цель работы 3

Введение 3

Теоретическая часть 3

Алгоритм выделения остовного дерева 6

Блок-схемы 8

Листинг программы 12

Тестирование программы. 14

2) Входящие данные: 15

15

Заключение 16

Список использованной литературы: 17
^

Цель работы


Целью данной работы является изучение и создание алгоритма решения задачи о составлении минимального остовного дерева, а так же разработка программы, реализующей этот алгоритм.

Введение


Теория графов это один из разделов дискретной математики, изучающий свойства графов. Теория графов имеет огромное практическое значение, к примеру маршрутизация данных.


^

Теоретическая часть



Рассмотрим чертеж вида


города


вершины

дороги

ребра


Обозначения и определения

V – множество точек – вершины;

X – множество линий – ребра;

Графом называется совокупность множеств вершин и ребер.

v - номер вершины;

{v,w} – обозначение ребра;

{v,v} – петли;

Одинаковые пары - параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

Пример: кратность = 3.
Если в графе есть петли и/или кратные ребра, то такой граф называют псевдографом.

Псевдограф без петель называется мультиграфом.

Мультиграф в котором ни одна пара не встречается более одного раза называется графом.

Если пары (v,w) являются упорядоченными, граф называется ориентированным (орграфом).

Ребра ориентированного графа называются дугами.

В неориентированном графе ребра обозначаются неупорядоченной парой - {v,w}.

В ориентированном графе дуги обозначаются упорядоченной парой - (v,w).

G, G0 - неориентированный граф, D, D0 – ориентированный.

Обозначают v,w - вершины, x,y,z – дуги и ребра.
Пример

1) V={v1, v2, v3, v4},

X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.














изолированная

вершина






висячая

вершина

2) V={v1, v2, v3, v4, v5},

X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.






















Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. (Для орграфа то же).

Подграф наз. собственным, если он отличен от самого графа.

Говорят, что вершина w орграфа D (графа G) достижима из верш. v, если либо w=v, либо существует путь (маршрут) из v в w.

Граф (орграф) наз связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.

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

Псевдографом, ассоциированным с ориентированным псевдографом D=(V,X) наз. псевдограф G=(V,X0), в котором X0 получается из X заменой всех упорядоченных пар (v,w) на неупорядоченные {v,w}.



Орграф наз слабо связным, если связным является ассоциированный с ним псевдограф.

Если граф (орграф) не является связным (слабо связным), то он наз. несвязным.

Компонентой связности графа G (сильной связности орграфа D) наз. его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа D).

Примеры.











опр || назовем орграф D=(V,X) нагруженным, если на множестве дуг X определена некоторая функция , которую называют весовой функцией

2

6

7

4

8

Числа – вес дуги, (цена дуги).

Для любого пути П нагруженного орграфа D обозначим через l(П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути. Если выбрать веса равными 1, то придем к ненагруженному графу.

^

Деревья и циклы


Граф G называется деревом, если он является связным и не имеет циклов. Граф G называется лесом, если все его компоненты связности - деревья.

Деревья обладают следующими свойствами:

1) Граф G есть дерево.

2) Граф G является связным и не имеет простых циклов.

3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

4)  две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл.
Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Предположим, что в графе G нет висячей вершины, тогда найдется цикл (в начале лекции это было доказано), тогда граф - не дерево.
Пусть G связный граф, а висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.
Пусть G - дерево с n-вершинами и m-ребрами. Тогда m(G)=n(G)-1.

Если m<n-1 то граф не связный.

Если m>n-1, и висячих вершин в графе нет, то можно выделить цикл, а следовательно, это – не дерево. В противном случае удалим висячую вершину вместе с инцидентным ей ребром. Повторяя эту операцию n-2 раза, придем к графу с двумя вершинами и более чем одним ребром  это не дерево.
Пусть G – дерево. Тогда любая цепь в G будет простой.

Если цепь – не простая, то в G есть циклы  G – не дерево.

Цепь единственна по той же причине.
Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n(G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер. Число называется цикломатическим числом графа G.

^

Алгоритм выделения остовного дерева


1) Выберем в G произвольную вершину , которая образует подграф, являющийся деревом. Положим i=1.

2) Если i=n(G), то задача решена и Gi – искомое остовное дерево графа G. Иначе переходим к п. 3.

3) Пусть уже построено дерево являющееся подграфом графа G, в которое входят вершины , где . Строим граф , добавляя к графу Gi новую вершину , смежную с некоторой вершиной графа и новое ребро . Во-первых, это можно всегда сделать, поскольку граф связен. Во-вторых, - дерево, т.к. если в не было циклов, то и в их не могло появиться.

Присваиваем i:=i+1 и переходим к шагу 2).
Замечание. Остовное дерево может быть выделено, вообще говоря, не единственным способом.

Если граф – нагруженный, то можно выделить остовное дерево с минимальной суммой длин содержащихся в нем ребер.

^ Алгоритм выделения минимального остовного дерева нагруженного графа.
Существует 2 алгоритма для выделения минимального остовного дерева в нагруженном графе: алгоритм Прима и алгоритм Краскала.
^ Алгоритм Краскала

Идея алгоритма. Искомые ребра соединяют вершины. Поэтому возможны две стратегии построения. Можно идти от вершин и для каждой из них искать минимальное ребро (как это сделано в алгоритме Прима) а можно для каждого ребра выяснять можно ли его включить в строящееся дерево. Алгоритм Краскала предлагает делать это следующим образом. Во-первых, ребра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с первого проверяем соединяет или нет оно две несвязные вершины, если да, то его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то работа алгоритма начинается с V несвязных компонент графа (пока из графа все ребра исключаем). Для того, чтобы их связать необходимо найти V-1 ребро.

Другими словами, алгоритм организует процесс роста компонент связности в процессе которого он объединяются друг с другом до тех пор пока не останется одна являющаяся конечным результатом.
Алгоритм.

  • Создаем список ребер по возрастанию.

  • Создаем множество компонент связности, каждая из которых содержит ровно одну вершину.

  • Пока компонент связности больше чем одна.

    • Взять ребро из начала списка ребер.

    • Если ребро соединяет две разных компоненты связности то

      • Компоненты связности объединить в одну.


Алгоритм Прима

Идея алгоритма. Пусть часть остовного дерева уже построена. Это утверждения всегда верно, так как в начале процесса вершина с которой начинается построение уже входит в дерево. Итак если часть основного дерева уже есть, то множество вершин графа можно разделить на два подмножества: подмножество состоящее из вершин уже построенного остовного дерева и оставшихся вершин графа.

Очевидно, что среди ребер соединяющихся эти два множества существует ребро наименьшего веса. Можно доказать, (но мы здесь этого делать не будем) что минимальное дерево проходит через это ребро.
Алгоритм.

  • Множество остовных вершин – исходная веришны

  • Множество оставшихся - все вершины за исключением исходной.

  • Пока множество оставшихся не пусто

    • Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.

    • Для найденного ребра, вершину принадлежащую множеству оставшихся:

      • Вычеркиваем из множества оставшихся.

      • Добавляем к множеству остовных.


Блок-схемы


В данной работе представлена программа для реализации алгоритма Прима.

























^

Листинг программы


#include <stdio.h>

#include <algorithm.h>

#include <conio.h>
const int MaxN = 101;
int n, m, s;
struct Tedge { int a, b, c; } R[MaxN * MaxN];

bool U[MaxN * MaxN];

int P[MaxN];
bool operator <(const Tedge& a, const Tedge& b) {

return a.c < b.c;

}
int get(int x)

{

if (P[x] != x) P[x] = get(P[x]);

return P[x];

}
void Join(int x, int y)

{

x = get(x);

y = get(y);

if (x == y) P[x] = y; else P[y] = x;

}
int main()

{

freopen("input.txt", "r", stdin);

scanf("%d%d", &n, &m);

for (int i = 1; i <= m; i++)

scanf("%d%d%d", &R[i].a, &R[i].b, &R[i].c);
sort(R, R + m);

memset(U, 0, sizeof(U));
s = 0;

for (int i = 1; i <= n; i++) P[i] = i;

for (int i = 1; i <= m; i++)

if (get(R[i].a) != get(R[i].b)) {

Join(R[i].a, R[i].b);

s += R[i].c;

U[i] = true;

}
printf("Ves dereva raven = %d\n", s);

printf("V derevo vhodat rebra:\n");

for (int i = 1; i <= m; i++)

if (U[i]) printf("%d %d\n", R[i].a, R[i].b);
getch();

return 0;

}

^




Тестирование программы.


1) Входящие данные:






Результат:


^



2) Входящие данные:









Результат:

Заключение


В курсовой работе был реализован алгоритм для выделения минимального остовного дерева. По данному алгоритму была составлена программа, работа которой была продемонстрирована.
^

Список использованной литературы:



Кузнецов О.П. Дискретная математика для инженера, 3-е изд., перераб. и доп. – СПб: Издательство «Лань», 2004.


Скачать файл (88.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации