Программная реализация построения минимального оставного дерева графа

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ        3

1 ИССЛЕДОВАНИЕ И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ        4

1.1Описание поставленной задачи        4

1.2 Обоснование актуальности исследуемой задачи        6

1.3 Современное состояние исследуемой задачи        7

1.4 Постановка задачи, системные требования, требования к входным данным и выходным формам        8

2 ПРОЕКТИРОВАНИЕ СТРУКТУРЫ И АРХИТЕКТУРЫ ПРОГРАММНОГО ПРОДУКТА        9

2.1 Выбор методов и средств для реализации, их обоснование        9

2.2 Описание применяемых алгоритмов        9

2.3 Структура, архитектура программного продукта        12

3 РЕАЛИЗАЦИЯ И ТЕСТИРОВАНИЕ ПРОГРАММНОГО ПРОДУКТА        13

3.1 Описание реализации        13

3.2 Описание пользовательского интерфейса        18

3.3 Тестирование и оценка надёжности программного продукта        20

ЗАКЛЮЧЕНИЕ        24

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ        25

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СИМВОЛОВ        26

ВВЕДЕНИЕ

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

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

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

Целью данного курсового проекта является создание удобного и информативного приложения для построения минимального оставного дерева графа.

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

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

1 ИССЛЕДОВАНИЕ И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

1. Описание поставленной задачи

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

Если ребра – упорядоченные пары, то такой граф называется ориентированным (сокращенно орграф), если же неупорядоченные, то неориентированным. Говорят, что ребро (a, b) соединяет вершины a и b.

В графе может быть не более одного ребра, соединяющего две данные вершины. Ребро типа (a, a) т.е. соединяющее вершину с ней же самой, называют петлей.

Таким образом, основные виды графов:

• ориентированный – граф, рёбрам которого присвоено определенное направление. Граф, в котором данное условие не выполняется, называется неориентированным. Направленные рёбра именуются дугами. Ненаправленные рёбра называются звеньями;
• граф, содержащий циклы. Циклом называется путь, в котором совпадают его начальная и конечная вершина. Граф, в котором данное условие не выполняется, называется лесом;
• мультиграф – граф, в котором пары вершин могут быть соединены более чем одним ребром, то есть содержащий кратные рёбра;
• дерево – связный граф, не содержащий циклов. Любые две вершины дерева соединены лишь одним маршрутом.

Способы представления графов:

• матрица смежности – это квадратная матрица размера , в которой каждый элемент принимает одно из двух значений: 1 или 0, в зависимости от того, существует ли ребро от вершины i к вершине j. Строки и столбцы матрицы соответствуют вершинам графа.[pic 1]

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