Банк рефератов содержит более 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)

Курсовая работа: Нахождение минимального остовного дерева алгоритмом Краскала

Название: Нахождение минимального остовного дерева алгоритмом Краскала
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 05:00:39 23 марта 2011 Похожие работы
Просмотров: 6109 Комментариев: 2 Оценило: 1 человек Средний балл: 4 Оценка: неизвестно     Скачать

Содержание

Введение

1. Постановка задачи

2. Методы решения данной проблемы

3. Описание алгоритма Краскала

4. Пример работы алгоритма Краскала

5. Код программы

6. Обзор работы программы

Заключение

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

Введение

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

Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной.

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

Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них перечислены ниже:

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

· Алгоритм Краскала;

· Алгоритм Борувки.

1. Постановка задачи

Пусть имеется связный неориентированный граф G, на ребрах которого задана весовая функция c (e). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом (spanning-tree) этого графа (иногда используют термин остовное дерево или остов). Весом остовного дерева будем считать сумму весов всех его ребер. Тогда возникает задача о нахождении максимального покрывающего дерева, т.е. такого, что его вес наибольший, либо равен весу любого из покрывающих деревьев для данного графа. Будем обозначать наибольшее покрывающее дерево графа G как MAX (G).

2. Методы решения данной проблемы

Остовным деревом графа называется дерево, содержащее все вершмины V графа. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер.

Идея решения:

Для остовного дерева верно следующее свойство:

Пусть G= (V,E) - свызный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через U подмножество множества вершин V. Если (u,v) - такое ребро наибольшей стоимости, что u из U и v из V\U, тогда для графа G существует остовное дерево максимальной стоимости, содержащее ребро (u,v)

На этом свойстве основан алгоритм Прима. В этом алгоритме строится множество вершин U, из которого "вырастает" остовное дерево. Пусть V={1,2,. n}. Сначала U={1}. На каждом шаге алгоритма находится ребро наименьшей стоимости (u,v) такое, что u из U и v из V\U, затем вершина v переносится из множества V\U в множество U. Процесс продолжается до тех пор, пока множество U не станет равным множеству V.

Детали реализации:

Удобно выбрать представление в виде списка дуг.

Допустим, необходимо проложить кабель по территории университета, связав все его здания, так, чтобы из каждого здания кабель по какому-либо пути доходил до любого другого здания. Кроме того, предположим, что надо минимизировать общую длину прокладываемого кабеля. Если рассматривать здания как вершины, а кабели между зданиями как ребра, то эта работа с прокладыванием кабеля превращается в задачу определения каркаса, охватывающего здания территории университета, в котором общая длина проложенного кабеля должна быть минимальной. Такую задачу называют нахождением каркаса минимального веса. В нашей работе длина проложенного кабеля должна быть максимальной.

Определим понятие каркаса более формально. Если дан связный неориентированный граф G= (V, E), то каркас (также называемый остовным или стягивающим деревом) T= (V, E’), где E’ÍE - это связный граф без циклов. Иными словами, каркас неориентированного графа G - это подграф графа G, дерево, содержащее все вершины графа. Понятно, что для того, чтобы T имело тот же набор вершин, что и связный граф G, и чтобы T не имело циклов, оно должно содержать ровно |V|-1 ребро.

Предположим, что для каждого ребра eÎE существует вес w (e), причем такой вес может выражать, например, цену, длину или время, необходимое для прохода по ребру (в нашем примере - длину кабеля между зданиями). Во взвешенном графе вес подграфа - это сумма весов его ребер. Тогда каркас T максимального веса - это каркас G, в котором вес дерева максимален относительно всех остовных деревьев G.

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

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

В алгоритме Краскала используется жадный подход к решению задачи, т.е. в любой момент выполнения данных алгоритмов существует множество ребер E’, представляющее подмножество некоторого минимального остовного дерева графа G. На каждом шаге алгоритмов из оставшихся ребер выбирается "лучшее" ребро, обладающее определенными свойствами, и добавляется к формируемому каркасу максимального веса. Одним из важных свойств любого ребра, добавляемого к E’, является его безопасность, т.е. то, что обновленное множество ребер E’ будет продолжать представлять подмножество некоторого минимального остовного дерева.

3. Описание алгоритма Краскала

Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

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

Алгоритм состоит из следующей последовательности действий:

1. Создается список ребер R, содержащий длину ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево.

2. Данный список упорядочивается в порядке возрастания длин ребер.

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

4. Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

Или в терминах теории графов:

Дан граф с n вершинами; длины ребер заданы матрицей. Найти остовное дерево максимальной длины.

В задаче Прима-Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение.

Как известно (это легко доказать по индукции), дерево с nвершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.

А как следить, чтобы новое ребро не образовывало цикла со старыми? Сделать это просто. До построения дерева окрасим каждую вершину 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- короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.

4. Пример работы алгоритма Краскала

Рисунок 1. Начальный граф

Рисунок 2. Максимальное остовное дерево.

В алгоритме Краскала мы не храним массив used [N]. Вместо этого мы будем на каждой итерации алгоритма проверять, принадлежат ли концы рассматриваемого ребра к разным компонентам связности (и добавлять ребро к каркасу, если это так).

Введем счетчик int counter = 0. Пусть N - количество вершин графа.

Упорядочим список ребер по возрастанию веса.

Если counter == N - 1, закончим выполнение алгоритма.

Проходя по списку ребер, найдем ребро (i, j) такое, что i и j принадлежат разным компонентам связности. Так как список упорядочен по возрастанию веса ребер, мы будем выбирать ребро с максимальным весом, удовлетворяющее условию.

Добавим это ребро в каркас, увеличим на единицу счетчик counter.

Перейдем к шагу 2.

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

5. Код программы

// ---------------------------------------------

#include <stdio. h>

#include <conio. h>

#include <iostream. h>

// -------------------------------------------

typedef int* tint; // указатель на int

void main ()

{ // int max=100; // Максимальный вес ребра

int n; // количество вершин

tint* G; // исходный граф

tint* H; // матрица списка ребер с весом

tint* K; /*матрица, отмечающая принадлежность

вершины компоненте*/

tint* T; // матрица остовного дерева

tint* L; // список ребер с ценами минимального дерева

// -----ввод графа

int max;

cout<<" Maximalno dopustimoe zna4enie vesa rebra = ";

cin>> max;

cout<<"\n Vvedite 4ilo vershin: \n ";

cin>> n;

G=new tint [n];

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

G [i] =new int [n];

cout<<" Vvedite nignij treugolnik matrici stoimosti: \n ";

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

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

cin>> G [i] [j];

}

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

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

G [j] [i] =G [i] [j];

// ---выделение памяти для списка ребер---

int kolreb=0;

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

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

if (G [i] [j] <max && G [i] [j]! =0)

kolreb++;

H=new tint [kolreb];

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

H [i] =new int [3];

// -------------------------------------------

int a=0;

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

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

if (G [i] [j] <max && G [i] [j]! =0) {

H [a] [0] =i+1;

H [a] [1] =j+1;

H [a] [2] =G [i] [j];

a++;

}

cout<<endl;

// ----сортировка ребер по возрастанию веса

int f,d,s;

for (int i=0; i<kolreb-1; i++)

for (int j=0; j<kolreb-1; j++)

if (H [j] [2] <H [j+1] [2]) {

f=H [j] [2];

H [j] [2] =H [j+1] [2];

H [j+1] [2] =f;

d=H [j] [0];

H [j] [0] =H [j+1] [0];

H [j+1] [0] =d;

s=H [j] [1];

H [j] [1] =H [j+1] [1];

H [j+1] [1] =s;

}

// вывод ребер отсортированных по возрастанию веса

cout<<"Matrica dostigimosni otsortirovannoe po ubivaniuy: \n ";

for (int i=0; i<kolreb; i++) {

cout<<H [i] [0] <<"-->";

cout<<H [i] [1] <<" = ";

cout<<H [i] [2] <<endl;

cout<<" ";

}

for (int i=0; i<kolreb; i++) {

H [i] [0] - -;

H [i] [1] - -;

}

// матрица для определения компоненты

K=new tint [n];

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

K [i] =new int [2];

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

K [i] [0] =i;

K [i] [1] =0;

}

// ----матрица остовного дерева

T=new tint [n];

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

T [i] =new int [n];

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

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

T [i] [j] =0;

// -присоединение первого ребра

T [H [0] [0]] [H [0] [1]] =H [0] [2];

T [H [0] [1]] [H [0] [0]] =H [0] [2];

K [H [0] [0]] [1] =1;

K [H [0] [1]] [1] =1;

// алгорит соединения ребер без создания цикла:

int m=2; // номер компоненты

for (int i=1; i<kolreb; i++) // пройти по всем ребрам

if (K [H [i] [0]] [1]! =K [H [i] [1]] [1])

// если 2 вершины не из одной компоненты

{

if (K [H [i] [0]] [1] >0 && K [H [i] [1]] [1] >0)

// если обе вершины принадлежат разной компоненте

{

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

if (K [H [i] [1]] [1] ==K [j] [1])

K [j] [1] =K [H [i] [0]] [1];

K [H [i] [1]] [1] =K [H [i] [0]] [1];

T [H [i] [0]] [H [i] [1]] =H [i] [2];

T [H [i] [1]] [H [i] [0]] =H [i] [2];

}

if ( (K [H [i] [0]] [1] >0 && K [H [i] [1]] [1] ==0)

|| (K [H [i] [0]] [1] ==0 && K [H [i] [1]] [1] >0))

// если одна вершина имеет компоненту а др. нет

{

if (K [H [i] [0]] [1]! =0)

K [H [i] [1]] [1] =K [H [i] [0]] [1];

if (K [H [i] [1]] [1]! =0)

K [H [i] [0]] [1] =K [H [i] [1]] [1];

T [H [i] [0]] [H [i] [1]] =H [i] [2];

T [H [i] [1]] [H [i] [0]] =H [i] [2];

}

if (K [H [i] [0]] [1] ==0 && K [H [i] [1]] [1] ==0)

// если обе вершины не имели компоненты

{

K [H [i] [0]] [1] =m;

K [H [i] [1]] [1] =m;

T [H [i] [0]] [H [i] [1]] =H [i] [2];

T [H [i] [1]] [H [i] [0]] =H [i] [2];

m++;

}

} // конец проверки всех ребер

// ---выделение памяти для списка ребер

kolreb=0;

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

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

if (T [i] [j] <max && T [i] [j]! =0)

kolreb++;

L=new tint [kolreb];

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

L [i] =new int [3];

// ------------------------------------------

// ---вывод ребер

cout<<endl<<" Vivod reber maximalnogo vesa: \n ";

a=0;

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

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

if (T [i] [j] <max && T [i] [j]! =0) {

L [a] [0] =i+1;

L [a] [1] =j+1;

L [a] [2] =T [i] [j];

a++;

}

for (int i=0; i<kolreb; i++) {

cout<<L [i] [0] <<"-->";

cout<<L [i] [1] <<" = ";

cout<<L [i] [2] <<"\n ";

}

int b=0;

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

b+=L [i] [2];

cout<<endl <<" Stoimost dereva = "<<b; // вывод стоимости

getch ();

// return 0;

}

// --------------------------------------------------------------

6 . Обзор работы программы

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

Заключение

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

Алгоритм Краскала действительно находит остовный лес максимального веса, поскольку он является частным случаем алгоритма Радо - Эдмондса для графического матроида, где независимые множества - ациклические множества рёбер.

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

1. Рыбаков Глеб. Минимальные остовные деревья.

2. Архангельский А.Я., C++Builder6. Справочное пособие.

3. Белов Теория Графов, Москва, "Наука", 19 68.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат , 1988.

5. http://rain. ifmo.ru

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:25:45 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:13:49 29 ноября 2015

Работы, похожие на Курсовая работа: Нахождение минимального остовного дерева алгоритмом Краскала
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
Граф H называется частью графа G, если подмножество вершин его V(H) содержится во множестве вершин V(G) и все ребра части графа H являются ребрами G и обозначается HIG.
Пустому бинарному отношению соответствует нуль-граф О. Универсальному бинарному отношению отвечает полный граф U. Бинарному отношению aRb, где R - отрицание R (дополнительное ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4171 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
AGraph: библиотека классов для работы с помеченными графами
1. Актуальность разработки библиотек для работы с графами К настоящему времени накоплен большой опыт решения теоретико-графовых задач на ЭВМ ...
В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на ...
Одна из проблем, которые возникают при разработке универсальной библиотеки для работы с графами - как реализовать поддержку различных видов графов: ориентированных и ...
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 1852 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Графы. Решение практических задач с использованием графов (С++
Курсовая работа Выполнил: студент 1-го курса факультета КНиИТ, группа № 121, Жучков Андрей Сергеевич Саратовский государственный университет им. Н.Г ...
Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа
} 3.Построить остовное дерево минимальной стоимости для связанного взвешенного графа, используя алгоритм Прима.
Раздел: Рефераты по математике
Тип: реферат Просмотров: 6612 Комментариев: 6 Похожие работы
Оценило: 5 человек Средний балл: 3.6 Оценка: неизвестно     Скачать
Построение минимального остовного дерева графа методом Прима
Пояснительная записка к курсовому проекту тема: Построение минимального остовного дерева графа методом Прима Введение При проектировании железных ...
Пусть G (V; E) - связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А - некоторый подграф G, являющийся в то же время подграфом некоторого ...
Как и алгоритм Краскала, алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро.
Раздел: Рефераты по математике
Тип: курсовая работа Просмотров: 4205 Комментариев: 3 Похожие работы
Оценило: 2 человек Средний балл: 3.5 Оценка: неизвестно     Скачать
Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і ...
Міністерство освіти і науки України Сумський Державний Університет Курсова робота з дисципліни "Теорія алгоритмів та математична логіка" На тему ...
Позначимо через U підмножину вершин V. Якщо (і, v) - таке ребро найменшої вартості, що й належить U і v належить V \ U, тоді для графа G існує остовное дерево мінімальної вартості ...
Алгоритм складається з N-1 ітерації, на кожній з яких до дерева додається рівно одне ребро, не порушує властивості дерева (тобто один кінець додається ребра належить дереву, а ...
Раздел: Рефераты по математике
Тип: курсовая работа Просмотров: 315 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Алгоритмический язык Паскаль
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ им. А.В. ЛУНАЧАРСКОГО КАФЕДРА ИНФОРМАТИКИ Дипломная ...
Выделяют из всех деревьев так называемые УПОРЯДОЧЕННЫЕ деревья - такие, у которых ребра (т.е. соответствующие им элементы), выходящие из каждой вершины, упорядочены по какому-либо ...
Здесь K-ELEMENT есть вершина дерева, а LEFT и RIGHT - поля ссылок на левую и правую вершины поддеревьев.
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 2870 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 4 Оценка: неизвестно     Скачать
Проектирование трансляторов
ЛЕКЦИЯ 1 СУЩНОСТЬ ПРЕДМЕТА. СОДЕРЖАНИЕ КП. СРОКИ. ОРГАНИЗАЦИЯ РАБОТ. МАТЕМАТИЧЕСКИЙ АППАРАТ. СТРУКТУРНАЯ СХЕМА ТРАНСЛЯТОРА. ПРОХОДЫ ТРАНСЛЯТОРА ...
- LR(k)=(U,X,H,T,b1,b2,S0,Z0,Sr), где:
Для вычисления значения выражения (a+b*c)/(f*g-(d+e)/(h+k))
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 655 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Задача остовных деревьев в k-связном графе
... Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: "Задача остовных деревьев в k-связном графе"
Из ранее известных результатов "глобальным ананлогом" теоремы Менгера в некоторой степени является доказанный результат: в графе G с реберной связностью (G)k существуют k остовных ...
Следовательно, в силу неравенства (2), и так как dG(z), остались неиспользованными еще хотя бы n-k ребер графа G, инцидентных вершине z. Для дополнения каждого из оставшихся ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1728 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Исследования в современном управлении
СОДЕРЖАНИЕ 1. ИССЛЕДОВАНИЯ В СОВРЕМЕННОМ УПРАВЛЕНИИ.. 5 1.1 Предпосылки исследования систем управления.. 5 1.2 Системный анализ как средство ...
В дальнейшем под деревом взаимосвязей будем понимать связный, неориентированный граф, вершины которого интерпретируются как элементы дерева, а ребра - как связи между ними.
Множество ребер R={rjiz} графа G обозначают взаимосвязи между элементами, из которых выходит ребро, и элементами, в которые оно входит. j - номер элемента i-го уровня, из которого ...
Раздел: Рефераты по менеджменту
Тип: учебное пособие Просмотров: 5165 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Эйлеровы и гамильтоновы графы
Министерство народного образования Республики Дагестан Дагестанский Государственный Университет Курсовая работа Программирование задач на графах ...
Пусть мы достигли некоторой вершины v, начав с вершины u, v = u. Удалив ребра пути из v в u, видим, что оставшийся граф G1 связен и содержит ровно две нечетных вершины v и u ...
Возьмём произвольную пару вершин j,k. Исключим непосредственное ребро D[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j,.,k. Пусть это расстояние ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 6739 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать

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

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

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



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

Рейтинг@Mail.ru