Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Построение минимального остовного дерева графа методом Прима

Название: Построение минимального остовного дерева графа методом Прима
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 15:57:52 23 апреля 2011 Похожие работы
Просмотров: 4205 Комментариев: 3 Оценило: 2 человек Средний балл: 3.5 Оценка: неизвестно     Скачать

Пояснительная записка

к курсовому проекту

тема: Построение минимального остовного дерева графа методом Прима


Введение

При проектировании железных дорог, линий электропередачи и других линий коммуникации возникает проблема построения сети с минимальными затратами. В теории графов такая задача успешно решается путем построения минимального остовного дерева неориентированного графа. Данная задача имеет несколько методов решения. Один из них – алгоритм Прима. Суть этого метода заключается в последовательном добавлении к остову минимального, «безопасного» ребра (ребра, которое не образует цикла). В данной работе представлена программа, базирующаяся на алгоритме Прима, которая вычисляет минимальное остовное дерево неориентированного графа и делает визуализацию графа.


1. Историческая справка

Известный алгоритм построения минимального остовного дерева восходит к Войтеху Ярнику (Vojtech Jarnik) [1930]. Он больше известен под именем алгоритма Прима (Robert Prim). Р. Прим независимо от Ярника придумал его в 1956 и представил более подробное и детальное описание, чем первооткрыватель. Еще раз этот алгоритм открыл Эдсгер Дейкстра (Edsger Wybe Dijkstra) в 1958 году, но название осталось за Примом, т. к. у Дейкстры уже был алгоритм с его именем (поиск кратчайших путей в ориентированном графе). Этот алгоритм можно отнести к группе алгоритмов, построенных на наращивании дерева: существует только одна нетривиальная компонента (остальные представляют собой одиночные вершины), и она постепенно наращивается добавлением «безопасных» ребер. Время работы алгоритма Джарника-Прима может достигать O (E+VlogV) при использовании фибоначчиевых куч.

2. Построение минимального остовного дерева

Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева с использованием жадной стратегии. Итак, пусть дан связный неориентированный граф G (V ; E ) c n вершинами и весовая функция w : ER .

Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G , который называется промежуточным остовным лесом . Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e =(u , v ) выбирается так, чтобы не нарушить этого свойства: A ∪ {e } тоже должно быть подграфом минимального. Такое ребро называется безопасным .

Вот как выглядит общий алгоритм построения минимального остовного дерева:

MST-GENERIC (G, w)

1: A ← 0

2: while (пока) A не является остовом

3: do найтибезопасноеребро (u , v ) ∈E дляA

4: AA ∪ {(u , v )}

5: return A

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

Далее приводится общее правило отыскания безопасных ребер. Для этого доказана теорема, которая поможет находить безопасные ребра. Предварительно докажем маленькую лемму:

Лемма: пусть Т – минимальное остовное дерево. Тогда любое ребро е из T – безопасное.

Док-во: в Т – (n-1) ребро. На каждом шаге Generic-MST мы добавляли одно безопасное ребро. Всего выполнено (n-1) шагов, следовательно, все ребра в T – безопасные по определению.

Теорема: Пусть G (V; E) – связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А – некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда ребро минимального веса из E(K) будет безопасным.
Док-во: Пусть e =(u , v ) – минимальное по весу ребро из E (K ). Пусть минимальный остов T не содержит e (в противном случае доказываемое утверждение очевидно по приведенной выше лемме). Т.к. T связен, в нем существует некоторый (единственный) ациклический путь p из u в v , и e замыкает его в цикл. Поскольку один из концов e лежит в K , а другой в V \ K , в пути p существует хотя бы одно ребро e' =(x , y ), которое обладает тем же свойством. Это ребро не лежит в A , т. к. в A пока что нет ребер между K и V \ K . Удалим из T ребро e' и добавим e . Так как w (e' ) < w (e ), мы получим остовное дерево T' , суммарный вес которого меньше суммарного веса T . Таким образом, T не является минимальным остовом. Противоречие. Следовательно, T содержит e .

В связи с приведенной теоремой введем следующее

Определение. Безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.

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

Как и алгоритм Краскала, алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро. Алгоритм Прима относится к группе алгоритмов наращивания минимального остова: на каждом шаге существует не более одной нетривиальной (не состоящей из одной вершины) компоненты связности, и каждый к ней добавляется ребро наименьшего веса, соединяющее вершины компоненты с остальными вершинами. По теореме такое ребро является безопасным.

При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r – вершина, на которой будет наращиваться минимальный остов. Все вершины G , еще не попавшие в дерево, хранятся в очереди с приоритетом Ω. Приоритет вершины v определяется значением key[v ], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p[v ] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на ноду дерева, в которою ведет ребро с весом key[v ] (одно из таких ребер, если их несколько).

Тогда алгоритм Прима выглядит следующим образом:

MST-PRIM (G , w , r )

1: Ω ← V [G ]

2: foreach (для каждой) вершины u ∈ Ω

3: do key[u ] ← ∞

4: key[r ] ← 0

5: p[r ] = NIL

6: while (пока) Ω ≠ 0

7: do u ← EXTRACT-MIN(Ω)

8: foreach (для каждой) вершины v ∈Adj(u )

9: do if v ∈Ωиw (u , v ) < key[v ] then

10: p[v ] ← u

11: key[v ] ← w (u , v )

На рисунках 1–8 показана схема работы алгоритма Прима с корнем r.


Рисунок 1 – Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер

Рисунок 2 – Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.

Рисунок 3 – Следующее безопасное ребро с весом 11. Добавляем его


Рис. 4

Рисунок 5

Рисунок 6

Рисунок 7


Рисунок 8 – Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Время работы алгоритма Прима зависит от того, как реализована очередь с приоритетами Ω. Если использовать двоичную кучу, инициализацию в строках 1–4 можно выполнить за время O(V ). Далее цикл выполняется |V | раз, и каждая операция EXTRACT-MIN занимает время O(V logV ). Цикл for в строках 8–11 выполняется в общей сложности O(E ), поскольку сумма степеней вершин графа равна 2|E |. Проверку принадлежности в строке 9 можно выполнить за время O(1), если хранить состояние очереди еще и как битовый вектор размера |V |. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (DECREASE-KEY), которая для двоичной кучи может быть выполнена за время O(logV ). Таким образом всего получаем O (V logV +E logV )=O(E logV ).

Лучшую оценку можно получить, если использовать фибоначчиевы кучи. С помощью фибоначчиевых куч можно выполнить операцию EXTRACT-MIN за учетное время O(logV ), а операцию DECREASE-KEY – за учетное время O(1). В этом случае суммарное время работы алгоритма Прима составит O (E +V logV ).

4. Составление программы

алгоритм остовной дерево программа

Интерфейс программы (приложение А, В) должен быть следующим. Сначала пользователь вводит порядок графа, чтобы программа могла сформировать таблицу ввода данных (матрица весов) с соответствующим количеством строк и столбцов. При этом все кнопки, кроме кнопки «Сделать таблицу» недоступны для пользователя. Затем пользователь вводит в таблицу данные, при этом он может оставлять пустые ячейки в таблице. Программа будет интерпретировать это как отсутствие ребра между вершинами. Когда данные будут введены, нужно нажать на кнопку «Рассчитать дерево», которая после создания программой таблицы станет активной. Программа рассчитает матрицу весов для минимального остовного дерева и нарисует искомый граф (длины ребер графа не будут соответствовать матрице весов). При этом таблица ввода и все кнопки, кроме кнопки «Продолжить», станут недоступны для пользователя. При нажатии на эту единственную активную кнопку программа перейдет в исходное состояние.

Теперь о том, как программа реализует алгоритм Прима.

Сначала программа создает некий массив a[10] [10] (предполагается, что число вершин графа меньше или равно 10). Этот массив инициализируется: каждому a[i] [j] присваивается 1000 (предполагается, что максимальная длина ребра меньше 1000). Потом данные из таблицы ввода копируются в массив. При этом если в ячейке таблицы ничего не содержится в массив ничего не копируется. Затем делается цикл, который прерывается только тогда, когда все элементы массива станут снова равны 1000. Как работает цикл? Сначала находится минимальный элемент массива (из области выше главной диагонали матрицы ввода). Он запоминается (переменная buf) и ему присваивается 1000. Согласно алгоритму Прима, если ребро подходящее минимальный элемент вычеркивается, а цикл начинается с начала. Подходящее ребро или нет? Ответ на этот вопрос находится следующим образом. Создается массив в n элементов. Каждый элемент равен 1 или 0. Когда вершина включается в дерево, в элемент массива с ее номером записывается 1 (изначально все элементы массива, кроме первого равны 0). Чтобы определить подходящее ребро или нет, нужно посмотреть, находятся ли единицы в массиве (номера элементов равны номерам вершин ребра). Если номерам вершин ребра соответствуют обе единица, значит, ребро не подходящее. Если это условие не выполняется – ребро подходящее. Алгоритм прекращает работу, когда все вершины включены в новый граф.

Отдельно можно выделить процедуру рисования графа. Программа создает двумерный массив координат вершин графа (krug[2] [10]). Вершины располагаются на окружности на одинаковом расстоянии друг от друга. Такой способ очень удобный, потому что не надо беспокоиться о том, что ребра будут наслаиваться одно на другое.

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

Тестирование программы проводилось на самых разных вариантах матрицы весов. В процессе тестирования ошибок не обнаружено.

Программа тестировалась на следующих примерах:

Матрица весов

2 4
3

Выдан результат

2
3

Матрица весов

2 3

Выдан результат

2 3

Матрица весов

3 5
4
1

Выдан результат

3
4

Матрица весов

6 5 3
2 5
6

Выдан результат

5 3
2

Матрица весов

5 6 4 7 8 5
8 5 19 6 9
2 8 7 10
7 3 8
6 7
5

Выдан результат

5 4 5
2
3
6

На рисунке 9 изображен результат работы программы

Рисунок 9 – Окно программы


Заключение

В ходе проделанной работы была написана программа, реализующая алгоритм Прима. В результате программа выдает матрицу весов минимального остовного дерева графа, и изображает полученный граф.


Список использованных источников

1. http://works.tarefer.ru

2. http://www.intuit.ru

3. http://www.offzone.litehosting.ru

Приложение А

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

// –

#include <vcl.h>

#pragma hdrstop

#include «Unit21.h»

// –

#pragma package (smart_init)

#include «math.h»

#pragma resource «*.dfm»

TForm1 *Form1;

int n=3;

// –

__fastcall TForm1:TForm1 (TComponent* Owner)

: TForm(Owner)

{

}

// –

void __fastcall TForm1: Button1Click (TObject *Sender)

{

n=StrToInt (Edit1->Text);

StringGrid1->ColCount=n;

StringGrid1->RowCount=n;

StringGrid2->ColCount=n;

StringGrid2->RowCount=n;

StringGrid1->Visible=true;

BitBtn1->Enabled=true;

Button1->Enabled=false;

}

// –

void __fastcall TForm1: BitBtn1Click (TObject *Sender)

{

BitBtn2->Enabled=true;

BitBtn1->Enabled=false;

Button1->Enabled=false;

StringGrid2->Visible=true;

int a[10] [10];

int mas[3] [10];

int kmas=0;

int versh[10];

for (int i=0; i<n; i++)

versh[i]=0;

versh[1]=1;

for (int i=0; i<n; i++)

for (int j=0; j<n; j++)

a[i] [j]=1000;

// *******

for (int i=0; i<n; i++)

for (int j=0; j<n; j++)

if (StringGrid1->Cells[i] [j]!=»») a[i] [j]=StrToInt (StringGrid1->Cells[i] [j]);

// **********

int k=n-1;

while (k!=0)

{

int buf=1000;

int x, y;

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

for (int j=0; j<i; j++)

{

if ((a[i] [j]<buf) && ((versh[i]==1) || (versh[j]==1)) && (versh[i]!=versh[j]))

{buf=a[i] [j]; x=i; y=j;}

}

if (versh[x]==1) versh[y]=1; else versh[x]=1;

a[x] [y]=1000;

mas[0] [kmas]=x;

mas[1] [kmas]=y;

mas[2] [kmas]=buf;

kmas++;

// *****

k –;

}

/// ***********************

for (int i=0; i<kmas; i++)

StringGrid2->Cells [mas[0] [i]] [mas[1] [i]]=IntToStr (mas[2] [i]);

// **********

// рисование

int krug[2] [10];

Form1->Canvas->Pen->Color=clBlack;

for (int i=0; i<n; i++)

{

krug[0] [i]=400+100*sin (6.28*i/n);

krug[1] [i]=400+100*cos (6.28*i/n);

}

for (int i=0; i<kmas; i++)

{

Form1->Canvas->MoveTo (krug[0] [mas[0] [i]], krug[1] [mas[0] [i]]);

Form1->Canvas->LineTo (krug[0] [mas[1] [i]], krug[1] [mas[1] [i]]);

}

}

// –

void __fastcall TForm1: BitBtn2Click (TObject *Sender)

{

Button1->Enabled=true;

StringGrid1->Visible=false;

StringGrid2->Visible=false;

BitBtn2->Enabled=false;

Form1->Canvas->Pen->Color=clBtnFace;

Form1->Canvas->Rectangle (295, 295,505, 505);

}

Программа тестировалась на следующих примерах:

Приложение Б

Инструкция пользователя

Ограничения программы:

– количество вершин графа не более 10;

– длина ребра – целое положительное число, меньше 1000.

Порядок работы:

1) Пользователь вводит количество вершин графа

2) Нажимается кнопка «Сделать таблицу»

3) Вводятся данные в таблицу

4) Нажимается кнопка «Рассчитать дерево»

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

5) Если пользователь хочет продолжить работу с программой, он должен нажать на кнопку «Продолжить»

Программа вернется в исходное состояние

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:04:43 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:31:39 29 ноября 2015
а где сама прога ?
18:00:57 16 октября 2011Оценка: 2 - Плохо

Работы, похожие на Курсовая работа: Построение минимального остовного дерева графа методом Прима
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
Тогда говорят, что ребро E инцидентно вершинам a и b. И обратно - вершины a и b инцидентны ребру E.
5 в качестве дополнительного творческого задания создать приложение на Delphi для реализации алгоритма ближайшего соседа, алгоритма Прима, алгоритма Уоршелла, алгоритма Дейкстры ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4172 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Задача остовных деревьев в k-связном графе
... Молдова Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: "Задача остовных деревьев в k-связном ...
Для произвольной вершины x графа G через dG(x) мы будем обозначать степень вершины x в графе G(V, E). Для x V, A V через dG(x, A) обозначим количество ребер, соединяющих вершину x ...
Таким образом, в графе Ti* ровно mi-1 цикл, причем не трудно заметить, что каждый из этих циклов проходит через вершину z. Следовательно, из графа Ti* можно удалить mi-1 ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1728 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Исследования в современном управлении
СОДЕРЖАНИЕ 1. ИССЛЕДОВАНИЯ В СОВРЕМЕННОМ УПРАВЛЕНИИ.. 5 1.1 Предпосылки исследования систем управления.. 5 1.2 Системный анализ как средство ...
В дальнейшем под деревом взаимосвязей будем понимать связный, неориентированный граф, вершины которого интерпретируются как элементы дерева, а ребра - как связи между ними.
Множество ребер R={rjiz} графа G обозначают взаимосвязи между элементами, из которых выходит ребро, и элементами, в которые оно входит. j - номер элемента i-го уровня, из которого ...
Раздел: Рефераты по менеджменту
Тип: учебное пособие Просмотров: 5168 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Алгоритмический язык Паскаль
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ им. А.В. ЛУНАЧАРСКОГО КАФЕДРА ИНФОРМАТИКИ Дипломная ...
Выделяют из всех деревьев так называемые УПОРЯДОЧЕННЫЕ деревья - такие, у которых ребра (т.е. соответствующие им элементы), выходящие из каждой вершины, упорядочены по какому-либо ...
Так, если дерево упорядочено по возрастанию, это означает, что самое левое ребро на графе заполнено наименьшим числом.
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 2870 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 4 Оценка: неизвестно     Скачать
Эйлеровы и гамильтоновы графы
Министерство народного образования Республики Дагестан Дагестанский Государственный Университет Курсовая работа Программирование задач на графах ...
Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер: v0,e1, . en,vn, в которой любые два соседних элемента инцидентны.
Возьмём произвольную пару вершин j,k. Исключим непосредственное ребро D[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j,.,k. Пусть это расстояние ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 6748 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать
Проектирование трансляторов
ЛЕКЦИЯ 1 СУЩНОСТЬ ПРЕДМЕТА. СОДЕРЖАНИЕ КП. СРОКИ. ОРГАНИЗАЦИЯ РАБОТ. МАТЕМАТИЧЕСКИЙ АППАРАТ. СТРУКТУРНАЯ СХЕМА ТРАНСЛЯТОРА. ПРОХОДЫ ТРАНСЛЯТОРА ...
справочной таблице или форматирование вершины в дереве разбора)
Пусть int i,j;
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 655 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
AGraph: библиотека классов для работы с помеченными графами
1. Актуальность разработки библиотек для работы с графами К настоящему времени накоплен большой опыт решения теоретико-графовых задач на ЭВМ ...
В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на ...
Одна из проблем, которые возникают при разработке универсальной библиотеки для работы с графами - как реализовать поддержку различных видов графов: ориентированных и ...
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 1852 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Основы C
Кафедра: Автоматика и Информационные Технологии ОСНОВЫ С ОГЛАВЛЕНИЕ Введение Глава 1. Основы языка Си 1.1. Алфавит 1.2. Основные конструкции Си 1.3 ...
extern int min(int, int, int); /*находит минимальное значение из 3*/
Если в селении i расположить пункт скорой помощи, то поездка по вызову в селение j займет время a[i,i]+a[i,j], где 1<=i,j<k,i не равно j. Найти номер селения i, поездка от которого ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 1161 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Прикладной системный анализ: ... проектов, метод прогнозного графа
В.К. Буторин, В. В. Карпов ПРИКЛАДНОЙ СИСТЕМНЫЙ АНАЛИЗ: СЕТЕВОЙ АНАЛИЗ И КАЛЕНДАРНОЕ ПЛАНИРОВАНИЕ ПРОЕКТОВ, МЕТОД ПРОГНОЗНОГО ГРАФА Кемерово 2002 УДК ...
D E J
Ориентированные дуги графа интерпретируют работы, а вершины графа - цели экспертов.
Раздел: Рефераты по экономико-математическому моделированию
Тип: книга Просмотров: 3695 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Курсовая работа: Построение минимального остовного дерева графа методом Прима (10305)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150310)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru