Читать курсовая по математике: "Задачи и алгоритмы дискретной математики" Страница 4

(Назад) (Cкачать работу)

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

Схема работы алгоритма представлена на рисунках 2-6.

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

Рисунок 3. Для каждой компоненты связности (для каждой вершины) находим безопасные ребра. Они отмечены стрелками от компоненты вдоль безопасного ребра

Рисунок 4. Добавляем безопасные ребра к минимальному остовному лесу

Рисунок 5. Находим безопасные ребра для каждой компоненты связности

Рисунок 6. Добавляем найденные ребра. Минимальное остовное дерево построено

2.3 Программная реализация алгоритма A ← (V, 0)(пока) в A больше одной компоненты связности

do CHOOSE-LEADERS(A)SAFE-EDGES(G)

foreach (для каждого) лидера v'

добавить safe(v') в AA

Вот простой возможный вид процедуры поиска безопасных ребер:

FIND-SAFE-EDGES(G)(для каждого) лидера v'(v') ← ∞

foreach (для каждого) ребра (u, v) ∈ E

u' ← leader(u)' ← leader(v)u' ≠ v' thenw (u, v) < w (safe(u')) then(u') ← (u, v)w (u, v) < w (safe(v')) then

safe(v') ← (u, v)

Итогом выполнения курсовой работы по дисциплине «Дискретная математика» на тему «Алгоритм Форда-Фалкерсона» является разработка программы, реализующей заданный алгоритм.

Работа по созданию программы позволила приобрести практические навыки по использованию методов программирования при решении задач теории графов. Список используемых источников1. Седжвик Р. Алгоритмы на C++. - Пер. с англ. - М.: Вильямс, 2011. - 1056 с.

2. Скиена С. Алгоритмы. Руководство по разработке. - 2-е изд.: пер. с англ. - СПб.: БХВ-Петербург, 2011. - 720 с.

. Кристофидес Н. Теория графов. Алгоритмический подход. - Пер. с англ. - М.: Мир, 1978. - 432 с.

. Окулов С.М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. - М.: БИНОМ. Лаборатория знаний, 2008. - 422 с.

. Акулич И.Л. C#. Программирование на языке высокого уровня: Учебник для вузов. - 1-е изд. - Санкт-Петербург.: Питер, 2010. - 423 с.

. Подбельский В.В. Язык С#. Базовый курс. - 2- е изд., доп. - М.: Информ-Студио, 2011. - 384 с.

. Мурлин А.Г., Мурлина В.А., Янаева М.В. Программирование с использование компонентов Windows Forms. Учебное пособие. Издательский дом ЮГ, 126 с.

. Официальная документация по Visual C# и Visual Studio [Электронный ресурс] - Режим доступа: URL: - http://msdn.microsoft.com/ru-ru/library/kx37x362 (v=vs.90).aspx

Похожие работы